Emna Salhi
email: emna.salhi@irisa.fr

Samer Lahoud
email: samer.lahoud@irisa.fr

Bernard Cousin
email: bernard.cousin@irisa.fr

Localization of Single Link-Level Network Anomalies: Problem Formulation and Heuristic

Keywords: Network monitoring, network diagnosis, anomaly localization, anomaly detection, link-level anomalies

Achieving accurate, cost-efficient, and fast anomaly localization is a highly desired feature in computer networks. A necessary and sufficient condition on the set of paths that need to be monitored upon detecting a single link-level anomaly in order to localize its source unambiguously have been established. However, this paper demonstrates that this condition is sufficient but not necessary. A necessary and sufficient condition that reduces the localization overhead, cost and delay significantly, as compared to the existing condition, is established. Furthermore, an ILP algorithm that selects monitoring paths and monitor locations which satisfy the established condition jointly, thereby enabling a trade-off between the number and locations of monitoring devices and the quality of monitoring paths, is devised. The problem is shown to be N P-hard through a polynomialtime reduction from the N P-hard facility location problem, and therefore, a scalable near-optimal heuristic is proposed. The effectiveness and the correctness of the proposed anomaly localization scheme are verified through theoretical analysis and extensive simulations.

I. INTRODUCTION

Anomaly localization aims at identifying unambiguously the link that causes an anomalous behavior of the network (e.g. excessive delay, high packet loss rate, etc.). Recent research works argued that continuous anomaly localization results in high overhead on the underlying network, and hence, is likely to interfere with the network services . Subsequently, most recent monitoring schemes proceed in two phases (e.g. [START_REF] Agrawal | Diagnosing linklevel anomalies using passive probes[END_REF] [2] [START_REF] Naidu | Detecting anomalies using end-to-end path measurements[END_REF] [12] [START_REF] Salhi | Joint optimization of monitor location and network anomaly detection[END_REF] [14] [START_REF] Salhi | Localization of single network link-level anomalies[END_REF]). The first phase, the detection phase, uses as few network resources as possible to only detect anomalies. A necessary and sufficient condition to detect all link-level anomalies is to cover all links of the network. Upon detecting an anomaly, the detection phase returns a set of suspect links. The localization phase is triggered then. It aims at reducing the set of suspect links to the anomalous link(s). Clearly, this reactive anomaly localization approach reduces significantly the monitoring overhead compared to the continuous anomaly localization approach. However it presents a serious challenge: the localization must be as fast as possible, in order to enable a fast recovery of the network.

Agrawal et al. [START_REF] Agrawal | Diagnosing linklevel anomalies using passive probes[END_REF] proposed an accurate link-level anomaly localization scheme that can localize all potential single linklevel anomalies in a given network. The key idea is to deploy resources that enable the monitoring of a set of paths that distinguishes all links of the network pairwise. Two links are said to be distinguished from each other if we are able to decide which one is anomalous when an anomaly occurs on one of them. Whenever an anomaly is detected, this set of paths is monitored in order to pinpoint the anomalous link. This technique is suboptimal in that it considers all the network links as suspect, ignoring the information provided by the detection process, which generates unnecessary overhead and delays the localization. More recently, Barford et al. [START_REF] Barford | Network performance anomaly detection and localization[END_REF] proposed another scheme that selects paths that are to be monitored during the localization phase. Although this technique minimizes the localization overhead, because the monitored paths distinguish only between the suspect links pairwise, it suffers from two imperfections. The first is the non-negligible time of computing the set of paths that are to be monitored upon detecting an anomaly, which increases the localization delay (i.e., time elapsed between the moment when an anomaly is detected and the moment when the anomalous link is pinpointed). The second is that there is no guarantee to localize all potential anomalies, because the deployed monitors ensure only the coverage of links 1 . In this paper, we demonstrate that 1) not all links of the network need to be distinguishable pairwise for localizing any potential anomaly, 2) all potential anomaly scenarios can be derived offline from any detection solution that covers all the network links. Thus, we compute full and cost-efficient localization solutions, i.e., monitors that are to be activated and paths that are to be monitored upon detecting an anomaly, for all potential anomalies offline. Subsequently, we achieve an important gain in the localization delay and overhead. Multiple works propose to compute the set of paths that are to be monitored dynamically upon detecting an anomaly (e.g., [START_REF] Rish | Adaptive diagnosis in distributed systems[END_REF]- [START_REF] Brodie | Optimizing Probe Selection for Fault Localization In Proceedings of Distributed Systems Operation and Management[END_REF]). Practically, this means that one probe that maximizes the information gain given the previous probe observations is selected and sent in the network at a time. Such an approach is practical for highly dynamic environments. However, it is not practical for networks where anomalies are rare events, especially, because it yields excessive delays.

Furthermore, most existing works consider only one criterion for monitoring path selection that is the minimization of the number of monitored paths, and only one criterion for monitor location selection that is the minimization of the number of deployed monitoring devices (e.g., [START_REF] Barford | Network performance anomaly detection and localization[END_REF] [START_REF] Agrawal | Diagnosing linklevel anomalies using passive probes[END_REF]). However, these criteria do not reflect the localization cost properly. Indeed, to reduce the localization delay and overhead, monitoring of links that do not provide extra localization information during the localization phase must be avoided. Moreover, monitor locations must be selected carefully towards minimizing the delay of communications between the Network Operation Center (NOC) and the deployed monitors. A novel anomaly localization cost model that considers the infrastructure cost, the localization overhead and the localization delay is, therefore, proposed. Besides, our anomaly localization scheme selects monitor locations and monitoring paths jointly, thereby enabling a trade-off between the number and locations of deployed monitoring devices and the quality of selected monitoring paths. We formulate the problem as an ILP, and we show that it is N P-hard through a polynomialtime reduction from the facility location problem.

Prior works on anomaly localization propose greedy approaches for computing localization solutions (e.g., [START_REF] Agrawal | Diagnosing linklevel anomalies using passive probes[END_REF], [START_REF] Barford | Network performance anomaly detection and localization[END_REF], [START_REF] Bejerano | Robust monitoring of link delays and faults in IP networks[END_REF], [START_REF] Zhao | Towards efficient large-scale vpn monitoring and diagnosis under operational constraints[END_REF]). In order to ensure the scalability, the number of candidate monitoring paths should reduced to a small subset of the network paths. Unfortunately, none of these works described how candidate monitoring paths are selected, however, the choice of candidate paths has a great impact on the quality of the localization solution. In this work we propose a heuristic that implements our anomaly localization scheme. We devise an efficient algorithm for candidate path computation that makes the heuristic scalable and near-optimal at a time. The key idea is to use a mathematically proven properties that enable us to find the best candidate monitoring paths between two given monitor locations by exploring a very small proportion of the network paths.

We verify the effectiveness of our anomaly localization scheme through extensive simulations and by comparing it with an hybrid anomaly localization scheme that combines the strengths of the scheme proposed in [START_REF] Agrawal | Diagnosing linklevel anomalies using passive probes[END_REF] and the scheme proposed in [START_REF] Barford | Network performance anomaly detection and localization[END_REF].

II. NETWORK MODEL AND PROBLEM STATEMENT

We model the network as an undirected graph G = (N , E) comprising a set of nodes N connected by a set of undirected links 2 in E. Let P be the set of all non-looping paths of the network. Unless otherwise mentioned, without loss of generality, we assume that all paths in P are candidate to be monitored and all the network nodes are candidate to support monitoring devices. We use the term monitoring paths to designate paths that are monitored during the detection phase, also referred to as detection paths, or during the localization phase, also referred to as localization paths. We consider that 2 This work can be easily applied for directed links. Each directed link is duplicated into a network path is a set of links, instead of a sequence of links, and therefore, we apply set operations (e.g., ∩, ∪) on paths. We denote the anomaly detection solution by (D m , D p ). D m is the set of monitor locations where to deploy monitoring devices. D p is a set of monitoring paths between the selected monitor locations that covers all the network links, ∪ p∈Dp p = E. Furthermore, We note that we use the vertical bar notation to denote both set cardinality and absolute value.

We consider separable anomalies (e.g., connectivity, highlow loss model, delay spike model, etc) that satisfy the following property: a path experiences an anomaly if and only if at least one of its constituent links is anomalous [START_REF] Duffield | Simple network performance tomography[END_REF]. According to this property all links that are traversed by at least one detection path not exhibiting an anomaly are not anomalous, and all paths crossing an anomalous links exhibit the same anomaly. The remaining links constitute the set of suspect links. Anomaly localization aims at reducing the set of suspect links, inferred upon detecting an anomaly from the detection information, to the anomalous link. This requires monitoring additional paths that can distinguish between suspect links pairwise. Two links are said to be distinguishable from each other if we are able to decide which one is anomalous when an anomaly occurs on one of them.

The objective of this work is to come up with a localization scheme that enables the localization of all potential link-level anomalies accurately; while minimizing the cost of acquiring and deploying monitoring devices, the localization overhead and the localization delay. Our localization scheme infers all potential anomaly scenarios from any detection solution that covers all links of the network. This has two major benefits. The first is that we do not need to monitor a set of paths that can distinguish between every single pair of the network links whenever an anomaly is detected. The second is that we pre-compute full localization solutions for all anomaly scenarios offline, thereby accelerating the localization process. The inputs into our localization problem are an instance of the graph G = (N , E) and a set of detection paths D p that covers all links in E, and the outputs are a set of monitor locations whose monitors are to be activated and a set of paths that are to be monitored for each potential anomaly. The localization solution must achieve a good trade-off between the monitor deployment cost, the localization overhead and the localization delay. To this end, a novel cost model that measures these three metrics is proposed. Also, our localization scheme selects monitor locations and localization paths jointly; as opposed to existing schemes that apply a two-step selection procedure, therefore omitting the trade-off between the number and locations of monitors and the quality of localization paths.

III. NOT ALL LINK PAIRS NEED TO BE DISTINGUISHABLE FOR LOCALIZING ANY SINGLE LINK-LEVEL ANOMALY

In this section, we first establish a necessary and sufficient condition to distinguish between two links. Then, we prove that not all link pairs need to be distinguishable for localizing any potential single link-level anomaly accurately. This excludes an already established condition claiming that it is necessary to monitor a set of paths that can distinguish between all links of the network pairwise whenever an anomaly is detected [START_REF] Agrawal | Diagnosing linklevel anomalies using passive probes[END_REF].

Theorem 1: The necessary and sufficient condition for two links e 1 and e 2 to be distinguishable from each other is the existence of a monitoring path that crosses either e 1 or e 2 , but not both.

Proof: We first demonstrate the sufficiency condition. Assume that either e 1 or e 2 is anomalous. Let p be a path that crosses e 1 (interchangeably e 2 ) but not e 2 (interchangeably e 1 ). If p exhibits an anomaly, then the anomalous link must be covered by p. We conclude that e 1 is the anomalous link. If, p does not exhibit an anomaly, then all its constituent links are not anomalous. It follows that the anomalous link is e 2 . Thus, p is sufficient to distinguish between e 1 and e 2 .

The necessary condition can be proved as follows. Assume that there does not exist any path that crosses only one of the two links. Then, the monitoring path set can be divided into two types of paths: paths that cross both e 1 and e 2 , and paths that neither cross e 1 nor e 2 . An anomaly on a given link affects all the monitoring paths that cross that link. Therefore, the latter type of paths is not affected by the anomalies that occur on any the two links, whereas the former type of paths is affected by the anomalies that occur on any of the two links. Thus, the set of monitoring paths that are affected by an anomaly on e 1 is exactly the same set of paths that is affected by an anomaly on e 2 . This means that e 1 and e 2 cannot be distinguished from each other.

