Frédéric Jouault

Bert Vanhooff

Hugo Brunelière

Guillaume Doux

Yolande Berbers

Jean Bézivin

Inter-DSL Coordination Support by Combining Megamodeling and Model Weaving

Keywords: D.2.11 [Software Engineering]: Software Architectures -Languages (description, interconnection, definition) D.2.12 [Software Engineering]: Interoperability -Data mapping D.2.13 [Software Engineering]: Reusable Software -Domain engineering, Reuse models D.3.2 [Programming Languages]: Language Classifications -Design languages, Very high-level languages Model-Driven Engineering, Domain-Specific Languages, Coordination, Megamodeling, Model Weaving

Model-Driven Engineering (MDE) advocates the use of models at every step of the software development process. Within this context, a team of engineers collectively and collaboratively contribute to a large set of interrelated models. Even if the main focus can be on a single model (e.g. a class diagram model), related elements in other models (e.g. a requirement model) often have to be considered and/or accessed. Moreover, all the involved models do not necessarily conform to the same metamodel and thus may have been built using different independent Domain-Specific Languages (DSLs). Such a situation has already been frequently observed in many large-scale industrial deployments of MDE. Manually coordinating all the involved models, i.e. being able to both manage and use the links existing between them, can become a cumbersome and difficult task. As a proposal to solve this inter-DSL coordination issue, we introduce in this paper a generic and extensible inter-model traceability and navigation environment based on the complementary use of megamodeling and model weaving. We illustrate our solution with a concrete working example.

INTRODUCTION

Model Driven Engineering (MDE) largely promotes the use of models at each step of the software development lifecycle. One possible approach, and the one mainly considered in this paper, is to model each aspect of the system using a different Domain Specific Language (DSL). A DSL is a modeling language that strongly focuses on a specific area of a system such as requirements, data structure or user interface navigation for instance.

All the different models representing a same system are often interrelated. However, we cannot assume that all the DSLs which have been used for building them systematically provide explicit inter-DSL coordination capabilities. On the contrary, a DSL is often deliberately defined in isolation, focusing on just one aspect of the system (while completely ignoring others) and being independent of other DSLs. This makes it more reusable but also means that useful interrelationships between models built with different DSLs cannot be expressed directly using them. Nevertheless, for a given set of DSLs within the context of a project or project's type, we can identify a cartography of the coordination by specifying the possible kinds of relationships that may occur. For instance, the link between a Class element in a Java model and a Paragraph element in a Requirements model, or an Entity element in a Data model, can be considered.

In an incremental development process, most of the models are constantly elaborated and updated. Modifying one model might have an impact on, and require corresponding modifications to, other related models. Therefore, a developer needs to be able to quickly and easily navigate from model to model and from model element to model element. As soon as an MDE process includes more than a few DSLs, manually maintaining links and navigating between models (and corresponding model elements) does not scale very well. The problem of language coordinationmanaging many interrelated DSLs -is thus emerging as a very important challenge in MDE software engineering.

In this paper, we propose a generic and extensible modeling solution which is based on the combined use of megamodeling [START_REF] Bezivin | On the Need for Megamodels[END_REF] and model weaving [START_REF] Del-Fabro | Weaving Models with the Eclipse AMW plugin[END_REF]. Concretely, we offer a framework for representing both model-level and model element-level links and provide tool support for developers to be able to use these links and to navigate along them. This general modeling solution has been directly applied within the specific context of inter-DSL coordination.

Within the paper, we use the Pet Store reference application as an example. This application involves several DSLs and underlying models, each one describing a different aspect of this software system. While the techniques of inter-model coordination have a much broader scope than presented in this simple example, it allows us to practically demonstrate our solution. We consider a snapshot of a given project at a certain point in the development process. At this point, a developer wants to contribute to the project, for example by adding a new feature. In order to do so, considering a single model often does not suffice. Rather, a number of interrelated models need to be considered and modified accordingly. Our solution, together with all the used metamodels and Pet Store models, are publicly available from the Eclipse AtlanMod MegaModel Management (AM3) project [START_REF]The Eclipse-GMT AM3 (AtlanMod MegaModel Management) project's website[END_REF]. This paper is organized as follows. Section 2 briefly presents the fundamental model engineering techniques, and more especially the AmmA MDE toolkit that is used in our approach. Section 3 explains in details the proposed generic and extensible modeling solution. Section 4 introduces the Pet Store example, and uses it in order to illustrate how concrete models can be coordinated so that related traceability links may be navigated. Similar works on inter-model coordination in general are listed in Section 5 whereas Section 6 discusses some related issues. Section 7 concludes the paper.

MODEL ENGINEERING WITH THE AmmA TOOLKIT

This section briefly describes the AmmA (AtlanMod Model Management Architecture) MDE toolkit that is used as a basis for this work. AmmA is composed of four functional blocks available from the Eclipse website: In order to allow developers to establish the cartography of the coordination between different related models, we need to be able to represent all the available links. In order to do so (section 3), we need the Model Weaving component to manage links at the model element-level (subsection 2.1) and the Global Model Management component to manage links at the model-level (subsection 2.2). This latest component will then be extended in order to effectively enable the required navigation. In the next subsections, both these components are briefly discussed.

Model Weaving with AMW

Model weaving operations are performed between models or metamodels (two or more). A weaving model (WM) specifies links between elements from different models (called woven models). A weaving model conforms to a weaving metamodel (WMM), which provides the semantics of the links. AMW provides concrete solutions to the following model weaving related problems:

• Automating link creation. The generation of abstract correspondence links between elements from different models can be partially automated by means of heuristics (several ones are already available); • Storing links. It is possible to record this set of model element-level links as a whole, in order to use it later in various contexts;

• Using links in tools. It is possible to use the links as the input of automatic or semi-automatic tools. The typical use is the generation of a concrete transformation from a weaving model with the help of a higher order transformation.

The output of a model weaving operation on a set of models is a WM that conforms to a WMM. Hence, this WM remains linked to the set of woven models. Each link (a model element of WM) is typed by a concept specified in the corresponding WMM.

The WMM defines the available link types. Since model-element level links can be used in many scenarios (e.g., traceability and model annotations) it is quite impossible to define a common WMM supporting all the situations. Therefore, AMW only defines a minimal WMM, which can be extended for specific purposes. The minimal metamodel only offers a single (but extensible) type of link. Depending on the purpose of the links, the user should specialize them to one or more project-specific link types by adding more data and constraints. Thus, a concrete WMM may be expressed as an extension of another WMM. This means that a hierarchy of metamodels is created, which allows AMW to generically deal with all weaving-related tasks.

Global Model Management with AM3

The AtlanMod MegaModel Management tool, AM3 [START_REF]The Eclipse-GMT AM3 (AtlanMod MegaModel Management) project's website[END_REF], is a generic and extensible environment for dealing with large collections of heterogeneous models and metamodels. They are often accompanied by the tools and services which are usually combined in a given domain of application and/or specific process. The Global Model Management (GMM) principles [START_REF] Allilaire | Global Model Management In Eclipse GMT/AM3[END_REF] are implemented in this tool: for each part of the "real-world" intended to be modeled, which is often composed of several different systems, it is assumed that a megamodel can be specified and used in order to define the associated metadata.

A conceptual overview of the AM3 framework is shown in Figure 1. MDE introduces three different kinds of models [START_REF] Jouault | KM3: A DSL for Metamodel Specification[END_REF]: terminal models (M1) conform to metamodels represent real-world systems, metamodels (M2) conform to a metametamodel and metametamodels (M3) conform to themselves. A megamodel is a specific kind of terminal model whose elements represent models themselves, as well as relationships between them and metadata on them. As it is a terminal model, a megamodel conforms to a specific metamodel. In the context of a given working zone, the P r e l i m i n a r y v e r s i o n megamodel records all available resources or artifacts and their inter-relations.

Figure 1. AM3 Conceptual Framework

A megamodel can thus be viewed as a metadata repository where representations of models and links between them are stored as a model. Other artifacts such as textual files and even tools or services can also be managed by a megamodel if the corresponding extension of the metamodel of megamodel is available.

The AM3 solution from the Eclipse foundation implements the previously described conceptual framework.

