Maha Driss
email: maha.driss@irisa.frjezequel@irisa.fr

Yassine Jamoussi
email: yassine.jamoussi@ensi.rnu.tnhenda.benghezala@ensi.rnu.tn

Jean-Marc Jézéquel

Henda Hajjami

Ben Ghézala

A Discrete-Events Simulation Approach for Evaluation of Service-Based Applications

One of the promises of the Service-Oriented Architecture (SOA) is to build complex added-value services in order to enhance and extend existing ones. Service-Based Applications (SBAs) are asked not only to perform required functionalities, but also to deliver expected level of Quality of Service (QoS). Dealing with QoS management of such distributed applications, which are executed in dynamic environments, raises the need to consider context characteristics. This paper proposes a discrete-events simulation approach which assures the evaluation of SBAs performance under different context status. The main contributions of this paper are: (i) the discrete-events modeling approach for SBAs, (ii) the context-based model for SBAs considered in the discrete-events simulation model, and (iii) the evaluation of a set of QoS metrics by simulation.

Introduction

Web services (WSs) have emerged as a major technology for deploying automated interactions between heterogeneous systems. They are based on a collection of standards and protocols that allow processing requests to remote systems by speaking a common, non-proprietary language and using common transport protocols. WSs are becoming a popular vehicle for organizations that need to integrate their applications within and across organizational boundaries. The process-based composition of WSs is gaining a considerable momentum as an approach for the effective integration of distributed, heterogeneous, and autonomous applications [START_REF] Zeng | Qos-aware middleware for web services composition[END_REF]. One of the major requirements for such Service-Based Applications (SBAs) is the Quality of Service (QoS). QoS for WSs refers to various non-functional characteristics such as response time, throughput, availability and security [START_REF] Menascé | Qos issues in web services[END_REF]. Since many WSs provide overlapping or identical functionality, different WS processes can be composed satisfying the same user requirement. A choice needs to be made to determine which process is to use to provide the more beneficial QoS. Also, providing the acceptable QoS is really a challenging task due to the dynamic and unpredictable nature of the execution environment (e.g. network resources, devices characteristics, etc.) [START_REF] Mani | Understanding quality of service for web services[END_REF]. The above factors will force service providers to understand and analyze WSs QoS in order to achieve the fulfilment of quality guarantees. Different analytical quality assurance techniques are proposed. The goal of these techniques is to evaluate QoS and to uncover faults in the composed applications after they have been created. An example for analytical quality assurance techniques is simulation. The goal of the simulation is to emulate the conversational behavior of atomic WSs participating in the composition. In this paper, we adopt a discrete-events simulation to test and verify WS compositions. We introduce a modeling approach for SBAs. This approach enables analytical description of SBAs and allows QoS predictions in different status and conditions of the execution context. We define a lightweight quality model for WSs focusing on essential properties of QoS that play a critical role for the effective management of WSs and that can be measured by simulation technique. We propose also a context model that supports explicit description of the execution environment of tested SBAs. This model is depicted into the simulation model in order to provide a context-based approach for evaluating SBAs. The rest of the paper is organized as follows. Section 2 reviews related work. In Section 3, simulation issues are addressed. We describe, in Section 4, the proposed context model. In Section 5, we introduce our quality model and explain metrics used to measure considered QoS properties. Section 6 describes a case study. Finally, Section 7 provides conclusions and outlines future works.

Sixth European

Related Work

To achieve the desired quality of an SBA, different analytical quality assurance techniques can be employed. The goal of these techniques is to evaluate QoS and to uncover faults in the SBA after it has been created. Among these techniques, we distinguish testing approach. The goal of testing is to (systematically) execute SBA with concrete inputs and to observe the produced outputs. Analyzing observed outputs allows determining and evaluating specific QoS properties. In this work, we adopt simulation as a testing technique for analyzing the efficiency of SBAs. Simulation allows us to predict system performance in different status and load conditions of the execution environment. The predicted results are used to provide feedback on the efficiency of the system. Simulating Web processes for performance evaluation is a research area with little previous work. Works in simulation that are the closest to ours are described by [START_REF] Narayanan | Simulation, verification and automated composition of web services[END_REF] [3] [START_REF] Mancini | A simulation-based framework for autonomic web services[END_REF]. [START_REF] Narayanan | Simulation, verification and automated composition of web services[END_REF] proposes a model-theoretic semantics as well as distributed operational semantics that can be used for simulation, validation, verification, automated composition and enactment of DAML-S-described SBAs. To provide a fully service description, Narayanan and McIlraith use the machinery of situation calculus and its execution behaviour described with Petri Nets. They use the simulation and modeling environment KarmaSIM to translate DAML-S markups to situation calculus and Petri Nets. The KarmaSIM tool allows for interactive simulation and supports various verification and analysis techniques to test functional correctness as well as quality performances. In this work, three verification problems are simulated and analyzed: reachability, liveness and existence of deadlocks. Use of simulation for WSs is described also in [START_REF] Chandrasekaran | Performance analysis and simulation of composite web services[END_REF]. This work focused on problems related to SBA specification, evaluation and execution using Service Composition and Execution Tool (SCET). SCET allows to compose statically a WS process with WSFL and to generate simulation model that can be processed by the JSIM simulation environment. JSIM is a Java-based simulation and animation environment that contains several features to support simulation of WS processes. After its simulation run, JSIM generates statistical information about the completed simulation. This statistical information provides feedback on the process performance. In this work, Chandrasekaran et al. have enhanced WSFL to include QoS estimates (e.g. execution time, cost and reliability) obtained by performing simulation tests. SCET manages also WS process execution; it is capable of automatically generate Perl executable code from WSFL based process description. In [START_REF] Silver | Modeling and simulation of quality of service for composite web services[END_REF], SCET was integrated with METEOR-S system [START_REF] Aggarwal | Constraint driven web service composition in meteor-s[END_REF] in order to validate the QoS model developed by Cardoso et al. [START_REF] Cardoso | Quality of service and semantic composition of workflows[END_REF]. Only the QoS response time dimension is supported by the implementation of JSIM in both works [3] [11]. In contrast to our approach, both [START_REF] Narayanan | Simulation, verification and automated composition of web services[END_REF] [3] don't consider execution environment information in simulation model. [START_REF] Mancini | A simulation-based framework for autonomic web services[END_REF] presents a framework, named MAWeS (MetaPL/HeSSE Autonomic Web Services) whose aim is to support the development of self-optimizing predictive autonomic systems for WS architectures. It adopts a simulation-based methodology, which allows predicting system QoS in different status and load conditions. MAWeS integrated the simulation tool HeSSE. HeSSE allows the user to simulate the performance behavior of a wide range of distributed systems for a given application, under different computing and network load conditions. MetaPL is an XML-based metalanguage for parallel programs description. Starting from a MetaPL program description, a set of filters produce different program views, among which are the trace files that can be used to feed the HeSSE simulation engine. HeSSE and MetaPL allow users to perform SBA QoS optimization, without actual execution of the application on the target environment. In contrast to [START_REF] Narayanan | Simulation, verification and automated composition of web services[END_REF] [3], this work considers execution environment information in simulation model. This work adds autonomic behavior to WSs, but it proposes only one possible optimization target that is response time minimization. Enhancement of MaWeS implementation is needed to add more optimization rules for QoS parameters. The contributions of this work on this topic are complementary to ours, insofar as they do not deal with QoS evaluation.

