Daniel Le Berre
email: leberre@cril.univ-artois.fr

Pascal Rapicault
email: pascal_rapicault@ca.ibm.com

Dependency Management for the Eclipse Ecosystem Eclipse p2, metadata and resolution

Keywords: D.2.7 [ Distribution, Maintenance, and Enhancement]: Extensibility, D.2.13 [Reusable Software]: Reusable libraries, F.4.1 [Mathematical Logic]: Logic and constraint programming Algorithms, Design, Experimentation OSGi, dependency management, boolean encoding

HAL is

INTRODUCTION

Eclipse is a very popular open platform mainly written in Java and designed from the ground up as an integration platform for software development tools but also for rich client * The work on explanations detailed in section 4.4 has been supported in part by Genuitec company.

applications [START_REF] Powell | Eclipse on rails and rockets[END_REF]. As the Eclipse ecosystem becomes more and more important, the Eclipse platform itself and the vertical platforms built on Eclipse all rely on the concept of extensibility, and as such the necessity of a mechanism to acquire those extensions is primordial. To that end, almost since its inception, Eclipse featured an extension acquisition mechanism named Update Manager. However over time, as inter plug-in dependencies became more complex and expressed at a finer grain, and more versions of each component was made available, limitations were being discovered in Update Manager which were hindering the adoption and retention of Eclipse. The term "plug-in hell" was coined. It is at that time that we started to work on Eclipse p2 with the goal of building a "right-grained" provisioning platform attempting to address the challenges that Update Manager had been faced with.

One of the first challenge was heterogeneity in the set of things being deployed since over time it had become clear that most OSGi-and Eclipse-based applications needed to have a manageable way to interact with their environment (e.g JRE, Windows registry keys, etc.).

Second was the need to address in one platform the diversity of provisioning scenarios and offer a solution that would work against controlled repositories -similar to the case of linux packages managed by a specific Linux distribution-or uncontrolled repositories, would allow for fully automated solutions or user-driven ones, or would sport the delivery of extensions as well as complete products.

Finally, and the most important challenge, was to solve the "plug-in hell" that was partially rooted in the non modular way of acquiring components since Update Manager forced extensions to be installed by a special abstraction one level above the actual extension itself. The term "rightgrained" provisioning is a response to this problem and indicates that p2 is not an obstruction to the granularity of what a user would want to make available or obtain.

In order to achieve this goal of "right-grained" provisioning, the efficiency, reliability and scalability of the dependency resolver was key. Having learnt from our experience of authoring the OSGi runtime resolver for Equinox, it was obvious that we would need to base our dependency analysis mechanism on proven solver techniques. Coincidentally, later that year, the work of OPIUM [START_REF] Tucker | Opium: Optimal package install/uninstall manager[END_REF] and EDOS [START_REF] Mancinelli | Managing the complexity of large free and open source package-based software distributions[END_REF] backed up our intuition on the usability and maturity of a SAT-based approach to address the problem. The dependency problem for Eclipse is closer to the problem addressed by the follow-up to EDOS project, the Mancoosi Project [START_REF] Mancoosi | Managing the Complexity of the Open Source Infrastructure[END_REF][START_REF] Treinen | Solving package dependencies : from Edos to Mancoosi[END_REF], that is the problem of updating complex open source en-vironments. Nevertheless, dependency constraints [START_REF] Abate | Strong dependencies between software components[END_REF] studied in both cases are significantly different. In this paper we are presenting the p2 metadata and the motivation for some of these constructs, detail the implementation of our resolver and conclude by the challenges we are interested in addressing in future releases.

P2 METADATA

Core to the majority of installers that deal with composable systems (e.g RPM, Debian, etc.) lies a concept of metadata. One of the goals of this metadata, and the point of focus of this paper, is to capture the dependencies that exist between the components of the system and thus to find missing dependencies or to validate dependencies of a system before it is being modified. As described previously, p2 is intended to deal with more than just the typical Eclipse constructs of OSGi bundles. As such, despite the presence of dependency information in the OSGi bundles composing most of Eclipse applications, p2 abstracts dependencies from the elements being delivered in an entity called an Installable Unit (also referred to as IU). We now introduce the three kinds of installable units that p2 defines.

Anatomy of an installable unit

An installable unit, the simplest construct, has the following attributes:

An identifier A string naming the installable unit.

A version

The version of the installable unit. The combination identifier and version is treated like a unique ID. We will refer to versions of an installable unit to mean a set of installable unit sharing the same identifier but a different version attribute.

A set of capabilities A capability is the way for the installable unit to expose to the rest of the world what it has to offer. This is just a namespace, a name and a version. Namespace and name are strings. The namespace is here to prevent name collision and avoid having everyone adhere to name mangling conventions.

A set of requirements A conjunction of requirements. A requirement is the way for the IU to express its needs. Requirements are satisfied by capabilities. A requirement is composed of a namespace, a name and a version range 1 . In addition to these usual concepts, a requirement can have a filter (under the form of an LDAP filter [8]) which allows for its enablement or disablement depending on the environment where the IU will be installed, and it can also be marked optional meaning that failing to satisfy the requirement does not prevent the IU from being installable. Finally there is a concept of greed discussed later in this section.

An enablement filter An enablement filter indicates in which contexts an installable unit can be installed.

Here again the filter will pass or fail depending on the environment in which the IU will be installed.

Greed

Optional Semantics true false this is a "strong" requirement. true true this is a "weak" requirement. false true this is a "weakest" requirement, where the match will not be brought in. false false this indicates a case where the requirement has to be satisfied but the IU with this requirement wants this to be brought in by another one. Such a need will be presented in 2.3.

Table 1: Greed and optional interaction.

A singleton flag This flag, when set to true, will prevent a system to contain another version of the installable unit with the same identifier.

An update descriptor

The identifier and a version range identifying predecessors to this IU. Making this relationship explicit allows to deal with IUs being renamed or avoid undesirable update paths.

An example of an Installable unit representing the SWT bundle is given in Figure 1. The few things to notice are the usage of namespace to avoid clashes between the Java packages and the IU identifier; the usage of singleton because no two versions of this bundle can be installed in the same eclipse instance; the "typing" of the IU as being a bundle (see namespace org.eclipse.equinox.p2.type valued to bundle); and the identification of the IU by providing a capability in the org.eclipse.equinox.p2.iu namespace. Now, let's come back on requirements and detail the semantics of greed and optional. By default, a requirement is "strong"2 (optional is false, greed is true). This means that the IU can only be installed if the requirement is met. If a "strong" requirement is guarded by a filter that does not pass, the requirement is ignored. When the optional flag is set to true, then a requirement becomes "weak" and it does not have to be satisfied for the IU to be installed. However any IU potentially satisfying this requirement will be considered, and a best effort will be made to satisfy the requirement.

When it comes to greed, this is a rather atypical concept that we have added to control the addition of IUs as part of the potential IUs to install in order to satisfy the user request. When the greed is true (default case, and the case for strong requirements), the IU satisfying the dependencies are added to the pool of potential candidates. However when the greed is set to false, such a requirement relies on other dependencies from its own IU or others to bring in what is necessary for its satisfaction. This is used in Figure 1 to capture the fact that even though we have an optional dependency on org.mozilla.xpcom we don't want to try to satisfy it eagerly. As such, this optional and non greedy requirement is weaker than a typical optional dependency. However what is interesting is the different usage we have observed of this metadata and the implication it has on the rest of the system. Indeed, most people building on top of Eclipse are delivering "products" or "subsystems" and as such they want to guarantee that their customer is getting what has been tested. Failing to do this could result in a non stable product, maintenance nightmare and unsatisfied customers. However in an ecosystem where products can be mixed and where repositories can not be used as control points3 , guaranteeing a functional system is harder. Consequently, to palliate to these possible problems, product producers are using installable units as a grouping mechanism (also referred to as group) serving three goals:

1. Facilitate the reusability of a set of functionality by aggregating under one group a set of installable units.

2. Capture a particular configuration of the system, and thus group under one IU an extensible element and a default implementation.

3. Lock down the dependencies on installable units being used, which limits the variability of what can be installable and thus guarantees reproducibility of an installation independently of the content of the repository.

These three goals are visible in the abridged version of the Platform group shown in Figure 2. It shows the grouping of a set of unrelated functions together to facilitate reuse; how the default setup of the help system is being delivered using the org.eclipse.help.jetty IU4 ; and finally the ranges expressed all show the desire to precisely control a particular version of each IU being delivered.

The counter part of the lock down which is used extensively throughout Eclipse, is that it makes the delivery of service (e.g. the replacement of a particular IU by another one) complex for the following reasons:

1. Products are often made of groups, themselves recursively composed of other groups (in the Figure 2, the Platform group includes the RCP group), which can make for a rather vast ripple on effect all throughout the system when a low level component needs to be serviced.

2. Not all groups deployed on the user's machine are in the control of the same organization. For example, someone can be running a composition of IBM and Artois University products (both including the Eclipse Platform group), but the Platform group is controlled by the Eclipse open source community. Therefore when the Platform team needs to deliver a fix to a user, it simply can not require all the referring groups to be updated.

3. Not all the dependencies onto a particular IU are known ahead of time.

Anatomy of an Installation Unit Patch

To palliate to these problems, p2 provides the concept of installable unit patch (referred to as patch). The simplest way to think of a patch is as a mechanism that can reach into any IU and change any requirement. A patch is a regular installable unit to which three concepts have been added:

Requirement change It represents the changes made to installable units. It is a set of requirement pairs where each pair represents a rewriting rule. In the rewriting rule, the left part captures the original requirement that needs to be replaced and the right part captures the resulting requirement. No constraints are applied to the capturing requirement or the new value, the replacement could widen the range, or narrow it, or completely change the requirement (e.g. remove a filter, change optionality, etc.). In order to provide flexibility, the capturing requirement applies on an original requirement if the ranges expressed on the two requirements intersect.

Applicability scope It identifies the installable units to which the patch should be applied. It has enough flexibility to patch all the IUs of the system where a requirement change is applicable, or target just a few IUs. The IUs to patch are identified by requirements.

Lifecycle It indicates when the installable unit patch can be applied. This can be seen as a precondition that has to be satisfied for the patch to be applied. It represents the "when" to apply the patch whereas the applicability scope represents the "what" to patch. It takes the form of a non greedy requirement. The example in Figure 3 shows a patch replacing the IUs org.eclipse.ant.core and org.eclipse.ant.ui. This patch will only try to replace the references to these two IUs from the Platform group (see applicability scope) and will only be applied if the my.product IU is installed.

We have shown how installable unit patches avoid a large ripple-on change across metadata by "rewriting" requirements and also how updates to an IU could be delivered without knowing all the dependencies on it. Given the alteration possibilities, another possible use of patches is to add or remove dependencies in an installable unit you would want to reuse but had unsatisfactory dependencies.

Installable unit fragment

The third and last concept of p2 metadata is the installable unit fragment. This concept inspired from the OSGi fragment concept [START_REF]OSGi Service Platform[END_REF] aims at providing a mechanism to augment an installable unit by adding to it properties or configuration information 5 . The need for this stems from the desire to make installable units as reusable as possible and thus to extract out of an installable unit the configuration information that would otherwise bind it to a particular environment. The canonical example of this is how p2 chose to handle the delivery of OSGi start levels. Some of the OSGi bundles delivered by p2 need to be configured with an information indicating when they can be started. Because the IU for OSGi bundles can be reused in different applications with different configuration needs, they can not carry the start level information so that information is separated out into an installable unit fragment. This fragment is then attached to the IU(s) it is augmenting (referred to as host) at resolution time and treated as part of the host during the installation. Fragments also offer the ability to attach to several IUs and thus deliver default configuration information to all of them, thus reducing the configuration burden.

An installable unit fragment augments the concept of installable unit by adding the concept of host requirement. This identifies the host or hosts to which the fragment applies and is expressed by a set of requirements. These requirements have to be satisfied for the fragment to be installable.

What is interesting in the expression of host requirement is the importance of the concept of greed, especially when dealing with a fragment delivering default configuration information. Indeed, in those cases, even though you have a fragment that can apply to multiple IUs does not mean that you want to install all the IUs to which it applies. To indi- 5 These are not detailed in this paper because their content and representation is irrelevant to the discussion cate this, the host requirement is set to be non greedy. This is the case described in the fourth line of Table 1. It is used in Eclipse by the IU fragment responsible for the delivery of the default start level to every OSGi bundles installed in the system (see Figure 4). To perform its job, the host requirement of this fragment requires "IUs that are bundles" (names-pace=org.eclipse.equinox.p2.eclipse.type, name=bundle, range=[1.0.0], greed=false) which matches the capabilities of the same namespace and name provided by IUs like the SWT one (see Figure 1). If the greed attribute had been set to true, then the resolver would have brought in all the IUs delivering bundles thus growing unnecessarily the set of IUs that would have been added to the pool of potential IUs for the solution, whereas what is intended is to have this IU only attach to the bundles that will be brought through other dependencies. To be pedantic, in the case of the current Eclipse release, the size of the problem would have been multiplied by a factor 10 since the Eclipse SDK is made of about 380 IUs and the Galileo repository6 contains about 3800 IUs.

RESOLVER OVERVIEW

This section describes the overall functioning of our resolver. However the discussion on the propositional constraints encoding and explanation support appears in the next section.

Before detailing the overall solver, it is worth mentioning how p2 manages the installed software. p2 has a concept of profile which keeps track of two key information: the list of all the Installable Units installed, and the set of root installable units. The root IUs are not a new kind of installable units, they are installable units that are remembered as having been explicitly asked for installation. These roots are essential for installation, uninstallation and update, since they are used as strict constraints that can't be violated, thus for example avoiding the uninstallation of an IU when installing another one.

Resolution

p2 resolution process is logically organized in 5 phases:

Change request processing Given a change request capturing the desire to install or uninstall an installable unit, a future root set representing the application of this request over the initial root set is produced.

Slicing For each element in the future root set, the slicing produces a transitive closure of all the IUs (referred as slice) that could potentially be part of the final solution of the resolution process by consulting all repositories also passed in. This transitive closure is done with only taking into account enough context7 to evaluate the various filters but without worrying if any IU being added could be colliding with any others. For each IU, it looks at each requirement, queries the repositories for matches, and add the results of the query to a set of IU to process. In the case of fragment IUs, the host requirement is also treated and for patches the replacement value contained in the requirement changes are as well. If the requirement greed is set to false, or if the requirement enablement filter is not evaluating to true, the process is short-circuited and the next requirement is considered. The slicing phase reduces the dependency problem to the only IUs applicable to a given setting (the OS for instance). Another solution would have been to encode everything into constraints.

Our approach here is to use the constraints solver only for non trivial matters.

Projection/encoding The goal of the projection phase is to transform all the installable units of the slice and their dependencies into a system of propositional constraints (see section 4 for details). For each IU, each requirement8 is queried against the slice and each resulting IU is encoded. In contrast to the slicing phase, the greed flag is ignored and every requirement, except when filtered, is processed since at that point the slicing has isolated the elements that will be part of the solution. It is also during this phase that patches are applied. For this, for each IU being processed, applicable patches (matching the applicability scope) are searched for in the slice and applied. Since patches may or may not be part of the final solution but logi-cally "modifies" the original requirements, special care has to be taken to have a variable representing the initial IU with the patch applied on it, and another one with the patch not applied on it. This is detailed in section 4.3. In addition to this transformation, this phase also fills in a data structure keeping track of every potential hosts for each fragment IU. Finally for each root the corresponding variable in the SAT encoding is set to true to capture the intent of the solution being searched. The generation of the propositional constraints completed, the optimization function is being generated.

PBO-solving

The result of the projection is passed to the pseudo boolean solver SAT4J [START_REF] Le | SAT4J, a SATisfiability library for java[END_REF] which is responsible for finding an assignment.

Solution extraction

From the assignment returned by the solver, a solution is extracted and the final attachment of IU fragment to their host(s) is concretized. In case of failure the solver is invoked to produce an explanation (see section 4.4).

Updating

In p2, the detection and installation of all applicable updates is not a completely automated process and no simple function in the p2 API is provided to perform this operation. Instead, the only mechanism provided is a function which given a root IU and a set of repositories returns a set of candidates IUs that are updates of the given IU 9 . This allows for selectively searching for updates or looking for an update of everything that is installed. Once all the candidates have been gathered, a subset of the matches are picked and a change request is created and passed to the resolver for validation. Because p2 is a platform, the picking responsibility is left to code outside of the scope of the core of p2. For example, the graphical interface available in the Eclipse SDK performs filtering and the user is only presented with the most recent version of each IU to select from. The user input obtained, a corresponding profile change request is created and passed to the resolver for validation.

The obvious drawback of this approach is that the user may have to go through several iterations of selection to find a suitable alignment of IUs to update to. However, even if p2 could provide some logic to return the most pertinent and up-to-date set of IUs using techniques like MAX-SAT [START_REF] Argelich | On solving boolean multilevel optimization problems[END_REF], the results would only be relevant in case of a completely automated update mechanism, since giving the opportunity to the user to pick something from the set of updates available could invalidate the solution initially returned and thus potentially lead to similar problems.

CONSTRAINTS ENCODING

In the following, we describe the encoding of p2 installation problem into propositional constraints, i.e. clauses or cardinality constraints. We also provide some examples of problems generated with that encoding.

prov(IU ) denotes the set of capabilities provided by the installable unit IU and req(IU ) denotes the set of capabilities required by the installable unit IU. alt(cap) = {IU k |cap ∈ prov(IU k )} denotes the set of IUs providing a given capability. Finally, optReq(IU ) denotes the optional requirements of a given IU, and versions(IUx) denote the ordered set of IUs sharing the same identifier as IUx but having different version attribute (IUx ∈ versions(IUx)), from the latest to the oldest.

Basic encoding

Each requirement of the form "IUi requires capability capj" is represented by a simple binary (Horn) clause IUi → capj So, for each IUi the requirements are expressed by a conjunction of binary clauses

ĉap j ∈req(IU i ) IUi → capj
The alternatives for a given capability is given by the clause

capi → IUj 1 ∨ IUj 2 ∨ ... ∨ IUj n
where IUj x ∈ alt(capi).

Since we are only interested in the IUs to install, the above two constraints can be aggregated into a conjunction of constraints:

f (IUi) = ĉap j ∈req(IU i ), (IUi → _ IUx∈alt(cap j ) IUx) (1)
Note that there is the specific case of alt(capj) = ∅ which means that IUi cannot be installed due to missing requirements. In that case, the unit clause ¬IUi is generated.

Some installation units cannot be installed together (e.g. because of the singleton attribute set to true). This can be modeled either with a conjunction of binary negative clauses

versions(IUv)={IU 1 v ,...,IU n v },1≤i<j≤n (¬IUv i ∨ ¬IUv j )
or equivalently with a single cardinality constraint:

( X IU x v ∈versions(IUv ) IU x v ) ≤ 1 (2)
We use the second option because our solver manages those constraints natively and because it makes the explanation support easier to implement (see 4.4 for details).

Finally, the user wants to install the installable units identified by the roots. This is modeled with unit clauses:

ÛI i ∈rootIU s U Ii (3)
Summing up, the constraints (1), ( 2) and (3) altogether form an instance of a classical NP-complete SAT problem. That encoding is basically the encoding presented in Edos [START_REF] Mancinelli | Managing the complexity of large free and open source package-based software distributions[END_REF] and Opium [START_REF] Tucker | Opium: Optimal package install/uninstall manager[END_REF] and used more recently in Open-Suse 11 10 .

Encoding of optionality

One of the specificity of p2 is the semantic of "weak" dependencies expressed using the greed and optional attributes. We do not have to worry here about greedy dependencies since there are simply ignored during the slicing stage. An IU IUi may have optional dependencies to IU IUj means that IUj is not mandatory to use IUi, so IUi can be installed successfully if IUj is not available. However, it is expected that p2 should favor the installation of optional packages if possible, i.e. that all optional packages that could be installed are indeed installed. In Figure 1, one can see that SWT has two optional dependencies on SWT accessibility2 and Mozilla XPCOM. The encoding of optional packages is done by creating two specific propositional variables: Abscap denotes the fact the capability cap is optional, and N oopIU i is a variable to be satisfied in case none of the optional capabilities of IUi can be installed. The first set of constraints expresses how to satisfy the required capabilities:

ĉap j ∈optReq(IU i ) (Abscap j → _ IUx∈alt(cap j ) IUx) (4)
The second set of constraints expresses that if N oopIU i is true then all the abstract capability variables must be false, i.e. that N oopUI i can only be set to true when none of the optional dependencies could be installed.

ĉap j ∈optReq(IU i ) (N oopIU i → ¬Abscap j ) (5)
Note that such set of constraints could also have been expressed equivalently by a single pseudo boolean constraint:

( X cap j ∈optReq(IU i ) Abscap j ) + n × N oopIU i ≤ n
where n = |optReq(IUi)|. We used the first option in our encoding since it looked easier to understand. The second option could be used in order to reduce the number of constraints used in the solver. Contrariwise to the encoding of the singleton attribute, there is no need to use a single constraint here because optionality encoding constraints cannot prevent an IU to be installed, thus cannot be part of an explanation.

Finally, we express that IUi has optional dependencies using a disjunction ending with the N oopIU i variable. That way, even if none of the optional requirements can be installed, the constraint can still be satisfied by setting N oopIU i to true.

IUi → _ cap j ∈optReq(IU i ) Abscap j ∨ N oopIU i (6)
Example 1. Let's see how to encode the optional dependencies of SWT on accessibility2 and xpcom shown in Figure 1:

Abs accessibility2 → IU 1.0 accessibility2 ¬Abs accessibility2 ∨ ¬N oopIU SW T Absxpcom → IU 1.1 xpcom ¬Absxpcom ∨ ¬N oopSW T IUSW T → Abs acessibility2 ∨ Absxpcom ∨ N oopSW T
An alternative encoding would be:

Abs accessibility2 → IU 1.0 accessibility2 Absxpcom → IU 1.1 xpcom Abs accessibility2 + Absxpcom + 2 × N oopIU SW T ≤ 2 IUSW T → Abs acessibility2 ∨ Absxpcom ∨ N oopSW T
That encoding of optionality was the original one that shipped with Eclipse 3.4. The encoding has evolved since then. This will be discussed in section 4.5.

Encoding of patches

Applying a patch from the encoding point of view only applies to requirements changes (see section 2.2), i.e. it means to enable or disable some dependencies according to the application or not of a given patch. We denote by patchedReqs(IU, p) the set of pairs < old, new > of the installable unit IU denoting the rewriting rules of patch p in the requirements of IUs.

We associate to each patch a new propositional variable. We introduce that variable in dependency constraints [START_REF] Mancoosi | Managing the Complexity of the Open Source Infrastructure[END_REF] and ( 4) the following way:

• Negatively when the patch introduces a new dependency.

• Positively when the patch removes an existing dependency.

It can be summarize that way:

<old,new>∈patchedReqs(IU,p) (p → encode(new))∧(encode(old)∨p)
where encode(x) denote the encoding of a regular or an optional dependency. The patch encoding changes only the encoding of the requirements affected by a patch.

Example 2. The patch shown in Figure 3 would lead to the following encoding of the dependencies for the IU Platform: If the patch is enabled (i.e. the propositional variable patch is set to true) then the initial constraints (a) are disabled while the new dependencies (b) are enabled. If the patch is not enabled (i.e. the propositional variable patch is set to false), then the new dependencies (b) are disabled and the original optional dependencies (a) apply. Note that the requirements untouched by the patch (c) do not see their encoding changed.

IU P latf orm → IU 3.1.0 ant-core ∨ patch (a) patch ∧ IU P latf orm → IU 3.4.

When things go wrong: explanation

Explanation is key to help the user understands why a change request cannot be fulfilled. In the above encoding, one can note that there are only two reasons that could prevent a request to succeed:

• At least one of the required IUs is missing.

• The request requires two IUs sharing the same identifier but with different versions that cannot be installed together due to the singleton attribute on at least one of those IUs (see for instance Figure 5).

As a consequence, it is not hard to check why a request cannot be completed. However users expect the explanation to be returned in terms of IUs they know about, the root IUs and the IUs that they are trying to install, and would be confused if provided with just the low level dependency errors. In practice, it means that knowing why a problem occurred is not sufficient. It is important to be able to detail the whole dependencies from the root to the actual cause of the problem. For instance, in Figure 5, the user cannot install the Eclipse Platform IU version 3.5.0.20090528 because the Eclipse SDK version 3.5.0.20090430 is already installed and both of them rely on different versions of Eclipse RCP that is a singleton.

Let S be the set of the constraints encoding presented in the previous sections. From a logical point of view, it is possible to compute one minimal subset S ′ of the constraints that cannot be satisfied altogether: S ′ ⊆ S, S ′ |= ⊥, ∄S ′′ ⊂ S ′ |S ′′ |= ⊥. Such set of constraints is often called a MUS (minimal unsatisfiable subformula). S ′ is an explanation of the impossibility to fulfill the request. If the subset contains a negated literal (specific case of Equation (1), ¬U Ix ∈ S ′ ) then the global explanation is a missing requirement, i.e. the request cannot be completed because IUx cannot be found in the user's repositories. If the subset contains a cardinality constraints ( P IU x v ≤ 1 ∈ S ′ ), then the global explanation is a singleton attribute violation, i.e. the request cannot be completed because it requires several versions of IUv. Note that if we decided to use a clausal encoding instead of the cardinality constraints encoding, we would have lost the one to one mapping between the original dependencies and the constraints of our encoding.

There are several ways in practice to compute S ′ from S. The ones based on local search algorithms [START_REF] Bertrand | Detecting logical inconsistencies[END_REF] detect constraints that are likely to be part of S ′ among the most falsified ones during the search and compute S ′ in a second step using a complete SAT solver. A more recent and widely used approach is based on the analysis of the last conflict found by a conflict driven SAT solver [START_REF] Zhang | Extracting small unsatisfiable cores from unsatisfiable boolean formulas[END_REF]. Such approach requires some changes in the SAT solver to keep track of all resolutions steps and does not ensure that the computed subset S ′′ ⊆ S is minimal. A third approach is to rely on a new encoding of the problem into an optimization problem using selector variables [START_REF] Lynce | On computing minimum unsatisfiable cores[END_REF]: it is possible to use an optimization function on selector variables to compute a set S ′ of minimal size. Finally, a generic approach to explanation in constraints solvers was proposed in [START_REF] Junker | Quickxplain: Preferred explanations and relaxations for over-constrained problems[END_REF] and implemented in Ilog solver: QuickXplain. The main advantage of such approach is to be independent of the underlying solver, and to work with any kind of constraints.

Our approach inherits some ideas from all those approaches. We decided to implement the QuickXplain algorithm in our framework because it is non intrusive (does not require any change to the solver) and works perfectly with mixed constraints (clauses and cardinality constraints in our case). We use selector variables in our encoding to allow the QuickXplain algorithm to enable/disable the constraints when computing S ′ . Finally, the constraints given to the QuickXplain algorithm are ordered in decreasing order of their activity in the spirit of the local search approaches.

More precisely, we translate S into S ′′ by adding a new selector variable seli to each constraint in S: S ′′ = {seli ∨ si|si ∈ S}. Let SEL denotes the set of all added selector variables. Instead of looking for an assignment satisfying S, we are looking for an assignment satisfying S ′′ under the assumption that all variables in SEL are set to false, S ′′ V sel i ∈SEL ¬seli 11 . If such assignment exists, it is an assignment satisfying S, so we are done. If it is not the case, then we use a tailored version of the QuickXplain algorithm that makes use of the selector variables to enable/disable constraints in order to compute S ′ .

From decision to optimisation

When all the constraints can be satisfied, there are usually many possible solutions, that are not of equal quality for the end user. Here are a few remarks regarding the quality of the expected solution:

1. An IU should not be installed if there is no dependency to it.

2. If several versions of the same bundle exist, the latest one should preferably be used.

3. When optional requirements exist, the optional requirements should be satisfied as much as possible.

4. User installed patches should be applied independently of the consequences of its application (i.e. the version of the IUs forced, the number of installable optional dependencies, etc.).