It is an open source project which is part of the GMT subproject, which is itself part of the top-level Eclipse Modeling project. The generic and extensible AM3 megamodeling solution provides not only the capabilities to explicitly specify the metadata associated with a given system or process, but also a standard Megamodel Navigator as well as generic and extensible editors for instantiating and editing the megamodel in a more user-friendly way (Figure 6 and Figure 7). In addition, it offers several extension points allowing domainspecific extensions of the tool. Both the metamodel of megamodel and its related UI components can be extended.

AM3 is composed of two distinct sets of Eclipse plug-ins:

• The core plug-ins providing the basic metamodel of megamodel, the core APIs , the core runtime environment and associated generic navigator and editors; • The extension plug-ins providing extensions of the metamodel of megamodel and corresponding extensions of the UI (for instance specific editor pages, contextual actions, etc).

With AM3, users can build their customized megamodeling solution by extending either the core plug-ins or other already existing extension plug-ins. A set of generic MDE extensions have already been developed: GMM for Global Model

Management, GMM4ATL for model transformation with ATL, GMM4CT for Composite Transformations.

In the next section, we describe a new extension that is specifically focused on the problems that were described earlier.

By integrating the use of model weaving in the megamodeling environment and providing a number of UI extensions, we aim to provide some easy-to-use inter-DSL coordination capabilities.

COMBINING MODEL WEAVING AND MEGAMODELING

The problem of inter-DSL coordination, considering inter-model traceability and navigability, can be divided into two complementary problems corresponding to two different abstraction levels:

• traceability/navigability between models (higher level);

• traceability/navigability between model elements (lower level).

These two levels are related by a refinement relationship: navigability between model elements is a refinement of navigability between models. To support these two levels, both model-level links and model element-level links must be considered. Global Model Management proposes to use a megamodel (section 2.2) to represent all models involved in a given context as well as various relationships between them. Therefore, GMM is a solution applicable for model-level links. Model weaving (section 2.1) allows representing different kinds of fine-grained relationships between elements from different models. Model element-level links can thus be managed by using Model Weaving.

Figure 2. Support for navigation links in the GMM extension of the metamodel of megamodel

What was missing was a way to represent the refinement relation between the two levels of links. We have solved this problem by incorporating the notion of traceability links and models directly into the GMM extension of the metamodel of megamodel (Figure 2). The top part of the figure shows basic concepts, from the metamodel of megamodel, to represent models and relationships between them in a megamodel. On the bottom left, we have extended these to the notion of ModelWeavingRelationship and ModelTraceRelationship, the latter being a more specific case of the former. Since they both derive from the Relationship element, they have the ability to express high-level links between models.

On the bottom right, we introduce the WeavingModel and TraceModel concepts as representations of weaving models expressed by AMW (low-level links). The refinement relationship between both levels can now be represented simply by adding an This solution handles the navigability problem in a generic and extensible way. Navigability is provided by recording traceability links between both models and model elements. The concrete weaving or trace metamodel used can differ from project to project (extensibility) while navigation will be handled generically since each weaving metamodel will derive from a common base metamodel (AMW). Figure 3 describes an example of a megamodel. The legend at the bottom may be informally interpreted as a summary of the metamodel of this megamodel, previously presented in Figure 2. Each of the models (Mx) contains a number of model elements. These models conform to different metamodels (MMx) and are interrelated via model-level links (MWRelation). Each modellevel link can be associated to a weaving model (WeavingModelxy) which refines this link. All this information is stored within a single megamodel. Note that the weaving models are also registered into the megamodel, just like any other models.

Within a specific context, the semantics of the traceability links can be specialized: additional information about model-level links is specified by the metamodel of the megamodel and specific semantics for model element-level links can be provided by specializing the weaving metamodel(s). The proposed solution allows users and tools to retrieve and navigate all kinds of traceability links recorded into the megamodel. We have also extended the AM3 megamodeling environment with two specific views to allow users to zoom in on a given model-level link. This way, it is possible to see which elements of the corresponding models are actually concerned and how they are precisely interrelated.

In the next section, we apply the proposed solution to a concrete example and demonstrate how the extended AM3 megamodeling environment can thus be used by developers as an inter-DSL coordination solution.

USE CASE: THE "PET STORE" APPLICATION

In 2001, Sun described an application named Pet Store with the objective of providing to developers a typical example of program built using J2EE best practices. Later, Microsoft reproduced this experiment using their DotNet framework. This Pet Store sample application has since been used in many areas of software development as a benchmark to evaluate alternative development methodologies. The Java Pet Store 2.0 is the reference application for building Ajax web applications on Java Enterprise Edition 5 platform [START_REF]The Sun JAVA Pet Store demo[END_REF]. It illustrates good practices for using AJAX with Java, building AJAX-enabled JSF component libraries, using Java Persistence APIs, applying MVC (Model/View/Controller) and other design patterns. In this particular AJAX Web application, several services such as Google Maps service for location, PayPal service for payment, etc. are used to implement parts of the functionalities.

We consider a snapshot taken during the software development cycle of a simplified Pet Store application: all artifacts developed at this time are models built using various DSLs. How the various models have been built and how the traceability relations between them have been established is out of the scope of this paper. They can be created manually, derived automatically or generated by model transformations. We currently focus solely on the representation of these traceability links and on their navigability.

A Pet Store case, based on seven different types of models (i.e. Requirements, Use Cases, Deployment, Entity-Relationship, Class Diagram, Page Navigation and Java Project), has been developed. These terminal models are provided in EMF-XMI.

The seven corresponding metamodels are expressed in KM3 [START_REF] Jouault | KM3: A DSL for Metamodel Specification[END_REF] but are also available in EMF-XMI (conforming to Ecore).

All these available models and metamodels are registered into a megamodel. In this megamodel, we also record the high-level relationships between the models. As discussed in the previous section, we also represent low-level relationships using weaving models. Figure 4

Figure 6. Model-level navigability

All kinds of links that have been presented above need to be persisted (i.e., they need to be stored and then potentially retrieved). We consider that representing these links directly inside the Pet Store models is not a suitable approach because the models are then polluted by additional traceability information. This is why, following our generic and extensible approach, the model level links are stored directly in the megamodel like any other relations. The model-element level links are represented as links in weaving models attached to the model element links. All the work presented in this section, including the AM3-based megamodel, editors and the sample models, is available from the Eclipse-GMT AM3 project webpage [START_REF]The Eclipse-GMT AM3 (AtlanMod MegaModel Management) project's website[END_REF].

Figure 7. Model element-level navigability

We insist in this example on the way one may navigate all the models developed in a project (with different DSLs) at a given time. Thus, the available links may be used in order to ensure part of the inherent coordination existing between the different languages. However, the main interest of this work has been to demonstrate that this set of artifacts together with their mutual relationships and metadata, all providing the cartography of the coordination, may be represented as a megamodel (i.e. a model) conforming to a given (extensible) metamodel. This result is quite strong and new applications of it are still being found. For example, it is possible to check this megamodel for global consistency and this can be easily expressed with a model transformation. Similarly, it is possible to project this megamodel on a given display surface or to extract any kind of simplified view from it, again using a single model transformation.

P r e l i m i n a r y v e r s i o n

RELATED WORK

The problem of the coordination between multiple related artifacts is not a new one. In code-centric environments, we also have to deal with multiple types of mostly textually-oriented artifacts such as source code, SQL code, Web service descriptions (WSDL), language dictionaries or any DSL. All these artifacts, their integration and their interrelations can be managed in different ways. Classically, the management of these relations has been performed using an Integrated Development Environment (IDE). Usually, a single data (meta)model is defined for all artifacts and only predetermined relationships are available.

Considering some other approaches, the coordination is realized thanks to a dedicated DSL such as in [START_REF] Groenewegen | Declarative Access Control for WebDSL: Combining Language Integration and Separation of Concerns[END_REF]. Our approach focuses not on textual artifacts but more generally on models and is based on an extensible metamodel that allows to potentially link any types of model (i.e. models which conform to any metamodel) without modifying the core of the tools. Typical services offered by classical IDEs are 'find usages' and back/forward navigation throughout code. Our initial implementation is a first step in the direction of offering similar kinds of services for model-centric approaches.

In order to implement our solution for coordination, model traceability (which is an application of model weaving) and global model management (based on megamodeling in our case) have been combined. In the next two subsections we discuss related works in these two different but somehow interrelated areas.