Existing localization schemes (e.g., [START_REF] Agrawal | Diagnosing linklevel anomalies using passive probes[END_REF]) claim that all links of the network must be distinguished pairwise in order to localize any potential anomalies. According to Theorem 1, this means that ∀e 1 , e 2 ∈ E there exists a localization path that crosses either e 2 or e 2 , but not both. However, we will demonstrate that this is a sufficient but not necessary condition, and we show how to infer the minimal set of pair of links that are to be distinguished from a given detection solution that covers all the network links.

Consider a network link e ∈ E. We denote by D e+ and D e-the set of detection paths that cross e and the set of detection paths that do not cross e, respectively. The set of suspect links associated to an anomaly on a link e is the set of all links that cannot be distinguished from e using only the detection information.

Theorem 2: The set of suspect links associated to an anomaly on a given link e ∈ E equals ∩ p∈De + p -∪ p∈De -p.

Proof: We prove this theorem by construction. The set of detection paths can be divided into two sets:

• D e+ : paths that cross link e.

• D e-: paths that do not cross link e. An anomaly on link e affects only paths that cross this link. Subsequently, paths in D e-do not exhibit an anomaly. It follows that all the links that are traversed by paths in D e-are not suspect. Now, let L be the set of links that are traversed by paths in D e+ and that are not traversed by paths in D e-, L = ∪ p∈De + p -∪ p∈De -p . L can be divided into two subsets of links:

• L 1 : links that do not belong to ∩ p∈De + p -∪ p∈De -p • L 2 : links that belong to ∩ p∈De + p -∪ p∈De -p We prove by contradiction that all links in L 1 are not suspect. Assume to the contrary that a link l ∈ L 1 is suspect. This means that there does not exist any path in D e+ that distinguishes between l and e. It follows that for each p ∈ D e+ , p crosses e and l. Thus l ∈ ∩ p∈De + p -∪ p∈De -p, leading to a contradiction.

Likewise, we prove by contradiction that all links in L 2 are suspect. Assume to the contrary that a link l ∈ L 2 is not suspect, then, there exists at least one path p ∈ D e+ such that p distinguishes between e and l. Since all paths in D e+ cross e, then p does not cross l. It follows that l / ∈ ∩ p∈De + p -∪ p∈De -p, leading to a contradiction. Theorem 2 states that the set of suspect links returned at the end of the detection phase whenever an anomaly on link e occurs is ∩ p∈De + p -∪ p∈De -p. Therefore, instead of computing monitors that are to be activated and paths that are to be monitored during the localization phase whenever an anomaly is detected, we propose to perform these computations for all potential anomalies only once offline. Having a set of detection paths that cover all links of the network, we infer the set of suspect links for all potential anomalies as described in Theorem 2. Then, a single anomaly scenario is

{(0, 1)} (0, 2) {(0, 2), (1, 3), (1, 7)} (1, 2)
{(0, 6), [START_REF] Rish | Real-time problem determination in distributed systems using active probing[END_REF][START_REF] Cheng | Efficient active probing for fault diagnosis in large scale and noisy networks[END_REF], [START_REF] Rish | Adaptive diagnosis in distributed systems[END_REF][START_REF] Rish | Real-time problem determination in distributed systems using active probing[END_REF], [START_REF] Barford | Network performance anomaly detection and localization[END_REF][START_REF] Rish | Adaptive diagnosis in distributed systems[END_REF], (1, 2)} (0, 3) {(1, 5), (0, 5), (0, 3), [START_REF] Barford | Network performance anomaly detection and localization[END_REF][START_REF] Cheng | Efficient active probing for fault diagnosis in large scale and noisy networks[END_REF], (6, 7)} (1, 3) {(0, 2), [START_REF] Agrawal | Diagnosing linklevel anomalies using passive probes[END_REF][START_REF] Naidu | Detecting anomalies using end-to-end path measurements[END_REF], (1, 7)} (2, 3) {(2, 3)} (0, 4) {(0, 4), (1, 4)} (1, 4) {(0, 4), (1, 4)} (2, 4) {(0, 6), [START_REF] Rish | Real-time problem determination in distributed systems using active probing[END_REF][START_REF] Cheng | Efficient active probing for fault diagnosis in large scale and noisy networks[END_REF], [START_REF] Rish | Adaptive diagnosis in distributed systems[END_REF][START_REF] Rish | Real-time problem determination in distributed systems using active probing[END_REF], [START_REF] Barford | Network performance anomaly detection and localization[END_REF][START_REF] Rish | Adaptive diagnosis in distributed systems[END_REF], (1, 2)} (0, 5)

{(1, 5), (0, 5), (0, 3), [START_REF] Barford | Network performance anomaly detection and localization[END_REF][START_REF] Cheng | Efficient active probing for fault diagnosis in large scale and noisy networks[END_REF], (6, 7)} (1, 5)

{(1, 5), (0, 5), (0, 3), [START_REF] Barford | Network performance anomaly detection and localization[END_REF][START_REF] Cheng | Efficient active probing for fault diagnosis in large scale and noisy networks[END_REF], (6, 7)} (4, 5)

{(0, 6), [START_REF] Rish | Real-time problem determination in distributed systems using active probing[END_REF][START_REF] Cheng | Efficient active probing for fault diagnosis in large scale and noisy networks[END_REF], [START_REF] Rish | Adaptive diagnosis in distributed systems[END_REF][START_REF] Rish | Real-time problem determination in distributed systems using active probing[END_REF], [START_REF] Barford | Network performance anomaly detection and localization[END_REF][START_REF] Rish | Adaptive diagnosis in distributed systems[END_REF], (1, 2)} (0, 6) {(0, 6), [START_REF] Rish | Real-time problem determination in distributed systems using active probing[END_REF][START_REF] Cheng | Efficient active probing for fault diagnosis in large scale and noisy networks[END_REF], [START_REF] Rish | Adaptive diagnosis in distributed systems[END_REF][START_REF] Rish | Real-time problem determination in distributed systems using active probing[END_REF], [START_REF] Barford | Network performance anomaly detection and localization[END_REF][START_REF] Rish | Adaptive diagnosis in distributed systems[END_REF]

∪ e∈E S(e) = ∪ S(i)∈dS S(i) = E Corollary 5: ∑ S(i)∈dS | S(i) | = | E | Clearly,
an upper bound of the number of anomaly scenarios, whatever the topology of network and whatever the detection solution, is the number of the network links. It is easy to show that when this bound is reached, the set of suspect links for an anomaly on link e, ∀e ∈ E, is reduced to the link e. In such case, the localization of all potential anomalies is immediate from the detection information. According to Corollary 2, we need to deploy monitors that enable the monitoring of a set of paths distinguishing links of each anomaly scenario pairwise in order to ensure the localization of all potential anomalies.

To illustrate, consider the sample network topology depicted in Figure 1(a). An associated anomaly detection solution that covers all links of the network is depicted in Figure 1(b). We use Theorem 2 to compute the set of suspect links for all potential anomalies. The result is depicted in Table I. The sets of suspect links associated to link (2, 3) and link (0, 7) are unitary. When an anomaly occurs on one of these two links, there is no need to trigger the localization phase because the anomalous link is immediately pinpointed by intersecting the detection paths that exhibit the anomaly. Furthermore, four non-unitary anomaly scenarios (a 1 , a 2 , a 3 , a 4 ) are created for this topology (see table II). These are the four distinct nonunitary sets of suspect links.

Let AllP airs denotes the number of all the network link pairs. Clearly, AllP airs

= (| E | (| E | -1))/2. Let dP airs
denotes the number of pair of links that need be distinguishable for localizing any potential link-level anomaly.

Corollary 6: dP airs = AllP airs -∑ S(i),S(j)∈dS:i<j

| S(i) || S(j) |

Corollary 6 confirms that we do not need to distinguish between all the network link pairs unless the number of detection paths equals 1, which is very unlikely.

The proofs of Corollary 4, Corollary 5 and Corollary 6 are described in Appendix A.

V. ANOMALY LOCALIZATION COST

Consider a set of candidate monitor locations, M, a set of network paths that are candidate to be monitored, P, and a set of anomaly scenarios A. The anomaly localization cost includes two costs:

• Monitor cost: it includes the effective cost of acquiring hardware and software monitoring devices and the cost of their maintenance. In addition, it includes the cost of communications between the monitors and the NOC. For instance, the cost of communications between a monitor and the NOC can be expressed as a function of the number of routing hops that separates them. Let us denote by C n the cost of deploying a monitor on node n. Let Y n be a binary variable that indicates whether node n is selected to hold a monitoring device. The monitor cost can be expressed as follows:

∑ n∈M C n Y n (1)
• Probe cost: it expresses the overhead of monitoring flows on the underlying network. Measurements of links that do not provide localization information should be avoided in order to minimize the monitoring overhead. Clearly, measuring links that do not belong to the set of suspect links of an anomaly scenario does not provide any extra localization information. Furthermore, measurement of links that belong to the set of suspect links might be useless. Revisit Figure 1 and table I to illustrate. Consider an anomaly on link [START_REF] Cheng | Efficient active probing for fault diagnosis in large scale and noisy networks[END_REF][START_REF] Brodie | Active probing strategies for problem diagnosis in distributed systems In Proceedings of the International Joint Conferences on Artificial Intelligence[END_REF]. The associated set of suspect links is Sa 3 = {(1, 5), (0, 5), (0, 3), [START_REF] Barford | Network performance anomaly detection and localization[END_REF][START_REF] Cheng | Efficient active probing for fault diagnosis in large scale and noisy networks[END_REF], (6, 7)}. Consider now the set of localization paths {p1:

⟨(1, 5)(5, 6)(2, 6)⟩; p2:⟨(1, 5)(0, 5)(0, 2)⟩; p3:⟨(1, 7)(6, 7)(2, 6
)⟩} that distinguishes between all the links of Sa 3 pairwise. Path p 1 divides Sa 3 into two subsets: (2, 6)} and S 2 a 3 {(0, 5), (0, 3), (6, 7)}. p 1 distinguishes each link of S 1 a 3 from each link of S 2 a3 . Link [START_REF] Rish | Real-time problem determination in distributed systems using active probing[END_REF][START_REF] Cheng | Efficient active probing for fault diagnosis in large scale and noisy networks[END_REF] that is traversed by p 1 does not belong to Sa 3 , and therefore, it does not provide any localization information. Path p 2 divides S 1 a 3 into two subsets: S 11 a 3 {(1, 5)} and S 12