Discrete-events simulation modeling

Simulation is an important testing technique, as it allows users to tune and to evaluate different WS composition processes that provide identical functionality without experiencing the cost of enacting them. In this work, we propose an SBA modeling approach that is oriented towards performance evaluation through discrete-events simulation. To elaborate our simulation model for SBAs, we are based on the work presented in [START_REF] Nikolaidou | An applicationoriented approach for distributed system modeling and simulation[END_REF] that focus on modeling distributed applications. Discrete-events simulation is frequently used to analyze and predict the performance of real word systems. In discreteevents simulation, a system is represented as a collection of entities that interact over time by exchanging events. Given the evolution of the operation of a system, we can analyze its behavior and evaluate appropriate quality measures.

We model an SBA as a combination of two types of entities: distributed application and network infrastructure entities. Our simulation model is shown in Figure 1. Each process is executed on a processing node. Processing action indicates invocation of the processing unit of the corresponding node and is characterized by the amount of data to be processed. According to the SOA, communication between processes is performed through exchanging SOAP messages. Request action indicates invocation of a server process and is characterized by the name of the server, the name of the WS, its invoked interface and the required inputs. Forking processes are modeled as a parallel execution of multiple requests. There are two actions available for data storing, read and write, which are characterized by the amount of data stored and retrieved, respectively, and the server invoked. Transfer action is used to indicate SOAP messages exchange between processes. Synchronize action is needed since replication of processes and data is a common practice in such distributed applications. Synchronize action parameters include the process replicas that must be synchronized and the amount of data transferred.

In the proposed modeling scheme, the network infrastructure is considered as a collection of internetworks, exchanging messages through relay nodes (active communication devices e.g. routers). Communication element entity represents protocol suites (i.e. routing protocols (OSI layers 2 and 3) and peer-to-peer protocols (OSI layers 4-7)).

We have conducted simulation experiments using NS-2 simulator [START_REF] Fall | The ns manual[END_REF]. NS-2 is a discrete-events simulator; its code is written in C++ with an OTcl interpreter as a front end. NS-2 is targeted at networking research. It provides substantial support for simulation of TCP, routing, and multicast protocols over wired and wireless networks. The main advantages of such an object-oriented simulator are reusability and easy maintenance. To support SBA simulation, we have extended the C++ class hierarchy in order to implement HTTP, SMTP and SOAP protocols.

Context model

By the term "context", we mean "information utilised by the web service to adjust execution and output to provide the client with a customised and personalised behaviour" [START_REF] Keidl | Towards context-aware adaptable web services[END_REF]. Since SBAs are operating in dynamic environments, variations of execution context lead to variations in QoS expectations. In this work, we propose a context-based approach for evaluating SBAs performances. We consider a context model, described in Figure 2, which consists of a set of elements grouped in 2 axes. • Computing context: describes network connectivity (e.g. Internet connexion, locality, bandwidth, etc.) and devices capabilities (e.g. memory capacity, CPU speed, etc.).

Context information is described in the simulation model. Context changes are modeled as discrete events.

QoS model

In this approach, we define a light-weight quality model focusing on essential properties of QoS that play critical role for the effective management of WSs and that can be measured by simulation technique. The QoS properties detailed above are defined in the context of elementary WSs. They are also used to evaluate the QoS of composite WSs. We use the QoS computation model described by Cardoso et al. [START_REF] Cardoso | Quality of service and semantic composition of workflows[END_REF] to provide aggregation functions for computing the QoS of composite WSs.

• Response Time: it corresponds to the total time needed by a WS to transform a set of inputs into outputs. Response Time (RT) for a service (s) can be computed as follows:

RT(s) = ST(s) + DT(s) -Service Time (ST) is the time that the WS takes to perform its task.

-Delay Time (DT) is the time taken to send/receive SOAP messages.

• Reliability: it corresponds to the likelihood that the service will perform for its users on demand. Reliability (R) of a service (s) is function of the Failure Rate (FR): • Scalability: it computes service's capacity to manage loads. To test the scalability of a WS, we conducted the simulation while changing the number of concurrent clients.

Case Study

In this section, we describe two WS processes which provide the same required functionality. We use our simulation approach to evaluate each of these processes. We propose a validation method that help user to choose the appropriate process that fit the best to his preferences and his execution environment. Both WS Process 1 and 2 (WSP1, WSP2), described in Figure 3 and Figure 4, ensure on-line books acquisition. WSP1 begins by invoking FindISBN (FI) service. This service allows the customer to find the ISBN code of the wanted book. The price of this book is retrieved using the BarnesGetPrice (BGP) service. The user's account is then checked for sufficient funds using the CheckCredit (CCr) service. If the user has sufficient credit, the CheckInventory (CI) service is invoked; otherwise, the SendCreditLowInfo (SCLI) service is invoked. If the CheckInventory Web service returns true the ReleaseOrder (RO) service is invoked in order to send the book; otherwise, the GenerateBackOrder (GBO) service is invoked. In WSP2, the customer begins also by searching ISBN code of the book that he wants to buy. The FindLowest-Fare (FLF) service allows him to find the cheapest bookstore. The user's credit card is then checked by CreditCard-Validator (CCV) service. If the user has sufficient credit, ChargeCard (CC), DispatchBook (DB) and SendConfirma-tionSMS (SCS) are invoked. Otherwise, InsufficientCred-itSMS (ICS) is executed in order to inform customer of his insufficient credit. Figure 5 shows the execution context of the user. • Network: topology: Client is connected to an Internet Server Provider (ISP), which is in its turn connected to Server through two Routers (R1) and (R2).

-Link Client ISP: throughput: 56KB/s, delay: 50ms.

-Link ISPs R1: throughput: 1.54MB/s, delay: 25ms. -Link R1 R2: throughput: 10MB/s, delay: 35ms.

-Link R2 Server: throughput: 512KB/s, delay: 50ms. The configuration of the simulation platform is four Pentium IV-based Windows 2000 systems. For each QoS property, we performed a set of simulation experiments, and we have considered the average value. Simulation results in Figure 6 show that WSP1 is more reliable, available, and scalable than WSP2, but WSP2 is faster than WSP1.

Figure 6. Simulation results

To validate these results in order to help the user to choose the appropriate WS process, we use a Benefit Function (BF). BF is computed as follows:

BF = i=1 n d i * w i with i=1 n w i = 1
Where d i is a normalized value of a QoS dimension d i and w i denotes the client's assigned relative importance to the dimension. As dimensions can be of different units (e.g., response time is in second and availability in percentage), in order to allow for a uniform measurement of WS QoS independent of units, data normalization is applied, which essentially transforms values of different units into comparable ones. By considering a 75% confidence interval, the dimensions that are stronger with larger values (e.g., reliability, availability and scalability) are normalized according to the following equation:

f (n) = ⎧ ⎨ ⎩ d i = 1 if d i -m(d) > 2 * δ(d) d i = 0 if d i -m(d) < 2 * δ(d) d i = di-m(d)
4 * δ(d) + 0.5 otherwise While for QoS dimensions that are stronger with smaller values (e.g., response time), they are normalized according to the following equation so that smaller values contribute more to the user benefit: 2.