We are now looking for the "best" solution, not just any solution, i.e. we moved from providing a certificate for the answer to a decision problem (NP-complete from a complexity theory point of view) to return the solution of an optimization problem (NP-hard). Furthermore, we need to solve a multi-criteria optimization problem since it is likely that several IUs do have optional requirements and that several IUs are available in multiple versions.

To solve our problem, we build a linear optimization function to minimize in which the propositional variables are either given a penalty (positive integer) or a reward (negative integer) to prevent or favor their appearance in the computed assignment. 11 Assumption based satisfiability testing is available in all Minisat [START_REF] Eén | An extensible sat-solver[END_REF] inspired solvers (including SAT4J).

• Each version of an IU gets a penalty as a power of 2 proportional to its age, the older it is the more penalized it is:

X IU i v ∈versions(IUv ) 2 i × IU i v (7)
That way, each installation of an IU raises at least a penalty equals to one, thus expressing that only required IUs should be installed.

• Each N oopx variable gets a penalty to favor the installation of optional IU.

X 2 K × N oopx (8)
where K is a constant such that 2 K is greater than the maximum penalty for a version (i.e. K > max(|versions(IUv)|).

• Each Absx variable gets a reward to favor the installation of optional dependencies

X -2 K+1 × Absx (9)
• Each patch variable gets a reward of n × -2 K+3 if it is applicable (where n denotes the number of applicable patches), else a penalty of 2 K+2 X p i ∈applicableP atches() n×-2 K+3 pi+ X p i ∈applicableP atches()

2 K+2 pi (10)
The objective function of our optimization problem is thus to minimize ( 7) + (8) + ( 9) + [START_REF] Le | SAT4J, a SATisfiability library for java[END_REF].

The weights in [START_REF] Eén | An extensible sat-solver[END_REF] are not satisfactory since they do not provide a total order on the final solution. Suppose that we have two IUs IUa and IU b that are available in respectively 3 and 2 versions (namely IU 3 a , IU 2 a , IU 1 a and IU 2 b , IU 1 b ). The objective function for those IUs is thus

IU 3 a + 2 × IU 2 a + 4 × IU 1 a + IU 2 b + 2 × IU 1 b
The best solution for such objective function if both IUa and IU b must be installed is obviously to install IU 3 a and IU 2 b . However, if those two IUs cannot be installed together, the solver will answer that the best option is either to install IU 3 a and IU 1 b or IU 2 a and IU 2 b . The common approach to solve this problem is to rank each IUs in a total order, IU1 < IU2 < ... < IUm, meaning that IUi is more important than IUj iff IUj < IUi. Then the coefficients of the optimization function should be generated in such a way that the sum of the coefficients of IUj should be smaller than the smallest coefficient of IUi. In our example, it would mean for instance to use the following optimization function:

IU 3 a + 2 × IU 2 a + 4 × IU 1 a + 8 × IU 2 b + 16 × IU 1 b
In that case, the best option is still to install IU 3 a and IU 2 b , but the second best option is to install IU 2 a and IU 2 b . Unfortunately, as noted before, we are in the context of uncontrolled repositories, so there is no obvious/easy way to order the IUs in a total order, so it was decided to keep the initial solution [START_REF] Eén | An extensible sat-solver[END_REF] In the constraints our first solution to this problem has been to contextualize (4):

ĉap j ∈optReq(IU i ) (Abscap j ∧ IUi → _ IUx∈alt(cap j ) IUx) (11)
That way, the variable AbsIU i can be forced to true by the objective function but it will not fire the installation of the dependencies if the IUi is not to be installed. However, that solution has an unexpected behavior in the following test case: suppose that IUa has an optional dependency on capability b provided by IU b that has in turn an optional dependency on the capability c provided by IUc for which we have alt(IUc) = ∅. We would generate the following constraints:

Absc ∧ IU b → ⊥ ≡ ¬Absc ∨ ¬IU b (a) Abs b ∧ IUa → IU b IUa → IU b ∨ N oopIU a
Since we would like to satisfy as many Absx variables as possible, the solver would force Absc and Abs b to be set to true. As a consequence, IU b has to be set to false to satisfy (a). This is possible because the dependency to IU b is optional, else a strong dependency would force IU b to be set to true. Such unexpected behavior is a direct consequence of changing the constraints because of a wrong behavior of the objective function. The fix should not change the constraints but the objective function itself.

In the objective function The other option is to use a non linear optimization function in our problem, i.e. to make the reward a function of both the abstract variable Abscap i and IUj where capi ∈ optReq(IUj):

X -2 K+1 × Abscap i × IUj ( 12
)
The problem is that our solver does not propose yet an easy way to work with non linear optimization functions. A solution based on the introduction of new variables y k ↔ Abscap i ×IUj where y k replaces Abscap i × IUj in the objective function and with the additional constraints y k → Abscap i ∨ IUj,Abscap i → y k ,IUj → y k should fix that issue.

That last issue was discovered late in the release cycle of Eclipse 3.5 Galileo. Considering the fact that meeting the scenario of the issue of the first option was less likely than introducing a new issue by integrating a barely untested implementation of the second option in SAT4J, the former has been adopted for Eclipse 3.5.

CONCLUSION AND PERSPECTIVE

We presented Eclipse p2, a "right-grained" provisioning platform aimed at solving the diversity of provisioning requirements in a componentized world. We focused on presenting the three metadata constructs which allow the assembly of complex products from components:

• Installable unit, to capture dependencies among component at their lowest level, but also to capture lock downs and ease reusability by grouping;

• Installable unit patch, to tweak dependencies of installable units that can't be changed;

• Installable unit fragment, to "augment" an installable unit and as such allow for installable units to be as reusable as possible by staying context free from their used one deployed.

From there we presented the overall functioning of our resolver and gave a description of our SAT-based encoding that is resolved by the SAT4J Pseudo Boolean solver. We can report that this approach that has been live for more than one year has proven to be reliable, efficient and scalable even when faced with repositories containing more than 10000 installable units and solution involving about 3000 installable units. Furthermore, a direct consequence of our work is the integration of the very same technology to manage dependencies in other Java related products, namely the upcoming major release of Maven (Maven3) and the repository manager Nexus.

That said, we are looking to further improve the metadata and the resolver to facilitate composition and to address the challenges encountered so far. For the metadata, the main changes we want to investigate are:

1. The ability for the line-up information that is usually expressed in groups to be extracted out into a new kind of installable units. Once extracted, this information would no longer be directly encoded as propositional constraints but would instead be used to drive the optimization function. We hope that such a change would facilitate the serviceability by avoiding the need to create patches, but the biggest challenge with this feature would be composability of several of these new IUs.

2. The ability to express capabilities and requirements on other domains than just version and version ranges. For example we are thinking about adding scalars to describe the amount of memory available.

3. Add negation and disjunction to improve the expressiveness of the requirements.

On the resolver, the main changes planned surround:

1. Stability of resolution to not cause updates of IUs that are not directly related to the change request being performed. The canonical example is where requirements toward an IU tolerate several possibilities and the installation of something new cause the update of the IU because a newer version is available in the repositories. We hope that the concept of line-up previously described will help there.

2. Resolution over a set of profiles, in order to perform the coordinated management of several applications meant to work together (e.g. the client needs to be in sync with the server).

3. Speed up the explanation process. Depending on the size of the set of constraints, it can take several minutes to provide the answer which is not ideal in an interactive tool. This is caused by the n × log(n) satisfiability tests used by the explanation algorithm used (QuickXplain) where n is the size of the input of the algorithm in number of constraints. n can be as big as the number of constraints in the encoding in the worst case.The idea is to ask more information to the SAT solver instead of using a purely external approach as currently in order to minimize n in the spirit of [START_REF] Cimatti | A simple and flexible way of computing small unsatisfiable cores in sat modulo theories[END_REF][START_REF] Asín | Efficient generation of unsatisfiability proofs and cores in sat[END_REF].

Figure 2 :

 2 Figure 2: An IU representing the Plaform subsystem of Eclipse

3

 3 ant-core (b) IU P latf orm → IU 1.0.0 ant-ui ∨ patch (a) patch ∧ IU P latf orm → IU 1.1.0 ant-ui (b) IU P latf orm → IU 4.0 help (c) IU P latf orm → IU 4.0 jetty (c) IU P latf orm → IU 3.1 rcp (c)

Table 1

 1

	reviews the four combinations of greed and option-
	ality.

  id=org.eclipse.platform.feature.group, version=3.5.0.v2009 Capabilities: {namespace=org.eclipse.equinox.p2.iu, name=org.eclipse.platform.feature.group, version=3.5.0.v2009} Requirements: {namespace=org.eclipse.equinox.p2.iu, name=org.eclipse.rcp.feature.group, range=[3.1.0.v2009,3.1.0.v2009]} {namespace=org.eclipse.equinox.p2.iu, name=org.eclipse.ant.core, range=[3.2.0.v2009,3.2.0.v2009]} {namespace=org.eclipse.equinox.p2.iu, name=org.eclipse.ant.ui, range=[1.0.0.v2008,1.0.0.v2008]} {namespace=org.eclipse.equinox.p2.iu, name=org.eclipse.help, range=[4.0.0.v2009,4.0.0.v2009]} {namespace=org.eclipse.equinox.p2.iu, name=org.eclipse.help.jetty, range=[4.0.0.v2009,4.0.0.v2009]} Updates: {namespace=org.eclipse.equinox.p2.iu, name=org.eclipse.platform.feature.group, range=(3.4.0, 3.5.0.v2009]}

  id=org.eclipse.ant.critical.fix,version=1.0.0 Capabilities: {namespace=org.eclipse.equinox.p2.iu, name=org.eclipse.ant.core.critical.fix, version=3.5.0.v2009} Requirement Changes: { from={namespace=org.eclipse.equinox.p2.iu, name=org.eclipse.ant.core, range=[3.1.0, 3.4.0)}, to={namespace=org.eclipse.equinox.p2.iu, name=org.eclipse.ant.core, range=[3.4.3,3.4.3]}} { from={namespace=org.eclipse.equinox.p2.iu, name=org.eclipse.ant.ui, range=[1.0.0.v2008,1.0.0.v2008]}, to={namespace=org.eclipse.equinox.p2.iu, name=org.eclipse.ant.ui, range=[1.1.0.v2009,1.1.0.v2009]}} Figure 3: Example of installable unit patch, patching the Platform group.

	Applicability Scope:
	{namespace=org.eclipse.equinox.p2.iu, name=org.eclipse.platform.feature.group, range=[3.5.0.v2009,3.5.0.v2009]}
	Lifecycle:
	{namespace=org.eclipse.equinox.p2.iu, name=my.product, range=[1.0.0,1.0.0], greed=false}
	Updates:
	{namespace=org.eclipse.equinox.p2.iu, name=org.eclipse.platform.feature.group, range=[0.0.0, 3.5.0.v2009)}
	id=osgi.bundle.default.startlevel, version=1.0.0
	Hosts:
	{ {namespace=org.eclipse.equinox.p2.eclipse.type, name=bundle, range=[1.0.0], greed=false} }
	Capabilities:
	{namespace=org.eclipse.equinox.p2.iu, name=osgi.bundle.default.startlevel, version=1.0.0}

Figure 4: Installable unit fragment attaching to any bundle.

  instead of ranking arbitrarily the IUs. Another drawback of our objective function appeared recently when new IUs got added to the release repository. The part (9) of the optimization function has the undesirable effect to favor the installation of optional requirements Cannot complete the install because of a conflicting dependency. Software being installed: org.eclipse.platform.sdk 3.5.0.I20090528 Software currently installed: org.eclipse.sdk.ide 3.5.0.I20090430 Only one of the following can be installed at once: org.eclipse.rcp.configuration_root.gtk.linux.x86 1.0.0.I20090430 org.eclipse.rcp.configuration_root.gtk.linux.x86 1.0.0.I20090528

	Cannot satisfy dependency:
	From: org.eclipse.platform.sdk 3.5.0.I20090528-2000
	To: org.eclipse.rcp.configuration.feature.group [1.0.0.I20090528]
	Cannot satisfy dependency:
	From: org.eclipse.rcp.configuration.feature.group 1.0.0.I20090430
	To: org.eclipse.rcp.configuration_root.gtk.linux.x86 [1.0.0.I20090430]
	Cannot satisfy dependency:
	From: org.eclipse.rcp.configuration.feature.group 1.0.0.I20090528
	To: org.eclipse.rcp.configuration_root.gtk.linux.x86 [1.0.0.I20090528]
	Cannot satisfy dependency:
	From: org.eclipse.sdk.ide 3.5.0.I20090430-2300
	To: org.eclipse.rcp.configuration.feature.group [1.0.0.I20090430]
	Figure 5: Example of explanation
	of an IU even if such IU is not installed. A contextualization
	of the reward is necessary to fix such problem:

A version range is expressed by two version number separated by a comma, and surrounded by an angle bracket, meaning value included, or a parenthesis, meaning value excluded.

Strong is weaker in our context than the notion of strong dependency introduced in[START_REF] Abate | Strong dependencies between software components[END_REF]

Controlled repository is the approach taken by a majority of linux distributions.

The Eclipse help system allows different web-servers to be used.

http://download.eclipse.org/releases/galileo

The context can be seen as a map of key/value pair

Here again, requirement host of IU fragments, replacement values in requirement changes of patches as well as applicability scope are treated.

Each candidate has its update descriptor match the IU it is an update of.

http://en.opensuse.org/Package_Management/Sat_ Solver/Basics


Christyves Chevallier
email: christyves.chevallier@supelec.fr

Frédéric Genty

Nicolas Fressengeas

Joel Jacquet

Joël Jacquet

J Jacquet

Robust Design by Antioptimization for Parameter Tolerant GaAs/AlOx High Contrast Grating Mirror for VCSEL Application

Keywords: High contrast grating mirror, mid-infrared VC-SEL, robust design, parameter tolerant

A GaAs/AlOx high contrast grating structure design which exhibits a 99.5 % high reflectivity for a 425 nm large bandwidth is reported. The HCG structure has been designed in order to enhance the properties of mid-infrared VCSEL devices by replacing the top Bragg mirror of the cavity. A robust optimization algorithm has been implemented to design the high contrast grating structure not only as an efficient mirror but also as a robust structure against the imperfections of fabrication. The design method presented here can be easily adapted for other high contrast grating applications at different wavelengths.

I. INTRODUCTION

H IGH contrast gratings (HCG) are diffractive structures made of a material with a high optical index for the grating slabs surrounded by a low index material. With a high optical index contrast (∼ 2) and a near-wavelength grating period, the structure diffracts only into the 0 th order of diffraction and can be seen as a 1D photonic crystal supporting only a few propagative Bloch modes. However, contrary to photonic crystal slabs, the modes propagate perpendicularly to the slab plane [START_REF] Lalanne | Optical properties of deep lamellar gratings: A coupled bloch-mode insight[END_REF], [START_REF] Chang-Hasnain | High-contrast gratings for integrated optoelectronics[END_REF]. The resonance of these modes between the two grating interfaces and their coupling at the interfaces can be adjusted to obtain different and very promising properties in a large range of applications [START_REF] Chang-Hasnain | High-contrast gratings for integrated optoelectronics[END_REF] such as broadband mirrors [START_REF] Goeman | First demonstration of highly reflective and highly polarization selective diffraction gratings (GIRO-gratings) for long-wavelength VCSELs[END_REF]- [START_REF] Foley | Broadband long-wavelength infrared Si/SiO 2 subwavelength grating reflector[END_REF], high-Q resonators [START_REF] Zhou | Surface-normal emission of a high-Q resonator using a subwavelength high-contrast grating[END_REF], planar lenses [START_REF] Fattal | Flat dielectric grating reflectors with focusing abilities[END_REF], wavefront control [START_REF] Carletti | High-indexcontrast grating reflector with beam steering ability for the transmitted beam[END_REF], optical isolators [START_REF] Ye | Unidirectional transmission in non-symmetric gratings made of isotropic material[END_REF], waveplates [START_REF] Magnusson | Guided-mode resonant wave plates[END_REF], circular polarizers [START_REF] Mutlu | Broadband circular polarizer based on high-contrast gratings[END_REF] or electromechanical mirrors [START_REF] Hane | Variable optical reflectance of a self-supported Si grating[END_REF], [START_REF] Huang | A nanoelectromechanical tunable laser[END_REF]. The mirror effect is particularly interesting since it can exhibit not only a polarization independence [START_REF] Shokooh-Saremi | Leaky-mode resonant reflectors with extreme bandwidths[END_REF] with good angular insensitivity [START_REF] Wu | A multilayer-based wideband reflector utilizing a multi-subpart profile grating structure[END_REF] but also a good reflectivity selectivity between TE and TM modes [START_REF] Goeman | First demonstration of highly reflective and highly polarization selective diffraction gratings (GIRO-gratings) for long-wavelength VCSELs[END_REF], [START_REF] Shokooh-Saremi | Multi-level periodic leakymode resonance elements: Design and applications[END_REF]. With only one high contrast grating layer, it is thus possible to obtain a very large bandwidth of ∆λ/λ = 30% for more than 99% reflectivity and even ∆λ/λ = 17% for 99.9% [START_REF] Mateus | Ultrabroadband mirror using low-index cladded subwavelength grating[END_REF].

The development of VCSEL devices emitting in the 2-3 µm wavelength range remains a challenging task today. The realization of VCSEL devices which are single-mode, low cost and tunable light sources [START_REF] Ortsiefer | Long-Wavelength VCSELs with Buried Tunnel Junction[END_REF] is of great interest for gas detection in the mid-infrared wavelength range where gas species such as carbon monoxide exhibit strong absorption lines [START_REF] Ouvrard | Single-frequency tunable Sb-based VCSELs emitting at 2.3 µm[END_REF], [START_REF] Chen | VCSEL-based calibration-free carbon monoxide sensor at 2.3 µm with in-line reference cell[END_REF]. VCSEL structures based on InP system have demonstrated mid infrared laser emission in continuous wave (CW) at room temperature for λ = 2.3 µm [START_REF] Ortsiefer | Electrically pumped room temperature CW VCSELs with 2.3 µm emission wavelength[END_REF]. However this wavelength seems to be the maximum limit for this material system [START_REF] Ortsiefer | Long-Wavelength VCSELs with Buried Tunnel Junction[END_REF]. Thus several VCSEL structures based on AlGaInAsSb material system have been developed. A VCSEL structure using a buried tunnel junction for current confinement have shown CW emission at λ = 2.36 µm up to 363 K [START_REF] Bachmann | Long wavelength electrically pumped GaSb-based buried tunnel junction VCSELs[END_REF] while another structure based on selective lateral etching of the tunnel junction in order to realize a current aperture have shown CW emission at λ = 2.31 µm up to 343 K [START_REF] Sanchez | Single-mode monolithic GaSb vertical-cavity surface-emitting laser[END_REF]. More recently, a GaSb-based VCSEL using a lateral wet oxidation of AlAs for current confinement has been demonstrated and exhibits CW laser emission at λ = 2.38 µm for a temperature of 253 K [START_REF] Laaroussi | Oxide-confined mid-infrared VCSELs[END_REF]. The development of VCSEL based on AlGaInAsSb is thus a very promising solution for the mid infrared wavelength range. However, laser emission is still limited today at λ = 2.6 µm at room temperature [START_REF] Arafin | Electrically pumped continuous-wave vertical-cavity surface-emitting lasers at 2.6 µm[END_REF], [START_REF] Ducanchez | Midinfrared GaSb-based EP-VCSEL emitting at 2.63 µm[END_REF]. One of the main problem at such large wavelengths is the increase of the device thickness which reaches about 12 µm since more than 20 pairs of quarter-wavelength AlSb/GaSb layers are required for the VCSEL Bragg mirrors [START_REF] Cerutti | GaSb-based VCSELs emitting in the midinfrared wavelength range (2-3 µm) grown by MBE[END_REF].

The large and high reflectivity bandwidth, low mirror thickness and high polarization selectivity of HCG structures make them good candidates for replacement of Bragg mirrors in VCSEL diodes. VCSEL designs which use a grating as a polarizing mirror in order to enhance the laser properties have thus been proposed [START_REF] Magnusson | Vertical-cavity laser and laser array incorporating guided-mode resonance effects and method for making the same[END_REF], [START_REF] Magnusson | Photonic devices enabled by waveguide-mode resonance effects in periodically modulated films[END_REF]. Several VCSEL structures based on HCG have then been developed and have demonstrated laser emission with GaAs-based material around 850 nm [START_REF] Huang | A surface-emitting laser incorporating a high-index-contrast subwavelength grating[END_REF] and 980 nm [START_REF] Gilet | High-index-contrast subwavelength grating VCSEL[END_REF] or with InP-based material at 1320 nm [START_REF] Hofmann | Long-wavelength high-contrast grating vertical-cavity surface-emitting laser[END_REF] and 1550 nm [START_REF] Boutami | Compact and polarization controlled 1.55 µm vertical-cavity surface-emitting laser using single-layer photonic crystal mirror[END_REF]- [START_REF] Sciancalepore | CMOS-compatible ultracompact 1.55-µm emitting VCSELs using double photonic crystal mirrors[END_REF].

The short amplification length of VCSEL structures imposes the use of a high quality mirror with reflectivity larger than 99.5 % for large bandwidths which are typically about 150 nm in mid-infrared [START_REF] Cerutti | GaSb-based VCSELs emitting in the midinfrared wavelength range (2-3 µm) grown by MBE[END_REF]. The mirror efficiency required for VCSEL application is thus demanding and imposes a precise adjustment of HCG geometrical parameters during the design process. Even if the physic of HCG is well understood [START_REF] Lalanne | Optical properties of deep lamellar gratings: A coupled bloch-mode insight[END_REF], [START_REF] Karagodsky | Theoretical analysis of subwavelength high contrast grating reflectors[END_REF], numerical simulations by RCWA [START_REF] Moharam | Stable implementation of the rigorous coupled-wave analysis for surface-relief gratings: enhanced transmittance matrix approach[END_REF] of the reflectivity

789A9

Fig. 1. Scheme of the GaAs/AlOx mirror. The grating period Λ, Fill Factor F F = L f /Λ, grating thickness Tg , GaAs layer thickness T L and AlOx layer thickness T A are optimized by an optimization algorithm to exhibit reflectivities higher than 99.5 % for a VCSEL application at 2.3 µm.

of HCG structures allow the use of an optimization algorithm [START_REF] Bisaillon | High reflectivity air-bridge subwavelength grating reflector and fabry-perot cavity in AlGaAs/GaAs[END_REF]- [START_REF] Chevallier | Optimized subwavelength grating mirror design for mid-infrared wavelength range[END_REF] to design the mirror properties for a specific application.

Since VCSEL devices require high quality mirrors and HCG have sub-micrometric square-shaped patterns, the fabrication of HCG structures needs to control masking and etching process with a high accuracy in the nanometric range [START_REF] Chevallier | Optimized subwavelength grating mirror design for mid-infrared wavelength range[END_REF]. On the other hand, HCG mirrors can be designed to have a good robustness of several percent on the geometrical dimensions. So, to achieve a robust and efficient mirror, the tolerance with respect to the errors of fabrication has to be taken into account during the design of the structure [START_REF] Wu | A high performance polarization independent reflector based on a multilayered configuration grating structure[END_REF], [START_REF] Chevallier | Optimized Si/SiO 2 high contrast grating mirror design for mid-infrared wavelength range: Robustness enhancement[END_REF], [START_REF] Zhou | Large fabrication tolerance for VCSELs using high-contrast grating[END_REF].

In this paper, we present the design of a GaAs HCG combined with an AlO x sublayer as low index material to replace the top DBR of mid infrared GaSb-based VCSEL. In a first part, an optimization algorithm is used to find the best dimensions of the HCG structure. Then, the tolerance of the geometrical parameters of the optimum design with respect to the errors of fabrication are numerically investigated. In a second part, an anti-optimization algorithm is combined to the optimization process to develop a robust optimization algorithm. This original design approach of high contrast gratings takes into account the tolerances required by the manufacturers on the different parameters directly during the design process. The gratings mirrors are thus optimized to exhibit not only high efficiency but also large tolerance values.

II. OPTIMIZATION METHOD

A. Structure of the mirror

The mirror structure presented in Figure 1 is made of a GaAs grating (n = 3.3) with a period Λ, a thickness T g and a Fill Factor F F = L f /Λ. The high contrast of optical index required for large bandwidth mirror is obtained thanks to the use of a low index AlO x sublayer (n = 1.66) with a thickness T A . The choice of the GaAs/AlO x material system has been made in order to allow a monolithic epitaxial process during the integration of the HCG mirror in a VCSEL structure [START_REF] Gilet | High-index-contrast subwavelength grating VCSEL[END_REF], [START_REF] Almuneau | High reflectivity monolithic sub-wavelength diffraction grating with GaAs/AlOx stack[END_REF]. The AlO x layer can be obtained from a wet oxidation process of AlAs similar to the one used for current confinement by oxide aperture in VCSEL structures [START_REF] Huffaker | Native oxide defined ring contact for low threshold vertical cavity lasers[END_REF]- [START_REF] Laaroussi | Efficient lateral confinement by an oxide aperture in a mid-infrared GaSb-based vertical light-emitting source[END_REF]. The GaAs top layer is not completely etched during the grating fabrication resulting in a GaAs intermediate layer of thickness T L . The presence of an intermediate GaAs layer should enhance the mechanical stability of the grating above the AlO x layer since the oxidation process decreases the AlAs layer thickness of about 10 % [START_REF] Almuneau | High reflectivity monolithic sub-wavelength diffraction grating with GaAs/AlOx stack[END_REF].

HCG mirrors presented in this work are designed to be used as VCSEL top mirrors, thus in the HCG structure presented in Figure 1, the GaAs substrate corresponds to the VCSEL cavity with light propagating from substrate to the air. In order to obtain a laser cavity, a minimum reflectivity value of 99.5 % is required for VCSEL mirrors for the largest possible bandwidth. To solve the problem of polarization instability and mode hoping of VCSEL devices, the mirror is chosen to be polarization dependent by reflecting light only for the transverse magnetic mode (TM) while keeping the transverse electric (TE) reflection coefficient R T E below a 90 % threshold.

B. Optimization of the mirror parameters

In order to satisfy all the previously defined VCSEL requirements, the structure dimensions Λ, T g , F F , T A and T L have to be carefully designed. An optimization algorithm has been used to automate the search of the most efficient mirror design. The efficiency of the HCG structure has been defined through the use of a figure of merit M F [START_REF] Chevallier | Optimized subwavelength grating mirror design for mid-infrared wavelength range[END_REF] which represents quantitatively the mirror quality from a VCSEL application point of view :

M F = ∆λ λ 0 1 N λ2 λ=λ1 R T M (λ)g(λ) (1)
The figure of merit M F mainly represents the normalized bandwidth of the mirror, defined as the wavelength range ∆λ = λ 2 -λ 1 around λ 0 where the reflectivity is larger than 99.5 % for TM mode and below 90 % for the TE mode. The normalized bandwidth is also multiplied by a Gaussian weighted average of the transverse magnetic reflection coefficients R T M of the bandwidth to ensure a centering around λ 0 . Reflection spectra of the mirror are computed by rigorous coupled wave analysis (RCWA) [START_REF] Bienstman | CAMFR[END_REF] for transverse magnetic and transverse electric polarizations.

Several optimization algorithms can be used to design HCG structures such as simulated annealing [START_REF] Bisaillon | High reflectivity air-bridge subwavelength grating reflector and fabry-perot cavity in AlGaAs/GaAs[END_REF], genetic algorithm [START_REF] Shokooh-Saremi | Particle swarm optimization and its application to the design of diffraction grating filters[END_REF] or particle swarm [START_REF] Shokooh-Saremi | Leaky-mode resonant reflectors with extreme bandwidths[END_REF], [START_REF] Wu | A high performance polarization independent reflector based on a multilayered configuration grating structure[END_REF]. Due to the presence of many local maxima, a global optimization approach is required. In this work, we have implemented a particle swarm optimization (PSO) algorithm [START_REF] Kennedy | Particle swarm optimization[END_REF] to maximize the figure of merit M F . The particle swarm algorithm is based on a population of particles which are candidate solutions sharing their knowledge of optimum positions when exploring the search space. The particles of the swarm, of which positions correspond to a set of the design parameters X = {Λ, T g , F F , T A , T L }, are moved at each algorithm iteration with a velocity v i,p :

v i,p = v i-1,p + c l * (x l p -x i-1,p ) + c g * (x g p -x i-1,p ) (2)
The velocity v i,p at the iteration i of the particle p of the swarm is composed of 3 terms. Firstly, the inertia of the particle is taken into account by keeping the velocity of the previous iteration v i-1,p . Secondly, a local velocity term moves the particle toward the local best position x l p known by the particle p. Finally, the swarm concept is created by sharing the best position of all particles thanks to the global best position x g p which creates a global velocity term. The parameters c l and c g are two weights for the local and global velocities which are randomly chosen from a uniform law in the range [0, 2] at each particle move [START_REF] Kennedy | Particle swarm optimization[END_REF].

The dimensions of the mirror structure have been optimized within bounds that take technological constraints into account. The AlO x layer thickness T A has been shown to maximize the reflectivity for values of (2k -1)λ/4 [START_REF] Almuneau | High reflectivity monolithic sub-wavelength diffraction grating with GaAs/AlOx stack[END_REF], but has been bounded between 300 nm and 400 nm to limit the optical losses within the oxide. The Fill Factor limitations are chosen with respect to the e-beam lithography and etching process and have been bounded between 35 % and 55 %. The other parameter constraints are only given to define a search space for the optimization algorithm but can also be chosen with respect to other technological limitations : 500 nm < T g < 1100 nm, 900 nm < Λ < 1300 nm and 50 nm < T L < 1000 nm.

C. Optimization results

The particle swarm optimization algorithm has been executed with the previously defined parameters to design the GaAs/AlO x HCG mirror presented in Figure 1. The optimum mirror found by the algorithm exhibits a 493 nm large bandwidth with structure dimensions of T g = 657 nm, F F = 0.5380, T A = 352 nm, Λ = 1117 nm and T L = 283 nm (Table I). In order to validate the result obtained by our implementation of the particle swarm optimization, a comparison has been made with a differential evolution [START_REF] Storn | Differential evolution -a simple and efficient heuristic for global optimization over continuous spaces[END_REF] optimization algorithm [START_REF] Kroshko | OpenOpt 0.27[END_REF] under the same technological constraints for the mirror structure. The execution of the latter algorithm results in a 481 nm large bandwidth (Table I) which is equivalent to the PSO algorithm. Both points are very close and satisfy all VC-SEL requirements and technological constraints. The 99.5 % high TM reflectivity and large bandwidth (∆λ/λ = 21.5 %) of the mirror optimized by PSO exhibits a good polarization selectivity by keeping R T E below 70 % (Figure 2). The high reflectivity performances of the GaAs/AlO x HCG structure

D. Tolerance of the optimum design

From a fabrication point of view, it is important to know how tolerant the structure is with respect to the error of fabrication on the different dimensions. The tolerance of one parameter is defined as the variation range for which the mirror keeps a TM reflectivity larger than 99.5 % together with a TE reflectivity smaller than 90 % at λ 0 = 2300 nm. The evaluation of the tolerance of one dimension of the structure is done by increasing and decreasing its optimum value while keeping all the other ones at their optimum values. It is important to note that the way the evaluation of tolerance is performed does not give any information on an error of fabrication made simultaneously on different dimensions [START_REF] Chevallier | Optimized Si/SiO 2 high contrast grating mirror design for mid-infrared wavelength range: Robustness enhancement[END_REF].

As it has already been reported in the literature, HCG can exhibit large tolerances on the design parameters [START_REF] Wu | A high performance polarization independent reflector based on a multilayered configuration grating structure[END_REF], [START_REF] Chevallier | Optimized Si/SiO 2 high contrast grating mirror design for mid-infrared wavelength range: Robustness enhancement[END_REF], [START_REF] Zhou | Large fabrication tolerance for VCSELs using high-contrast grating[END_REF]. For instance, minimum and maximum values of the parameters of the optimum designs found by the algorithms result in variation range of more than 10 % as it can be seen in Table II and Table III. Despite large variation ranges, the tolerance value of the dimension can be as small as ± 3 nm for instance on the grating thickness T g (Table II). Such a critical tolerance value would make the etching control difficult and decrease drastically the probability of successfully etching the grating. Since the optimization algorithm will search for the most efficient design regardless of its tolerance, if an optimum is localized at the edge of the variation range, the optimization can result in a non tolerant design [START_REF] Chevallier | Optimized Si/SiO 2 high contrast grating mirror design for mid-infrared wavelength range: Robustness enhancement[END_REF], [START_REF] Kontio | Broadband infrared mirror using guided-mode resonance in a subwavelength germanium grating[END_REF].

The design of GaAs/AlO x HCG by an optimization algorithm provides very efficient mirrors with large bandwidth well Fig. 2. Reflection spectra for transverse magnetic mode (blue) and transverse electric mode (dashed red) of the optimum design optimized by the particle swarm algorithm which dimensions are described in Table I. The inset shows the 493 nm large reflectivity bandwidth well centered at λ 0 = 2.3 µm.

adapted for VCSEL integration. However the optimization process can randomly result in a point very sensitive to the error of fabrication and can be difficult to fabricate.

III. ROBUST OPTIMIZATION

A. Anti-optimization method

In order to make the fabrication of HCG possible for a VC-SEL integration, mirror structures have to be not only efficient but also robust with respect to the fabrication errors. A simple way to improve the mirror tolerance is to manually center the structure dimensions within their variation ranges [START_REF] Chevallier | Optimized Si/SiO 2 high contrast grating mirror design for mid-infrared wavelength range: Robustness enhancement[END_REF]. However, since the tolerance is evaluated for each parameter independently, the centering within the variation range does not take into account the error made on several parameters simultaneously. The tolerance computation of combination of parameters such as L f = F F * Λ, can increase the knowledge of the robustness, but the adjustment of the grating dimensions becomes complex when the number of parameters increases. Moreover, since the manual robustness enhancement can only be performed once the dimensions are optimized, the use of an optimization algorithm to make the design process easy and automated is lost.

The maximization of the figure of merit M F in order to find the most efficient mirror structure by an optimization algorithm can be coupled to an anti-optimization process to form a robust optimization algorithm. The purpose of anti-optimization [START_REF] Elishakoff | Structural design under bounded uncertainty-optimization with anti-optimization[END_REF] is to search for the worst scenario of fabrication of the optimum found which would result in the least efficient mirror. For that purpose, a new figure of merit M F ′ has been introduced :

M F ′ (X) = 1 2 min ∆X M F (X ± ∆X) + M F (X) (1 + η) ∀(X ± ∆X) ∈ Ω (3)
The robustness of the design is taken into account in the figure of merit M F ′ for a design defined by X = {T g , F F, T A , Λ, T L } by computing the average value of the figure of merit M F with the minimum of figure of merit associated to the worst scenario of fabrication. The search of the minimum is done in the hyper-space Ω = X ± ∆X around X delimited by user-defined tolerance specifications with ∆X = {∆T g , ∆F F, ∆T A , ∆Λ, ∆T L }. The last parameter η of the figure of merit M F ′ corresponds to a percentage of the process of tolerance evaluation. Thus, efficient mirrors which keep good performances within user-defined variation ranges will have a larger figure of merit M F ′ than non tolerant structures.

The evaluation of M F ′ (X) requires to know the minimum value of M F (X) within the whole tolerance area defined by X ± ∆X. The search for this minimum could be done by an optimization algorithm but would be time consuming. Moreover, if the current point M F (X) has a low value, the evaluation of its robustness would be useless since a weak solution will not be kept during the optimization. Since the particle swarm algorithm moves the particles by directing them to local and global optimum values (x l p and x g p ) stored in memory, the tolerance evaluation can be done only on the best positions known by the swarm. In order to make a fast evaluation of the tolerance which does not rely on an optimization algorithm to find the worst design within the tolerance area, only the extremum values of each parameter T g ± ∆T g , F F ± ∆F F, T A ± ∆T A , Λ ± ∆Λ and T L ± ∆T L are computed. The estimation of the minimum used for the averaging of the M F ′ in Eq. 3 is thus evaluated with only 10 points in the case of the GaAs/AlO x HCG structure and does not take into account errors made simultaneously on several parameters or a local minimum located between T g and T g + ∆T g for instance. In a N D dimension problem, with N D parameters to optimize, the tolerance evaluation process is done in 2N D steps for the positive and negative tolerance estimation of each parameter. The parameter η in Eq. 3 represents thus the percentage of achievement of the 2N D tolerance evaluation process. At each step, the figure of merit M F ′ is updated and if its value becomes lower than another point stored in memory, the anti-optimization process stops and the optimization continues to find a new optimum. A competition between optimization and anti-optimization is thus used to enhance the efficiency of the robust algorithm by decreasing the number of points evaluated and the computational cost.

To increase the reliability of the tolerance evaluation, the errors made simultaneously on several structure parameters have been taken into account by comparing the new computed design to the optimum known by the swarm. Since the particles move towards their local and global optimum, if a new minimum is computed around the optimum within the tolerance area x l p ± ∆X or x g p ± ∆X during the optimization process, its figure of merit M F will be used to adjust the figure of merit M F ′ associated to x l p or x g p . The PSO exploration of the search space is thus used advantageously to increase the robustness by taking into account errors made simultaneously on several design parameters.

B. Tolerance requirements and first result

The execution of the robust optimization algorithm imposes to define tolerance requirements for the mirror parameters. One of the most critical parameter to control is the oxide layer thickness T A since a 8-13 % decrease of the layer arises from the oxidation process of AlAs [START_REF] Almuneau | High reflectivity monolithic sub-wavelength diffraction grating with GaAs/AlOx stack[END_REF]. The tolerance of the AlO x layer thickness has been set to be of ∆T A = ± 50 nm during the optimization. Nevertheless, simulations have already shown that the low index sublayer thickness T A is not a critical parameter [START_REF] Almuneau | High reflectivity monolithic sub-wavelength diffraction grating with GaAs/AlOx stack[END_REF] of the HCG mirror and a 50 nm tolerance should not be a severe design constraint [START_REF] Chevallier | Optimized subwavelength grating mirror design for mid-infrared wavelength range[END_REF], [START_REF] Chevallier | Robust design of Si/Si 3 N 4 high contrast grating mirror for mid-infrared vcsel application[END_REF]. The grating parameters F F and T g linked to the etching process are more critical and require large tolerance values of ∆T g = ± 20 nm and ∆F F = ±0.02. The other parameters are either defined by the epitaxial growth of the structure (T L ) or by e-beam lithography (Λ) and are better controlled. Tolerance requirements for these parameters have been set to lower values with ∆T L = ± 1 nm and ∆Λ = ±3 nm.

The optimization of the GaAs/AlO x mirror with the robust optimization algorithm performed in the same conditions as described in Section II results in a structure which dimensions are given in Table IV and exhibits a 369 nm large bandwidth. A tolerance study of the mirror parameters shows that all dimensions meet the tolerance requirements and that the optimum is correctly centered within the variation ranges (Table IV). A comparison with the design optimized with the particle swarm algorithm without anti-optimization (Table III) shows that the bandwidth is 124 nm smaller for the mirror obtained by robust optimization. A decrease of tolerance values is also exhibited for ∆T g and ∆F F but are still larger than the requirements. However, when performing a statistical test by varying simultaneously and randomly the structure dimensions with a uniform law for the previously defined tolerance values, the failure rate (R T M < 99.5 % at λ 0 ) decreases from 1.9 % from the design without robust optimization to less than 0.01 % for the robust design. Despite a decrease of bandwidth and tolerances, the robustness of the grating is still enhanced by the use of the robust optimization algorithm which improves tolerance with respect to errors made on several parameters and guarantees the resulting optimized design to meet userdefined tolerance requirements.

C. Final robust design

The use of a robust optimization algorithm allows the search of not only the most efficient but also robust solution. However, with a 25 % decrease of the bandwidth and smaller tolerances for the critical parameters T g and F F , the optimum found by the robust optimization algorithm described in section III-A seems to be a poor result compared to the non robust optimization. The combination of the anti-optimization and the particle swarm algorithm has introduced a perturbation of the convergence of the optimization algorithm. When a new robust optimum is discovered, it could take several iterations of the algorithm to perform a good enough exploration of its neighborhood and decrease the robustness if a new minimum is found in the user defined tolerance ranges. A new optimum is then chosen by the swarm to be the best one, but its robustness has to be evaluated from scratch by the anti-optimization process and will not take into account the previously computed points.

To enhance the speed of the tolerance evaluation process of the anti-optimization, the robust optimization algorithm has been improved. Instead of using only the new points computed during the optimization to adjust the tolerance of the best known design, the minimum used in the figure of merit M F ′ is made on every points computed since the start of the optimization algorithm. This requires to store in memory all the tested designs and their associated figure of merit M F . The process of adding a memory in the swarm allows it to remember where the designs which are sensitive to error of fabrication are located and avoid them more easily.

The execution of the modified robust optimization with the same technological and tolerance requirements as before returns a HCG mirror with a 425 nm large bandwidth which dimensions are given in Table V. The tolerance evaluation of the parameters shows a good robustness with an optimum value well centered within large variation range. The grating thickness T g and Fill Factor F F tolerances are very large with T g = 668 ± 70 nm and F F = 0.5351 ± 0.0630. A statistic study with 30 000 tests of the tolerance of the optimum by varying simultaneously all the design parameters with ∆T g = ± 20 nm, ∆F F = ±0.02, ∆T A = ± 50 nm, ∆Λ = ± 3 nm and ∆T L = ± 1 nm have returned 0 mirror with less than 99.5 % of TM reflectivity at λ 0 = 2300 nm.

Finally, the tolerance of the optical index values of the materials have been explored. Indeed, the refractive index of Fig. 3. Reflection spectra of the robust HCG mirror designed with the parameters described in Table V. The inset exhibits a large 99.5% high reflectivity bandwidth of 425 nm centered at 2290 nm for the TM coefficient (blue) with a good polarization selectivity by keeping R T E < 70 % (dashed red). the GaAs, and the AlOx especially, can vary with respect to the conditions of fabrication. Computations have shown that the high contrast grating presented in Table V exhibits a reflictivity of more than 99.5 % at λ 0 for GaAs index values between 3.22 and 3.6 and AlOx index values between 1 and 1.78. Besides the variation of the refractive index, AlOx can present absorption in the mid infrared wavelength range [START_REF] Ravaro | Nonlinear measurement of mid-infrared absorption in AlOx waveguides[END_REF].

Even though the absorption is negligible below 2.5 µm [START_REF] Ravaro | Nonlinear measurement of mid-infrared absorption in AlOx waveguides[END_REF], the maximum absorption allowed to keep a 99.5 % reflectivity has been computed and is α = 110 cm -1 (k = 0.00183).

IV. CONCLUSION

A robust optimization algorithm has been developed to design high contrast grating mirrors for a VCSEL application at 2.3 µm. An anti-optimization process based on particle swarm optimization is used to adjust the geometrical parameters of the HCG structure by taking into account technological constraints. The fabrication accuracy of our equipments is also taken into account within the optimization process by defining tolerance requirements that the HCG parameters have to meet. The execution of the robust optimization algorithm thus results not only in an efficient mirror with a 99.5 % high reflectivity for a 425 nm large bandwidth but also in a robust design with more than ±10 % of tolerance on the grating thickness, which is one of the most critical parameter of the grating fabrication process. The mirror also exhibits a strong polarization selectivity by keeping the reflection coefficient of the TE mode lower than 70 %. This polarization selectivity combined with high mirror efficiency and large fabrication tolerance should make the GaAs/AlO x HCG design presented in this work a very good VCSEL mirror to allow emission above 2.3 µm.

TABLE II TOLERANCE

 II OF THE HCG OPTIMIZED BY DIFFERENTIAL EVOLUTION ENSURING R T M > 99.5 % AND R T E < 90 % AT λ 0 .

		Optimum	Min	Max	Tolerance
	Tg	685 nm	682 nm	756 nm	∆Tg = ±3 nm
	F F	0.513	0.507	0.590	∆F F = ±0.006
	T A	390 nm	364 nm	>499 nm	∆T A = ±26 nm
	Λ	1158 nm	1014 nm	1163 nm	∆Λ = ±5 nm
	T L	268 nm	221 nm	272 nm	∆T L = ±4 nm
	λ 0	2340 nm
	∆λ	481nm
	∆λ/λ 0	20.6 %

TABLE III TOLERANCE

 III OF THE HCG OPTIMIZED BY THE PARTICLE SWARM ALGORITHM ENSURING R T M > 99.5 % AND R T E < 90 % AT λ 0 .

		Optimum	Min	Max	Tolerance
	Tg	657 nm	609 nm	737 nm	∆Tg = ±48 nm
	F F	0.538	0.418	0.607	∆F F = ±0.069
	T A	352 nm	282 nm	447 nm	∆T A = ±70 nm
	Λ	1117 nm	993 nm	1148 nm ∆Λ = ±31 nm
	T L	283 nm	248 nm	308 nm	∆T L = ±25 nm
	λ 0	2298 nm
	∆λ	493 nm
	∆λ/λ 0	21.5 %
	makes it a very promising mirror for VCSEL application at
	2300 nm.

TABLE V OPTIMUM

 V AND TOLERANCE VALUES OBTAINED BY THE ENHANCED ROBUST OPTIMIZATION ALGORITHM.OptimumTolerances for R T M > 99.5% at λ 0

	Tg	668 nm	598 nm < Tg < 738 nm	∆Tg = ±70 nm
	F F	0.5351	0.4361 < F F < 0.5981	∆F F = ±0.063
	T A	360 nm	228 nm < T A	∆T A = ±132 nm
	Λ	1098 nm	993 nm < Λ < 1162 nm	∆Λ = ±64 nm
	T L	282 nm	240 nm < T L < 331 nm ∆T L = ±42 nm
	λ 0	2290 nm
	∆λ	425 nm
	∆λ/λ 0	18.6 %

ACKNOWLEDGMENTS

The authors thank the French ANR for financial support in the framework of Marsupilami project (ANR-09-BLAN-0166-03) and IES and LAAS (France), partners of LMOPS/Supélec in this project. This work was also partly funded by the InterCell grant (http://intercell.metz.supelec.fr) by INRIA and Région Lorraine (CPER2007).

This work was supported by the French ANR in the framework of Marsupilami project (ANR-09-BLAN-0166-03) and by INRIA and Région Lorraine with the InterCell grant (http://intercell.metz.supelec.fr -CPER2007).