Traceability

In order to enable navigation across different DSLs so that they can be coordinated, we use traceability links, stored as weaving models, between models and model elements. Many traceability approaches focus on requirements tracing and many different metamodels have been proposed [START_REF] Gills | Survey of traceability models in IT projects[END_REF], some of them trying to distill a standard metamodel [START_REF] Limon | The Need for a Unifying Traceability Scheme[END_REF]. Our model weaving approach offers a basic traceability metamodel that can be extended to fit almost any traceability scenario. Since the navigation operations are only dependent of the basic metamodel, it works transparently to the specific traceability needs of a project, meaning that any traceability links can be used for navigation.

In [START_REF] Olsson | Supporting traceability and inconsistency management between software artefacts[END_REF], a number of problems related to the management of many artifacts that have different purposes and different notations (describing parts of the same system, similarly to our problem statement) are discussed. They have developed an approach for traceability and inconsistency management between descriptions of software requirements, UML-style use case models and blackbox test plans. Traceability links are often used to notify developers if changes might have to be propagated throughout the chain of artifacts, i.e. if the different artifacts have to be coordinated. Our approach can be used to accomplish the same goals if each artifact is described by a DSL. Developers can thus easily navigate between artifacts to manually analyze possible required changes. Automatic analysis of change impact could be added as an extension to our tools.

Global Model Management

The concept of a megamodel was proposed in [START_REF] Bezivin | On the Need for Megamodels[END_REF] and in [START_REF] Favre | Towards a megamodel to model software evolution through transformations[END_REF]. The Eclipse AM3 project [START_REF] Allilaire | Global Model Management In Eclipse GMT/AM3[END_REF] has served as a cooperative framework to experiment with concrete implementations of various forms of megamodels. The global view presented by a megamodel also uses the concept of a weaving model proposed in [START_REF] Del-Fabro | Weaving Models with the Eclipse AMW plugin[END_REF]. The idea of a joint use of megamodeling and model weaving was first presented in [START_REF] Barbero | Traceability and Provenance Issues in Global Model Management[END_REF]. However, this work was really exploratory and at the time mostly focused on traceability in model transformation. This initial idea has now been generalized to any kinds of possible relationships between models, so that many different underlying coordination problems can be addressed.

There have been several mentions of using megamodeling techniques in recent works when dealing with complex situations. In [START_REF] Graaf | Model-Driven Evolution of Software Architectures[END_REF], an example of a megamodel describing model transformations is given, as well as a megamodel more focused on the model-driven evolution of software architectures. In [START_REF] Favre | Formalizing MDA components[END_REF], a megamodel is used in order to define families of reusable components. It refers to several metamodels and model transformations organized in an architectural framework. This megamodel allows formalizing the relations between different languages and thus provides some kind of support for coordination. In [START_REF] Del-Fabro | Industrial-strength Rule Interoperability using Model Driven Engineering[END_REF], an important network of transformations is described within the context of a rule-based management system. The paper illustrates that the development of a set of bridges between different DSLs implies the production of a high number of different artifacts (metamodels, projectors, transformations, etc) whose coordination is difficult to ensure and maintain without any automated support. Applying MDE techniques to the management of a high number of MDE artifacts naturally suggested using megamodeling techniques in this case.

As far as we know, there are not so many existing global model management approaches. However, some available ones have similarities with the megamodeling approach. For instance "macromodeling", as described in [START_REF] Salay | Using Macromodels to Manage Collections of Related Models[END_REF], proposes to define and use hierarchical models whose elements denote models and model relationships: as a consequence, a macromodel can be seen as some kind of megamodel. Moreover, this approach suggests considering macromodels for checking integrity constraints on the represented models and relationships. This is also the type of verification that can be performed from a megamodel, for example by applying a validation (model-to-model) transformation on it and generating a diagnostic model as a result.

The work described in [START_REF] Hesselund | Guided development with Multiple Domain-Specific languages[END_REF] is also somehow related to global model management, even if it does not make use of explicit megamodels. The precise analysis of a significant application (the Apache Open for Business OFBiz framework) leads to identify a set of seventeen different DSLs used in this context. These languages belong to different technical spaces (XML, grammarware, modelware), but they are not disjoint. The work presented there is a strong motivation for studying the problem of coordination between the programs written in these different languages. An experimental tool for navigating them is described (SmartEMF) which is quite similar to the browser presented in our work. The main difference with our work is that, in their case, there is no global representation of the situation by a (mega)model, which leads to the direct handling of the connections between artifacts by the various technologies. Moreover, as the underlying metadata is not explicitly expressed as a model like in our approach, this information cannot be directly reused for other purposes (validation, analysis, code generation, documentation generation, statistics and reports generation, etc).

P r e l i m i n a r y v e r s i o n

DISCUSSION

The work presented in this paper is a step in the direction of providing a generic and extensible inter-DSL coordination solution. A prototype based on the AM3 megamodeling tool has been developed and some experiments have been performed considering the Pet Store application as an example. The first results are very promising: the cost to develop the proposed prototype is relatively low since our solution is based on a generic and extensible megamodeling environment. Moreover, we could easily add many new DSLs to our example without requiring a lot of additional effort.

Apart from the evolution of the proposed example, the prototype in itself may be improved in different ways. From the navigability side, some user facilities such as navigation history support (Web browser-like) or additional navigation views may be developed. From a security side, user rights and restrictions of access on certain models and links may also be managed (this problem is somehow related to the notion of views and points of view on a system).

From a more theoretical point of view, the main lessons learnt in this work have been about the effective need of megamodeling techniques. Indeed, this exploratory work showed us the importance of megamodeling for inter-DSL coordination, but more generally for the management of any MDE process. The approach has a particularly high potentiality when used in combination with other basic MDE techniques such as model weaving or model transformation. MDE is based on the concepts of metamodel, metametamodel and model transformation.

Considering our important experience with the model transformation applications (thanks to the ATL community), we came to the conclusion that the notions of model weaving and megamodeling should also be considered as essential concepts of MDE.

The three-level metamodeling stack [START_REF] Bézivin | Towards a precise definition of the OMG/MDA framework[END_REF] is now consensually accepted. However, there are still many degrees of liberty in deploying MDE in practical contexts. One choice still on the floor is about considering either a minimal or universal metametamodel (this corresponds to the level M3 of the stack). In our work, we have clearly opted for this alternative by using the KM3 proposal [START_REF] Jouault | KM3: A DSL for Metamodel Specification[END_REF]. A second choice is about using either a universal or several specific metamodels (this corresponds to the level M2 of the stack). UML may be seen as a universal modeling language which obliges to handle a restriction device (the so-called profile mechanism) when the scope of the language needs to be more narrowly defined. We have clearly opted for the second approach where a metamodel is considered for defining the abstract syntax of a DSL [START_REF] Kurtev | Modelbased DSL Frameworks[END_REF]. These choices have a cost: nowadays we are facing the multiplication of small DSLs. As a consequence the penalty to pay is fragmentation, and megamodeling comes here as an obvious generic and extensible solution for coordinating a high number of related modeling artifacts.

One of the other interesting properties of our proposal is its low conceptual cost. Since weaving models (i.e. trace models) and megamodels are models, a lot of new functionalities can be achieved and plugged to the existing solution at a very low cost, thanks to the model unification principle and to all available MDE techniques. There are plenty of nice properties that come naturally out from the fact that a megamodel is a standard terminal model. Thus, it is possible to transform a megamodel into another model providing a different view on it. For example, some experiments we have already done allow to generate a graphical view, automatically obtained from the PetStore megamodel (using ATL), showing (using DOT) the conformance dependences between all the registered models.

We also discovered that megamodeling is necessary but not sufficient when used alone, as is model weaving. The joint efficient use of both techniques for coordination purposes is the main original contribution of the present paper. It has already been proved to work on a relatively small but significant application. It has now to be deployed on more important real life applications to be completely assessed. Following this idea, we already have observed several interesting properties of our proposal. In particular, it should scale up very nicely due to the recursive property of megamodeling: since a megamodel may represent any kind of models, it can represent megamodels also. Thus, we have the intuition that scalability issues in presence of a very high number of different artifacts may be addressed using the recursive property of megamodeling.