f (n) = ⎧ ⎨ ⎩ d i = 0 if d i -m(d) > 2 * δ(d) d i = 1 if d i -m (

Table 2. Validation results

WSP1 WSP2 BF 0.33 0.228

This validation proves that WSP1 is more appropriate for user's expectations than the WSP2 is.

Conclusion

In this work, we adopt a discrete-events simulation approach to evaluate QoS of SBAs. We present a simulation modeling approach. This approach enables analytical description of SBAs and allows QoS predictions in different status and conditions of the execution context. We define a light-weight quality model considering a set of QoS properties that can be measured by simulation technique. We propose also a context model that describes execution environment and user's preferences. This model is depicted into the simulation model in order to provide a context-based approach for evaluating SBAs. To show the effectiveness of our approach, we have conducted a set of simulation experiments in order to evaluate and to validate two WS processes that provide the same required functionality. Future work is devoted to extend both our context and QoS model and to perform extensive experiments to evaluate more complex composite WSs.

  Conference on Web Services 978-0-7695-3399-5/08 $25.00 © 2008 IEEE DOI 10.1109/ECOWS.2008.19

Figure 1 .

 1 Figure 1. Simulation model for SBAs

Figure 2 .

 2 Figure 2. Context model

R

  (s) = (1-FR(s))*100 -FR= successful executions/scheduled executions • Availability: it refers to the rate of Service Activity (SA). Availability (A), during a time Interval (I), for a service (s) corresponds to: A(s) = SA(s)/I

Figure 3 .Figure 4 .

 34 Figure 3. Activity diagram of WSP1

Figure 5 .

 5 Figure 5. Context scenario

  d) < 2 * δ(d) d i = 0.5 -di-m(d) 4 * δ(d) otherwise where d i is the value of dimension d for the service instance i, and m(d) and δ(d) are the mean and standard deviation values for dimension d respectively. Validation of WSP1 and WSP2 has given the results shown in Table

Table 1

 1

	illustrates user's preferences. For each QoS prop-erty i, user attribute a weight w i (0≤w i ≤1 and i=1 n w i = 1).

Table 1 . User's QoS preferences QoS property Weight

 1

	Response Time	0.35
	Reliabiliy	0.3
	Availability	0.2
	Scalability	0.15


Stéphane Gosselin
email: stephane.gosselin@liris.cnrs.fr

Guillaume Damiand
email: guillaume.damiand@liris.cnrs.fr

Christine Solnon
email: christine.solnon@liris.cnrs.fr

Signatures of combinatorial maps

Keywords: Combinatorial map, canonical representation, signature, linear isomorphism

Motivations

Combinatorial maps are good data structures for modelling space subdivisions. First defined in 2D [START_REF] Edmonds | A combinatorial representation for polyhedral surfaces[END_REF][START_REF] Tutte | A census of planar maps[END_REF][START_REF] Jacques | Constellations et graphes topologiques[END_REF][START_REF] Cori | Un code pour les graphes planaires et ses applications[END_REF], they have been extended to nD [START_REF] Brisson | Representing geometric structures in d dimensions: topology and order[END_REF][START_REF] Lienhardt | Subdivision of n-dimensional spaces and n-dimensional generalized maps[END_REF][START_REF] Lienhardt | Topological models for boundary representation: a comparison with n-dimensional generalized maps[END_REF] and model the subdivision cells and their adjacency relations in any dimension.

There are many different data structures for modelling the partition in regions of an image. All these structures are more or less derived from Region Adjacency Graphs (RAG) [START_REF] Rosenfeld | Adjacency in digital pictures[END_REF]. It has been shown that using combinatorial maps allows a precise description of the topology of the image partition (for example in 2D [START_REF] Braquelaire | Image segmentation with topological maps and inter-pixel representation[END_REF] or in 3D [START_REF] Damiand | Topological model for 3d image representation: Definition and incremental extraction algorithm[END_REF]) and there are efficient image processing algorithms using this topological information .

Our general goal is to define new algorithms for combinatorial maps allowing new and efficient image processing algorithms. Among these operations, we are interested in image classification. In particular, we propose to characterize image classes by extracting patterns which occur frequently in these classes. When modelling images with combinatorial maps, this involves finding frequent submaps. Finding frequent patterns in large databases is a classical data mining problem, the tractability of which highly depends on the existency of efficient algorithms for deciding if two patterns are actually different or if they are two occurrences of a same object. Hence, if finding frequent subgraphs is intractable in the general case, it may be solved in incremental polynomial time when considering classes of graphs for which subgraph isomorphism may be solved in polynomial time, such as trees or outerplanar graphs [START_REF] Horvath | Frequent subgraph mining in outerplanar graphs[END_REF].

⋆ The authors acknowledge an Anr grant Blanc 07-1 184534: this work was done in the context of project Sattic. In this paper, we address the problem of computing a canonical representation of combinatorial maps which may be used to efficiently search a map in a database. This work may be related to [START_REF] Jiang | Optimal quadratic-time isomorphism of ordered graphs[END_REF], which proposes a polynomial algorithm for deciding of the isomorphism of ordered graphs, based on a vertex labelling. Recently, this work has been extended to deal with combinatorial maps by proposing a polynomial algorithm for map and submap isomorphism based on a traversal of the map [START_REF] Damiand | Polynomial Algorithm for Submap Isomorphism: Application to searching patterns in images[END_REF]. We use these principles of labelling and traversal to define canonical representations of combinatorial maps.

More precisely, we define two map signatures. Both signatures may be computed in quadratic time with respect to the number of darts of the map. The first signature is a lexicographic tree and has a quadratic space complexity. It allows one to decide in linear time if a new map is isomorphic to a map described by this signature. The second signature is a word and has a linear space complexity. As a counterpart, isomorphism with a new map becomes quadratic.

Notions of combinatorial maps are introduced in section 2. Section 3 presents an algorithm for labelling maps. Two signatures for connected maps are defined in section 4 and section 5. These signatures are extended to non connected maps in section 6. Finally, we experimentally evaluate our work in section 7.

Recalls on Combinatorial Maps

Definition 1 (Combinatorial map [START_REF] Lienhardt | Topological models for boundary representation: a comparison with n-dimensional generalized maps[END_REF]). An nD combinatorial map, (or nmap) is defined by a tuple M = (D, β 1 , . . . , β n ) where -D is a finite set of darts; -β 1 is a permutation on D, i.e., a one-to-one mapping from D to D; -∀ 2 ≤ i ≤ n, β i is an involution on D, i.e., a one-to-one mapping from D to D such that

β i = β -1 i ; -∀ 1 ≤ i ≤ n -2, ∀ i + 2 ≤ j ≤ n, β i • β j is an involution on D.
We note β 0 for β -1

1 . Two darts i and j such that i = β k (j) are said to be k-sewn. Fig. 1 gives an example of a 2D combinatorial map.

In some cases, it may be useful to allow some β i to be partially defined, thus leading to open combinatorial maps. The basic idea is to add a new element ǫ to the set of darts, and to allow darts to be i-sewn with ǫ. By definition, ∀0 ≤ i ≤ n, β i (ǫ) = ǫ. Fig. 2 gives an example of open map (see [START_REF] Poudret | Cartes combinatoires ouvertes[END_REF] for precise definitions).

Lienhardt has defined isomorphism between two combinatorial maps as follows.