S 1 a 3 {(1, 5),
a 3 {(2, 6)},
and divides S 2 a 3 into two subsets: S 21 a 3 {(0, 5), (6, 7)} and S 22 a 3 {(0, 3)}. Finally, p 3 distinguishes between (0, 5) and (6, 7). However, it crosses [START_REF] Barford | Network performance anomaly detection and localization[END_REF][START_REF] Cheng | Efficient active probing for fault diagnosis in large scale and noisy networks[END_REF] that is already distinguished from all the other suspect links. Thus, measuring [START_REF] Barford | Network performance anomaly detection and localization[END_REF][START_REF] Cheng | Efficient active probing for fault diagnosis in large scale and noisy networks[END_REF] by p 3 does not provide extra localization information, although it belongs to Sa 3 .

Let us denote by C e the cost of measuring link e. C e should be proportional to the load of link e, in order to avoid multiple measurements of the most overloaded links of the network.

Consider an anomaly scenario a ∈ A. Let us denote by S a the set of suspect links associated to the anomaly scenario a. Let X pa be a binary variable that specifies whether path p is part of the localization solution of a. Let δ pe be a binary input parameter that indicates whether path p crosses link e. The probe cost of the localization solution of a reads as follows:

∑ e∈E,p∈P ′ C e δ pe X pa (2)

VI. ILP FORMULATION

The objective of the ILP is to find a localization solution for each anomaly scenario in A such that the anomaly localization cost is minimized. Let δ pn be a binary parameter that indicates whether node n is an end-node of path p. For simplicity of notation, we define the following sets:

• δ PE = {δ pe ; p ∈ P, e ∈ E} • δ PM = {δ pn ; p ∈ P, n ∈ M} • C M = {C n ; n ∈ M} • C E = {C e ; e ∈
α ∑ n∈M C n Y n + β ∑ a∈A,e∈E,p∈P C e δ pe X pa ( 3
)
The ILP is subject to two constraints. The first constraint ensures that either end node of each selected monitoring paths is selected as monitor location. It reads as follows:

Y n ≥ δ pn X pa ; ∀n ∈ M, ∀p ∈ P, ∀a ∈ A (4)
The second constraint ensures that the suspect links associated to each anomaly scenario are distinguishable pairwise. To this end, according to Theorem 2, the constraint ensures that for each anomaly scenario a and for each pair of suspect links (e 1 , e 2 ) : e 1 , e 2 ∈ S a there exists at least one monitoring path that crosses either e 1 or e 2 , but not both. This constraint reads as follows:

∑ p∈P (δ pe1 + δ pe2 -2δ pe1 δ pe2 )X pa > 0; ∀a ∈ A; ∀e 1 , e 2 ∈ S a (5)
We show that the above inequality is sufficient to distinguish between all the link pairs of each anomaly scenario using the argument of the following theorem.

Theorem 3: Let P 1 be the subset of paths of P that cross either e 1 or e 2 , but not both.

∑ p∈P (δ pe1 + δ pe2 -2δ pe1 δ pe2 ) =| P 1 |.
Proof: Refer to Appendix B.

Corollary 7: If ∑ p∈P (δ pe1 + δ pe2 -2δ pe1 δ pe2 )X pa > 0, then there exists at least one path in P that crosses either e 1 or e 2 but not both, then there exists at least one path in P that distinguishes between e 1 and e 2 .

VII. THE ANOMALY LOCALIZATION PROBLEM IS N P -HARD

Theorem 4: The anomaly localization problem presented in the previous section is N P-Hard.

Proof: Our formulation of the anomaly localization problem can be reduced from the N P-Hard facility location problem.

Facility location problem [START_REF] Chudak | Improved Approximation Algorithms for the Uncapacitated Facility Location Problem[END_REF]: consider a set of potential facility locations F, and a set of clients D. Opening a facility at location i incurs a non-negative cost that is equal to f i . The cost of servicing client j ∈ D by a facility installed at location i ∈ F is d ij . The problem is to find an assignment of each client to exactly one facility such that the sum of the facility opening costs and the service costs is minimized.

We denote by f the set of facility opening costs, f = {fi, i ∈ F}, and by d the set of service costs, d = {dij; i ∈ F, j ∈ D}. Given an instance I = (D, F, f, d) of the facility location problem, we produce an instance R(I) = (E, M, P, A, δ PE , δ PM , C E , C M , α, β) of the localization problem as follows. For each client j ∈ D, we create:

• Three nodes labeled by n j1 , n j2 , and n j3 .

• One link connecting n j1 to n j2 , labeled by e j1 .

• One link connecting n j2 to n j3 , labeled by e j2 .

• An anomaly scenario a j such that S aj = {e j1 , e j2 }.

C mi1 = C mi2 = f i /2.
The link measurement costs are defined as follows:

C ei1 = C ei2 = 0, C e 1 ij = C e 2 ij = d ij /2.
The remaining input parameters can be inferred easily from G, M, A and P as follows:

• δ aj e j ′ k = { 1 if j = j ′ 0 otherwise ; ∀j, j ′ ∈ D, k ∈ [1; 2] • δ aj e k ij = 0; ∀i ∈ F , j ∈ D, k ∈ [1; 2] • δ pij m i ′ k = { 1 if i = i ′ 0 otherwise ; ∀i, i ′ ∈ F, k ∈ [1; 2] • δ pij ej1 = δ pij e 1 ij = δ pij e 2 ij = 1; ∀i ∈ F , j ∈ D • δ pij ej2 = 0; ∀i ∈ F , j ∈ D • α = β = 1
It can be easily shown that the time complexity of the above reduction is O(| F | × | D |), and therefore, it can be carried out in polynomial-time. In the sequel, we show that there is an optimal solution to the Instance I of the facility location problem if and only of there is an optimal solution to the instance R(I) of our anomaly localization problem.

Let us start by demonstrating that if there is an optimal solution to the facility location instance, then there is a feasible solution to the anomaly localization instance. Let the facility location solution assign each client j to a facility installed at location i. Consider the anomaly localization solution that selects for each anomaly scenario a j the path p ij and the monitor locations m i1 and m i2 . Then, let us fix an anomaly scenario a j . By construction, path p ij crosses three links that are e j1 and e 1 ij and e 2 ij . It follows, according to Theorem 1, that p ij distinguishes between e j1 and e j2 . Constraint (4) states that if p ij is selected to be monitored, then, its end nodes must be selected to hold monitoring devices. Thus, the solution that selects for each anomaly scenario a j the path p ij to be monitored, and its end nodes, m i1 and m i2 , as monitor locations is a feasible solution to the anomaly localization instance.

Conversely, we demonstrate that if there is an optimal solution to the anomaly localization instance, then there is a feasible solution to the facility location instance. An optimal solution to the facility location problem selects exactly one path for each anomaly scenario. This is because, by construction, for each anomaly scenario a i ∈ A | S ai |= 2. Thus, monitoring one path that crosses exactly one of the two links is sufficient to distinguish between them. Let the optimal anomaly localization solution selects for each anomaly scenario a j the path p ij , and naturally, the monitor locations m i1 and m i2 . Trivially, the solution that assigns to each client j ∈ D the facility installed at location i is a feasible solution to the facility location instance.

We now prove that the constructed anomaly localization solution has the same cost as its corresponding optimal facility location solution (the proof holds in the converse case). Let W i be a binary variable that indicates whether a facility is installed at location i, and let Z ij be a binary variable that indicates whether client j is serviced by a facility installed at location i. Using the arguments that

Z ij = X pij aj and W i = Y mi1 = Y mi2
3 , we show that the cost of the localization solution, denoted by Cost(S R(I) ), is equal to the cost of its corresponding 3 Recall that Xpa is a binary variable that indicates whether path p is part of the localization solution of the anomaly scenario a, and Yn is a binary variable that indicates whether node n is selected as a monitor location facility location solution, denoted by Cost(S I ), as follows:

Cost(S R(I) ) = α ∑ mik∈M C mik Y mik + β ∑ aj ∈A,e∈E,pij ∈P C e X pij aj = ∑ mik∈M C mik Y mik + ∑ aj ∈A,pij ∈P (C e 1 ij + C e 2 ij )X pij aj = ∑ mi1∈M f i Y mi1 + ∑ aj ∈A,pij ∈P d ij X pij aj = ∑ i∈F f i W i + ∑ j∈D,i∈F d ij Z ij = Cost(S I )
Now, we show that the solution to the anomaly localization instance, denoted by S R(I) , that is constructed out of an optimal solution to the facility location instance, denoted by S * I , is optimal. Assume to the contrary that S R(I) is not optimal. Let S ′ * R(I) be an optimal solution to the anomaly localization instance, and let S VIII. HEURISTIC SOLUTION

In this section, we provide a monitor location and path selection algorithm for localizing single link-level anomalies. The inputs of the algorithm are a network graph G = (N , E), a set of anomaly scenarios A, a set of candidate monitor locations M, the costs of deploying monitoring devices on the network nodes C M = {C n ; n ∈ M}, and the costs of monitoring the network links C E = {C e ; e ∈ E}. The outputs are a set of monitor locations, SM a , and a set of monitoring paths, SP a , that can distinguish between all links of S a pairwise, for each a ∈ A.

Similarly to the ILP, the heuristic solution aims at minimizing the infrastructure cost, the communication cost and the probe cost jointly. To this end, we use a nested greedy approach that selects monitor locations jointly with monitoring paths. Algorithm 1 describes the pseudo-code. ProbeCost(p, C E ) is a function that returns the probe cost incurred by monitoring path p. This cost is computed as described in section V. m s stores the best current candidate monitor location. SM stores the monitor locations selected at the previous iterations. Pcost min stores the current lowest probe cost, and lc max stores the current largest localization capacity, i.e., the number of link pairs that can be distinguished by monitors in SM ∪ {m s }. CP stores paths selected by the current best solution. In the sequel, we define the criteria of monitor location selection and monitoring path selection.

A detailed description of how monitor locations and monitoring paths are selected, and how candidate localization paths are computed is provided in the following subsections.

A. Selection of monitor locations

The algorithm starts by selecting one candidate monitor location randomly. Alternatively, the candidate monitor location with the smallest monitor cost (sum of the infrastructure cost and the communication cost) can be selected. However, we advocate random selection for two reasons. The first is that the monitor location with the smallest monitor cost does not necessarily incur the smallest probe cost. The second is that selecting the starting point randomly enlarges the space of explored solutions over multiple runs of the algorithm. Monitor locations are, then, added to the solution greedily until all link pairs of all the anomaly scenarios are distinguished. At each greedy iteration (lines 5-36), all the remaining candidate monitor locations are explored. Let us fix a candidate monitor location m. A set of monitoring paths whose end nodes are in SM ∪ {m} is selected greedily (lines 7-35). The path selection procedure is described in details in section VIII-B. The candidate monitor location whose associated monitoring paths can distinguish between the largest number of link pairs over all the anomaly scenarios is selected (line 31). In case of a tie, a monitor location that incurs the smallest localization cost (α × monitor cost + β × probe cost, where the probe cost is the summation of the probe costs of the associated monitoring paths) is selected.

16 for (1 ≤ k ≤ s (j) ) do 17 if (| p a(j) ∩ S (j)k a |> 1) then S (j+1)l a ← p a(j) ∩ S (j)k a ; l ← l + 1; 18 if (| S (j)k a -{p a(j) ∩ S (j)k a } |> 1) then S (j+1)l+1 a = S (j)k a -{p a(j) ∩ S (j)k a }; l ← l + 1; 19 end 20 s (j) ← l
When a solution that distinguishes between all the link pairs of all the anomaly scenarios is found, the algorithm continues the exploration of the remaining candidate monitor locations, if any, towards reducing the probe cost. However, a filter is applied on these locations before exploring them (line 6). Only candidate locations whose monitor cost is smaller than the probe cost of the current best solution are explored. Clearly, the localization cost of any solution that selects a monitor location not satisfying this filter would be larger than the localization cost of the current best solution. The algorithm ends when the set of candidate monitor locations gets empty, i.e., all candidate monitor locations have been selected, or when remaining candidate monitor locations can neither improve the localization capacity nor the probe cost of the current best solution.

B. Selection of localization paths

Given a candidate monitor location m and a set of already selected monitor locations SM, the procedure of selecting an associated set of monitoring paths, (lines 7-35), is as follows. Let us fix an anomaly scenario a. A set of monitoring paths that maximizes the number of distinguished pair of links of S a while minimizing the probe cost is selected greedily as follows. First, one path that can distinguish between the largest number of link pairs of S a is selected. We refer to the number of pair of links of a set of suspect links S a that can be distinguished by a path p as the localization capacity of p with respect to S a , denoted by lc(p, S a ). It can be easily shown that:

lc(p, S a ) =| p ∩ S a | (| S a |-| p ∩ S a |) (6)
In case of a tie, a path that minimizes the probe cost is selected. The algorithm used for computing the candidate monitoring path is described in section VIII-C. Let p a(1) be the selected path. Two subsets of suspect links are generated: S . At the next step, we need to distinguish between the links of S ) is selected. Ties are broken by selecting a path that minimizes the probe cost.

Let p a(j) be the monitoring path selected at step (j). Let s (j-1) be the number of non-unitary subsets of suspect links generated at step (j -1). p a(j) is selected such that ∑ 1≤k≤s (j-1) lc(p, S (j-1)k a

) is maximized. In case of a tie, a path that minimizes the probe cost is selected. For each S (j-1)k a , 1 ≤ k ≤ s (j-1) , two subsets of suspect links are generated: S (j-1)k a ∩ p a(j) and S (j-1)k a -{S (j-1)k a ∩ p a(j) }. Each link of the former subset is distinguished from each link of the latter subset. Only non-unitary subsets, whose links need to be distinguished from each other, are considered at the next step. This greedy process is re-iterated until all the generated subsets of suspect links are unitary or until no candidate localization path can distinguish between the pair of links of non-unitary subsets. For each selected path p a(j) , the localization capacity of m is incremented by lc(p a(j) , S (j) a ) (line 13), and its probe cost is incremented by probeCost(p a(j) , C E ) (line 14). The above procedure is applied on the all the anomaly scenarios in A. Then, the localization capacity and the probe cost of m are evaluated (line 31). If the localization capacity of m is greater than lc max , or if the localization capacity of m equals lc max and its probe cost is less than Pcost min ; then lc max is set equal to the localization capacity of m, Pcost min is set equal to the probe cost of m and m s is set equal to m.

Furthermore, using the argument of the following theorem, we can compute a lower bound of the probe cost of the explored monitor location at any step in the path selection procedure.

Theorem 5: The theoretical minimal probe cost relative to a set of suspect links S denoted by T hM inP cost(S) reads as follows:

T hM inP cost(S) = ∑ e∈S C e -max e∈S C e ( 7
)
Proof: Refer to Appendix C. The lower bound of the probe cost of a candidate monitor location after path p a(j) is added to the set of its associated monitoring paths reads as follows: [START_REF] Maitreya | Probabilistic fault diagnosis using adaptive probing[END_REF] where P cost is the summation of the probe costs of the already selected paths.

P cost + s (j) ∑ k=1 T hM inP cost(S (j)k a ) + ∑ a ′ ∈A,a ′ >a T hM inP cost(S ′ a )
When the algorithm finds a solution that can distinguish between all link pairs of all the anomaly scenarios, it continues exploring the remaining candidate monitor locations that satisfy the monitor cost filter (line 6) towards reducing the probe cost. Using [START_REF] Maitreya | Probabilistic fault diagnosis using adaptive probing[END_REF], we propose an optimization of the exploration process of these candidate monitor locations. The idea is to update the lower bound of the probe cost of the explored monitor location whenever a monitoring path is selected, and to infer a lower bound of the localization cost (line 21). The exploration of the considered candidate monitor location is abandoned if, at any step of the path selection procedure, the calculated lower bound of the localization cost dominates the localization cost of the current best solution.

Procedure 2: candidatePathSelection(m, SM, G, S (j) a , CP)

1 pc ← newPath(); 2 li min ← ∑ S (j)k a ∈S (j) a | S (j)k a | /2 -1; Pcost min ← ∑ e∈E C e ; 3 foreach q ∈ CP do 4 li = ∑ S (j)k a ∈S (j) a | S (j)k a | /2-| S (j)k a ∩ q |;

C. Candidate path selection algorithm

This section describes the procedure candidatePathSelection called by Algorithm 1 at line 13. The inputs into this procedure are the network graph, the currently explored monitor location m, the subsets of suspect links generated at the current step of the path selection procedure S

(j) a = {S (j)1 a , ... S (j)k a , S (j)k+1 a ..., S (j)s (j) a
}, the set of the already selected monitor locations SM, and the set of monitoring paths selected by the current best solution CP. The output is one monitoring path, whose end nodes are in SM ∪ {m}, that maximizes the localization capacity while minimizing the probe cost.

The main difficulty of this procedure is the computation of the set of candidate paths. Generally, the smaller the set of candidate paths is, the worst the quality of the heuristic is. This is because good paths might be missed when reducing the number of candidate paths. However, this reduction is imper-ative to ensure the scalability of the heuristic. The procedure candidatePathSelection implements an algorithm for candidate localization path computation. The algorithm considers all the network paths whose end nodes belong to {m} × SM as candidate to be monitored. However, computing this set of paths is computationally expensive, because it requires exploring all the network graph. Moreover, since Algorithm 1 explores all remaining candidate monitor locations at each iteration, the graph would be explored multiple times; which makes the heuristic non-scalable and non-practical for dense networks. An alternative solution is to compute and store all paths traveling between all candidate monitor locations offline, thereby reducing the number of times the network graph is explored to one. Clearly, this solution is impractical due to memory issues. We conclude, based on the above discussion, that our candidate path computation algorithm must minimize the number of paths that are to be explored, while guaranteeing that good candidate paths are not missed. To this end, we make use of the argument of the following theorem:

Theorem 6: let lc(S (j) a , p) = ∑ S (j)k a ∈S (j) a lc(S (j)k a
, p) be the localization capacity of p with respect to S (j) . We have,

max p∈P lc(S (j) a , p) = min p∈P ∑ S (j)k a ∈S (j) a || S (j)k a | /2-| S (j)k a ∩ p || (9)
Proof: Refer to Appendix D.

We refer to

∑ S (j)k a ∈S (j) a || S (j)k a | /2-| S (j)k a ∩ p ||
as the localization indicator of path p with respect to S (j) a , and we denote it by li(p, S (j) a ). According to Theorem 6, the smaller li(p, S (j) a ) is, the higher the localization capacity of p with respect to S (j) a is. The localization indicator is used along with the probe cost to avoid exploring all the network graph, while guaranteeing that good candidate paths are not missed. Procedure 2 provides an overview of the pseudo-code. p s stores the current best candidate path, li min stores the localization indicator of p s , and Pc min stores its probe cost. p s , li min and Pc min are initialized to N ull, ∑

S (j)k a ∈S (j) a | S (j)k a | /2 -1 and ∑ e∈E C e , respectively. Note that the least upper bound of the localization indicator is ∑ S (j)k a ∈S (j) a | S (j)k a | /2,
which corresponds to a path that does not provide any localization information (i.e., ∀S

(j)k a ∈ S (j) a , S (j)k a ∩ p = ∅ or ∃S (j)k a ∈ S (j) a such that p = S (j)k a
) 4 ; whereas the least upper bound of the probe cost is ∑ e∈E C e , which corresponds to a path that crosses all the network nodes and does not provide any localization information. However, if CP is not empty, then p s is set equal to the best path in CP, i.e., the path that maximizes the localization capacity (in case of a tie, a path that minimizes the probe cost); and li min and Pc min are initialized to the localization capacity and the probe cost of that path, respectively. The rational behind considering paths in CP is to avoid re-exploring all candidate paths traveling between the already selected monitors. 4 By construction,

∩ k S (j)k a = ∅
The network graph is, then, explored in depth-first order starting from the candidate monitor location m. It is worth noting that we believe that a breadth-first search can find candidate paths faster. However, the depth-first search approach requires much less memory.

We now introduce the optimizations made to avoid exploring all the network graph, which speeds up the search and ensures the scalability of the algorithm. Let n be the currently explored node and p c the current path to that node. p s , li min and Pc min are set equal to p c , li(p c , S

probeCost(p c , C E ) < Pc min )) (10)
The above condition implies that the path selection criterion is the minimization of the localization indicator, which is equivalent to the maximization to the localization capacity, and that ties are broken by minimizing the probe cost. Moreover, it ensures that the end nodes of the selected path are in SM ∪ {m}. Now, the most important feature of the algorithm is that it is able, using Theorem (6), to decide whether all paths having a given prefix are not good. A good path is a path that dominates the current best path, i.e., a path that satisfies Condition [START_REF] Brodie | Optimizing Probe Selection for Fault Localization In Proceedings of Distributed Systems Operation and Management[END_REF]. In fact, all paths having as prefix the current path p c are undoubtedly inefficient if one of the following conditions is true: [START_REF] Bejerano | Robust monitoring of link delays and faults in IP networks[END_REF] li min = 0 and ∀S (j)k a ∈ S (j) a | S | /2 [START_REF] Salhi | Joint optimization of monitor location and network anomaly detection[END_REF] Whenever a node that is not in SM is explored, the current path to that node is examined. If it satisfies one of the above conditions, then the descendant nodes of the current node will not be explored, i.e., all paths having as prefix the current path will be discarded without exploring their suffixes. This achieves great savings in terms of the number of explored paths and in terms of time. The accuracy of conditions ( 11), ( 12) and ( 13) is demonstrated in Appendix E.

li min = 0 and ∃ S (j)k a ∈ S (j) a such that | S (j)k a ∩ p c |>| S (j)k a | /2

IX. PERFORMANCE EVALUATION

Extensive simulations are conducted on network topologies built using the BRITE generator [18] (Waxman model [START_REF] Waxman | Routing of Multipoint Connections[END_REF]: α = β = 0.4, random node placement 5 ). We use Cplex11. 2 [20] to solve ILPs and we implement our algorithms using C ++ . All the numerical results presented in this section are the mean over 30 simulations on random simulations. Our experiments indicate that the results are almost the same for larger number of simulations. Table III depicts a summary of the topologies considered. Our localization scheme takes as input any detection solution that covers all links of the network. For small topologies, i.e., TOP [START_REF] Maitreya | Probabilistic fault diagnosis using adaptive probing[END_REF]18), optimal detection solutions are computed using the detection scheme proposed in [START_REF] Salhi | Joint optimization of monitor location and network anomaly detection[END_REF]; whereas the anomaly detection heuristic proposed in [START_REF] Salhi | Heuristics for joint optimization of monitor location and network anomaly detection[END_REF] is used to compute detection solutions for larger topologies. Note that the anomaly detection problem is N P-Hard, therefore, optimal detection solutions could not be computed for large topologies. The evaluations are performed on a PC equipped with a 2,992.47 MHz Intel(R) Core(TM)2 Duo processor and 3.9 GB of RAM. We assume that every nodes of the network is candidate to support a monitoring device and all paths of the networks are candidate to be monitored. We set C n = C e = 1, ∀n ∈ N and ∀e ∈ E.

A. Comparing our Anomaly Localization Scheme with Existing Schemes

We compare our anomaly localization scheme with an hybrid anomaly localization scheme that combines the strengths of the schemes proposed in [START_REF] Agrawal | Diagnosing linklevel anomalies using passive probes[END_REF] and [START_REF] Barford | Network performance anomaly detection and localization[END_REF]. As proposed in [START_REF] Barford | Network performance anomaly detection and localization[END_REF], a set of paths that distinguishes only between the suspect links is monitored during the localization phase. However, to guarantee that all potential anomalies can be localized uniquely, a set of monitors that can distinguish between all pairs of the network links is deployed [START_REF] Agrawal | Diagnosing linklevel anomalies using passive probes[END_REF]. Such a scheme can be formulated as two ILPs. The first ILP computes a minimal subset of monitor locations that enables the localization of all potential anomalies. This ILP is run only once offline. It reads as follows:

Minimize ∑ n∈M Y n Subject to:

∑ p∈P (δ pe1 + δ pe2 -2δ pe1 δ pe2 )Z p > 0; ∀e 1 , e 2 ∈ E; ∀p ∈ P δ pn Y n ≥ Z p ; ∀p ∈ P, ∀n ∈ N
The second ILP is run whenever an anomaly is detected. The input is the set of monitor locations selected by the first ILP, M ′ , and a set of suspect links S. The output is a minimal set of monitoring paths that can distinguish between the suspect links pairwise. This ILP reads as follows:

Minimize ∑ p∈P Z p Subject to: We refer to this hybrid anomaly localization scheme as HLS.

∑ p∈P (δ pe1 + δ pe2 -2δ pe1 δ pe2 )Z p > 0;
Only small topologies for which the ILPs can deliver solutions in tractable time are considered. We set the weight associated to the probe cost β = 1, and we vary the weight associated to the monitor cost, α ∈ [START_REF] Agrawal | Diagnosing linklevel anomalies using passive probes[END_REF][START_REF] Barford | Network performance anomaly detection and localization[END_REF][START_REF] Rish | Adaptive diagnosis in distributed systems[END_REF] and α ≥ 6. Avg. nb. of monitoring paths per anomaly Fig. 3: Average number of monitoring paths per anomaly for TOP [START_REF] Maitreya | Probabilistic fault diagnosis using adaptive probing[END_REF]18). The first histogram to the left presents results for solutions computed using the hybrid localization scheme (HLS), and the other histograms present results for the solutions computed using our anomaly localization ILP with different values of α (β = 1).