However, some other topics, which were not the subject of this paper but are related to the present work, still remain to be explored. One obvious topic is the production of the coordination information, e.g. of the traceability links both at model and model element levels. In this paper, this information was considered as already available in the required format but this is not always the case. More often, these data are created manually afterwards or automatically generated during the model creation process (for instance when a model transformation is running). Sometimes, they are also inferred from provided metadata using some heuristics, or imported from various inputs in different formats (for example from available documentation). Within our context, the deep study of all these possible cases still represents a lot of work. Another interesting topic is the checking and validation of the coordination information. For instance, by providing a more precise semantics to the traceability links (maybe by attaching explicit constraints to them), it could be possible to perform their verification and validation. Thus, the correctness and the relevance of the provided coordination information could be ensured before its actual use.

CONCLUSIONS

The naïve view where an application was entirely developed in one unique general purpose language (like Java) and only maintained in this language is now considered as completely unrealistic. Present day's applications make use of a high number of different DSLs (for example XML-based DSLs) and code written with these different DSLs does not disappear when the application is put in use. We first observed in this paper that this fragmentation problem is serious but should be rapidly addressed by defining scalable coordination schemes.

We presented our generic and extensible solution for dealing with the inter-DSL coordination problem. Our approach is based on the combined use of two different but complementary MDE techniques: megamodeling (or global model management) and model weaving. We have shown that our solution can be practically applied in order to manage the various artifacts related to a given context in a software project. As an example, we have used a simple situation based on the development of a sample software system and we have shown that many applications of P r e l i m i n a r y v e r s i o n MDE generate or use a high number of artifacts. From there, we have reported significant progresses on handling the general situation. The example presented in this work shows how to use the Eclipse-GMT AM3 project as a coordination tool fitted with traceability and navigation capabilities.

It is also very important to notice that megamodeling has a much broader application scope than the one presented here. The inter-DSL coordination problem is just an example, among many others, of a possible use of a megamodel. The megamodeling approach, being by nature generic and extensible, can potentially have many different applications in all domains involving the management (and so the coordination) of a lot of modeling artifacts and their associated metadata. Dealing with the design, building, and execution of complex chains of model transformations is one example directly coming from the MDE field. Being able to efficiently manage hundreds (or even thousands) of heterogeneous models, retrieved from source code and documentation during the reverse-engineering process of a complex legacy software system, is another interesting problem we are currently exploring. Another application we are now experimenting on, which is also directly related to the reverseengineering domain, is the use of a megamodel in order to represent the actual high-level cartography of different software platforms (in terms of tools, services, plugins, etc). This should allow obtaining all the different available dependences, in order to check the validity and the appropriateness of the overall platform for instance.

Figure 3 .

 3 Figure 3. Overview of the proposed generic and extensible solution.

  shows a snapshot of the Pet Store project showing a number of such relevant links. Solid arrows are modellevel links whereas dotted arrows are model element-level links.

Figure 4 .

 4 Figure 4. Traceability links between models and model elements

Figure 5 .

 5 Figure 5. Detailed examples of traceability linksZooming in on the model-level link between the UseCase and ClassDiagram models (Figure5), we see that from the Browse Product use case we can navigate to design classes Category and Product. When we zoom in on the link between the ClassDiagram and EntityRelationship models, we see that the Category design class is related to the Category entity and that the ID class attribute is related to the ID field. Thus, it can be deduced that the Category entity is (indirectly) linked to the Browse Products use case.

Figure 6 and

 6 Figure 6 and Figure 7 show how the AM3 megamodeling environment provides all these navigation links to the developer. When we select the eStoreClassDiagram model on the right part of the Megamodel Navigator, related models immediately show up the Model Level view. We can then easily navigate to the related eStoreEntityRelationship and eStoreJavaProject models or open up any of them using their corresponding editor. In Figure 5, the ClassDiagram model has traceability links to the Entity-Relationship and JavaProject models (linked models part of the Model Level view). Zooming on the ClassDiagram to JavaProject traceability link available from the screenshot of Figure6there is a model element-level traceability link between the Category design class and the Category type from the Java project model (Figure7).

ACKNOWLEDGMENTS

This work is being supported by the IST-FP6 MODELPLEX European project [21] and the French IdM++ project.


Samer Lahoud
email: samer.lahoud@enst-bretagne.fr

Géraldine Texier
email: geraldine.texier@enst-bretagne.fr

Laurent Toutain
email: laurent.toutain@irisa.fr

Approximation Algorithm for Minimum Cost Flow Allocation with Varied Survivability

In this work, we study the minimum cost flow allocation problem with varied survivability. Given a set of demands and a capacitated network, the problem consists of allocating each demand to a set of primary paths that carry the flows realizing the demand volume in the normal operation mode. To ensure survivability, bandwidth is allocated over a disjoint set of backup links protecting the primary path. With the varied survivability concept, only a varied portion of the primary flow is guaranteed to be recovered in failure situations. The recovery ratio is predefined for a given demand and denotes the guaranteed quality of protection. We associate a unitary cost for using the installed bandwidth in core links. Thus, the problem provides a minimum cost solution for allocating the demands and ensuring their survivability. The main contribution of this paper is a new approximation algorithm using a primal-dual approach. This approximation algorithm computes a solution that is within a guaranteed factor of the optimal one and runs in time polynomial in the problem size.

I. INTRODUCTION

Providing minimum cost solutions is a crucial objective for many optimization tasks that are involved in the network design process. Particularly, network engineers solicit flow allocation solutions that induce minimum costs in terms of bandwidth consumption. This cost is strictly related to the capital expenditures spent at the capacity provisioning stage. In this work, we address the problem of finding a minimum cost flow allocation solution. Flow allocation refers to the routing and bandwidth allocation problem for a given set of demands over a capacitated network. Our approach is an off-line optimization that assumes the knowledge of a traffic demand matrix. This matrix defines the bandwidth requirements between network nodes and is generally based on statistical information. We provide support for the varied survivability concept where the backup capacity enables to recover a predefined portion of the primary traffic affected by failures. The recovery ratio is predefined for a given demand and denotes the guaranteed quality of protection. In this paper, we provide a mathematical formulation for the problem as a Linear Program (LP). We study the complexity of the separation oracle and derive a new approximation algorithm. We prove that the solution cost computed by our approximation algorithm is within a guaranteed factor of the optimal cost and that the algorithm runs in time polynomial in the problem size. This paper is organized as the following. In section II, we state the key elements of this work. We introduce the problem formulation in section III. Then we study the complexity of the problem and the relevant approaches in section IV, emphasizing the complexity of the oracle subproblem. Then, we give the approximation algorithm in section V. Finally, we present the numerical results in section VI, where we evaluate the performance of our algorithm on a typical network topology. We conclude in section VII with a brief summary of the achievements and the open questions encountered in this paper.

II. CONTEXT AND MOTIVATION

The flow allocation problem with varied survivability includes many key elements that make the corresponding optimization more challenging. In this section, we review the different concepts involved in flow allocation and motivate our approach. The protection we provide in our work follows the varied survivability concept used in [START_REF] Srivastava | Network traffic engineering with varied levels of protection in next generation internet[END_REF]. The basic idea is to offer different levels of protection for different customers while still providing best-effort services. For instance, a service classification can provide (i) guaranteed service quality under normal network operating conditions, i.e. no failure situations, (ii) full guarantee under normal situations plus a reduced level of service under failure situations and (iii) full guaranteed service both under normal or failure situations. Technically, we implement the varied survivability in our problem using a varied protection ratio for each demand: the backup bandwidth protecting the active path of the cycle is computed as a portion of the active bandwidth, and this portion varies form 0% to 100%. We use a general technique based on duality in LP in order to develop an approximation algorithm for the MCost-MCF problem. In essence, using duality, an optimization problem P given in a particular form, called primal problem, can be transformed to a related problem called its dual problem, so that the optimal solutions to both problems are closely related. Particularly, considering that P is a maximization problem, the objective value of any feasible solution to the primal problem is at most the objective value of any feasible solution of its dual. Hence, when these solutions are equal then they are optimal. Therefore, by comparing the objective values of the primal and dual formulations, we can measure the closeness of a solution (for the primal problem) to the optimal one. The BASIC PROBLEM NOTATION approach we present in this paper is particularly innovative in the sense that it provides fast and efficient solutions to the minimum cost problem:

• for any predefined 0 < ρ < 1, our algorithm computes a solution that is within a ρ/2 factor of being optimal • and our algorithm runs in time polynomial in the network size and the number of demands. Our contribution is even more relevant since solving directly the initial problem is time consuming in practice and the best practice methods does not perform better (more details are provided in section VI)

III. MATHEMATICAL FORMULATION

In the following, we consider a capacitated network represented by an undirected graph G = (V, E). All the notation is described in Table I. Using this notation, we provide a mathematical formulation for the flow allocation problem, referred to as MCost. This formulation is a Linear Program (LP) described in LP 1. Note that in our approach, we use the cycle formulation, where one cycle refers to a pair of disjoint paths. Using disjoint paths ensures the resistance to single link failures. As we allow splittable flows, the demand volume for one demand can be allocated to more than one cycle. Note also that for each unit of primary flow allocated on the primary path of one cycle realizing demand d, a ϑ d fraction is allocated on the corresponding backup set of links. Particularly, the objective in (1) consists of minimizing the total cost of allocating the demands. It takes into account the two unitary costs of allocating bandwidth for primary and backup flows. Moreover, constraint (2) ensures that the total demand volume for each demand d is allocated on cycles k ∈ K d , while constraint (3) ensures that the total flow on link e does not exceed its capacity. Now let us proceed to a basic reformulation of MCost in order to obtain an elementary problem similar to the problems reported in [START_REF] Fleischer | Approximating fractional multicommodity flow independent of the number of commodities[END_REF]. The MCost problem formulated in LP 1 consists of minimizing the cost of allocating all the demands subject to capacity constraints. Thus, MCost can be reformulated such that to maximize the portion of allocated demands subject to capacity constraints and a maximal Subject to:

k∈K d f dk ≥ h d , ∀d ∈ D (2) d∈D k∈K d (α p edk + α b edk ϑ d )f dk ≤ C e , ∀e ∈ E (3)
f dk ≥ 0, ∀d ∈ D, ∀k ∈ K d (4)
cost bound, and then finding the minimum cost bound that enables to allocate all the demands (details are provided in section V-C). We note that the MCost formulation in LP 1 is a generalization of the minimum cost multicommodity flow problem. Now, we provide in LP 2 an equivalent maximum concurrent flow formulation with a cost bound. This will be referred to as MCost-MCF. In LP 2, constraint [START_REF] Li | Finding disjoint paths with different path costs: Complexity and algorithms[END_REF] ensures that a minimum portion of all demands is allocated to the network: this minimum value is denoted by λ and is subject to maximization in the objective [START_REF] Xu | On finding disjoint paths in single and dual link cost networks[END_REF]. Moreover, constraint (8) denotes the maximum cost, denoted by S, that bounds the solution of allocating a portion of the demands. Finally, constraint (7) denotes the capacity limit on each link.

LP 2 MCost-MCF problem

Maximize λ (5)

Subject to:

k∈K d f dk ≥ λh d , ∀d ∈ D (6) d∈D k∈K d (α p edk + α b edk ϑ d )f dk ≤ C e , ∀e ∈ E (7) d∈D k∈K d e∈E (α p edk ξ p e + α b edk ξ b e ϑ d )f dk ≤ S ( 8
)
f dk ≥ 0, ∀d ∈ D, ∀k ∈ K d ( 9
)
In order to design an approximation problem, let us begin by introducing the dual of the MCost-MCF problem in LP 3. In the dual problem, π d , ω e and φ denote the dual variables associated with constraints (6), [START_REF] Liu | Spare capacity allocation method, analysis and algorithms[END_REF] and [START_REF] Laborczi | Solving asymmetrically weighted optimal or nearoptimal disjoint path-pair for the survivable optical networks[END_REF] respectively in the primal problem. In order to follow the same approach adapted from [START_REF] Fleischer | Approximating fractional multicommodity flow independent of the number of commodities[END_REF], we consider that the generalized weight of one cycle is given by the left-hand-side expression of constraint [START_REF] Diestel | Graph theory[END_REF]. Then, we need to find an oracle that computes the minimum weight cycle. Unfortunately, this appears as a difficult task, and the related problem deserves a loser look. In the following, we start by reviewing the relevant approaches to the MCost-MCF problem, then we point out the complexity of the oracle in order derive our approximation.

LP 3 Mcost-MCF: dual problem

Minmize φS + e∈E C e ω e [START_REF] Suurballe | A quick method for finding shortest pairs of disjoint paths[END_REF] Subject to:

d∈D h d π d ≥ 1 (11) e∈E α p edk (ω e + ξ p e φ) + α b edk ϑ d (ω e + ξ b e φ) ≥ π d , ∀d ∈ D, ∀k ∈ K d (12) ω e ≥ 0, ∀e ∈ E (13) φ ≥ 0 (14)

IV. COMPLEXITY STUDY AND ORACLE APPROXIMATION

A large set of optimization tools can be used in order to provide efficient solutions to the MCost problem. Notably, a similar problem is studied in [START_REF] Srivastava | Network traffic engineering with varied levels of protection in next generation internet[END_REF] in the context of network traffic engineering problem for tunnel provisioning. The authors provide a cycle formulation that enables to easily model the varied protection level. The allocation is constrained by bandwidth and tunnel constraints. In order to provide integral solutions to the problem, the authors use two heuristics. The first one consists of solving continuous relaxations of the problem ans then successively rounding the variables to the nearest integer. The second one uses a stochastic meta-heuristic approach by extending the simulated allocation approach introduced in [START_REF] Pióro | Simulated allocation: a suboptimal solution to the multicommodity flow problem[END_REF]. Another approach consists naturally in adapting the column generation approach as in [START_REF] Krithikaivasan | Backup path restoration design using path generation technique[END_REF], where no polynomial oracle was found. However, this approach requires maintaining a large set of candidate cycles and thus suffers from computational complexity (as we see in the numerical results in section VI). Therefore, the complexity of the problem is somehow related to the complexity of the oracle. Then, let us investigate the complexity of the oracle in order to get deeper insights on the related problem.

A. Oracle Discussion

1) General Formulation: In order to find a most violated constraint, an efficient subroutine, called oracle, computes the cycle that minimizes the left-hand-side expression of constraint [START_REF] Diestel | Graph theory[END_REF] for a given demand d. This is equivalent to finding the minimum weight cycle realizing demand d under the weight function ω p e = (ω e + ξ p e φ) for the links in the primary path and ω b e = ϑ d (ω e + ξ b e φ) for the links in the backup path. Note that link costs ξ p e and ξ b e are related to the capital expenditures in the capacity provisioning phase. Moreover, our problem supports cost differentiation: different unitary costs can be chosen for bandwidth units whether it is used for a primary or backup flow. Typically, we choose the cost for backup bandwidth to be lower as this bandwidth can be used to carry Best-Effort preemptible traffic. Thus, at his level, we make the assumption that ξ p e ≥ ξ b e , ∀e ∈ E. Since 0 ≤ ϑ d ≤ 1, we get ω p e ≤ ω b e , ∀e ∈ E. As we will see in the following study, this assumption plays an important role in the oracle design.

2) Related Work: A similar problem that consists of finding a pair of disjoint paths with minimum weight has been largely investigated recently. In [START_REF] Xu | On finding disjoint paths in single and dual link cost networks[END_REF], the authors present a general review of the relevant work. They summarize in the table in section 2 the computational complexity of various problems related to finding a pair of disjoint paths. Particularly, the problem of computing a minimum weight disjoint path pair with different weights for the primary and backup paths, called dual weights, is studied in [START_REF] Li | Finding disjoint paths with different path costs: Complexity and algorithms[END_REF] and proved to be N Pcomplete. A special case is to have ordered dual weights, e.g. ω p e ≥ ω b e , ∀e ∈ E. This problem of ordered dual weights is studied in [START_REF] Liu | Spare capacity allocation method, analysis and algorithms[END_REF] and also proved to be N P -complete. Even when weights are uniformly ordered, i.e. there exists a constant 0 < κ < 1 such that for all links we have ω b e = κω p e , ∀e ∈ E, the problem is still N P -complete. For directed graphs, the proof is provided in [START_REF] Laborczi | Solving asymmetrically weighted optimal or nearoptimal disjoint path-pair for the survivable optical networks[END_REF], while the proof for undirected graphs is provided in [START_REF] Xu | On finding disjoint paths in single and dual link cost networks[END_REF].