Definition 2 (Map isomorphism [START_REF] Lienhardt | N-dimensional generalized combinatorial maps and cellular quasimanifolds[END_REF]). Two maps M = (D, β 1 , . . . , β n ) and M ′ = (D ′ , β ′ 1 , . . . , β ′ n ) are isomorphic if there exists a one-to-one mapping

f : D → D ′ , called isomorphism function, such that ∀d ∈ D, ∀i, 1 ≤ i ≤ n f (β i (d)) = β ′ i (f (d))
. This definition has been extended to open maps in [START_REF] Damiand | Polynomial Algorithm for Submap Isomorphism: Application to searching patterns in images[END_REF] by adding that f (ǫ) = ǫ, thus enforcing that, when a dart is i-sewn with ǫ, then the dart matched to it by f is i-sewn with ǫ.

Finally, Def. 3 states that a map is connected if there is a path of sewn darts between every pair of darts.

Map Labelling

Our signatures are based on map labellings, which associate a different label with every different dart. By definition, the label associated with ǫ is 0. Definition 4 (Labelling). Given a map M = (D, β 1 , . . . , β n ) a labelling of M is a bijective function l : D ∪ {ǫ} → {0, . . . , |D|} such that l(ǫ) = 0.

Example 1. l = {ǫ : 0, a : 3, b : 1, c : 5 , d : 7, e : 2, f : 6, g : 4} is a labelling of the map displayed in Fig. 2.

One may compute a labelling of a map by performing a map traversal and labelling darts with respect to the order of their discovery. Different labellings may be computed, depending on (i) the initial dart from which the traversal is started, (ii) the strategy used for memorizing the darts that have been discovered but that have not yet been used to discover new darts (e.g., FIFO or LIFO), and (iii) the order in which the β i functions are used to discover new darts.

We define below the labelling corresponding to a breadth first traversal of a map where β i functions are used in increasing order.

Algorithm 1: BF L(M, d)

Input: an open connected map M = (D, β1, . . . , βn), and a dart d ∈ D Output: a labelling l : Proof. Proof. The while loop (line 7-13) is iterated |D| times as (i) exactly one dart d is removed from the queue at each iteration; and (ii) each dart d ∈ D enters the queue exactly once. The for loop (lines 9-13) is iterated n + 1 times.

D ∪ {ǫ} → {0, . . . , |D|} for each d ′ ∈ D do l(d ′ ) ← -1 1 l(ǫ) ← 0 2 let Q be an empty queue 3 add d at the end of Q 4 l(d) ← 1 5 nextLabel ← 2 6 while Q is not empty do 7 remove d ′ from the head of Q 8 for i in 0 . . . n do 9 if l(βi(d ′ )) = -1 then 10 l(βi(d ′ )) ← nextLabel 11 nextLabel ← nextLabel + 1
-l(ǫ) is set to 0 in line 2. -∀d, d ′ ∈ D, d = d ′ ⇒ l(d) = l(d ′ ). Indeed, each time a label is assigned to a dart (line 11), nextLabel is incremented (line 12). -∀d ∈ D, 1 ≤ l(d) ≤ |D|. Indeed,

⊓ ⊔

Given a map M and a labelling l, one may describe M (i.e., its functions β 1 to β n ) by a sequence of labels of l. The idea is to first list the n labels of the n darts which are i-sewn with the dart labelled by 1 (i.e., l(β 1 (1)), . . . , l(β n (1))), and then by 2 (i.e., l(β 1 (2)), . . . , l(β n (2))), etc. More formally, we define the word associated with a map and a labelling as follows.

Definition 6 (Word). Given a connected map M = (D, β 1 , . . . , β n ) and a labelling l : D ∪ {ǫ} → {0, . . . , |D|} the word associated with (M, l) is the sequence

W (M, l) =< w 1 , . . . , w n•|D| > such that ∀i ∈ {1, . . . , n}, ∀k ∈ {1, . . . , |D|}, w i•k = l(β i (d k )) where d k is the dart labelled with k, i.e., d k = l -1 (k).
Algorithm. Given a map M = (D, β 1 , . . . , β n ) and a labelling l, the word W (M, l) is computed by considering every dart of D in increasing label order and enumerating the labels of its n i-sewn darts. This is done in O(n • |D|).

Notation. The word associated with the breadth first labelling of a map M , starting from a dart d, is denoted by

W BF L (M, d), i.e., W BF L (M, d) = W (M, BF L(M, d))
Example 3. The words associated with the map of Fig. 2 for the two labellings of example 2 respectively are W BF L (M, a) =< 3, 0, 1, 0, 4, 0, 2, 5, 7, 4, 5, 0, 6, 0 > W BF L (M, e) =< 3, 4, 1, 0, 2, 0, 6, 1, 4, 0, 7, 0, 5, 0 >

The key point which allows us to use words for building signatures is that two maps are isomorphic if and only if they share a word for a breadth first labelling, as stated in theorem 1.

Theorem 1. Two connected maps M = (D, β 1 , . . . , β n ) and M ′ = (D ′ , β ′ 1 , . . . , β ′ n ) are isomorphic iff there exist d ∈ D and d ′ ∈ D ′ such that W BF L (M, d) = W BF L (M ′ , d ′ ) Proof. ⇒ Let us first consider two isomorphic maps M = (D, β 1 , . . . , β n ) and M ′ = (D ′ , β ′ 1 , . . . , β ′ n )
, and let us show that there exist two darts d and

d ′ such that W BF L (M, d) = W BF L (M ′ , d ′ ). If M and M ′ are isomorphic then there exists f : D → D ′ such that ∀d ∈ D, ∀i ∈ {1, . . . , n}, f (β i (d)) = β ′ i (f (d))
. Let d 1 be a dart of D, and let us note l (resp. l ′ ) the labellings returned by BF L(M, d 1 ) (resp. BF L(M ′ , f (d 1 ))). Claim 1: l and l ′ are such that ∀d i ∈ D, l(d i ) = l ′ (f (d i )). This is true for the initial dart d 1 as both d 1 and f (d 1 ) are labelled with 1 at the beginning of each traversal. This is true for every other dart d i ∈ D as the traversals of M and M ′ performed by BF L are completely determined by the fact that (i) they consider the same FIFO strategy to select the next labelled dart which will be used to discover new darts and (ii) they use the β i functions in the same order to discover new darts from a selected labelled dart. Claim 2: ∀k ∈ {1, . . . , |D|}, f (l -1 (k)) = l ′-1 (k). This is a direct consequence of Claim 1. Conclusion: ∀i ∈ {1, . . . , n}, ∀k ∈ {1, . . . , |D|}, the i.k th element of