We define three metrics for the comparison. The first metric is the time of computing the localization solution, i.e., monitors that are to be activated and paths that are to be monitored when an anomaly is detected. This metric reflects the speed of the localization scheme. The better is to avoid online computations, i.e., computations done upon detecting an anomaly, in order to shorten the localization delay. Table IV depicts the online computation time and the offline computation time for the hybrid localization scheme and for our localization scheme. Intuitively, as shown in the table, the online computation time is zero for our localization scheme. This is because we compute full localization solutions for all potential anomalies offline. In contradiction, the hybrid scheme leaves the selection of monitoring paths upon detecting an anomaly, thereby achieving a non-negligible online computation time. This time can be relatively high for large topologies where the number of candidate monitoring paths is large. For the offline computation time, the table shows that our scheme is about 10 times faster than the hybrid scheme, although, it computes full localization solutions for all potential anomalies. We explain this result by the fact that, unlike the hybrid scheme, our scheme does not distinguish between every pair of the network links.

The second metric is the localization cost. Figure 4 plots the total number of deployed monitors (Figure 4c), the average number of monitors activated per anomaly (Figure 4b), and the average overhead (4a), i.e., the number of links monitored that provide no localization information, per anomaly for the hybrid localization scheme and for our localization scheme with different values of α. Three conclusions can be drawn from the numerical results. The first is that there is an interplay between the monitor location cost and the probe cost. The different results for the different values of α illustrate this conclusion. Indeed, the larger the value of α is, the fewer the number of monitors is and the larger the localization overhead is. For instance, for α = 1, we have localization solutions with zero overhead and 7 monitors, i.e., 7 of the 8 nodes of the network hold monitoring devices. The second is that the existing localization scheme that deploys monitors offline and selects monitoring paths online does not take into consideration this interplay, and therefore, delivers sub-optimal localization solutions. Using the same number of monitors, for α ≥ 6, our localization scheme can localize any potential anomaly with about 65% less overhead than the existing localization scheme. The third metric is the number of monitoring paths. Recall that this is the path selection criterion for the existing localization scheme. We do not consider this criterion in our localization scheme for two reasons. The first is that, upon detecting an anomaly, the set of paths that distinguish between the suspect links are monitored simultaneously. Therefore, the minimization of the number of monitoring paths does not reduce the localization delay. The second reason is that this metric is tightly correlated to the number of monitors and the localization overhead. Indeed, if we relax the constraint on the localization overhead, this would allow long monitoring paths that cross a large number of links. Therefore, the number of monitoring paths that can distinguish between the suspect links would decrease. Similarly, if we relax the constraint on the number of monitors, we would deploy more monitors in the network, thus, the monitoring paths would get shorter. Therefore, the number of monitoring paths that can distinguish between the suspect links would increase. Figure 3 validates these claims. Hereby, we can observe that the larger α is, the more monitoring paths we have. Not surprisingly, for α ≥ 6, our localization scheme monitors only 8% more paths than the hybrid localization scheme, while deploying the same number of monitors and incurring 65% less overhead.