3) Efficient Algorithms: Given the N P -completeness of the above presented problems, the idea is to find a procedure that efficiently computes a good solution. However, when reviewing the work oriented in this direction, we realize that no existing approach suits our needs for the oracle. In [START_REF] Li | Finding disjoint paths with different path costs: Complexity and algorithms[END_REF], an algorithm with a worst-case guarantee is provided for the arbitrary dual weights problem. The idea is to average the weights on the links and then compute a disjoint pair of paths using the averages weights. Particularly, the algorithm computes a solution that is within a guaranteed factor of the optimal one. The factor depends on the maximal ratio between ω p e and ω b e . Take for instance, the simple case where 0 ≤ ϑ d ≤ 1, ∀d ∈ D and ξ p e = ξ b e , ∀e ∈ E, then this ratio depends on 1/ϑ d and the approximation factor is large for small ϑ d values. Thus, this algorithm is not suitable as an oracle. The authors of [START_REF] Kodialam | Dynamic routing of restorable bandwidth-guaranteed tunnels using aggregated network resource usage information[END_REF] consider the same problem and provide an approximation algorithm based on a sophisticated primal-dual approach. Particularly, they formulate the problem as an integer linear program. Then, they relax the integrality and generate a lower bound of the optimal solution. Hence, the algorithm consists of tightening the lower and upper bounds for the problem and evaluating the guaranteed approximation ratio. The authors claim that their algorithm runs fast and the quality of the obtained approximation is less 5%. However, no guarantee for the computation time, nor the number of iterations, is given. Therefore, this approach is not fully suitable for our guaranteed approximation with a desired polynomial running time.

4) Oracle Approximation: After this discussion, we conclude that finding a good oracle that computes a minimum weight pair of paths with dual ordered weights is not an easy task. Therefore, we introduce a new approximation to the oracle with dual ordered weights. This approximation achieves a guaranteed optimality factor of 2 and runs in time polynomial in the problem size. However, we note that this approximation will induce a structural modification on the basic problem formulation. Let us start by describing the approximation. Our approach is based on the famous algorithm in [START_REF] Suurballe | A quick method for finding shortest pairs of disjoint paths[END_REF]. Algorithm 1 begins by computing a shortest path form source to destination using weights ω p e , ∀e ∈ E. This will be the primary path of the output. Then, we construct a residual graph: Each link e on the computed shortest path is replaced by a directed link oriented toward the source and a zero weight. Each other link e is replaced by two directed links in opposite directions with the same weight ω b e . On the residual directed graph, we compute a shortest path denoted by q form source to destination. Then, going back to the original graph, we remove the interlacing links between q and the primary path and obtain the backup set of links q. Finally, the weight of the set of links in (p, q) is at most two times the weight of the minimum weight cycle realizing demand d. The formal approximation result is provided in Theorem 1. Hence ω q ≤ ω q ≤ ζ k * , which finally gives us that the weight

ζ k of k = (p, q) verifies ζ k = ω p + ω q ≤ 2ζ k * .
However, we note that the output of Algorithm 1 is not a cycle! In fact, when pruning the interlacing links, we get a set of backup links and not a disjoint backup path. Still, this set of backup links ensures the survivability in single failure situations. Thus, we consider that we use obtain a generalized form of protection and we call the pair of primary path and the set of disjoint backup links a survivable structure or simply a structure. To some extent, the structure and the generalized protection concept were used in a similar approach to our work, introduced in [START_REF] Li | Routing bandwidth guaranteed paths with local restoration in label switched networks[END_REF]. The approach formulates a backtracking concept for on-line routing of bandwidth guaranteed tunnels i.e. for a single commodity problem. Backtracking enables to bound the protected entity scope. Particularly, in the no backtracking case, the backup path must originate at the node at which the failed link originates. This case represents true local restoration. In the bounded backtracking case, the backup path can originate at a node on the primary path up to a predefined number of hops away from the node that owns replace e with a directed link oriented toward the source and let the weight of this link be zero; foreach e ∈ Ep do replace e with two directed links in opposite directions and let the weight of these links be ω b e ; q ← shortest path realizing demand d in the modified directed graph; q ← {set of links in the original graph that are in q and not in p}; k ← (p, q); Algorithm 1: Oracle Approximation the link. Moreover, in the infinite backtracking case, unlimited backtracking is allowed and therefore, in the worst case may result in backup paths that originate at the source node. The end-to-end restoration can be considered a special case of this where the maximum backtracking allowed is equal to the length of the primary path. The last case is very similar to the generalized approach we introduce in our work. The authors in [START_REF] Li | Routing bandwidth guaranteed paths with local restoration in label switched networks[END_REF] show that joint optimization of primary and backup paths is N P-hard in all cases and they consider algorithms that compute primary and backup paths in two separate steps. In the following we formalize the definition of the output structure of the oracle approximation.

input : graph G = (V, E), demand d = (s d ,

B. Structures and Cycles

We have noted above that a structure obtained by Algorithm 1 consists of a primary path going from source to destination and a set of backup links that are disjoint from the primary path and ensure the survivability. More formally, a structure k realizing demand d = (s d , t d ) is a set of links that consists of a primary path p from s d to t d and a set of backup links b the are disjoint from p. For each single failure situation the set (p ∪ b) contains a path from s d to t d . Thus, in a structure, backup links together with the primary links that are not failing are required to provide connectivity from source to destination in failure situations.

Mathematically, we can define a structure using basic properties of graph theory [START_REF] Diestel | Graph theory[END_REF]. Recall that an (st) cut, denoted by C (s-t) , in graph G = (V, E) is a partition of the set of vertices V into disjoint sets S and T = V -S, such that s ∈ S and t ∈ T . The links of the cut are those that have precisely one endpoint in both V and T . Let us denote the set of links of the cut by E C (s-t) . Therefore, a structure k realizing demand d = (s d , t d ) verifies that there are more than 2 links belonging to k ∩ E C (s d -t d ) , for any (s d , t d )-cut C (s d -t d ) . In Figure 1, we provide two examples that enable to illustrate the new concept of structures. Figure 1(a) is a general case of a structure obtained by the oracle approximation. However, in some cases and depending on the output of the approximation algorithm, a structure consists of two disjoint paths, as in Figure 1(b). Thus, we consider that the cycle formulation is a special case of the structure formulation.

V. APPROXIMATION ALGORITHM

Now that we have an approximate oracle, we continue the design of the global approximation to the MCost-MCF problem by adapting the approach introduced in [START_REF] Garg | Faster and simpler algorithms for multicommodity flow and other fractional packing problems[END_REF].

A. Algorithm Presentation

Algorithm 2 computes an approximation to the MCost-MCF problem. This algorithm works as follows: we start with initial link weights ω e = δ Ce , ∀e ∈ E and φ = δ S . The quantity δ depends on the approximation guarantee (particularly on a parameter introduced later) and will be stated later in the algorithm analysis section. The algorithm proceeds in phases. Each phase is composed of D iterations. In iteration d, we allocate h d units of flow for demand d. This flow is allocated in a sequence of steps. In each step, a cycle k * (realizing demand d) that minimizes the left-hand-side expression of constraint [START_REF] Diestel | Graph theory[END_REF] should be computed. However, as we have shown in the oracle study we can compute an approximate structure denoted by k. Now, we will compute the flow we allocate to this structure. Considering the varied survivability concept, k consists of a primary path p and a backup set of links b with bottleneck capacities denoted by c p and c b respectively. The bottleneck capacity of structure k is given by the minimum of (i) c p , and (ii) c b /ϑ d . This is due to the fact that we allocate a ϑ d fraction of bandwidth on the backup links for each 1 unit of flow on the primary path. Therefore, the maximum amount of flow allocated to structure k in this step is denoted by c and is the minimum of:

1) the bottleneck capacity of structure k given by min{c p , c b /ϑ d }, 2) the remaining amount of flow that need to be allocated for demand d to make a total of h d . However, we should ensure that the cost of allocating c units of flow to structure k does not exceed S, otherwise the flow should be scaled appropriately. Particularly, let us denote by s k the cost of allocating 1 unit of flow to structure k. Recall that this is equivalent to allocating 1 unit to the primary path and a ϑ d fraction of unit to the backup links. Thus,