W BF L (M, d 1 ) is equal to the i.k th element of W ′ BF L (M ′ , f (d 1 )), i.e., l(β i (l -1 (k))) = l ′ (β ′ i (l ′ -1(k))). Indeed, l(β i (l -1 (k))) = l ′ (f (β i (l -1 (k)))) (because of Claim 1) = l ′ (β ′ i (f (l -1 (k)))) (because f is an isomorphism function) = l ′ (β ′ i (l ′-1 (k))) (
(d j ) = l ′-1 (l(d k )). Note that this implies as well that l(d j ) = l ′ (f (d j )). Claim 3: ∀i ∈ {1, . . . , n}, ∀k ∈ {1, . . . , |D|}, l(β i (l -1 (k))) = l ′ (β ′ i (l ′ -1(k))). This comes from the fact that W BF L (M, d) = W BF L (M ′ , d ′ ) so that the i.k th element of W BF L (M, d 1 ) is equal to the i.k th element of W ′ BF L (M ′ , f (d 1 )). Conclusion: ∀i ∈ {1, . . . , n}, ∀d j ∈ D, f (β i (d j )) = l ′-1 (l(β i (d j ))) (by definition of f ) = l ′-1 (l ′ (β ′ i (l ′-1 (l(d j ))))) (because of Claim 3) = β ′ i (l ′-1 (l(d j ))) (by simplification) = β ′ i (l ′-1 (l ′ (f (d j )))) (by definition of f ) = β ′ i (f (d j )) (by simplification)
Hence, f is an isomorphism function and M and M ′ are isomorphic. ⊓ ⊔

Set Signature of a Connected Map

A map is characterized by the set of words associated with all possible breadth first labellings. This set defines a signature. Proof. The set signature contains at most |D| words (it may contains less than |D| words in case of automorphisms). Each word contains exactly n • |D| labels. Lexicographical tree. The set signature of a map may be represented by a lexicographical tree which groups common prefixes of words. For example, the lexicographical tree of the set signature of the map displayed in Fig. 2 is displayed in Fig. 3. Proof. To decide of the isomorphism, one has to build a breadth first labelling, starting from any dart of d ∈ D, and check if W BF L (M, d) is a branch of the lexicographical tree. Note that a node of the tree may have more than one son but, as the number of branches of the tree is bounded by the number of darts, deciding if a breadth first labelling corresponds to a branch of the tree may be done in linear time.

⊓ ⊔

Word Signature of a Connected Map

The lexicographical order is a strict total order on a set signature, and we have shown that if two set signatures share one word, then they are equal. Hence, one may define a map signature by considering the smallest word of the set signature. Proof. To decide of the isomorphism, one has to build breadth first labellings, starting from every different dart of d ∈ D, and check if

W BF L (M, d) = W S(M ′ ).
In the worst case, one has to build |D| labellings so that the overall time com-

plexity is in O(n • |D| 2 ). ⊓ ⊔

Signatures of Non Connected Maps

When a map is not connected, it may be decomposed in a set of disjoint connected maps in linear time with respect to the number of darts by performing successive map traversals until all darts have been discovered. The signature of a non connected map is built from the signatures of its different connected components. Word signature. To build a signature from the word signatures of the connected components, we sort the signatures by lexicographical order to obtain a list of words.

Set signature. To build a signature from the set signatures of the connected components, we merge the lexicographical trees as displayed in Fig. 4. Each node in the merged tree corresponding to a leaf in the tree of the i th connected component is labelled by i. Note that a node in the merged tree may have several labels as some connected components may be isomorphic. Note also that labelled nodes in the merged tree may be internal nodes as a branch of the tree of a connected component may be a prefix of the branch of another tree. To decide isomorphism between a non connected map and a Set Signature, we have to compute a breadth first labelling of each connected component starting from any dart, and check that each corresponding word ends in a node of the merged tree which is labelled by a different connected component.

Experiments

Using map signatures to search images. Maps may be extracted from segmented images by using the linear algorithm described in [START_REF] Damiand | Topological model for two-dimensional image representation: definition and optimal extraction algorithm[END_REF]. We obtain the same map whatever we submit the image to a rotation or a scale-up. Hence, map signatures may be used to identify images even if they have been rotated or scaled-up. Table 1 shows 5 images and gives the number of darts and faces of maps extracted from these images, and then gives the CPU time needed to compute set and word signatures. 1. From images to signatures: the first line displays images, the next two lines give the number of darts and faces in the corresponding maps; the last two lines give the CPU time in seconds for computing the set and word signatures of these maps. Scale-up properties of signature constructions. To compare scale-up properties of set and word signatures, we have performed experiments on randomly generated maps with exponentially growing sizes (with 1000, 2000, 4000 and 8000 darts). Table 2 first compares time complexities for constructing set and word signatures. To build the set signature, one has to perform a complete breadth first traversal for each dart so that the total number of visited darts is always equal to |D| 2 and the time complexity does not depend on the initial dart chosen to start the traversal. To build a word signature, one also has to perform a breadth first traversal for each dart but each traversal may be stopped as soon as the corresponding word is greater than the smallest word computed so far. Hence, if the worst case complexity is quadratic, Table 2 shows that the CPU time needed to compute a word signature is sub quadratic in practice. Indeed, the average number of darts visited for each traversal varies from 19.48 for the map with 1000 darts to 26.91 for the map with 8000 darts. Note that, if the number of visited darts actually depends on the order in which initial darts are chosen, standard deviations are rather low.

Scale-up properties of isomorphism. We now compare set and word signatures for deciding if a new map M ′ is isomorphic to a map M described by its signature. When using the set signature SS(M ), the worst case complexity is O(n•|D|). Table 3 shows that, when M ′ and M are isomorphic (when the percentage of different darts is 0%), the algorithm visits each dart exactly once. However, when M and M ′ are not isomorphic, the breadth first traversal of M ′ may be stopped as soon as no branch of the lexicographical tree matches the word under construction. Table 3 shows that the more different M and M ′ , the smaller the number of visited darts.

When using the word signature W S(M ), the worst case complexity is O(n • |D| 2 ) as one has to perform a breadth first traversal starting from every dart of M ′ . However, one may stop each breadth first traversal as soon as the word under construction is different from the signature. Hence, Table 3 shows that the more different M and M ′ , the smaller the number of visited darts. In practice, each is isomorphic to a map M given the signature of M . M and M ′ have the same number of darts, but M ′ is obtained from M by removing and then adding a given percentage of darts. When this percentage is 0%, M and M ′ are isomorphic. Each line successively gives: the number of darts of M , the percentage of different darts between M and M ′ , and, for each signature, the time and the ratio between the number of visited darts and the number of darts of M . We give average results (and standard deviations) obtained when changing the initial dart of M ′ .

dart is visited between 2 to 4 times. Interestingly, this ratio does not significantly vary when increasing the size of the map.

Conclusion

In this paper, we have defined two signatures of combinatorial maps, corresponding to canonical representations of n-dimensional combinatorial map. The memory complexity of the first signature is quadratic, but allows one to decide isomorphism in linear time in worst case and faster in average time. The memory complexity of the second signature is linear, but the complexity of the algorithm to decide isomorphism is quadratic in worst case and linear in average case.

The results of our experiments show that the signatures can be used to characterize images. This method is resistant to rotation and scale up. Moreover, both signatures can be used to find a map in a database. The Set Signature is faster but the size of the maps can be limited due to the memory size required to store the lexicographical trees. The Word Signature solves the memory problem, but the query's runtime is longer. We need to make several experiments in order to find the good compromise depending on the needs of the applications. Now, we plan to use these signatures to compute a similarity measure between two combinatorial maps. In order to do that, we have to modify the signature so that it becomes error-tolerant. In further works, we will use those signatures to search frequent submaps in a database of maps. Our objective is to apply such method to chemical compound or to images to make a classification.

Fig. 1 .

 1 Fig. 1. Combinatorial map example. Darts are represented by numbered black segments. Two darts 1-sewn are drawn consecutively, and two darts 2-sewn are concurrently drawn and in reverse orientation, with little grey segment between the two darts.

Fig. 2 .

 2 Fig. 2. Open combinatorial map example. Darts a, b, d, f and g are not 2-sewn.

Definition 3 (

 3 Connected map). A combinatorial map M = (D, β 1 , . . . , β n ) is connected if ∀d ∈ D, ∀d ′ ∈ D, there exists a path (d 1 , . . . , d k ) such that d 1 = d, d k = d ′ and ∀1 ≤ i < k, ∃j i ∈ {0, . . . , n}, d i+1 = β ji (d i ).

12 addl 14 Definition 5 (Example 2 .

 121452 βi(d ′ ) at the end of Q 13 return Breadth first labelling (BFL)). Given a connected map M = (D, β 1 , . . . , β n ) and a dart d ∈ D the breadth first labelling associated with (M, d) is the labelling returned by the function BF L(M, d) described in algorithm 1. The breadth first labellings associated with the map of Fig. 2 for darts a and e respectively are BF L(M, a) = {ǫ : 0, a : 1, b : 3, c : 4, d : 2, e : 5, f : 7, g : 6} BF L(M, e) = {ǫ : 0, a : 7, b : 5, c : 4, d : 6, e : 1, f : 3, g : 2} Proposition 1. Algorithm 1 returns a labelling.

because of Claim 2 )⇐

 2 Let us now consider two maps M = (D, β 1 , . . . , β n ) and M ′ = (D ′ , β ′ 1 , . . . , β ′ n ) and two darts d and d ′ such that W BF L (M, d) = W BF L (M ′ , d ′ ), and let us show that M and M ′ are isomorphic. Let us note l (resp. l ′ ) the labellings returned by BF L(M, d) (resp. BF L(M ′ , d ′ )), and let us define the function f : D → D ′ which matches darts with same labels, i.e., ∀d j ∈ D, f