B. Evaluating the Scalability and Quality of the Heuristic

In this section, we evaluate the performance of our anomaly localization heuristic. We set α >> β. For each network topology, we run the heuristic n times, where n is the number of the network nodes. The first monitor location that is selected randomly must be different for each run. Then, we consider the solution with the smallest localization cost. For TOP [START_REF] Maitreya | Probabilistic fault diagnosis using adaptive probing[END_REF]18), we compare the results obtained using the heuristic with the results obtained using our anomaly localization ILP (α ≥ 6), and the results obtained using the hybrid localization scheme. Furthermore, we evaluate the evolution of resource consumption and computation time with respect to the network size to evaluate the performance of the heuristic on larger topologies.

Table V depicts the heuristic computation time (this is the time of the n runs of the heuristic) and the average percentage of the network paths explored in one execution of Procedure 2 for all the topologies considered. For TOP [START_REF] Maitreya | Probabilistic fault diagnosis using adaptive probing[END_REF]18) the heuristic computation time is about 29.10 3 times faster than our ILP, and about 27.10 4 times faster than the hybrid localization scheme. Recall that all computations are done offline. For TOP [START_REF] Brodie | Optimizing Probe Selection for Fault Localization In Proceedings of Distributed Systems Operation and Management[END_REF]31), TOP [START_REF] Zhao | Towards efficient large-scale vpn monitoring and diagnosis under operational constraints[END_REF]41) and TOP [START_REF] Salhi | Localization of single network link-level anomalies[END_REF]59) the heuristic computation time is in the order of few seconds (< 25 s), while it was infeasible to obtain the ILP results for these topologies in tractable time. For TOP(20, 80), whose number of paths is in the order of hundreds of billions, it was impossible to run the ILPs due to memory insufficiency. However, the heuristic succeeded to compute solutions in less than one hour for these topologies. This confirms the efficiency of our candidate path computation algorithm that minimizes the number of the networks paths that are to be explored. For instance, we found that only 0.007% of the network paths are explored in one execution of Procedure 2 for TOP(20, 80). We now investigate the quality of the solutions delivered by the heuristic. Figure 5 plots the total number of monitors deployed (5c), the average number of monitors activated per anomaly (5b), and the average overhead per anomaly for the topologies considered in the evaluation5a.

First, we notice that two monitors are sufficient to localize all potential anomalies for all topologies, except TOP(20, 80) for which the average number of monitors deployed and the average number of monitors activated per anomaly are slightly larger than two. This is expected, since we set α >> β, which means that the heuristic minimizes in priority the number of monitors that are to be deployed. A comparison of Figure 5 with Figure 4 shows that, for TOP [START_REF] Maitreya | Probabilistic fault diagnosis using adaptive probing[END_REF]18), the solutions computed using our ILP (α ≥ 6) is very close to the solutions computed using the heuristic: the heuristic solution gnenerates about 9% more overhead, however, the two solutions deploy the same number of monitors and activate, in average, the same number of monitors when an anomaly occurs. This confirms that the candidate path computation algorithm that avoids exploring all paths of the network does not miss good paths. Moreover, the overhead of the heuristic solutions for TOP [START_REF] Brodie | Optimizing Probe Selection for Fault Localization In Proceedings of Distributed Systems Operation and Management[END_REF]31), TOP [START_REF] Zhao | Towards efficient large-scale vpn monitoring and diagnosis under operational constraints[END_REF]41) and TOP [START_REF] Zhao | Towards efficient large-scale vpn monitoring and diagnosis under operational constraints[END_REF]59) is smaller than the overhead of the hybrid localization scheme solutions for TOP [START_REF] Maitreya | Probabilistic fault diagnosis using adaptive probing[END_REF]18). It is worth to recall that the hybrid localization solutions for TOP [START_REF] Maitreya | Probabilistic fault diagnosis using adaptive probing[END_REF]18) are exact solutions. This confirms that i) the heuristic succeeds to minimize the localization costs, i.e., the monitor cost and the probe cost, jointly; ii) the heuristic outperforms the hybrid localization scheme, since the former can localize anomalies in large topologies using less resources that those used by the latter to localize anomalies in smaller topologies.

We finally evaluate the impact of the number and the quality of candidate monitoring paths on the quality of the localization solution. To this end, we compare the localization solutions obtained using the proposed heuristic, i.e., Algorithm 1 and Procedure 2, to the localization solutions obtained using Algorithm 1 and a procedure that computes candidate paths randomly (instead of Procedure 2). In the latter case, we variate the number of paths explored per one execution of the random candidate path computation procedure (0.015%, 0.03%, 0.15%, 0.3%). We report the results for TOP [START_REF] Salhi | Localization of single network link-level anomalies[END_REF]59) when α >> β in Figure 6 (The results are essentially the same for the other topologies). Not surprisingly, Figure 6 shows that, when candidate paths are explored randomly, the larger the number of paths explored is the smaller the localization overhead is. Furthermore, it shows that the proposed heuristic achieves smaller overhead than the random approach, thought it explores more than 15 times less paths as shown in Table V. This validates our claim on the correlation between the number and quality of monitoring paths and the quality of the localization solution.

X. DISCUSSION

The anomaly localization solution must be updated whenever the detection solution changes. However, the detection solution changes in rare cases where a persistent anomaly makes a network link unavailable for a long period of time, or where the network topology is modified voluntary (e.g., add and/or removal of network equipments).

Usually, in the first case, the detection solution is updated partially. Only the detection paths that are affected by the anomaly are re-computed. The anomaly scenarios are updated accordingly, and the localization solution is re-computed, The correctness proof of Conditions ( 11), ( 12) and ( 13) is based on (ii), (iv) and (v). According to [START_REF] Brodie | Optimizing Probe Selection for Fault Localization In Proceedings of Distributed Systems Operation and Management[END_REF], when minli = 0, a good path must have a zero localization indicator and a probe cost that subordinates minP c. Therefore, according to (ii), all paths having a prefix that satisfies [START_REF] Bejerano | Robust monitoring of link delays and faults in IP networks[END_REF] are not good; and according to (iv), all paths having a prefix that satisfies [START_REF] Zhao | Towards efficient large-scale vpn monitoring and diagnosis under operational constraints[END_REF] are not good. Further, according to (v), regardless the value of minli, the localization indicator of any path having a prefix that satisfies (13) dominates minli. Subsequently, according to [START_REF] Brodie | Optimizing Probe Selection for Fault Localization In Proceedings of Distributed Systems Operation and Management[END_REF], any path having a prefix that satisfies (13) is not good.