s k = e∈E (α p edk ξ p e + α b edk ξ b e ϑ d ).
Similarly, the cost of allocating c units of flow to structure k is given by cs k . Therefore, we ensure that: 1) if cs k > S, we scale c according to c = c S s k , 2) if else, the value of c remains unchanged. Finally, we get a value of c that denotes the amount of flow to be allocated to the structure k computed in this step. The primal variables are updated correspondingly and the dual weights are updated as follows (using the parameter that will determine the approximation ratio):

1) for each e ∈ p, ω e = ω e (1 + c Ce ), 2) for each e ∈ b, ω e = ω e (1 + ϑ d c Ce ), 3) and φ = φ(1 + cs k S ). The algorithm terminates when the dual objective function value becomes bigger than one. At termination, dual feasibility constraints will be satisfied. However, link capacity constraints in the primal solution will be violated, since we use the original (and not the residual) link capacities at each stage. The full details are provided in the following section, where we study the global performance of the algorithm and the corresponding approximation ratio.

input : Capacitated graph G, set of demands D, cost bound S and output : λ = t-1 log 1+ ( 1 δ ) , S = s log 1+ ( 1 δ ) initialize: t = 0; s = 0; ω e = δ Ce , ∀e ∈ E; φ = δ S ; while Ω < 1 do for d = 1, . . . , D do r ← h d ; while Ω < 1 and r > 0 do k = (p, b) ← structure realizing demand d given by Algorithm 1; c ← min{r, c p , c b /ϑ d }; s k ← e∈E (α p edk ξ p e + α b edk ξ b e ϑ d ; if cs k > S then c ← c s k ; s ← s + cs k ; ∀e ∈ p : ω e ← ω e (1 + c Ce ); ∀e ∈ b : ω e ← ω e (1 + ϑ d c Ce ); φ ← φ(1 + cs k S ); r ← r -c; t ← t + 1;
Algorithm 2: MCost-MCF approximation algorithm

B. Algorithm Analysis

Let us denote by ω e (i, d, j -1) the weight of link e and φ(i, d, j -1) the value of φ at the beginning of step j of iteration d in phase i. Let k * (i, d, j -1) denote the minimum weight cycle in K d in step j of iteration d of phase i, using weights ω e (i, d, j -1), and let ζ k * (i,d,j) (i, d, j -1) be its weight. We know that the weight of the computed structure ζ k(i,d,j) (i, d, j -1) does not exceed 2ζ k * (i,d,j) (i, d, j -1). Let also Ω(i, d, j) be the objective of the dual problem LP 3 at the end of the iteration. Assuming that there are J = J(i, d) steps executes at iteration d of phase i, let us consider that Ω(i) = Ω(i, D, J) and

Γ(i) = D d=1 h d ζ k * (i,d) (i, D), where ζ k * (i,d) (i, D
) denotes the weight of the minimum weight cycles (computed originally with respect to ω e (i, d -1, J) and φ(i, d -1, J)) at the end of phase i. Then, the dual problem is an assignment of weights ω e to links e ∈ E and a scalar φ, which we view as a weight associated with a pseudo-link of capacity S, such that Ω(i) Γ(i) is minimized. Moreover, the optimal dual objective is given by ψ := min i Ω(i) Γ(i) . In the algorithm analysis, we assume that ψ ≥ 1 but we shall remove this assumption later after. We start by computing the ratio between the optimal dual objective ψ and the primal objective obtained at the end of the algorithm. Knowing that we allocate h d units of flow for each demand d in each phase, then the primal objective is given by t -1, where t denotes the total number of phases. Lemma 1 gives the corresponding intermediate result. Note that this primal solution does not necessarily correspond to a feasible solution, and thus need to be scaled properly in order to become feasible. Therefore, Lemma 2 and Lemma 3 give the proper scaling that yields a feasible solution to the primal problem and the corresponding cost. For clarity, the full mathematical proof is left for the Appendix. Hereafter, we provide the main results of the algorithm analysis.

Lemma 1: At the end of Algorithm 2, the ratio between the optimal dual objective and the number of phases verifies

ψ t-1 ≤ 2 (1-2 ) ln 1-2 δ(E+1)
. T mws , where T mws is the time required to compute a minimum weight structure. The running time for computing a minimum weight structure as in Algorithm 1 is dominated by two minimum weight path computation that can be performed in O(E + V log V ) [START_REF] Fredman | Fibonacci heaps and their uses in improved network optimization algorithms[END_REF].

C. Finding the Minimum Cost Solution

With a ρ/2-approximation to the MCost-MCF problem, we can obtain a ρ/2-approximation to the MCost problem introduced in LP 1. For this purpose, we can use an efficient search method such as binary search to find the smallest value of S for which MCost-MCF has a solution of λ ≥ 1. Furthermore, the binary search can be improved by using an interpolation search as in [START_REF] Fleischer | A scalable algorithm for the minimum expected cost restorable flow problem[END_REF]. This improvement consists of estimating the next value using a linear interpolation as in the following:

• if MCost-MCF with a bound S returns a value λ ≥ 1, then the final cost bound is at most S/ λ; • if MCost-MCF with a bound S returns a value λ ≤ 1, then the final cost bound is at least S/ λ.

VI. NUMERICAL RESULTS

We present a typical numerical result corresponding to the KL topology [START_REF] Kodialam | Dynamic routing of restorable bandwidth-guaranteed tunnels using aggregated network resource usage information[END_REF]. KL is a 15-node 28-link topology. We associate a capacity of 200 bandwidth units with each link and consider that demands are defined between each node pair of the network, each having have a volume of 10 bandwidth units. We associate a unitary cost of 2 for the links in the primary path and 1 for the links in the backup path. For this typical simulation, the binary search ends in 6 steps. Note that we start with the simple upper cost bound as indicated in section V-C. In Figure 2, we evaluate the cost of the solution for the MCost-MCF problem throughout the binary search steps. Let us analyze simultaneously Figure 3 that gives the value of λ (the objective of the MCost-MCF problem) during the binary search process. At the first two steps, the cost bound is very loose, and the value of λ is around 1.15. Then, using the linear interpolation we start strengthening the bound in order to make λ converge toward 1. Thus, in the third step, the cost of the solution goes down from 7500 to 6500, while λ is still around 1.15. This is due to the fact that the solution of the problem is not unique and two allocations of the same bandwidth volume can lead to different costs. However continuing the interpolated binary search, we obtain two steps further (step 5) a solution with λ around 1.01 and a cost bound of 6500. We note that at this level, smaller reductions in the cost bound has bigger impact on the value of λ. Finally at the sixth step, the desired accuracy is reached for a cost of 6300 and λ around 1.0001. Finally, in Figure 4, we assess the time performance of the algorithm. We provide for each binary step the number of phases, and the total time spent in the algorithm. We can see that the total number of phases in each run of the algorithm decreases with the steps. This is due to the fact that λ is decreasing and less flow is allocated, then a smaller number of phases is needed. Similarly, the running time is decreasing with the binary steps. An important remark is that the total running time sum for the six steps) is very competitive with the running time for the column generation approach. A complete study and further comparison is provided in [START_REF] Lahoud | Survivable routing and flow allocation in next generation internet networks[END_REF].

VII. CONCLUSION

The advent of Next Generation Internet (NGI) networks has launched many services related to survivability. Therefore, the need for efficient algorithmic tools that enable network engineers to implement their provisioning strategies is becoming urgent. In this work we have designed an efficient algorithm for the flow allocation problem. Our problem takes into account varied survivability levels in terms of guaranteed protection and enables to minimize the network costs. An extension of this work encompasses multiple failure survivability is reported in [START_REF] Lahoud | Survivable routing and flow allocation in next generation internet networks[END_REF]. Moreover, detailed comparison with the best practice methods, especially with column generation, is provided in [START_REF] Lahoud | Survivable routing and flow allocation in next generation internet networks[END_REF]. Future work will include rounding the fractional solution to get integral flows and comparing the results with stochastic meta-heuristics.