Definition 7 (

 7 Set Signature). Given a map M = (D, β 1 , . . . , β n ) the Set Signature associated with M is SS(M ) = {W BF L (M, d)|d ∈ D} Algorithm. SS(M ) is built by performing W BF L (M, d) for each d ∈ D and collecting all different returned words in SS(M ). Hence, the overall time complexity is O(n • |D| 2 ).

Theorem 2 .Fig. 3 .Property 1 .

 231 Fig. 3. Lexicographical tree of the set signature of the map of Fig. 2.

Property 2 .

 2 Given a map M = (D, β 1 , . . . , β n ) and the lexicographical tree of the set signature SS(M ′ ) of another map M ′ , one determine the isomorphism between M and M ′ in O(n • |D|).

Definition 8 (Property 3 .Property 4 .

 834 Word Signature). Given a map M , the Word Signature of M is, W S(M ) = w ∈ SS(M ) such that ∀w ′ ∈ SS(M ), w ≤ w ′ . Example 4. The word signature of the map displayed in Fig.2is W S(M ) =< 3, 0, 1, 0, 2, 4, 6, 3, 4, 0, 7, 0, 5, 0 > The space complexity of a word signature is O(n • |D|).Algorithm. The word signature of a map M is built by calling W BF L (M, d) for each dart d ∈ D, and keeping the smallest returned word with respect to the lexicographical order. The time complexity for computing the word signature is O(n • |D| 2 ). Note that this process may be improved (without changing the worst case complexity) by incrementally comparing the word in construction with the current smallest word and stopping the construction as soon as it becomes greater. Given a map M = (D, β 1 , . . . , β n ) and the word signature W S(M ′ ) of another map M ′ , one determine the isomorphism between M and M ′ in O(n • |D| 2 ).

Fig. 4 .

 4 Fig. 4. Example of non connected map and its Set Signature.

Table 2 .

 2 Comparison of time complexities for computing set and word signatures of a map. Each line successively gives the number of darts |D| of the map and, for each signature, the CPU time (in seconds) and the ratio between the number of visited darts and |D|. We give average results (and standard deviations) obtained with different initial darts.

		Set Signature	Word Signature
		Time Visited darts |D|	Time Visited darts |D|
	|D|	avg avg	(sdv) avg avg (sdv)
	1000 0.054 1000	(0) 0.047 19.48 (3.24)
	2000 0.228 2000	(0) 0.084 19.27 (3.71)
	4000 1.056 4000	(0) 0.262 23.78 (5.31)
	8000 4.088 8000	(0) 0.352 26.91 (4.88)

Table 3 .

 3 Comparison of scale-up properties of set and word signatures for deciding if a new map M ′

		Set Signature	Word Signature
	|D|	Time Visited darts |D|	Time Visited darts |D|
		avg avg (sdv) avg avg	(sdv)
		0% 0.000099 1.000 (0.000) 0.035 2.13	(0.64)
		1% 0.000091 0.298 (0.214) 0.060 3.71	(1.48)
	1000	10% 0.000086 0.026 (0.021) 0.059 3.41 50% 0.000072 0.015 (0.006) 0.056 1.88	(1.34) (1.19)
		99% 0.000068 0.011 (0.004) 0.050 1.59	(0.90)
		0% 0.000215 1.000 (0.000) 0.084 2.59	(1.47)
		1% 0.000161 0.069 (0.081) 0.095 3.08	(1.79)
	2000	10% 0.000130 0.019 (0.032) 0.076 2.92 50% 0.000098 0.006 (0.005) 0.073 1.77	(1.76) (1.40)
		99% 0.000097 0.006 (0.003) 0.069 1.38	(0.83)
		0% 0.000341 1.000 (0.000) 0.262 2.46	(1.30)
		1% 0.000292 0.015 (0.037) 0.434 3.09	(1.89)
	4000	10% 0.000222 0.005 (0.005) 0.329 2.57 50% 0.000178 0.005 (0.006) 0.286 2.03	(1.81) (1.41)
		99% 0.000164 0.005 (0.003) 0.273 1.43	(0.85)
		0% 0.000697 1.000 (0.000) 0.352 2.23	(1.04)
		1% 0.000556 0.032 (0.178) 1.451 3.11	(1.86)
	8000	10% 0.000439 0.003 (0.009) 1.343 3.05 50% 0.000296 0.002 (0.003) 1.042 2.44	(1.81) (1.25)
		99% 0.000353 0.003 (0.003) 0.993 1.53	(1.02)


Guillaume Vermot Des Roches

Jean-Philippe Bianchi

Etienne Balmes

Remi Lemaire

Thierry Pasquet

Using component modes in a system design process

Classically Component Mode Synthesis has been used to couple models from different sources (mixed test and analysis, different companies, different software, ...) or reduce models. The focus of this paper is on using component modes in a design cycle. Component modes are the natural representation in the lowest part design cycle. In NVH applications, it is well known that coupling at the system level makes understanding of the impact of component design changes difficult. The paper details and uses the disjoint component synthesis method. Like classical CMS this synthesis method considers reduced component models and couples these models to obtain a system level synthesis. The first novel aspect is that a physical interface is assumed to exist between components. Synthesis thus becomes a trivial application of model assembly. The second novel aspect is that components are reduced using component modes and the trace of nominal system modes, thus allowing exact predictions for the nominal design. Illustrations of the methodology are given for an automotive brake application.

INTRODUCTION