Corollary 1 :Fig. 1 :

 11 Fig. 1: Illustrative network topology, (a), and an associated detection solution, (b).

  E} Let α be the weight associated to the monitor cost, and let β be the weight associated to the probe cost. α, β ∈ R. The input into the ILP is an instance of the graph G = (E, M, P, A, δ PE , δ PM , C E , C M , α, β). The objective function minimizes the sum of the monitor cost and the probe cost. It reads as follows:

  For each facility location i ∈ F , we create two nodes labeled by m i1 and m i2 . For each i ∈ F and for each j ∈ D, we create one link connecting m i1 to n j1 , labeled by e 1 ij , and one link connecting m i2 to n j2 , labeled by e 2 ij . We obtain a graph G = (E, N ), where N = {n ik ; i ∈ D, k ∈ [1; 3]} ∪ {m jk ; i ∈ F, k ∈ [1; 2]}, and E = {e jk ; j ∈ D, k ∈ [1; 3]}∪{e k ij ; i ∈ F , j ∈ D, k ∈ [1; 2]}. An example of a graph constructed out of a facility location instance with four facility locations and four clients is shown in Figure 2.

Fig. 2 :

 2 Fig. 2: Example of a graph constructed out of a facility location instance with four facility locations and four clients The candidate monitor location set is M = {m jk ; i ∈ F, k ∈ [1; 2]}. The set of anomaly scenarios is A = {a j ; j ∈ D}. The set of candidate localization paths is P = {p ij ; i ∈ F , j ∈ D}, where p ij is the non-looping path between m i1 and m i2 that crosses the links e 1 ij , e j1 and e 2 ij . The monitor deployment costs are defined as follows: C mi1 = C mi2 = f i /2. The link measurement costs are defined as follows: C ei1 = C ei2 = 0, C e 1 ij = C e 2 ij = d ij /2. The remaining input parameters can be inferred easily from G, M, A and P as follows:

′I

  be the facility location solution constructed out of S ′ * R(I) . We have Cost(S * I) = Cost(S R(I) ) < Cost(S ′ * R(I) ) = Cost(S ′ I), leading to a contradiction. Using the same arguments, we can show that the solution to the facility location instance constructed out of an optimal solution to the anomaly localization instance is optimal.

Algorithm 1 : 7 9 Clear 13 p

 17913 Monitor location and path selection algorithm for single anomaly localization Pcostmin ← INT MAX; lcmax ← 0; CP ← ∅; 2 SM ← {selectRandomElement(M)}; Remove the selected monitor location from M; 3 while (M ̸ = ∅) do 4 Reset ms ← N ull; 5 foreach (m ∈ M) do 6 if (( lcmax = nbP airs and βPcostmin ≤ αCm)) then Jump to line 5; Reset lc ← 0; Reset Pcost ← 0; 8 for (a ∈ A) do Pa; Clear Ma; 10 j ← 1; s (0) ← 1; S a(j) ← CandidatePathSelection(m, SM, G, S (j) a , CP); lc += ∑ 1≤k≤s (j) lc(p a(j) , S (j)k a ); 14 Pcost += P robeCost(p a(j) , CE ); 15 l ← 1;

=

  S a ∩ p a[START_REF] Agrawal | Diagnosing linklevel anomalies using passive probes[END_REF] and S (1)2 a = S a -{S a ∩ p a(1) }. According to Theorem 1, p a(1) distinguishes between every pair of links (e 1 , e 2 ) such that e 1 ∈ S (1)1 a and e 2 ∈ S (1)2 a

( 1

 1 )1 a pairwise and between the links of S (1)2 a pairwise. Hence, a path that maximizes lc(p, S (1)1 a ) + lc(p, S (1)1 a

5 if

 5 (li < limin or (li = limin and probeCost(pc, CE ) < Pcmin)) then 6 limin = li; Pcmin = probeCost(pc, CE ); ps = q; node-to-path(m, pc); 10 depthFirst (m, pc){ 11 foreach (n ∈ children(m, G) and (m, n) / ∈ pc) do 12 add-node-to-path(n, pc); a ) < limin or (li(pc, S (j) a ) = limin and probeCost(pc, CE ) <= Pcmin)) then 16 ps ← pc; limin ← li(pc, S (j) a ); Pcmin = probeCost(pc, CE ); 17 if (limin = 0 and Pcmin = 0) then 18 /*Stop the algorithm*/ Jump to line 31; = 0 and (probeCost(pc, CE )+li(pc, S (j) a )limin >= Pcmin or ∃ S

  and probeCost(p c , C E ), respectively, if the following condition is true: n ∈ SM and(li(p c , S (j) a ) < li min or (li(p c , S (j) a ) = li min and

| / 2

 2 (j)k a ∩ p c |≤| S (j)k a and probeCost(p c , C E ) + min e∈E C e li(p c , S (j) a ) ≥ Pc min (12) li(p c , S (j) a ) > li min and ∀S

o c e d u r e 1 AvgFig. 4 :

 14 Fig.4: Localization costs for TOP[START_REF] Maitreya | Probabilistic fault diagnosis using adaptive probing[END_REF]18)

Fig. 5 :o c e d u r e 1 Fig. 6 :

 516 Fig. 5: Localization cost of the heuristic solutions, α >> β

∩∩

  We have P robeCost(q) = ∑ e∈p C e = ∑ e ∈ p c C e + ∑ e∈e∈q\pc C e = probeCost(p c ) + ∑ e∈q\pc C e ≤ probeCost(p c ) + min e∈E C e * | q | -| p c | p |. Hence, P robeCost(q) ≤ probeCost(p c ) + min e∈E C e * ∑ k a ∩ q | -| S (j)k a ∩ p c |. Further, ∀S (j)k a | S (j)k a ∩ p c |>| S (j)k a | /2, thus, according to (iii), P robeCost(q) ≤ probeCost(p c ) + min e∈E C e * li(q, S (j) a ) -li(p c , S (j) a ) (v) ∀S (j)k a ∈ S (j) a | S (j)k a ∩ p c |≥| S (j)k a | /2 ⇒ li(q, S (j) a ) ≥ li(p c , S (j) a )Proof: According to (i), p c |. Therefore, according to (iii), (v) is true.

TABLE I :

 I Sets of suspect links for all potential anomalies

	Anomalous link	Set of suspect links
	(0, 1)

TABLE II :

 II Anomaly scenarios

	Anomaly scenario	Set of suspect links
	a1	Sa 1 = {(0, 2), (1, 3), (1, 7)}
	a2	Sa 2 = {(0, 6), (5, 6), (4, 5), (2, 4), (1, 2)}
	a3	Sa 3 = {(1, 5), (0, 5), (0, 3), (2, 6), (6, 7)}
	a4	Sa 1 = {(0, 4), (1, 4)}
	created for all links that have the same set of suspect links, i.e.,
	an anomaly scenario is created for each distinct set of suspect

links. Let us denote by A the set of all anomaly scenarios, and let S a denotes the set of suspect links associated to the anomaly scenario a ∈ A. Let dS = {S a , ∀a ∈ A}. dS have the following properties.

Corollary 4:

  -1;

	21	if (lcmax = nbP airs and (αCm + β(PCost
		+	s (j+1) ∑	ThMinPCost(S a (j+1)l	) +
		∑	l=1
				a ′ ∈A,a
	29	end
	30	end
	34	end
	35
	36	end
	37	if (ms = N ull) then return ({SPa, SMa}; ∀a ∈ A) ∪
	38	Update CP ←		SPa;
				a∈A

′ >a ThMinPCost(S a ′ )) ≥ 22 αCm s + βPcostmin)) then 23 /*Stop the exploration of the current candidate monitor location*/ 24 Jump to line 5; 25 end 26 Add the end nodes of p a(j) to Ma; 27 Add p a(j) to Pa; 28 j ← j + 1; 31 if (lc > lcmax or (lc = lcmax and αCm + βP cost < αCm s + βPcostmin)) then 32 ms ← m; lcmax ← lc; 33 Pcostmin ← P Cost; SPa ← Pa; SMa ← Ma; 39 Add ms to SM; Remove ms from M; 40 end 41 return ({SPa, SMa; ∀a ∈ A});

TABLE III :

 III Summary of the topologies considered in the evaluation

	Topology	Nb. of nodes	Nb. of links
	TOP(8, 18)	8	18
	TOP(10, 31)	10	31
	TOP(12, 41)	12	41
	TOP(15, 59)	15	59
	TOP(20, 80)	20	80

  ∀e 1 , e 2 ∈ S; ∀p ∈ P Z p ≤ δ pn Y n ; ∀p ∈ P, ∀n ∈ M

	′

TABLE IV :

 IV Average ILP computation time for TOP[START_REF] Maitreya | Probabilistic fault diagnosis using adaptive probing[END_REF]18)

		Hybrid scheme	Our scheme
	Offline Computation Time	64.16 s	6.67 s
	Online Computation Time	25.7 10 -3 s	0 s

TABLE V :

 V Heuristic computation time (all computations are done offline) and percentage of paths explored in one execution of Procedure 2

	Topology	Heuristic computation	% of paths explored in one
		time	execution of Procedure 2
	TOP(8, 18)	0.00023 s	1.22%
	TOP(10, 31)	0.08 s	0.21%
	TOP(12, 41)	0.78 s	0.07%
	TOP(15, 59)	24.11 s	0.02%
	TOP(20, 80)	3525.52 s	0.007%

This work was supported by Alcatel-Lucent Bell Labs, France, under the grant n. 09CT310-01

The monitors used for anomaly detection are deployed such that all the network links are covered by at least one monitoring paths. They can not necessarily localize all potential anomalies

These parameters are not to be confused with the monitor cost weight (α) and the probe cost weight (β) introduced in Section VI. Their values equal the values used by Waxman to generate network topologies[START_REF] Waxman | Routing of Multipoint Connections[END_REF].

partially, for the affected anomaly scenarios. The evaluation results show that, for instance, the average computation time of the localization solution for one anomaly scenario using the heuristic is in the order of 5 minutes for TOP (20,80). Knowing that anomalies are rare events, we assert that it is rather unlikely that anomalies occur before the localization solution is updated. However, in case an anomaly occurs before the localization solution is updated, the localization process could be executed for the current solution, though, not all anomalies could be localized accurately. The best solution for such situation is to provide backup detection and localization solutions. However, this issue is out of the scope of this paper.

Furthermore, voluntary network changes are usually planned in advance. Thus, detection and localization updates could be computed offline before voluntary network changes are made.

XI. CONCLUSION

In this paper, we addressed the problem of localizing single link-level anomalies. Two findings were presented and demonstrated: 1) Not all pairs of the network links need to be distinguishable for localizing all potential link-level anomalies, 2) All potential anomaly scenarios can be derived offline from any detection solution that covers all the network links. These findings were exploited to develop an anomaly localization scheme that computes full localization solutions offline. In order to achieve a good trade-off between the number and locations of monitoring devices and the quality of monitoring paths, monitor locations and monitoring paths are selected jointly. A novel anomaly localization cost model is proposed, and the localization scheme is formulated as an ILP. However, it is demonstrated that the problem is N P-hard. Therefore, an efficient heuristic is proposed. The proposed scheme is compared with an hybrid anomaly localization scheme that combines the strengths of two existing schemes through extensive simulations. Results demonstrate the superiority of the proposed anomaly localization scheme, and the efficiency of the heuristic solution. Our ongoing work is on extending the proposed scheme to localize multiple link-level anomalies.

APPENDIX A