APPENDIX I ANALYSIS OF ALGORITHM 2

In the following, we highlight the basic steps in the algorithm analysis. In [START_REF] Lahoud | Survivable routing and flow allocation in next generation internet networks[END_REF] a complete version is provided.

A. Proof of Lemma 1

As we have noted, Algorithm 2 proceeds in phases: each phase is composed of D iterations. In iteration i, we allocate h d units of flow of demand d and the flow is allocated in a sequence of steps. Using the notation introduced in section V-B, we have:

Ω(i, d, j) = φ(i, d, j)S + e∈E C e ω e (i, d, j) =φ(i, d, j -1)(S + cs k ) + e∈E C e ω e (i, d, j -1) + c e∈E α p edk ω e (i, d, j -1) + α b edk ϑ d ω e (i, d, j -1).
Using the fact that s k = e∈E (α p edk ξ p e + α b edk ξ b e ϑ d ), we get:

Ω(i, d, j) = Ω(i, d, j -1) + cζ k(i,d,j) (i, d, j -1) ≤ Ω(i, d, j -1) + 2 cζ k * (i,d,j) (i, d, j -1) (15)
Assume that there are J = J(i, d) steps executed in iteration d in phase i. Adding the inequalities in (15) for demand d of phase i and noting that

ζ k * (i,d,j) (i, d, j -1) ≤ ζ k * (i,d,j) (i, d, J), we get Ω(i, d, J) ≤ Ω(i, d, 0) + 2 h d ζ k * (i,d,j) (i, d, J).
Adding the above inequalities over all demands in phase i, and using the fact that weights are monotonically increasing over iterations, we get Ω(i) ≤ Ω(i -1) + 2 Γ(i).

where Ω(i, D) = Ω(i). Since Ω(i) Γ(i) ≥ ψ, we have

Ω(i) ≤ Ω(i -1) 1 -2 ψ
and with Ω(0) = δ(E + 1), we have for i ≥ 1

Ω(i) ≤ δ(E + 1) (1 -2 ψ ) i = δ(E + 1) 1 -2 ψ (1 + 2 ψ -2 ) i-1 ≤ δ(E + 1) 1 -2 ψ e 2 (i-1) ψ-2 ≤ δ(E + 1) 1 -2 e 2 (i-1) ψ(1-2 )
where we assume that ψ ≥ 1 in the last inequality. At phase t, we get Ω(t) ≥ 1 and the procedure stops. Therefore, .

B. Proof of Lemma 2

Considering edge e and associated weight ω e . The value of ω e is updated when flow is allocated on edge e. Particularly, this is done when e belongs to the active or backup set of links of a chosen structure. In either cases, ω e is updated by a factor of at most 1+ . Let the sequence of flow allocation that require an update of ω e be ∆ 1 , ∆ 2 , . . . , ∆ l . Let l i=1 ∆ i = κC e , i.e. the total flow allocated to edge e exceeds its capacity by a factor of κ. Scaling t-1 (the allocated portion at the end of the algorithm) by κ lead to a feasible solution (satisfying capacity constraints). Since the algorithm terminates when Ω(t) ≥ 1, we have Ω(t -1, D, J) < 1 and Ω(t, D) < 1 + . Therefore, we have C e ω e (t -1, D, J) < 1 and

ω e (t -1, D, J) = δ C e l i=1
(1 + ∆ i c e ).

Knowing that (1+ax) ≥ (1+x) a , ∀x ≥ 0 and any 0 ≤ a ≤ 1, we get Therefore κ < log 1+ 1 δ and scaling t -1 by κ gives the result in the lemma. For scaling the computed value of the total cost s, the proof follows the same sketch as the one provided for λ. Note that φ(t -1, D, J) < 1/S, φ(1, 0, 0) = δ/S and that every time we allocate a flow whose total cost is S, we increase φ by a factor of 1 + .

C. Proof of Theorem 2

Let η be the ratio of the values of the optimum dual and primal solutions. Then, η verifies

η < ψ t -1 log 1+ ( 1 δ ).
By substituting the bound value given by Lemma1, we get

η ≤ 2 (1 -2 ) ln 1-2 δ(E+1) log 1+ ( 1 δ )
For δ = ( E+1 1-2 ) -1/ , we obtain

η ≤ 2 (1 -)(1 -2 ) ln(1 + ) ≤ 2(1 -2 ) -3 .
Therefore, choosing = 1-ρ 1 3

2

will lead to a ρ/2approximation algorithm with 0 < ρ < 1. By weak duality we have

1 ≤ η ≤ ψ t -1 log 1+ ( 1 δ )
hence the number of phases, t, is strictly less than 1 + ψ log 1+ ( 1 δ ) which implies that t = ψ log 1+ E+1 1-2 . Following the analysis provided in [START_REF] Garg | Faster and simpler algorithms for multicommodity flow and other fractional packing problems[END_REF], we can scale the capacities so that ψ ≥ 1 and the total number of phases is T log D (refer to [START_REF] Lahoud | Survivable routing and flow allocation in next generation internet networks[END_REF] for more details). Moreover, in each step, except the last step in an iteration, we increase either the weight of some edge or the value of φ by a factor 1 + . Hence, the weights of the edges and φ can be increased by a factor 1 + at most log 1+ 1+ δ times. Therefore the number of steps exceeds the number of iterations by at most (E + 1) 1 log 1+ E+1 1-2 .

V

  set of vertices E set of undirected links D set of demands K d set of cycles realizing demand d Ce capacity of link e h d volume of demand d ϑ d partial protection ratio for demand d ξ p e unitary cost for allocating primary flow over link e ξ b e unitary cost for allocating backup flow over link e α p edk binary constant that equals 1 if link e belongs to the primary path of cycle k; 0, otherwise α b edk binary constant that equals 1 if link e belongs to the backup path of cycle k; 0, otherwise f dk flow allocated to cycle k realizing demand d TABLE I

LP 1

 1 MCost problem Minmize d∈D k∈K d e∈E (α p edk ξ p e + α b edk ξ b e ϑ d )f dk (1)

Theorem 1 :

 1 Algorithm 1 computes a 2-approximation for the minimum weight cycle problem with ordered dual weights. Proof: Let k * denote the minimum cycle realizing demand d and let ζ k * be its weight, given by ζ k * = e∈E α p edk * ω p e + α b edk * ω b e = ω p * + ω b * , where ω p * (respectively ω b * ) denotes the weight of the primary path (respectively, the backup path) of the minimum weight cycle. According to Algorithm 1, p is the minimum weight path realizing demand d, with respect to weights ω p e . Therefore, the weight of path p, denoted by ω p , verifies ω p ≤ ω p * ≤ ζ k * . Moreover, considering the algorithm in [10]: the aim of the second step is to compute a minimum cost path on the residual graph (obtained by removing the forward edges on path p). This is a minimum cost flow problem and any cycle is a feasible solution to this problem. Particularly, k * is a feasible solution, which gives us ω q ≤ e∈E (α p edk * + α b edk * )ω b e ≤ e∈E α p edk * ω p e + α b edk * ω b e (using the assumption that ω b e ≤ ω p e , ∀e ∈ E).

Fig. 1 .

 1 Fig. 1. Examples of survivable structures

Lemma 2 : 3 :Theorem 2 : 2 )

 2322 At the end of Algorithm 2, λ = t-1 log 1+ ( 1 δ ) yields a feasible primal solution. Lemma At the end of Algorithm 2, S = s log 1+ ( 1 δ ) is the cost of the feasible primal solution. Assuming that 0 < ρ < 1, = 1-ρ -1/ , Algorithm 2 computes a ρ/2-approximation to the MCost-MCF problem in time O (2D log D + E + 1) 1 log 1+ E+1 1-2

Fig. 3 .

 3 Fig. 2. Cost evolution

Fig. 4 .

 4 Fig. 4. Time performance

1

  > C e ω e (t -1, D, J) ≥ δ

  t d ), {ω p e , ∀e ∈ E} and {ω b e , ∀e ∈ E} output : approximate minimum weight structure k ∈ K d assume : ω p e ≥ ω b e , ∀e ∈ E foreach e ∈ E do assign a weight ω p e ; p ← shortest path realizing demand d; foreach e ∈ p do