Numerical prototyping is widely used in industrial design processes to allow optimization and limit the cost of validation through experimental testing. A typical organization of the design is so called V-model shown in figure 1. In NVH applications, performance can often only be evaluated in the system verification and validation step. It is thus quite difficult to specify requirements or component level verifications. The purpose of the present work is to introduce a methodology that, given a base system model (current design), leads to a rapid iteration between component level properties and system level predictions. The existence of a base model ensures that the component coupling with its environment is appropriate and will allow system level predictions of performance. The first issue that will be addressed is to build a method that does not require computationally intensive evaluations of performance to validate the impact of component changes. The second issue is to allow the evaluation of design changes in terms of component frequencies and damping rather than detailed model geometry and properties.

To simplify the integration of components into a system model, section 1.1 introduces the idea of coupling components using physical interfaces rather than the assumption of continuity classically introduced in Component Mode Synthesis (CMS) methods [START_REF] Craig | A Review of Time-Domain and Frequency Domain Component Mode Synthesis Methods[END_REF][START_REF] De Klerk | General Framework for Dynamic Substructuring : History, Review and Classification of Techniques[END_REF] . With this disjoint component synthesis method, components have fully distinct Degrees Of Freedom (DOF) and one distinguishes component and coupling matrices. Earlier work on this approach can be found in Refs. [START_REF] Balmes | Use of generalized interface degrees of freedom in component mode synthesis[END_REF] to cope with incompatible meshes, [START_REF] Corus | Amélioration des méthodes de modification structurale par utilisation de techniques d'expansion et de réduction de modèle[END_REF] for structural dynamics modification applications, [START_REF] Roy | Damping Specification of Automotive Structural Components via Modal Projection[END_REF] for damping allocation.

As components are disjoint, their reduction is a direct application of Ritz analysis. The only requirement is to build a basis approximating the component motion. Section 1.2 shows that reduced component models can be built using the trace of system responses thus leading to coupled responses that are exact for the nominal design and very accurate otherwise. In such models, it is not necessary to represent all possible interface deformations as classically done using static interface or constraint modes [START_REF] Craig | A Review of Time-Domain and Frequency Domain Component Mode Synthesis Methods[END_REF] . In a number of cases, this results in much smaller reduced models.

Finally, using disjoint components gives a wide range of options for defining component DOF. Section 1.3 thus discusses how component free/free modes can be used as Rayleigh Ritz vectors. Component mode frequency and damping are then used as design parameters in a specification phase. The models being very small, system performance evaluations are typically very fast.

The use of the proposed methods is then illustrated in section 2 on the case of a state of the art automotive brake model.

CMS PROCEDURES FOR DESIGN 1.Coupling components with physical interfaces

Component Mode Synthesis methods [START_REF] Craig | A Review of Time-Domain and Frequency Domain Component Mode Synthesis Methods[END_REF][START_REF] De Klerk | General Framework for Dynamic Substructuring : History, Review and Classification of Techniques[END_REF] divide structures into components and generate coupled predictions by introducing assumptions on the interfaces between components. Most of the literature on CMS considers that the fundamental assumption for coupling is the fact that displacement is continuous at interfaces. The approach, considered here, assumes that the components are physically disjoint and that coupling occurs through interfaces that have a physical extent. Since the components are disjoint, the associated DOF {q ci } are always distinct. Matrices associated with full or reduced components are non zero for a single component, while interfaces can have nonzero values coupling multiple components. Their diagonal blocks are non null on interface component DOF. In the case of two components one thus has

[Z T ] = [Z el ] + [Z I ] = Z 1 0 0 Z 2 + Z I11 Z I12 Z I21 Z I22 (1)
Figure 2 shows the matrix connectivities for a sample 3 component/2 interface model. The block structure of the component and interface models is indicated through colors. In the application of section 2, the interface matrices correspond to tangent contact/friction coupling models.

{q ci } ≈ [T ci ] {q ciR } (2)
Thus yielding a reduction basis defined on the whole model

q c1 q c2 = T c1 0 0 T c2 q c1R q c2R (3)
Displacements are by nature continuous since they are defined on a single component, and system predictions are readily obtained by reducing the coupling matrices

[Z I ] ijR = [T ci ] T [Z I ] ij [T cj ] (4)
It is important to note that block size for component interface is equal to the number of vectors (2). The number of interface DOF between components thus has no effect on the reduced model size. This feature is a strong deviation from what would be obtained with classical reduction methods, such as the Craig-Bampton method [START_REF] Craig | A Review of Time-Domain and Frequency Domain Component Mode Synthesis Methods[END_REF] , which tend to have very high numerical costs in cases with large interfaces. In the coupling matrix reduction, accounting for block operations on components that are actually coupled often leads to major performance gains.

Reduced models with exact modes

In the proposed setting, computing the nominal model modes is considered to be straightforward. This is nowadays the case using either classical iterative method (Lanczos, Implicitly Restarted Arnoldi, ...) or automated multi-level substructuring methods [START_REF] Bennighof | Meeting the NVH Computational Challenge: Automated Multi-Level Substructuring[END_REF][START_REF] Gao | An Implementation and Evaluation of the AMLS Method for Sparse Eigenvalue Problems[END_REF] . The key point in design procedures is rather the ability to accurately perform parametric studies. It is then critical to compute the system modes several hundred times for reanalysis, which requires the use of reduced models to be performed in reasonable computation times.

In classical CMS methods [START_REF] Craig | A Review of Time-Domain and Frequency Domain Component Mode Synthesis Methods[END_REF] , one assumes component independence : the data from one component should be independent of the data from other components. While this made sense for the purpose of getting faster computations or coupling test and analysis derived models, this assumption is a poor idea in a design cycle. Indeed model precision is altered despite the fact that the nominal design gives appropriate coupling information. It is thus proposed to replace component modes by the trace of the global system modes [Φ] on each component c i

[T ci ] = Φ |ci 1:Ns Orth. (5)
The clear advantage of this reduction basis is that both reduced and full models share the same modes. Such dynamic behavior equivalence allows to retain a good accuracy for modal based computations like forced response or complex mode computation.

If multiple system configurations are of interest, one can use the trace of multiple mode sets (

Φ |ci (p 1 ) Φ |ci (p 2 ) . . . ).
Variable rotation speeds are thus considered in [START_REF] Sternchüss | Multi-level parametric reduced models of rotating bladed disk assemblies[END_REF] , where the issue of generating bases from vector sets is also addressed. Fixed basis reduction for variable configurations can be applied to all or specific components.

For compatibility with existing software, it is also possible to include static interface or constraint modes [START_REF] Craig | A Review of Time-Domain and Frequency Domain Component Mode Synthesis Methods[END_REF] . For interfaces with a large number of DOF this is however often very detrimental for the reduced model size. With the present methodology, the component model really only needs as many base vectors as there are independent shapes in the trace of system level modes (for example a very stiff component only needs 6 shapes to describe its rigid body modes).

Using component modes as DOF and design parameters

In a detailed design phase, component parameters to be optimized are known and the CMS methodology detailed above gives a rapid way to evaluate system level performance. But in a specification phase, one typically seeks to understand how the component behavior impacts system response.

The idea proposed here is to analyze the impact of changes in frequency and damping of the free/free component modes. These represent a series of simple scalar parameters and introducing detailed design changes to shift the frequency or damp specific modes is often a clear process. A similar idea with fixed interface modes is used to study mistuning of bladed disk assemblies in Ref. [START_REF] Sternchüss | Multi-level parametric reduced models of rotating bladed disk assemblies[END_REF] .