This section presents the proofs of corollaries 2, 3, 4, 5 and 6.

| S(i) || S(j) |

Proof: According to Corollary 1, only links that belong to same set of suspect links need to be distinguishable pairwise. Therefore, the set of link pairs that are to be distinguished can be expressed as {{(e i , e j ); e i , e j ∈ E} -{(e i , e j ); S(e i ) ̸ = S(e j )}}. We conclude that dP airs = AllP airs -

Clearly, the number of pair of links that need to be distinguishable equals the number of all link pairs of the network if and only if the number of distinct sets of suspect links equals 1, i.e. the number of detection paths equals 1.

APPENDIX B

This section presents the proof of Theorem 3.

Proof: Paths in P ′ can be divided into three subsets of paths.

• P 1 : paths that cross either e 1 or e 2 , but not both.

• P 2 : paths that cross both e 1 and e 2 .

• P 3 : paths that neither cross e 1 nor e 2 . On the one hand, we have ∀p ∈ P 2 , δ pe1 = 0 and δ pe2 = 0. Thus, ∀p ∈ P 2 , (δ pe1 + δ pe2 -2δ pe1 δ pe2 ) = 0. Contributing to ∑ p∈P2 (δ pe1 + δ pe2 -2δ pe1 δ pe2 ) > 0. On the other hand, we have ∀p ∈ P 3 , δ pe1 = 1 and δ pe2 = 1. Thus, ∀p ∈ P 3 , (δ pe1 + δ pe2 -2δ pe1 δ pe2 ) = 0. Contributing to

). Now, we have ∀p ∈ P 1 δ pe1 + δ pe2 = 1 and δ pe1 δ pe2 = 0. Thus,

This section presents the proof of Theorem 5.

Proof: Let P ′ be a set of paths that can distinguish between all links of S. According to Theorem 1, for each e 1 , e 2 ∈ S ∃p ∈ P ′ such that p crosses either e 1 or e 2 , but not both. Thus, at most one link of S is not traversed by paths in P ′ . We conclude that any localization solution must imperatively monitor | S | -1 links of S in order to distinguish between all links. It follows that the localization solution that incurs the minimal probe cost is a solution that monitors exactly | S | -1 links of S whose have the lowest measurement costs. Thus, T hM inP cost(S) = ∑ e∈S C e -max e∈S C e . Note that such a solution is feasible only if each link of the | S | -1 links is monitored separately, which requires to have monitors deployed on the end nodes of each of these links.

APPENDIX D

This section presents the proof of Theorem 6.

Proof:

We have max p∈P lc(S (j) a , p) = ∑


Miguel A Fernández
email: miguel.fernandez@inria.fr

Mikel Landajuela
email: mikel.landajuelaarma@inria.fr

Numerical Analysis/Mathematical Problems in Mechanics

published or not. The documents may come

A fully decoupled scheme for the interaction of a thin-walled structure with an incompressible fluid Miguel Angel Fernández, Mikel Landajuela

Introduction

Fractional-step schemes have been widely used in incompressible fluid-structure interaction as a way to avoid the infamous added-mass numerical instabilities featured by conventional explicit coupling schemes (which invoke the fluid and solid solvers only once per time-step). The resulting time-marching procedures are semi-implicit in the sense that they combine either a fractional-step method in the fluid [START_REF] Fernández | A projection semi-implicit scheme for the coupling of an elastic structure with an incompressible fluid[END_REF][START_REF] Quaini | A semi-implicit approach for fluid-structure interaction based on an algebraic fractional step method[END_REF][START_REF] Badia | Splitting methods based on algebraic factorization for fluid-structure interaction[END_REF] or in the solid [START_REF] Guidoboni | Stable loosely-coupled-type algorithm for fluid-structure interaction in blood flow[END_REF][START_REF] Fernández | Incremental displacement-correction schemes for incompressible fluid-structure interaction: stability and convergence analysis[END_REF][START_REF] Fernández | Explicit Robin-Neumann schemes for the coupling of incompressible fluids with thin-walled structures[END_REF] with an implicit-explicit treatment of the interface conditions. These methods guarantee different degrees of fluid-solid splitting in the time-marching, via an explicit treatment of either the fluid viscous contributions or the solid (visco-)elastic contributions, without compromising stability.

In this note, we consider the case of the coupling with a thin-walled structure and propose to go further in the time-splitting of the coupled system by combining both approaches. The resulting schemes enable (for the first time) a fully decoupled computation of the entire fluid-solid state (velocity, pressure, displacement). We present an a priori energy estimate which guarantees (added-mass free) unconditional stability. The accuracy of the methods is illustrated in a numerical benchmark. The results show that one of the variants preserves the optimal convergence rate.

A linear fluid-structure model problem

We consider a low Reynolds regime and assume that the structure undergoes infinitesimal displacements. The fluid is described by the Stokes equations in a fixed domain Ω ⊂ R d (d = 2, 3), with boundary partitioned as ∂Ω = Γ ∪ Σ, where Σ stands for the fluid-structure interface. The structure is assumed to behave as a linear thin membrane represented by the (d -1)-manifold Σ. The coupled problem reads then as follows: find the fluid velocity u :

Ω × R + → R d , the fluid pressure p : Ω × R + → R, the solid normal displacement η : Σ × R + → R and the solid normal velocity η : Σ × R + → R such that          ρ f ∂ t u -divσ(u, p) = 0 in Ω, divu = 0 in Ω, σ(u, p)n = -p Γ n on Γ, u • τ = 0 on Σ, (1)
         u • n = η on Σ, ρ s ǫ∂ t η + L v η + L e η = -(σ(u, p)n) • n in Σ, η = ∂ t η in Σ, η = 0 on ∂Σ, (2)
complemented with the initial conditions u(0) = u 0 , η(0) = η 0 and η(0) = η0 . Here, ρ f and ρ s stand for the fluid and solid densities, ǫ for the solid thickness, ε(u) def = 1 2 ∇u + ∇u T for the fluid strain rate tensor, µ for the fluid dynamic viscosity, σ(u, p) def = -pI + 2µε(u) for the fluid Cauchy stress tensor, p Γ for a given inlet/outlet pressure and n and τ for the exterior unit normal and tangent vectors on ∂Ω. The differential operators L e and L v describe the viscoelastic behavior of the structure. Though simplified, problem (1)-( 2) features some of the main numerical issues that appear in complex non-linear fluid-structure interaction problems involving a viscous incompressible fluid (see, e.g., [START_REF] Causin | Added-mass effect in the design of partitioned algorithms for fluid-structure problems[END_REF]).

Time semi-discretization: fully decoupled time-marching

In this section we introduce a time discretization of the coupled problem (1)-( 2) which enables a fully decoupled sequential computation of the fluid-solid state (u, p, η). The main idea consists in combining an overall fractional-step time-marching in the system with a specific splitting of the fluid-structure interface coupling. The fluid problem (1) is discretized using a standard Chorin-Temam scheme as follows (see, e.g., [START_REF] Guermond | An overview of projection methods for incompressible flows[END_REF]):

   ρ f ũn -u n-1 δt -2µdivε(ũ n ) = 0 in Ω, ũ • τ = 0 on Σ, (3)
           ρ f u n -ũn δt + ∇p n = 0 in Ω, divu n = 0 in Ω, p n = p Γ on Γ, u n • τ = 0 on Σ. (4)
In [START_REF] Causin | Added-mass effect in the design of partitioned algorithms for fluid-structure problems[END_REF] we perform the following three-step Yanenko splitting, with a specific treatment of the fluid-solid kinematic and kinetic coupling,

   ũn • n = ηn-1 3 on Σ, ρ s ǫ ηn-1 3 -ηn-1 δt = -(2µε(ũ n )n) • n in Σ, (5)
   u n • n = ηn-2 3 on Σ, ρ s ǫ ηn-2 3 -ηn-1 3 δt + L v η⋆ + L e η ⋆ = p n in Σ, (6)
           ρ s ǫ ηn -ηn-2 3 δt + L v ( ηn -η⋆ ) + L e (η n -η ⋆ ) = 0 in Σ, ηn = η n -η n-1 δt in Σ, η n = 0 on ∂Σ. (7)
The superscript ⋆ indicates zeroth-(i.e., without) or first-order extrapolation from the previous time-steps. Hence, the solid displacement and velocity extrapolations considered in ( 6) and ( 7) are either (η ⋆ , η⋆ ) = 0 or (η ⋆ , η⋆ ) = (η n-1 , ηn-1 ). Some remarks are in order. The traditional velocity/pressure splitting of the Chorin-Temam scheme (3)-( 4) is preserved via the splitting of the viscous and pressure contribution of the interface fluid stress in steps ( 5) and [START_REF] Fernández | Explicit Robin-Neumann schemes for the coupling of incompressible fluids with thin-walled structures[END_REF]. Added-mass free stability is simply guaranteed (see Proposition 3.1 below) by treating implicitly the coupling between the fluid pressure/incompressibility and the solid inertia, that is, by simultaneously solving steps (4) and [START_REF] Fernández | Explicit Robin-Neumann schemes for the coupling of incompressible fluids with thin-walled structures[END_REF]. At last, the extrapolation of the viscoelastic solid contributions, in steps ( 6) and [START_REF] Guermond | An overview of projection methods for incompressible flows[END_REF], is performed to control the perturbation of the kinematic coupling, which dramatically affects accuracy (see Section 4 below, and [START_REF] Fernández | Explicit Robin-Neumann schemes for the coupling of incompressible fluids with thin-walled structures[END_REF]).

The resulting time-marching scheme is detailed in Algorithm 1. The standard 'Neumann' solid sub-step (10) is obtained by simply adding the relations (5) 2 , (6) 2 and (7) 1 . We have eliminated u n-1 in (3) via (4) 1 , and the projection sub-step (4) is reformulated as a pressure-Poisson problem. It is worth noting that, since the structure is thin, the simultaneous solution of (3) and (5) (resp. ( 4) and ( 6)) is embedded into the single sub-step (8) (resp. ( 9)) through explicit Robin conditions. The pressure-Poisson problem [START_REF] Pironneau | Freefem++[END_REF] has a rather intrinsic nature, independent of the viscoelastic contributions involved in [START_REF] Fernández | Explicit Robin-Neumann schemes for the coupling of incompressible fluids with thin-walled structures[END_REF]. In fact, from the relations (10) 1 and (8) 2 , we can infer that L v η⋆ + L e η ⋆ = p ⋆ + ρ s ǫ δt (ũ ⋆ • n -η⋆ ), which yields a purely algebraic relation in terms of ũ⋆ , p ⋆ and η⋆ , with (ũ ⋆ , p ⋆ , η⋆ ) = 0 or (ũ ⋆ , p ⋆ , η⋆ ) = (ũ n-1 , p n-1 , ηn-1 ). In practice, this means that modifications in the solid equation only affect the solid sub-step in Algorithm 1.

The following result states the energy based stability of Algorithm 1, whose proof can be found in the forthcoming work [START_REF] Fernández | Fractional-step time-marching schemes for the coupling of incompressible fluids with thin-walled structures[END_REF]. Proposition 3.1 Assume that p Γ = 0 (free system). The following a priori energy estimate holds for n ≥ 1:

E n + D n <    E 0 if (η ⋆ , η⋆ ) = (0, 0), E 0 + δt 2 2 Σ η0 L e η0 + δt 2 2ρ s ǫ L v η0 + L e η 0 2 L 2 (Σ) if (η ⋆ , η⋆ ) = (η n-1 , ηn-1 ),
where the total semi-discrete energy and dissipation are defined by

E n def = ρ f 2 u n 2 L 2 (Ω) + ρ s ǫ 2 ηn 2 L 2 (Σ) + 1 2 Σ η n L e η n , D n def = n m=1 δt 2µ ε(ũ m ) 2 L 2 (Ω) + Σ ηm L v ηm .
Algorithm 1 Time semi-discrete fully decoupled scheme (for (1)-( 2)) (i) Fluid viscous sub-step: find ũn :

Ω → R d such that            ρ f ũn -ũn-1 δt -2µdivε(ũ n ) = -∇p n-1 in Ω, (2µε(ũ n )n) • n + ρ s ǫ δt ũn • n = ρ s ǫ δt ηn-1 on Σ, ũn • τ = 0 on Σ. (8)
(ii) Fluid projection sub-step (pressure-Poisson formulation): find

p n : Ω → R such that            - δt ρ f △ p n = -div(ũ n ) in Ω, p n = p Γ on Γ, δt ρ f ∂p n ∂n + δt ρ s ǫ p n = δt ρ s ǫ p ⋆ + ũ⋆ • n -η⋆ on Σ. (9)
(iii) Solid sub-step: find η n : Σ → R and ηn : Σ → R such that

           ρ s ǫ ηn -ηn-1 δt + L v ηn + L e η n = -(σ(ũ n , p n )n) • n in Σ, ηn = η n -η n-1 δt in Σ, η n = 0 on ∂Σ. (10)

Numerical experiment

In order to illustrate the accuracy of the proposed schemes, we consider the well-known example of the propagation of a pressure-wave within an elastic tube (see, e.g., [START_REF] Fernández | Incremental displacement-correction schemes for incompressible fluid-structure interaction: stability and convergence analysis[END_REF]). We couple the 2D Stokes equations with a 1D generalized string model, L e η = -c 1 ∂ xx η + c 0 η and L v η = -βc 1 ∂ xx η + αρ s ǫ η in [START_REF] Causin | Added-mass effect in the design of partitioned algorithms for fluid-structure problems[END_REF]. The fluid domain is given by the rectangle Ω = [0, 6] × [0, 0.5] and the interface by the segment Σ = [0, 6] × {0.5}, all the units are given in the CGS system. At x = 0 we impose a sinusoidal pressure of maximal amplitude 2 × 10 4 during 5 × 10 -3 seconds, corresponding to half a period. Zero pressure is enforced at x = 6 and a symmetry condition is applied on the lower wall y = 0. The fluid physical parameters are given by ρ f = 1.0, µ = 0.035. For the solid we have ρ s = 1.1, ǫ = 0.1, α = 1, β = 10 -3 , c 1 = Eǫ/(2(1 + ν)) and c 0 = Eǫ/(0.25(1 -ν 2 )), with Young's modulus E = 0.75 × 10 6 and Poisson's ratio ν = 0.5. Piece-wise affine continuous finite elements are used for the discretization in space. The computations have been performed with FreeFem++ [START_REF] Pironneau | Freefem++[END_REF].

Figure 1(left) reports the time-convergence history of the solid displacement at time t = 0.015, in the relative elastic energy-norm, obtained with Algorithm 1 and a fully implicit first-order scheme. The reference solutions have been generated with the implicit scheme using a high space-time resolution. We have refined both in time and in space according to (δt, h) = {5 • 10 -4 /2 i , 10 -1 /2 i } 4 i=0 . In Figure 1(right) we show a comparison of the solid displacements at time t = 0.015, obtained with i = 3. The results show that the proposed fully decoupled scheme with first-order extrapolations is able to retrieve the optimal first-order convergence rate of the implicit scheme. A sub-optimal overall rate is obtained without viscoelastic extrapolation.

Figure 1 .

 1 Figure 1. Left: displacement convergence history in time, h = O(δt). Right: displacement at time t = 0.015s.

.

1 . This work has been supported by the french National Research Agency (ANR) through the EXIFSI project (ANR-12-JS01-0004).


E Jacques

L Ni

A C Salaün

R Rogel

L Pichon

Polysilicon Nanowires for chemical sensing applications

Polycrystalline silicon nanowires are synthesized using a classical fabrication method commonly used in microelectronic industry: the sidewall spacer formation technique. Assets of this technological process rest on low cost lithographic tools use, classical silicon planar technology compatibility and the possibility to get by direct patterning numerous parallel nanowires with precise location on the substrate. Grounded and suspended polycrystalline silicon nanowires with a curvature radius as low as 150nm are integrated into resistors and used as gas (ammonia) sensors. Results show potential use of these nanowires for charged chemical species detection with an increase of the sensitivity with the increase of SiNWs exchange surface with the environment.

INTRODUCTION

Semiconducting nanowires are currently attracting much attention as promising components for future nanoelectronic devices such as nanowire field effect transistors [1], photonic and optoelectronic devices [2], and as chemical or biological sensors [3][4][5]. As their surface can be sensitive to charged species combined with their high surface to volume ratio, silicon nanowires (SiNWs) are the subject of intense research activities for high sensitivity chemical sensor fabrication. The first application of SiNWs in biological and chemical molecule sensor was reported by Lieber's group in 2001 [3]. In addition, because SiNWs synthesis is compatible to the established Si technology, enormous research efforts to design and develop new generation of high performance biological and chemical sensors by incorporating the SiNWs as the functional sensitive units are performed. Indeed, SiNWs based sensor integration will allow a lower manufacturing cost, in addition to the advantageous electronic features of embedded detection and signal processing in silicon technology. The intrinsic reliability of the well-known semiconductor CMOS (Complementary Metal Oxide Semiconductor) process also guarantees a reproducible and reliable diagnosis.

SiNWs can be prepared by one of two approaches, "top-down" and "bottom up". In a bottom up strategy the individual base elements (atoms, molecules…) of the system are linked together to form larger subsystems. Synthesis methods most developed are layer-by-layer self assembly [6], Vapor Liquid Solid (VLS) and Solid Liquid Solid (SLS) growth techniques [7,8], and use of matrix template [9]. The main drawbacks of these synthesis methods for a 3 D integration are the difficulty in control of size and positioning of the nanowires. In this case, nanowires need to be selectively collected and manipulated to be assembled in a planar layout.

The "top down" approach starts from bulk materials and scales down the patterned areas. In this way, several advanced nanopatterning techniques were developed such as e-beam [10], atomic force microscopy (AFM) [11,12], deep UV [13] and nanoimprint lithographies [14,15], to obtain SiNWs. The main drawbacks of these advanced lithographic tools with nanometer size resolution rest on the high cost generated, and more generally the low throughput capability unsuitable with mass production.

In this study, we present a direct patterning technique to get SiNWs planar arrays by conventional optical lithography, compatible with the existing planar CMOS silicon technology. Such SiNWs are promising active building blocks for gas (ammonia) sensors.

EXPERIMENTAL DETAILS

.

Spacer polycristalline SiNWs fabrication

The key fabrication steps of the polycrystalline silicon NWS are illustrated in figure 1. At first, a dielectric film A is deposited and patterned into islands by conventional UV lithography.

Then, a polycrystalline silicon layer is deposited by low pressure chemical vapor deposition (LPCVD) technique and plasma etched by anisotropic reactive ion etching (RIE). Accurate control of the polycrystalline silicon layer RIE rate leads to the formation of nanometric size sidewall spacers that can be used as nanowires. The feasibility of these polyscrystalline silicon NWs with curvature radius as low as 50 nm was previously demonstrated [16]. This method allows the fabrication of parallel SiNWs network

SiNWs based devices fabrication

Two types of devices used as gas (ammonia) sensors are fabricated as illustrated schematically in figure 2: grounded or suspended SiNWs based resistors. For each type of resistor, the fabrication of spacer polycrystalline SiNWs follows step described in the figure 1.

Next, a highly in-situ doped polycrystalline silicon layer is deposited by LPCVD technique at 550°C in the amorphous state and crystallized by thermal annealing at 600°C and patterned by At first, a flow of nitrogen is injected continuously into the chamber and the current measurement as a function of time is started. After the current stabilizes, a flow of ammonia is injected with the chosen ratio of NH 3 /N 2 . After a certain period of time exposure, the gases injection is cut off. Then, the mixture gas of NH 3 /N 2 is evacuated to get back to the environment at the initial state. During the whole period of measurement, the mixture of gas NH 3 /N 2 is exchanged all the time whereas the concentration of the gases is constant. This means that the dynamic protocol is suitable to detect a certain concentration of gases flowing through a fixed space.

The potential use of SiNWs as sensitive units to ammonia detection is checked by measuring the detector response, S g , defined as:

I I - I R R - R S g g g g = = (1)
where R (I) and R g (I g ) are the resistance (current) values for devices under nitrogen and reactive ambient respectively.

DISCUSSION

-11

I (A) V (V)
grounded SiNWs suspended SiNWs The sensitivity of the SiNWs to ammonia species is reported in the figure 5 for the measurement of detection response, S g , with a bias voltage of 0.5V at room temperature. Upon exposure to ammonia electrical resistance decreases because ammonia species act as donor of electrons (reducing agents) at the SiNWs surface [17]. As the ammonia gas molecules adsorption occurs at the SiNWs surface, electrons are transferred to the SiNWs crystal core. Such interactions induce significant changes in the carriers transport along the nanowires and thus for SiNWs electrical resistance in different possible cumulative ways. First, as the SiNWs conductance can be modulated by an applied voltage [17,18], positively charged gas molecules (electron donors) bonded on SiNWs surface can modulate their conductance by changing the volume of the conductive layer. In this case, ammonia may act as chemical gates. In other words, it means that the Fermi level of the Si nanowires is shifted reducing the sample electrical resistance.

The higher chemical response for the suspended based resistors is related to the higher exchange surface of the SiNWs with the environment. In this case, for a constant gas mixture, a higher exchange SiNW surface allows a higher number of bonded ammonia molecules on the SiNWs surface leading to a higher electrons concentration taking part to carriers transport into the SiNWs.

CONCLUSIONS

Based on this nanospacer method, 2D polycrystalline SiNW arrays can be fabricated, at low-temperature (<600°C), by direct patterning technique using classical lithographic tools, compatible with established silicon technology. Results show that such SiNWs can be used as potential sensitive units for integrated gas (ammonia) sensors applications operating at room temperature. Such SiNWs based sensor integration will allow a lower manufacturing cost, in addition to the advantageous electronic features of embedded detection and signal processing in CMOS silicon technology.

In addition, thanks to silicon surface functionalization possibilities, such results offer a great potential for further developments of integrated SiNWs based (bio)chemical sensors .

Figure 1 .

 1 Figure 1. Fabrication of polycrystalline silicon NWs by the sidewall spacer formation technique

Figure 2 .

 2 Figure 2. Grounded (a), suspended (b) SiNWs based resistors

Figure 3 shows

 3 Figure3shows SEM pictures of grounded and suspended polycrystalline silicon

Figure 3 .

 3 Figure 3. SEM pictures of: (a) grounded (after [16]), (b) suspended spacer polycrystalline

Figure 4 .

 4 Figure 4. I-V characteristics of grounded and suspended polycrystalline SiNWs based resistors.

Figure 5 .

 5 Figure 5. Variations of the detector response versus time under controlled ammonia (350ppm)

ACKNOWLEDGMENTS

This work was supported by the Agence Nationale de la Recherche (France) with the Project Sena (ANR-09JCJC-0072-01).