To obtain accurate predictions, one now seeks to retain exact modes for both the system and components. For each component i, one thus uses a reduction basis that combines component modes in free/free conditions [φ ci ] and the trace on the component of exact system modes Φ |ci

[T ci ] = [φ ci ] Φ |ci Orth. (6)
In practice, Φ |ci may not be orthogonal to the component free/free modes, one thus generates an orthonormal basis by some appropriate method [START_REF] Sternchüss | Multi-level parametric reduced models of rotating bladed disk assemblies[END_REF] . The component modes are kept explicitly and are not modified by the orthonormalization process since by definition they are orthonormal to start with. The difference between the subspace of system modes and the component modes is also kept with the only differences linked to numerical round off errors in the orthonormalization process.

Since the component basis is orthonormal, the reduced component mass is identity and the stiffness is diagonal with the first terms corresponding to the square of component mode pulsations. Damping is a full matrix if a damping model exists (non-proportional damping) but in a design phase it is typically assumed to be diagonal (modal damping). Parametric studies on component mode frequencies or modal damping ratio thus simply correspond to changes on the associated diagonal terms of the reduced component models. This process will be illustrated in section 2.2.

As shown in figure 3, the interface matrices are now fully populated of blocks corresponding to connected components. When the component basis contains more vectors than interface DOF with another component, specific basis reordering can significantly reduce interface coupling and thus lead to sparse reduced models. For the illustrations shown in this paper, one considers a state of the art brake model shown in figure 4. The model is an assembly of 8 components in contact with each other finely meshed to comply with the need to compute its modes up to 16kHz for squeal simulations, thus leading to the use of 600,000 DOF. Static computations of the steady state shape of the brake are performed using ABAQUS. Component and interface models are then imported into SDT [START_REF] Balmes | Structural Dynamics Toolbox 6.2 (for use with MATLAB)[END_REF] whose the superelement utilities are used to manage further computations. Figure 5 shows the relative frequency error between reduced and full system real modes. The error is within numerical precision for the whole range. The non-linearities induced by contact and friction yield system instabilities responsible in particular for brake noises (groan, moan, squeal, ...). These instabilities are non destructive and an end goal of the present work is time simulation of the full brake assembly (see [START_REF] Vermot Des Roches | Time simulation of squeal phenomena in realistic brake models[END_REF] for details).

This paper focuses on an earlier part of the design cycle, where performance is analyzed using unstable complex modes and structural modifications are tested for their impact. Section 2.2 illustrates the effectiveness of the proposed reduced model for reanalysis studies. Section 2.3 shows how component modes can be used to guide design.

Reanalysis in design phase

In a design phase, the ability to rapidly evaluate the impact of modifications is a key advantage of the proposed method. These modifications can be physical (one will consider a modulus or mass change here) or correspond to component modes (which will be illustrated in the next section). The uses of reanalysis are classically perturbation/sensitivity, uncertainty and model updating analyses. The low cost allows the evaluation for a large number of intermediate values. This makes tracking of poles practical as will be illustrated. The two examples given in this section are chosen to illustrate the robustness of the method for significant changes.

The first example shows the effect of the disc Young modulus on the global system modes. Such shift is trivial to apply to a component with an isotropic material. Since the stiffness matrix is proportional to the modulus, the impact of a modulus change is a simple multiplicative coefficient applied to the block of the reduced elastic matrix of figure 2.

Figure 6 shows the prediction accuracy for the system real modes with a +10% shift of the Young modulus. Predicted and exact frequency shifts ∆f = f nomf mod are plotted along with the shift error ∆∆f = ∆f pred -∆fcompt ∆fcompt

. The error on predicted shifts is clearly small on the whole frequency range. Figure 7 shows two complex mode prediction showing high disc participation. It appears that changing the modulus leads to stable/unstable transitions, which is of clear interest in a squeal study. A variation from -20% to +30% of Young modulus is considered and compared to full order computations at -20%, +10% and +20% modulus shifts. The correspondence is very good and clearly demonstrates the ability to predict complex pole patterns found in stability analysis. The second example presents the effect of mass modification on a component. The brake anchor has a so-called handle which drives the anchor rigidity in torsion. The effect of the handle inertia can be studied to set anchor handle modes at frequencies where no interaction involving anchor torsion occurs. The effect of adding a 9 gram point mass at the anchor handle center is considered.

Figure 8 shows the additional mass effect on all the anchor modes, a variation from nothing to -6% is observed. To apply the mass modification, a ∆M anchor matrix is computed and projected on the anchor reduction basis which can then be added to the system mass. The error on real mode frequencies is presented in figure 9 following the same evaluation than for the disc Young modulus variation. Frequency shifts due to the modification are well predicted. It can be noticed that significant frequency shifts (with high anchor modal participation) show the smallest errors on frequency shift.

Sensitivity to component modes

The previous section focused on the structural modification effect predictions. This section focuses on the methodology used to identify components needing modifications. Since component modes appear as explicit DOF in the reduced system matrices, the sensitivity of the stiffness matrix to a frequency change is a matrix with only one non zero element on the diagonal at position p. The sensitivity of a complex pole to a change in the p frequency of a component mode is thus simply given by the product of the complex mode components associated with that DOF

∂λ j ∂p = ψ T jL p ψ T j p (7)
The sensitivity of all system to all component modes of the reduced model is easily computed in less than 60 seconds. Since the focus is on instabilities, one only considers the damping sensitivity of unstable modes. Figure 10 shows a global sensitivity map. The plot gives a direct illustration of which modes of which component impacts the instabilities.

CONCLUSION

This paper introduced the disjoint component mode synthesis method and showed how this approach gives a clear mechanism to evaluate the impact of component modes on the system response. This evaluation is done using very compact models and can thus be used in a for systematic sensitivity studies that are needed in a design phase.

Figure 1 :

 1 Figure 1: V-model for product development

Figure 2 :

 2 Figure 2: Finite element stiffness matrices

Figure 3 :

 3 Figure 3: Reduced stiffness matrices

Figure 4 :

 4 Figure 4: Full brake model

Figure 5 :

 5 Figure 5: Reduced real mode relative frequency error to full modes

Figure 6 :

 6 Figure 6: Frequency shift prediction error for a +10% disc Young Modulus shift. -∆f pred , -∆f compt , -∆∆f

Figure 7 :

 7 Figure 7: Complex mode evolution prediction for disc Young modulus variation. red ⋄ : full recomputation, yellow ⋄ prediction corresponding to recomputed points, green ⋄: nominal point, +: prediction

Figure 8 :

 8 Figure 8: Anchor handle mass modification. Left, original mode #11 and #13 (highly impacted by handle design modification). Right, anchor real modes frequency variation

Figure 9 :

 9 Figure 9: Frequency shift prediction error for a mass variation of the anchor handle. -∆f pred , -∆f compt , -∆∆f

Figure 10 :

 10 Figure 10: Sensitivity map of the first 150 system modes to all component modes. The larger the marker, the hotter the color the higher the sensitivity

Figure 11 :

 11 Figure 11: Brake squealing mode, partial restitution plot

Figure 12 :

 12 Figure 12: Mode #55 damping sensitivity to all component modes