Gilles Bertrand

Samer Lahoud

Miklós Molnár

Géraldine Texier

Inter-Domain Path Computation with Multiple Constraints

Keywords: Inter-domain routing, multi-constrained path computation Routage inter-domaine, calcul de chemin soumis à plusieurs contraintes

The interest for providing services with performance guarantees across domain boundaries has driven recent technical solutions allowing the computation of constrained inter-domain paths. The computation of optimal paths subject to multiple constraints is an NP-complete problem for which efficient exact solutions exist in the intra-domain case. However, these solutions cannot be used for inter-domain path computations, because of confidentiality and scalability constraints. Thus, the present paper investigates the problem of computing inter-domain paths subject to multiple constraints. We describe the information exchanges required between the domains for optimal computations. We extend existing algorithms for inter-domain computations, and describe new heuristics approximating exact solutions. We propose an exact solution, named pID-MCP, allowing the precomputation of path segments in the domains. After proving the correctness and the complexity of exact solutions, we evaluate by simulation the performance of the algorithms and the heuristics proposed. Our solutions allow the computation of inter-domain paths subject to multiple constraints without breaking the confidentiality constraints of the domains. Moreover, the heuristics can be used in large-scale networks.

Computing inter-domain paths subject to multiple constraints has long been considered as impracticable because of scalability and confidentiality constraints. Thus, in the Internet, inter-domain routing is mainly based on connectivity and domain policies. The computation of constrained inter-domain paths has become a highly regarded topic in the last decade, to provide more control on routing to the operators and to enable the delivery of services with quality of service (QoS) across domain boundaries. There are several propositions for extending the inter-domain routing protocol of the Internet, the Border Gateway Protocol (BGP), with QoS capabilities (see for instance [3,[START_REF] Howarth | End-to-end quality of service provisioning through inter-provider traffic engineering[END_REF][START_REF] Quoitin | A performance evaluation of BGP-based traffic engineering[END_REF][START_REF] Xiao | QoS extension to BGP[END_REF][START_REF] Xu | MIRO: Multi-path Interdomain ROuting[END_REF]). However, modifying BGP is difficult, because this protocol is widely deployed.

Recent initiatives propose solutions based on Multiprotocol Label Switching (MPLS) for allowing the computation of constrained inter-domain paths without breaking the confidentiality constraints of the domains [START_REF]IPSphere Framework Technical Specification[END_REF][START_REF] King | Path Computation Architectures Overview in Multi-Domain Optical Networks Based on ITU-T ASON and IETF PCE[END_REF]. The present paper pertains to this recent stream of work. Our goal is to investigate the problem of computing inter-domain paths following a predetermined domain sequence and subject to multiple constraints. We call this problem Inter-MCP. We show that the present solution to the problem Inter-MCP [5,[START_REF] Vasseur | A Backward Recursive PCEbased Computation (BRPC) Procedure to Compute Shortest Constrained Inter-domain Traffic Engineering Label Switched Paths[END_REF] sometimes forbids to solve it exactly, because the tree structure used for exchanging information between the domains does not include enough data. Thus, we describe the information that the domains must exchange for solving the problem Inter-MCP exactly.

The computation of a path subject to multiple constraints related to independent additive link-weights is an important, but difficult, problem. This problem arises for example when computing a path satisfying the constraints of an application (e.g., short mouth-to-ear delay for telephony) and the constraints of the network (e.g., traffic engineering objectives). It is called the multi-constrained path (MCP) problem. The problem MCP is NP-complete [START_REF] Wang | Quality-of-Service Routing for Supporting Multimedia Applications[END_REF]. Nevertheless, recent work shows that most of its instances in telecommunication networks can be solved exactly [START_REF] Kuipers | The impact of correlated link weights on QoS routing[END_REF][START_REF] Van Mieghem | Concepts of exact QoS routing algorithms[END_REF]. Several exact solutions are described in the literature (e.g., SAMCRA [START_REF] Van Mieghem | Hop-by-hop quality of service routing[END_REF], H_MCOP [START_REF] Korkmaz | Multi-constrained optimal path selection[END_REF]). These algorithms solve the problem MCP inside a domain.

This work explains why the solutions of the intra-domain MCP problem cannot be used to solve the problem Inter-MCP. Consequently, we adapt these solutions. We prove the resulting algorithms and compute their worst-case complexity. In particular, the present paper describes an exact solution allowing the precomputation of path segments by the domains crossed by a path. This solution has two desirable properties, considering that the problem Inter-MCP is NP-complete. First, it divides the path computation operations into per-domain computations. Second, it reuses the path segments computed, independently of the sequence of domains crossed. We derive heuristics approaching with a tunable accuracy the exact algorithms proposed. We evaluate the performance of the exact algorithms and the heuristics in a realistic scenario, as well as in extreme cases, which allows us to illustrate the trade-offs among the solutions proposed and improves our understanding of the problem considered.

The remainder of the paper is organized as follows. In Section 2, we introduce the technological context of this study. Section 3 describes the MCP problem and related intradomain solutions. In Section 4, we discuss the limitations of present solutions for inter-PI n 1902 domain path computations. Section 5 introduces the extension of exact intra-domain MCP algorithms for problem Inter-MCP, proves the exact algorithms proposed and derives efficient heuristics approaching them. Finally, we evaluate our solutions to the problem Inter-MCP in Section 6.

2 Inter-Domain Routing and Path Computation

General Scenario and Assumptions

In this work, we consider the path computation problem across multiple domains and subject to multiple constraints. For the purpose of this document a domain consists of an Autonomous System (AS) that resides under a single path computation responsibility. In each domain, the nodes that interconnect to other domains are called Border Nodes (BN). Path computation across multiple domains typically occurs when the source and the destination nodes of the path belong to different domains. The entity that is responsible for the path computation can be the source node, the intermediate BNs, or dedicated computation elements such as the Path Computation Element (PCE) [START_REF] Farrel | RFC 4655: A Path Computation Element (PCE)-Based Architecture[END_REF]. Several computation models exist based on the different computation entities. A path computation entity uses its own vision of the state of the domains in order to output a path that connects the source and the destination nodes and satisfies the given constraints. An objective function may also be optimized during the computation procedure. Thus, the efficiency of one computation model depends on the amount of information that is available on the computation entities. This is a key issue for the inter-domain path computation due to the limited information that is spread outside the domain borders [START_REF] Farrel | RFC 4726: A Framework for Inter-Domain Multiprotocol Label Switching Traffic Engineering[END_REF]. Particularly, resource and topology information is considered to be confidential for each domain and may be hidden from other domains.

In this work, we assume that the path computation problem follows a preliminary step that determines the sequence of traversed domains. Precisely, we consider computing a path between source and destination nodes, subject to multiple constraints, and traversing a pre-computed sequence of domains. This assumption follows a compromise between the quality and the complexity of the global solution. On the one hand, the computation of the sequence of domains and the computation of the path itself can be thought as a joint optimization problem. This approach should capture both the constraints and the objectives of the two components. For instance, computing the sequence of domains is mainly subject to policy and business constraints whereas computing the path is subject to performance constraints. This increases the complexity of the joint optimization and makes the search for efficient solutions a big challenge. On the other hand, the computation of the sequence of domains can be performed in advance of the path computation. This approach enables to capture the specificity of the two computation tasks, though it does not guarantee to reach global optimal solutions. In the following, we consider that the sequence of domains is precomputed outside of the scope of our study and focus on the subsequent path computation problem. Thus, in all the following occurrences, an optimal path is implicitly defined for a pre-computed sequence of domains.

Irisa

Inter-Domain Path Computation with Multiple Constraints

In order to illustrate the general path computation problem across multiple domains, let us consider the scenario in Figure 1. In this figure, node A in domain X is trying to communicate with node B in domain Z. A path, subject to a set of constraints, should be computed to enable nodes A and B to communicate. According to the assumptions presented above, a preliminary sequence of domains is computed, i.e. domains X,Y, and Z, fulfilling some policy or business constraints. Hence, the path computation problem consists of computing a path from A to B traversing successively domains X, Y, and Z. This computation can be performed by the source node A if it has sufficient topology or resource information on the three domains. Otherwise, the path computation can be distributed on the intermediate border nodes, or offloaded onto dedicated per-domain entities such as PCEs. For instance, when the domains X, Y, and Z belong to a single management organization, one computation entity may have sufficient information to perform end-to-end efficient computations. Otherwise, when these domains belong to concurrent organizations, topology and resource information may not be spread outside the domain border. Thus, the computation result is less efficient unless some collaboration is introduced between perdomain computation entities.

Domain Visibility

In order to compute a constrained path crossing multiple domains, a computation entity needs to gather information about each domain crossed. The optimality of the computation depends on the amount of gathered information. Thus, three scenarios are defined depending on the domain visibility level: multi-domain visibility, partial visibility and local domain visibility [START_REF] Farrel | RFC 4726: A Framework for Inter-Domain Multiprotocol Label Switching Traffic Engineering[END_REF]. First, in a multi-Domain visibility scenario, the computation entity may have sufficient visibility of the topology for all of the domains crossed by the constrained path. Thus, the computation entity may compute and provide the entire path. However, achieving this information scenario may not be practical given the requirement that a domain should never

PI n 1902

Bertrand & Lahoud & Molnár & Texier advertise resources and topological information outside its boundaries.

Second, in a partial visibility scenario, the computation entity has full information about its own domain, and has information about the connectivity between domains as well as resource availability across other domains. However, it does not have full visibility of the topologies inside other domains. Consequently, the computation entity is not able to provide, a fully specified strict explicit path from source to destination. It can still supply some useful information such as the path to reach its domain boundary, abstract nodes to replace intermediate domains or a loose hop for the destination.

Third, in a local domain visibility scenario, the computation entity has full visibility of its own domain and connectivity information only as far the BN of the local domain. In this case the computation entity computes an explicit path that comprises explicit hops to reach the local BN and a loose hop identifying the destination.

In this work, we consider a local domain visibility scenario, where each computation entity has full visibility of its own domain. This choice reflects the limitations imposed by network operators on topology and resource information related to their domain. This information is considered confidential, thus is not spread outside the domain borders. However, the local domain visibility scenario compromises the optimality of the computation due to lack of information. One solution to remedy this problem consists of implementing a collaboration between computation entities in each domain. Such collaboration should not violate the aforementioned inter-domain limitations, though it may restore the optimality of the computation. The level of collaboration enables to introduce different computation models as defined in the following section.

Path Computation Models

Depending on the localization of the computation entities, two basic computation models may be defined: per-domain path computation and PCE-based computation.

Per-domain Path Computation

Per-domain computation [START_REF] Vasseur | RFC 5152: A Per-Domain Path Computation Method for Establishing Inter-Domain Traffic Engineering (TE) Label Switched Paths (LSPs)[END_REF] applies where the inter-domain path cannot be or is not determined at the source node. This is most likely to arise owing to visibility limitations. The path through each domain, possibly including the choice of exit point from the domain, must be determined within the domain.

The per-domain path computation technique involves the computation of individual path segments in every intermediate domain without the sharing of any path information from other domains. The complete path is obtained by concatenating the path segments that are computed for every domain. Figure 2 illustrates a simple scenario of per-domain path computation. The source node computes the first path segment to a selected exit BN. The second path segment is then computed for the second domain by this BN to the next nearest exit BN.

Irisa

PCE-Based Computation

As standardized in [START_REF] Farrel | RFC 4655: A Path Computation Element (PCE)-Based Architecture[END_REF], the PCE is an entity responsible for computing an inter-domain path upon receiving a request from a path computation client (PCC). In most cases, the source node serves as the PCC. When a new path computation request arrives, the PCC forwards the path computation request to a selected PCE using PCC-to-PCE communication [START_REF] Vasseur | Path Computation Element (PCE) Communication Protocol (PCEP)[END_REF]. A PCE may compute the end-to-end path itself if enough topology and resource information is available to it. Furthermore, the PCE architecture provides mechanisms for the resolution of path computation requests when an individual PCE does not have sufficient visibility.

For example, a PCE may cooperate with other PCEs to determine intermediate loose hops, or a full explicit path.

Backward Recursive PCE-based Computation

Path computation across domains is particularly difficult when the visibility of a source node is restricted only to the local domain. As introduced in [START_REF] Vasseur | A Backward Recursive PCEbased Computation (BRPC) Procedure to Compute Shortest Constrained Inter-domain Traffic Engineering Label Switched Paths[END_REF], the Backward Recursive PCE-Based Computation (BRPC) utilizes multiple PCEs to compute the shortest inter-domain constrained path along a determined sequence of domains. This technique also preserves confidentiality across domains, an important requirement when domains are managed by different service providers [START_REF] Farrel | RFC 4726: A Framework for Inter-Domain Multiprotocol Label Switching Traffic Engineering[END_REF]. The BRPC procedure is backward, as the path is computed starting from the destination domain to the source domain. It is recursive since the same basic sequence of steps is repeated for every intermediate domain lying between the source and destination. Consider a pre-computed sequence of D domains denoted by V 1 to V D where V 1 represents the source domain and V D the destination domain. BRPC uses the concept of a virtual shortest path tree (VSPT). VSPT(i) with 1 ≤ i ≤ D denotes the multipoint-to-point (MP2P) tree formed by the set of constrained shortest paths from the entry BNs of domain i to the destination node. Each link of tree VSPT(i) represents a shortest path. The BRPC procedure is as follows. For the destination domain V D , VSPT(D) is computed from the

PI n 1902

Bertrand & Lahoud & Molnár & Texier list of shortest paths from all the entry BNs to the destination node. This is illustrated in Figure 3. VSPT(D) is then sent to the PCEs in the previous domain D -1 where it is concatenated to their topology and resource information database. The updated database is then used by the PCEs in domain D -1 to compute VSPT(D -1). This sequence of operations is repeated until the source domain and, subsequently, the source node of the path are reached, as shown in Figure 3. The general problem of computing paths subject to several additive constraints (e.g., a maximum propagation delay D and a maximum number of hops H) is called the multi-Irisa constrained path (MCP) problem. The problem of finding a feasible multi-constrained path that is optimal with respect to a length function is called the multi-constrained optimal path (MCOP) problem [START_REF] Kuipers | An overview of constraintbased path selection algorithms for QoS routing[END_REF]. MCP and MCOP problems consider additive constraints only, because, first, constraints related to bottleneck metrics (e.g., bandwidth) can be easily treated by edge pruning and, second, positively-valued multiplicative constraints can be transformed into additive constraints by using a logarithm function. The MCP and MCOP problems are NP-complete if the additive metrics are considered to be independent [START_REF] Wang | Quality-of-Service Routing for Supporting Multimedia Applications[END_REF].

The MCP and MCOP problems can be defined more formally, as follows. We consider a network represented by a directed graph G = (V, E) where V is the set of vertices or nodes and E the set of edges or links. Each edge l ∈ E is associated with K additive weights1 w k (l) ∈ R + , k = 1..K. We assume that at least one of the K weights associated with an edge l is different from zero. We define a path as a finite sequence of adjacent edges denoted by p = (s, i), (i, j), . . . , (k, t) . The set of paths between two nodes s ∈ V and t ∈ V is denoted as P s→t . Each path p is associated with K weights denoted as w k (p) ∈ R + and defined by w k (p) ≡ l∈p w k (l), k = 1..K. Moreover, a length function c(p) is associated with the path p subject to K constraints related to the weights considered and denoted as W k , k = 1..K. The most appropriate path length function, defined in Reference [START_REF] Van Mieghem | Hop-by-hop quality of service routing[END_REF], expresses the critical value of the path with respect to the constraints:

c(p) = max i=1..K w i (p) W i (1)
Intuitively, the expression for c(p) means that the path that is the furthest from violating the constraints is selected. With this path length measure, a path p is feasible if and only if c(p) ≤ 1. Hereafter, we formally define the two fundamental problems that are used in this work, namely MCP and MCOP.

Problem. MCP -Multi-Constrained Path Problem [START_REF] Korkmaz | Multi-constrained optimal path selection[END_REF][START_REF] Kuipers | An overview of constraintbased path selection algorithms for QoS routing[END_REF] Given a source s and a destination t, K constraints W k , k = 1..K, find a path p ∈ P s→t such that w k (p) ≤ W k , for k = 1..K.

Any solution of the problem MCP is called a feasible path.

Problem. MCOP -Multi-Constrained Optimal Path Problem [START_REF] Korkmaz | Multi-constrained optimal path selection[END_REF][START_REF] Kuipers | An overview of constraintbased path selection algorithms for QoS routing[END_REF] Given a source s and a destination t, K constraints W k , find a feasible path p * ∈ P s→t such that for every other feasible path p ∈ P s→t , c(p * ) ≤ c(p).

Exact and Approximated Intra-Domain Solutions

An overview of multi-constrained path computation methods is provided in Reference [START_REF] Kuipers | An overview of constraintbased path selection algorithms for QoS routing[END_REF]. Exact solutions for the MCP problem include brute-force solutions (e.g., depth first search with backtracking). Several brute-force algorithms including search-space reduction mechanisms have been described in the literature (e.g., SAMCRA [START_REF] Van Mieghem | Hop-by-hop quality of service routing[END_REF], H_MCOP [START_REF] Korkmaz | Multi-constrained optimal path selection[END_REF]). Due to

Bertrand & Lahoud & Molnár & Texier the computational intractability of the MCP and MCOP problems, the time complexity of brute-force algorithms grows exponentially, in the worst-case. Thus, several approximation algorithms have been described. For example, Jaffe's algorithm [START_REF] Jaffe | Algorithms for finding paths with multiple constraints[END_REF] is an approximation algorithm addressing the MCP problem with two constraints. This algorithm determines two positive multipliers d 1 and d 2 , and optimizes the length function d 1 w 1 (p) + d 2 w 2 (p).

According to [START_REF] Kuipers | An overview of constraintbased path selection algorithms for QoS routing[END_REF], Jaffe's algorithm can be extended to an arbitrary number of constraints.

In Reference [START_REF] Kuipers | The impact of correlated link weights on QoS routing[END_REF][START_REF] Van Mieghem | Concepts of exact QoS routing algorithms[END_REF], Kuipers and Van Mieghem assert that the NP-complete behavior of the MCP problem emerges only in specially constructed graphs with edge weights carefully chosen. Thus, exact QoS routing algorithms seem feasible in practice.

A standard strategy for computing a path subject to several additive constraints involves optimizing a single measure of the path length. This measure of the path length can be defined as a composition function of the original weights considered. If the weights considered are positively-correlated, a linear composition function p → k=1..K d k w k (p), with d k ∈ R + may be used (e.g., Lagrangean-based linear composition, Jaffe's algorithm [START_REF] Jaffe | Algorithms for finding paths with multiple constraints[END_REF]). However, in the general case, non-linear composition functions like the one defined in Equation 1(e.g., TAMCRA [6], SAMCRA [START_REF] Van Mieghem | Hop-by-hop quality of service routing[END_REF], H_MCOP [START_REF] Korkmaz | Multi-constrained optimal path selection[END_REF]) provide better results according to an evaluation performed by Korkmaz and Krunz in Reference [START_REF] Korkmaz | Multi-constrained optimal path selection[END_REF].

The difficulty of computing a shortest path with respect to a non-linear length function resides in the property that segments of an optimal path are not necessarily optimal. Thus, it is not sufficient to remember a single shortest path segment to each intermediate node, as is done when considering a single linear path length function (see the counter-example in Figure 4 explained in Section 4). A guaranteed optimal solution for the MCP problem remembers all intermediate segments. The best existing algorithms try to keep track of as few intermediate path segments as possible. This implies memorizing only k-shortest paths to intermediate nodes (e.g., TAMCRA [6,[START_REF] De Neve | TAMCRA: a tunable accuracy multiple constraints routing algorithm[END_REF]), memorizing non-dominated feasible paths only (e.g., SAMCRAv1 [START_REF] Van Mieghem | Hop-by-hop quality of service routing[END_REF] and H_MCOP [START_REF] Korkmaz | Multi-constrained optimal path selection[END_REF]) or using predictions of end-to-end cost to avoid memorizing path segments of infeasible paths (e.g., H_MCOP, MPMP [START_REF] Shin | A multiconstraint QoS routing scheme using a modified Dijkstra's algorithm[END_REF], SAMCRAv2 [START_REF] Van Mieghem | Concepts of exact QoS routing algorithms[END_REF]).

Problems of the Current Approaches

The purpose of this work is to devise solutions for the computation of inter-domain paths subject to several constraints. In this section, we show, first, that MCP and MCOP algorithms cannot be applied for inter-domain path computations and, second, that current inter-domain approaches are not applicable for exact MCP computations.

Limitations of MCP Algorithms

In communication networks, domains (e.g., ASes) usually are independent, preserve the confidentiality of their topology and compute paths autonomously. Due to these constraints, multi-constrained path computation solutions which do not consider the segmentation of the network into domains are not acceptable for inter-domain path computations. For Irisa example, SAMCRA relies on a queue containing shortest path segments to all intermediate nodes. Thus, all domains involved in the computation of a path have access to information about path segments in other domains, which is usually unacceptable for confidentiality and scalability reasons. Consequently, we investigate methods for multi-constrained interdomain path computation that fulfill autonomy, scalability and confidentiality constraints.

Limitations of Inter-Domain Path Computation Methods

With the per-domain method, the end-to-end path is a concatenation of segments computed independently by the domains. Thus, it cannot guarantee to compute an optimal (shortest) constrained inter-domain path. Furthermore, it cannot be efficiently used to compute a set of inter-domain diversely routed TE LSPs [START_REF] Vasseur | A Backward Recursive PCEbased Computation (BRPC) Procedure to Compute Shortest Constrained Inter-domain Traffic Engineering Label Switched Paths[END_REF].

The current version of the Internet draft describing the BRPC procedure states that with this procedure, optimal end-to-end paths across a predetermined sequence of domains can be computed [START_REF] Vasseur | A Backward Recursive PCEbased Computation (BRPC) Procedure to Compute Shortest Constrained Inter-domain Traffic Engineering Label Switched Paths[END_REF]. In this assertion, optimal means that the path selected is the same as if the computations were performed in a single domain. However, when several additive constraints are considered, the VSPT structure described in Reference [START_REF] Vasseur | A Backward Recursive PCEbased Computation (BRPC) Procedure to Compute Shortest Constrained Inter-domain Traffic Engineering Label Switched Paths[END_REF] sometimes forbids to find a feasible path when it exists, because it contains at most a single shortest path from each entry border node to the destination (tree structure). Figure 4 illustrates this problem. In this figure, the weight vectors are indicated close to the edge to which they apply. We compute a path between s and t, considering the constraints (W 1 , W 2 ) T = (4, 4) T , which means that both weights w 1 (p) and w 2 (p) of the path p selected must be lower or equal to 4. The shortest path computation procedure inside each domain considers the path length measure used by SAMCRA [START_REF] Van Mieghem | Hop-by-hop quality of service routing[END_REF] and H_MCOP [START_REF] Korkmaz | Multi-constrained optimal path selection[END_REF] (Equation 1). A single shortest path (solid line) from the domain border router a to the destination t is included in the VSPT. Its length is given by max 2 4 , 2 4 = 1 2 . The shortest path from s to t using this segment has a length equal to 5 4 > 1. Thus, the BRPC procedure is not able to find a feasible path, whereas, the optimal path from s to t has a length equal to 4 4 = 1 and thus, is feasible. But this path cannot be found using the BRPC procedure because it includes a non-shortest path segment (dotted line, length 3 4 ) between a and t going through b and this path segment is typically not included into the VSPT. Figure 4: An example of non optimal multi-constrained path computation with the BRPC procedure Neither the per-domain method, nor the BRPC method computes inter-domain paths subject to multiple constraints exactly. Thus, we investigate a more accurate methods

PI n 1902

Bertrand & Lahoud & Molnár & Texier approximating the optimal solution. Due to the aforementioned limitations of the perdomain method, we focus on extending the BRPC method.

5 Extensions for Inter-Domain Path Computation

Information Required for Exact Inter-Domain MCP Computations

We focus on describing algorithms solving the MCP problem for inter-domain path computations. With this purpose, we extend the BRPC procedure [START_REF] Vasseur | A Backward Recursive PCEbased Computation (BRPC) Procedure to Compute Shortest Constrained Inter-domain Traffic Engineering Label Switched Paths[END_REF] for enabling the computation of optimal inter-domain paths subject to multiple constraints. The counter-example in Figure 4 demonstrates that, for exact computations, the VSPT structure described in Section 2.3.2 must sometimes include more than a single shortest path per entry border node2 . Despite its name, such extended VSPT is not necessarily a tree. We evaluate the performance gain brought by including into the VSPT several paths from each ingress to the destination. The extension of the VSPT considered does not require any further change of the PCE protocol than the ones introduced in Reference [START_REF] Vasseur | A Backward Recursive PCEbased Computation (BRPC) Procedure to Compute Shortest Constrained Inter-domain Traffic Engineering Label Switched Paths[END_REF] and is fully backwardcompatible with the BRPC procedure. We assume that the PCE protocol supports the additive constraints considered in this work. As explained in Section 3.2, segments of shortest paths with respect to a non-linear length function are not necessarily optimal. Thus, the VSPT must be able to store more than a single shortest path between each ingress and the destination. However, during the computation of a multi-constrained path not every path must be memorized at intermediate nodes. First, as positive weights are considered, infeasible paths segments do not have to be memorized [START_REF] De Neve | TAMCRA: a tunable accuracy multiple constraints routing algorithm[END_REF].

Lemma. If a path segment p 1 is infeasible with weights w k (p 1 ), k = 1..K, then the weights w k (p) of any path p using p 1 are such that w(p) ≥ w(p 1 ), thus p is infeasible.

Second, dominated paths do not have to be memorized [START_REF] De Neve | TAMCRA: a tunable accuracy multiple constraints routing algorithm[END_REF][START_REF] Van Mieghem | Concepts of exact QoS routing algorithms[END_REF], which means that every path p such that there is a path p ′ verifying w k (p ′ ) ≤ w k (p), ∀k = 1..K and such that there is a i ∈ [1..K] for which w i (p ′ ) < w i (p) does not need to be considered.

Lemma. If a path segment p 1 with weights w k (p 1 ), k = 1..K is dominated by a path p 2 with weights w k (p 2 ), then any path p using p 1 is dominated by the path p ′ obtained by replacing p 1 by p 2 in p, thus p is non-optimal.

Figure 5 illustrates the concept of dominance. In this figure the paths represented by circles are non-dominated, whereas the one represented by a square (p 4 ) is dominated by p 2 , because p 2 is better than p 4 for all weights considered (w k (p 2 ) ≤ w k (p 4 ), for k = 1..K) and strictly better with respect to at least one weight (w 1 (p 2 ) < w 1 (p 4 )). Figure 6 extends the example presented in Figure 4 assuming that all feasible nondominated paths are included in the VSPT. Thus, the source s learns both paths to the Figure 5: Non-dominance with K=2 destination t and is able to select the shortest end-to-end path. Considering the same constraint vector as before: (4, 4)

T , s selects the path segment with cost (3, 1)

T leading to a feasible path.

Extended MCP Algorithms

In this section, we focus on the extension of MCP algorithms for inter-domain path computation. Let us define the problem Inter-MCP as follows:

Problem. Inter-MCP -Given a sequence S = V 1 , . . . , V D of domains, a source node s ∈ V 1 , a destination node t ∈ V D and a set of K constraints W k , k = 1.
.K, find a feasible path from s to t following the sequence of domains S.

Any solution to the problem Inter-MCP must compute a multi-constrained path from the source s ∈ V 1 to at least one of the nodes of V 1 connected to a node in V 2 . This means that to solve the problem Inter-MCP, a NP-complete problem must be solved. Thus, the problem Inter-MCP is NP-complete.

In the following, we start by detailing the adaptation steps of SAMCRA and H_MCOP for Inter-MCP and introduce a new algorithm called ID-MCP. Then, we detail the algorithmic steps of ID-MCP and illustrate it by a step-by-step example.

Adaptation of the Principles of SAMCRA and H_MCOP

ID-MCP is a direct adaptation of existing algorithms to solve the Inter-MCP problem. ID-MCP uses the same principles as SAMCRA [START_REF] Van Mieghem | Hop-by-hop quality of service routing[END_REF] and H_MCP [START_REF] Korkmaz | Multi-constrained optimal path selection[END_REF] for reducing the search-space. We have adapted these principles to the specificities of inter-domain path PI n 1902 computations. We have not implemented the use of cost predictions (look-ahead [START_REF] Van Mieghem | Concepts of exact QoS routing algorithms[END_REF]) for excluding segments of non-feasible path in the first version of our algorithm. ID-MCP performs shortest path computations with respect to the cost function of SAMCRA given by c(p) = max i=1..K ( wi(p) Wi ) for a path p and returns feasible paths (c(p) ≤ 1). Unlike SAMCRA or H_MCOP, ID-MCP is able to compute inter-domain paths while preserving the confidentiality of topology and resource information, as detailed in Section 4. ID-MCP adopts the principle of the BRPC method described in Reference [START_REF] Vasseur | A Backward Recursive PCEbased Computation (BRPC) Procedure to Compute Shortest Constrained Inter-domain Traffic Engineering Label Switched Paths[END_REF] for segmenting end-to-end path calculations into per-domain segment computations. This segmentation implies that, in each domain, shortest paths from several nodes (the border nodes connected to the previous domain) to the destination must be computed. However, SAMCRA and H_MCOP do not compute a multi-constrained path from multiple sources to one destination. Particularly, H_MCOP is designed to compute paths between two nodes only, namely the source and the destination [START_REF] Korkmaz | Multi-constrained optimal path selection[END_REF], whereas, SAMCRA can be used to compute paths from one source to several destinations [START_REF] Van Mieghem | Concepts of exact QoS routing algorithms[END_REF]. Thus, we adapt SAMCRA and reverse the direction of its computations. Hence, ID-MCP computes the paths backward from the single destination considered to multiple sources, namely the border nodes connected to the upstream domain.

In the algorithmic steps, we adopt the terminology of SAMCRA: the path computation is based on a queue. In this queue, a path is marked gray if it is selected and black if it is discarded. The paths that are not marked are said to be white. SAMCRA terminates when either a path attached to the destination has been marked gray, or the queue contains no more white elements. ID-MCP must provide all feasible non-dominated path segments to the previous domain. Thus, ID-MCP continues its computations even if all source nodes of an intermediate domain have been associated with a path marked gray. Consequently, in each domain, ID-MCP terminates only when the queue contains no more white elements. If a single path is required, the path computation procedure in the source domain can be stopped as soon as a path from the source has been marked gray.

ID-MCP: Algorithm and Example

A solution to the problem Inter-MCP, called Inter-Domain-MCP (ID-MCP), is presented below, using the notations of Figure 7. In this algorithm, we assume that at most one link exists between any two nodes. The input of the algorithm is a request (source node, destination node, source domain, destination domain, vector of constraints) and a sequence of domains. The sequence of domains crossed by the path is denoted as

S = V 1 , . . . , V D .
During the operations of ID-MCP in each domain, the topology and the state of the links of the domain considered, as well as the state of the links connected to this domain are supposed to be known. The path segment computation procedure in each domain relies on a queue containing the paths memorized. Queue elements are of the following form: (node, predecessor, weights, color). The output of the computations in each domain is a VSPT containing one or several non-dominated virtual paths from the ingresses of the domain to the destination. In the general case each domain may return only a subset of Irisa the paths computed, according to its policies (e.g., a maximum financial cost), but this problem is outside of the scope of this paper. Computations are performed from the destination domain V D to the source domain V 1 as is performed by the BRPC procedure. In the destination domain, the queue is initialized with a white element corresponding to a path to the destination t with a cost equal to zero (line 3). In any other domain V i , the queue is initialized with the paths extracted from the leaves of the VSPT transmitted by the downstream domain V i+1 and a virtual topology is constructed. This virtual topology includes the virtual nodes and virtual links of the VSPT, aggregated to the graph of V i (line 5 of Algorithm 5.1, step 1 of the example in Figure 8). In each domain, the algorithm loops while there is at least one white element in the queue (line 7). During each execution of this loop, a white path with minimum cost is extracted from the queue (line 8) and marked gray (line 9). Then, this path is relaxed (line 10), which means that the neighbors of the node to which this path is attached are visited, and the paths from the neighbors to the destination t are memorized if and only if they are feasible and non-dominated by the ones already in the queue. If some paths in the queue are dominated by a path newly discovered, then, these paths are marked black. Finally, the VSPT is extracted from the queue and transmitted to V i-1 , which means that the paths from the ingresses of V i are transmitted to the upstream domain V i-1 in accordance with the policy of domain V i . In the source domain, extracting the VSPT means that one or several end-to-end paths are retrieved from the final VSPT.

An example appears in Figure 8 and helps to understand the principle of ID-MCP. For more clarity, in this example, only two additive metrics are considered (K=2) and they take integer values. An intermediate domain V i receives a VSPT containing three feasible, nondominated virtual paths to the destination t. V i concatenates this VSPT with its topology (step 1 ) and initializes the computation queue. The paths extracted from the VSPT are initially white. Then, the algorithm enters the loop (steps 2 to 9 ). The path computation operations end when no more white elements are present in the queue. Finally, the VSPT to be transmitted to the upstream domain is extracted and forwarded.

ID-MCP considers the end-to-end constraints for the path segment calculations in each domain to guarantee the optimality of the paths computed. Splitting the constraints between the domains would make more intermediate paths be detected as non-feasible and thus, decrease the complexity of the path computation operations. However, the optimality could not be guaranteed anymore. if

V i = V D then 3:
queue ← {node:dest, predecessor:∅, w:0, color:white} vspt i ← extract_vspt(queue) 13: end for

Proof and Complexity of ID-MCP

Theorem 1. Termination: the algorithm ID-MCP terminates.

Proof. The algorithm ID-MCP marks at least one white path3 during each iteration of its main loop. As the number of paths in each domain is finite and the algorithm stops when all paths have been marked or before, the algorithm terminates.

Theorem 2. Correctness: the algorithm ID-MCP computes all feasible non-dominated inter-domain paths along the sequence of domains V 1 , . . . , V D considered.

Proof. The algorithm ID-MCP is essentially a brute-force algorithm with search-space reduction mechanisms. Thus, we only have to prove that no solution is excluded from the search-space. The proof of SAMCRAv1 in Reference [START_REF] Van Mieghem | Hop-by-hop quality of service routing[END_REF] can be adapted for ID-MCP. Thus, we know that in the destination domain V D all non-dominated feasible paths from the ingresses to the destination t are computed. The same proof also implies that in each intermediate domain, all non-dominated feasible paths from the ingresses to the destination are computed in the virtual graph resulting from the aggregation of the VSPT with the graph of the domain. Thus, we only have to show that the paths computed in this virtual graph correspond to the non-dominated feasible paths from the ingresses to the destination t in the real graph.

A finite recursion shows that ID-MCP computes all non-dominated feasible paths from the source s to the destination t. We assume that all feasible non-dominated paths from every ingress of the next domain V i+1 , i < D to the destination t are included in VSPT i+1 . In domain V i , ID-MCP concatenates the topology of V i with VSPT i+1 . We know that all feasible non-dominated paths between the ingresses of V i and the destination t follow non-dominated path segment between an ingress of V i and t is excluded by considering only the path segments in VSPT i+1 instead of all the paths from domain V i+1 to t, hence, ID-MCP computes all feasible, non-dominated paths from the ingresses of V i (or the source of the request if it belongs to V i ) to the final destination of the paths.

Theorem 3. Worst-case complexity: the worst-case time complexity of the algorithm ID-MCP is in O Dα 2 K(αN

+ E + N 2 )
, where α is the maximum number of paths memorized for a node5 , K is the number of additive link metrics considered, D is the number of domains in the sequence considered, N and E are the maximum number of nodes and the maximum number of edges in a domain of the sequence of domains considered.

Proof. The worst-case complexity of the operations of ID-MCP inside a domain can be shown to follow the same expression as the one of SAMCRAv1 which is in O αN log(αN )+ α 2 KE according to [START_REF] Van Mieghem | Hop-by-hop quality of service routing[END_REF], where α is the maximum number of paths memorized for a node in the queue, N is the number of nodes, K the number of additive link metrics considered and E the number of edges of the single domain considered. However, with ID-MCP the domains are extended by the contents of the VSPT. Thus, the number of nodes to consider is the number N i of nodes of the domain plus the number of ingresses Ingr i+1 of the next domain V i+1 that are represented in the VSPT, plus the destination. Moreover, the number of links to consider is the number E i of edges of the domain, plus the number of inter-domain links between V i and V i+1 , which is bounded by N i • Ingr i+1 and, in addition, the number of virtual edges extracted from the VSPT, which is bounded by α • Ingr i+1 . Hence, the worst-case complexity of the operations of ID-MCP inside a domain is in

O α(N i + Ingr i+1 + 1) • log(α(N i + Ingr i+1 + 1)) + α 2 K(E i + (α + N i ) • Ingr i+1
) . This expression can be simplified into O αN • log(αN ) + α 2 K(αN + E + N 2 ) by introducing the notations of the theorem and noting that Ingr i+1 ≤ N and N i ≤ N . It can be further simplified into O α 2 K(αN + E + N 2 ) by noticing that αN log(αN ) is in O(α 2 N 2 ). The operations of SAMCRA are repeated in every domain along the sequence of domains, thus the complexity is multiplied by the number D of domains crossed. In addition, the operations for the aggregation of the VSPT with the graph of the domain (at most α • Ingr i+1 edges are added), the initialization of the queue (at most α • Ingr i+1 + 1 elements are added) and the extraction of the final VSPT (at most α • N i elements of the queue are considered) must be taken into account. However, all these terms are in O(αN ), which leads to the complexity of the theorem.

Enhancement of ID-MCP

Parallelization and Complexity Reduction (pID-MCP)

ID-MCP does not allow the computation of path segments in parallel in the domains crossed or the precomputation of path segments. Moreover, ID-MCP performs several times similar computations if several non-dominated paths from the same ingress are learned from the VSPT. However, we show that it would be sufficient to compute the non-dominated path segments from each ingress in V i to each ingress of V i+1 mentioned in the VSPT and to add the costs of the virtual edges from the ingresses of V i+1 to t in a final stage. Splitting these two stages allows the domains crossed to perform some path computations operations in parallel or in advance (precomputation). The segments computed can then be combined in a later stage. We have implemented an algorithm implementing these operations. We name this algorithm pID-MCP.

pID-MCP computes the non-dominated path segments from each ingress of a domain to the ingress of the next domain. Thus, the non-dominance comparisons are applied to the paths depending on their destination. For example, a path with weights (4, 4)

T and destination ingress A, does not dominate a path with weights (5, 5)

T and destination ingress B, attached to the same node. Consequently, the elements of the queue must include their destination. Their form evolves to: (node, predecessor, destination, weights, color). In addition, initial weights equal to zero are considered for the elements retrieved from the VSPT received from the downstream domain. Thus, the operations performed by pID-MCP for extracting the VSPT from the queue are different from the operations performed by ID-MCP. The algorithm pID-MCP needs to combine the segments computed in the domain with the virtual edges of the previous VSPT, and to compute the end-to-end weights of the paths computed.

Consider the example in Figure 9 and Figure 10. In this example, ID-MCP performs an approximately two times higher number of calls to its sub-functions compared to pID-MCP. However, the VSPT transmitted by both algorithms is the same. Proof. We know that any feasible non-dominated path is made up of feasible non-dominated segments. Thus, the feasible non-dominated paths from the ingresses of V i to t are made up of one feasible non-dominated segment from an ingress of V i to an ingress of V i+1 and one virtual path of VSPT i+1 . pID-MCP computes all feasible non-dominated segments from the ingresses of V i to the ingresses of V i+1 represented in the VSPT. Moreover, the VSPT includes all feasible non-dominated segments from the ingresses of V i+1 to t. Consequently, in each domain V i , pID-MCP computes all feasible non-dominated paths from the ingresses of V i to the destination t.

Theorem 5. Worst-case complexity: the worst-case time complexity of the algorithm pID-

MCP is in O Dα 2 K(E + N 2 )
Proof. The worst-case time complexity of pID-MCP can be computed as in the proof of Theorem 3. The only differences with this proof are, first, that the number of edges to consider for the operations of SAMCRA is the number E i of edges of the domain, plus the number of inter-domain links between V i and V i+1 , which is bounded by N i • Ingr i+1 and, in addition, the number of virtual edges extracted from the VSPT, which is now bounded by Ingr i+1 , instead of α • Ingr i+1 . Second, the operations for combining the segments computed in domain V i with the edges of VSPT i+1 have to be taken into account. The time complexity of these operations is in

O(α 2 • Ingr i • Ingr i+1 ) which is in O(α 2 N 2 ).
The complexity of pID-MCP can be significantly higher than the one of ID-MCP in two specific situations. First, pID-MCP performs the non-dominance comparisons depending on the destination of each element, thus, in the worst-case, at least one feasible non-dominated path per destination is memorized for each intermediate node. Consequently, if one domain is connected to the next domain through many ingress nodes, a large number of paths may be memorized by pID-MCP. However, in realistic network configurations, the number of nodes connected in a domain connected the another domain is rather limited. Second, pID-MCP considers initial weights equal to zero, thus, less paths may be detected as non-feasible considering the end-to-end constraints.

We expect pID-MCP to decrease the maximum number α of paths memorized for a node compared to ID-MCP and thus to bring a reduction of the computational complexity. α is usually lower with pID-MCP than with ID-MCP, because fewer elements are considered in the initial queue for each domain. Thus, compared to ID-MCP, pID-MCP improves the time and space complexity in certain network configurations.

pID-MCP can easily be adapted to compute segments in each domain in parallel, then combine the elements computed and eventually determine the best path. If path segments are computed in parallel in the domains, the worst-case complexity is in O Kα 2 (E + N 2 ) with the same notations as in Theorem 5. Alternatively, each domain could compute and Irisa advertise6 its elements (the feasible non-dominated paths from its ingresses to the ingresses of its neighboring domains in an alliance of domains) for a few constraint-vectors corresponding to common classes of service. If we assume, that the link weights are relatively static (so that the elements advertised remain valid for a reasonable time). Then, the elements advertised could later be used by the source domain for computing an end-to-end multi-constrained path. The intra-domain paths advertised should not depend on the sequence of domains crossed, and, thus, not depend on the weights of the segments from the next domain to the destination, which explains why we consider initial weights equal to zero. This way, a single execution of pID-MCP in a domains provides all feasible non-dominated path segments for any request inside a class of service (same constraint vector W), independently of the domain sequence crossed.

The proof of Theorem 5 can easily be extended to show that, if pID-MCP is used inside a domain A to precompute paths from the entry BNs of A to the entry BNs of M neighboring domains, then the worst-case complexity of the precomputation operations inside A is in

O Dα 2 K(E + M • N 2 ) .
If the domains compute the path segments sequentially with pID-MCP7 , then the initial weights considered for each ingress a in the VSPT of the next domain (VSPT(i+1)) should be the ones in Equation 2, where E a is the set of elements associated with the ingress a in VSPT(i+1).

This higher initial cost has a positive effect on the computational complexity, because it decreases the number of feasible paths. Exact algorithms like pID-MCP compute all feasible non-dominated paths, which is interesting for balancing the traffic load, especially when the elements advertised by every domain remain valid for relatively long periods and the paths computed use different resources.

Heuristics

In Reference [START_REF] Van Mieghem | Hop-by-hop quality of service routing[END_REF], Van Mieghem, De Neve and Kuipers study the problem of connectionless QoS routing inside a single domain and simulate a MCP computation algorithm on fictitious random topologies. They note that, in their simulations, in about 90% of the cases, a multi-constrained optimal path can be found by a distributed algorithm memorizing a single shortest path only and called hop-by-hop distance based only (HbHDBO) routing8 . Moreover, they note that the cost of the paths computed with HbHDBO routing is close to the optimal. Hence, we describe several heuristics that are expected to provide both excellent performance with respect to the quality of the path computed and a significant reduction of the computational complexity.

We introduce three simplified algorithms. The first is called kID-MCP, k=1. It resembles ID-MCP except for the relaxation of the paths (line 10 of Algorithm 5.1). kID-MCP, k=1 explores the paths of the neighboring nodes and keeps at most one path per node: a single shortest path (SSP) with respect to c. Consequently, kID-MCP, k=1 cannot guarantee exact MCP computations. In each domain, kID-MCP, k=1 performs similar operations as the reverse Dijkstra's algorithm. kID-MCP, k=1 is equivalent to ID-MCP with α = 1, thus kID-MCP, k=1 terminates and the worst-case complexity of kID-MCP, k=1 is in O DK(E + N 2 ) , with the same notations as in Theorem 3. The expressions for the complexity of ID-MCP and pID-MCP include a dependency on α 2 , which indicates that reducing the maximum number α of elements memorized for a node may improve the computational complexity of these algorithms9 , significantly.

In fact, as its name indicates, kID-MCP, k=1 is a special case of the second algorithm named kID-MCP. kID-MCP resembles ID-MCP except that, for each node, at most k elements attached to this node can be memorized in the computation queue. Thus, kID-MCP is an adaptation of TAMCRA [START_REF] De Neve | TAMCRA: a tunable accuracy multiple constraints routing algorithm[END_REF]. The heuristic kID-MCP represent and intermediate cases between the algorithm memorizing every non-dominated feasible path (ID-MCP) and kID-MCP, k=1 (at most one path is memorized for each node). Similarly, we define the algorithm kpID-MCP, which is similar to pID-MCP except that at most k paths are memorized for each node. For kID-MCP and kpID-MCP, the parameter limiting the value of α must be carefully selected. Contrary to the first intuition, kpID-MCP with k > 1 can provide worst results than kID-MCP, k=1 in certain situations, which does not reduce its interest as an approximation of pID-MCP. Consider the example in Figure 11. In this example, kpID-MCP does not find any feasible solution considering the constraints W = (5, 5)

T , whereas kID-MCP, k=1 finds a feasible solution with cost (4, 1)

T + (1, 1) T = (5, 2)

T . This type of situation can be partially avoided by considering the initial weights in Equation 2. The third algorithm is called oID-MCP. It resembles ID-MCP except that it uses the original VSPT structure. This means that with oID-MCP each domain computes all feasible non-dominated segments in the virtual graph, but includes at most a single path from each ingress to the destination into the VSPT. Thus, oID-MCP cannot guarantee exact MCP computations. oID-MCP terminates for the same reason as ID-MCP and it can be proved that its worst-case complexity is in O Dα 2 K(E + N 2 ) . Both pID-MCP and oID-MCP consider at most a single path per ingress of the downstream domain and their worst-case complexity is similar. However, compared to pID-MCP, oID-MCP degrades the quality of the paths computed. Thus, we have not studied oID-MCP any further.

Simulation and Results

Methodology

Topologies

We have compared the performance of the algorithms presented in previous sections through simulations. The performance of most routing algorithms is closely related to the properties (e.g., topology, metrics) of the network to which they are applied. Here, intuitively, the size (number of domains, number of nodes in each domain) and the connectivity (domain degrees, node degrees) of the topologies considered have a strong effect on the performance of the routing algorithms compared. Thus, the topologies considered in the simulations have been carefully selected. A difficulty arising in this selection is that the PCE architecture is not expected to be deployed in the whole Internet but only in small sets of ASes, and the structure of these sets of ASes is not publicly available. Therefore, we have evaluated the performance of our algorithms on two types of topologies. First, we have used the following lattice topologies to assess the performances of the algorithms in extreme configurations. Lattice topologies represent an extreme case for QoS routing algorithms, as described in Reference [START_REF] Kuipers | The impact of correlated link weights on QoS routing[END_REF]. These topologies are square grids in which the top-left node is the source and the bottom-right node is the destination of a request. We consider two topologies based on lattices.

• LatticeFM(N,D) (Full-Mesh) represents a worst-case for the complexity of the algorithms 10 . This topology is a chain of D identical domains, every domain is a grid made up of N nodes and E = 2 √ N ( √ N -1) undirected links. Every node of every domain is connected to every node of the previous domain, as well as to every node of the next domain in the chain.

• LatticeSL(N,D) (Single Link) is similar to LatticeFM(N,D) except that only the topleft node of each domain is connected to the bottom-right node of the previous domain.

Second, we have used more realistic topologies to assess the applicability of our algorithms to real networks.

• A realistic backbone topology including measurements of the networks of eight major Internet service providers in the USA. We refer to this topology as REAL [START_REF] Farrel | RFC 4655: A Path Computation Element (PCE)-Based Architecture[END_REF]. This topology appears in Reference [START_REF] Liljenstam | Development of an Internet backbone topology for large-scale network simulations[END_REF] and is based on topologies measured by Rocket-Fuel [START_REF] Spring | Measuring ISP topologies with Rocketfuel[END_REF], essentially.

• A fictitious inter-area topology named SYM-CORE, which was used in Reference [5].

Link Weights

Random weights have been added to the edges of the topologies considered, except for the topology REAL [START_REF] Farrel | RFC 4655: A Path Computation Element (PCE)-Based Architecture[END_REF], which includes delay estimations. Most simulations have been realized with two weights (K=2). We have not taken any assumption about the kind of additive weights considered: for example, the weights may be related to the number of hops (w l = 1, ∀l ∈ E), to the link propagation delay, to the inverse of the capacity of the links, or to a measure of the reliability of the links. In addition, we have considered additive constraints only: for instance, we have not considered the effect of the capacity of the links, because bandwidth is a bottleneck metric that can easily be treated by edge pruning. We consider that every edge has enough bandwidth to serve the requests considered. This assumption seems reasonable if the largest requests are rejected by an admission control mechanism or if the network considered is overdimensioned. Link weight information is usually advertised through a routing protocol that allocates a fixed number of bits for this information. Thus, link weights can be considered to be bounded by a function of the size in bits of the corresponding field of the routing messages. The bounds on the link weights have been chosen arbitrarily, without any loss of generality, as weights can be considered to be scaled. The number of possible values of the weights has an effect on the number of non-dominated paths and, thus, on the complexity, consequently, we have considered weights with a relatively fine granularity.

The work in Reference [START_REF] Van Mieghem | A scaling law for the hopcount in internet[END_REF] suggests that, in the Internet, the link weights can be modeled using a uniform distribution. In addition, several important papers in the area adopt uniformly distributed weights (e.g., [START_REF] De Neve | TAMCRA: a tunable accuracy multiple constraints routing algorithm[END_REF][START_REF] Korkmaz | Multi-constrained optimal path selection[END_REF][START_REF] Van Mieghem | Hop-by-hop quality of service routing[END_REF]). Hence, we have generated uniformly distributed link weights. We have assumed that the weights of inter-domain links follow the same distribution as the ones of intra-domain links. Constant weights (e.g., number of hops) represent a special case of uniformly distributed weights.

The correlation of the weights w k , k = 1..K is known to have an effect on the complexity of MCP algorithms [START_REF] Kuipers | The impact of correlated link weights on QoS routing[END_REF]. Thus, we have performed both simulations with independent link weights and simulations with positively or negatively-correlated link weights. When we consider correlated weights, we assume that the correlation of the weights is the same in all domains crossed, so that the effect of correlation is visible on end-to-end path computations. The method used for generating correlated weights is inspired by Reference [START_REF] Korkmaz | Multi-constrained optimal path selection[END_REF]: to generate K positively-correlated weights in the interval ]A, B], we partition the interval ]A, B] into

I 0 ≡ A, A + B-A 2 , I 1 ≡ A + B-A 2 , B .
We generate a random weight w 1 . If w 1 is in I 0 then we generate w k , k = 2..K in the interval I 0 , else we generate w k , k = 2..K inside the interval I 1 .

Irisa

Constraints

The value of the end-to-end constraints considered has an effect both on the complexity of ID-MCP and of pID-MCP and on their performance compared to kID-MCP (k=1). For example, if p 1 is a shortest path with respect to w 1 and p 2 a shortest path with respect to w 2 , then the constraints W 1 and W 2 should be selected in the interval w 1 (p 1 ) < W 1 < w 1 (p 2 ) and w 2 (p 2 ) < W 2 < w 2 (p 1 ). If the constraints are chosen outside these intervals, then, either there is no solution, which can be verified with a polynomial complexity, or, a shortest path with respect to a single metric is an evident solution, which can be computed with a polynomial complexity. Reference [START_REF] Kuipers | The impact of correlated link weights on QoS routing[END_REF] investigates the effect of the choice of the constraints.

We know that the exact algorithms will find a solution if one exists. Consequently, we have chosen the constraints to obtain a high rate of success of the path computation procedure, which means that we focus on the cases where a solution exists. We have performed both simulations where the constraints are equally strict in average or where one constraint is stricter than the other. We consider the proportion of the requests for which the exact algorithms find a solution, as well as the value of the cost metric of SAMCRA (Equation 1) for the lowest-cost solutions computed, to determine a posteriori if the constraints are strict or loose. More precisely, loose means that exact algorithms find a solution for every request simulated and at least one solution has a low cost (c(p) ≤ 0.2). Strict means that in average the lowest-cost solutions found by exact algorithms have a high cost (c(p) ≥ 0.8) or a feasible solution exists for less than 60% of the requests simulated.

Weights

uniform distribution with 10 ≤ w k ≤ 1023, k = 1..K or k = 1..K -1; correlated or not; delay estimations and number of hops for REAL(8) Constraints constant during a simulation, fixed depending on a posteriori observation of the rate of success of the computation and the cost of the paths computed Table 1: Parameters used for the generation of the weights and of the requests in the main simulations

Selection of Domain Sequences

We focus on the problem of computing inter-domain paths along predefined domain sequences. In each simulation run, we have selected a source and a destination node in different domains. In the Internet, the sequence of domains followed by traffic from a source to a destination domain is not necessarily the shortest, because this sequence depends on the policies of the domains. However, modeling the policies of each domain explicitly is difficult. Thus, we have rather tried to reproduce the average length of the AS-paths in the Internet. We have considered sequences of three domains, which matches the average domain sequence lengths in the Internet, according to [4]. In the realistic topology, we have computed a shortest domain-sequence between the source and the destination domain and

PI n 1902

Bertrand & Lahoud & Molnár & Texier considered this sequence for the node-level path computation between the source node and the destination node.

Performance Metrics

We denote as M(A) the average value of the metric M for the algorithm A for a batch of simulations. For example, α(pID-MCP) denotes the value of α measured for the algorithm pID-MCP in a set of simulations. Confidence intervals are computed for all performance metrics. When the number of requests simulated is not provided explicitly, this means that it is large enough to provide statistically significant results.

We define the absolute success rate (ASR) as the percentage of success of the algorithms to find a feasible path when a solution exists. The success rate (SR) is the percentage of success of the algorithms to find a feasible path for the requests considered. As ID-MCP and pID-MCP are exact, their ASR is 100%, whereas the ASR of kID-MCP, k=1 or kpID-MCP is not necessarily 100%. The number of paths returned by the algorithms is denoted as NP. Both exact algorithms return all end-to-end feasible non-dominated paths, thus NP(ID-MCP)=NP(pID-MCP). The number of paths returned by kpID-MCP can exceed k, because the segments computed by a domain are combined with the segments in the previous VSPT. Our implementation of kID-MCP, k=1 returns a single path per request.

The cost (C) is the lowest value of the path length function of SAMCRA among the paths computed, thus, it takes the same value for all exact algorithms. We define an additional path length function c ′ as µ i=1..K wi W , where µ denotes the arithmetic mean operator. We call multi-dimensional cost (MC) the value of c ′ for the end-to-end path computed with the lowest value of c ′ . MC helps to evaluate the quality of the paths returned considering all metrics, whereas C indicates their quality with respect to the most restrictive metric. The costs (C and MC) of the paths are taken into account only for the requests for which both heuristics and exact algorithms succeed to find a feasible path, so that the comparison of the algorithms is meaningful.

In accordance with the results in Theorem 3 and Theorem 5, we derive the relative time complexity of the algorithms from the measurement of the maximum number (α) of paths attached to a node and memorized in the computation queue. The value of α provides also an indication of the spatial complexity of the algorithms. By definition, α(kID-MCP, k=1) = 1.

We evaluate the signaling overhead (SO) induced by the algorithms considered. This quantity is evaluated as the number of elements that are carried in the VSPTs exchanged, for a single request. An element represents a single virtual path from an ingress to the destination. With this definition, the overhead is equal for ID-MCP and pID-MCP. Note, however, that the segments precomputed by pID-MCP are expected to be used for several requests.

Evaluation

We have simulated the algorithms ID-MCP, pID-MCP, kID-MCP, k=1 and kpID-MCP (k>1) on various network configurations to assess their performance and to illustrate their Irisa strengths and weaknesses. The scenarios simulated allow us to outline some of the trade-offs of the inter-domain multi-constraint path computation methods described in Section 5.

For more clarity, we define a reference simulation scenario to which all other scenarios are compared. The reference simulation scenario involves positively-correlated weights and its constraints are identical for all weights (W i = W j , 1 ≤ i ≤ K, 1 ≤ j ≤ K). Simulations with independent or negatively-correlated weights use the same constraints as in the reference scenario. We refer to the constraints as strict or loose constraints with respect to the reference scenario.

Effect of Inter-Domain Connectivity

First, we compare the performance of the algorithms on ID-MCP and of the algorithms on pID-MCP on the topologies LatticeFM [START_REF]Sprint. Service Level Agreements[END_REF]3) and LatticeSL [START_REF]Sprint. Service Level Agreements[END_REF]3) presented in Section 6.1.1. This comparison illustrates the effect of the inter-domain connectivity of the domains on the complexity of these algorithms.

On the Lattice topologies considered, the exact algorithms are penalized by a large path diversity that induces an increased time complexity. In particular, the topology Lat-ticeFM [START_REF]Sprint. Service Level Agreements[END_REF]3) is designed to illustrate a drawback of the algorithms based on pID-MCP. In this topology, the number of inter-domain links is extremely large: each domain is connected to the next domain through 625 inter-domain links. As the algorithms based on pID-MCP perform non-dominance comparisons depending on the destination of each element, they memorize many paths if one domain is connected to the next domain through a large number of ingress nodes. The algorithm kpID-MCP limits the number of paths memorized per node, which solves the problem about the complexity. However, the paths memorized must be selected carefully among the many paths available so that the end-to-end path is close to the optimal. The version of kpID-MCP implemented selects k shortest paths considering the length measure defined in Equation 1. Considering larger initial cost (Equation 2) is probably a better solution to this problem, however it is not desirable for precomputing of path segments independently of the sequence of domains considered.

Table 2 presents the results of the simulations for the topologies LatticeSL(25,3) and LatticeFM [START_REF]Sprint. Service Level Agreements[END_REF]3) with loose constraints in the reference scenario. These results illustrate the aforementioned drawback of the methods based on pID-MCP when the inter-domain connectivity is large. As expected, in the LatticeSL topology α(ID-MCP) is greater than α(ID-MCP), whereas in the LatticeFM topology α(ID-MCP) is much lower than α(ID-MCP). This underlines the need for limiting α in the algorithm pID-MCP, which justifies the heuristic kpID-MCP proposed in Section 5.4.2. In the LatticeSL topology kpID-MCP, k=3 provides better results (lower value of C and MC) than kID-MCP, k=1. However, in the LatticeFM topology kpID-MCP, k=3 provides worse results (lower value of C and MC) than kID-MCP, k=1. This problem is solved by allowing larger values of α in kpID-MCP and, if the segments are computed sequentially in the domains, by considering the initial costs in Equation 2.

Table 3 presents the results of the simulations in the same scenario but this time with strict constraints. In this scenario kpID-MCP, k=3 provides better results (lower value of

PI n 1902

Bertrand & Lahoud & Molnár & Texier C and MC, higher value of SR and NP) than kID-MCP, k=1 in the LatticeSL topology. In the LatticeFM topology, kpID-MCP, k=3 and kID-MCP, k=1 provide similar results.

SR [%]

C T for LatticeSL and (400, 400) T for LatticeFM)

Effect of the Strictness of the Constraints

Second, we investigate the effect of the non-feasibility check in the exact algorithms ID-MCP and pID-MCP by simulating either strict constraints or loose constraints in the topologies LatticeSL [START_REF]Sprint. Service Level Agreements[END_REF]3) and LatticeFM [START_REF]Sprint. Service Level Agreements[END_REF]3). ID-MCP considers non-zero initial weights, which allows it to discard several non-feasible paths when the constraints are strict, whereas pID-MCP considers initial weights equal to zero for the virtual nodes. Thus the strictness of the constraints has an effect on the complexity of exact algorithms. We compare the results in Table 2 and in Table 3. In the LatticeFM topology: the values of α are several times smaller with strict constraints than with loose constraints (3.5 times smaller with ID-MCP and even 6.5 times smaller with pID-MCP). These results are explained by the large path diversity in the LatticeFM, which can be drastically reduced when strict constraints are used. With strict constraints, pID-MCP is less penalized by the large inter-domain connectivity of the LatticeFM topology. Typically, the success rate of the path computation procedure, the value of α, as well as the number of paths returned decrease and the cost of the paths computed increases, when the constraints become stricter.

Irisa

Inter-Domain Path Computation with Multiple Constraints 29

Effect of Asymmetric Constraints

Third, we investigate the performance of the heuristics in the topologies LatticeSL [START_REF]Sprint. Service Level Agreements[END_REF]3) and LatticeFM [START_REF]Sprint. Service Level Agreements[END_REF]3) when the constraints are asymmetric (W 1 is large and thus, easily fulfilled, whereas W 2 is more restrictive) and the link-weights are negatively-correlated. The heuristics studied memorize shortest paths with respect to the cost c and thus, select the paths depending on the most restrictive metric. Intuitively, this can lead to non-optimal values of the other metrics for the end-to-end path selected.

Table 4 presents the results of the simulations, which we compare to the results in Table 5 for simulations with symmetric constraints. We have selected the constraints so that the cost C and the success rate SR take similar values in both tables. As expected, the difference between C and MC is larger with asymetric constraints than with symmetric constraints for all algorithms. However, somewhat surprisingly, the difference between the value of MC for the heuristics and for the exact algorithms is smaller with asymetric constraints than with symmetric constraints.

Effect of the Correlation of the Weights

Forth, we investigate the effect of the correlation of the weights on the performance of the algorithms considered. We keep the same constraints as in the reference scenario and simulate requests in the LatticeSL and LatticeFM topologies, but, this time, with negativelycorrelated weights. These simulations are performed because the correlation of the weights is known to affect the number of non-dominated paths. When the weights are positivelycorrelated, a path with a low value for a metric is likely to take a low value for the other metric too: considering two paths p 1 and p 2 , if w 1 (p 1 ) < w 1 (p 2 ), then, it is likely that w 2 (p 1 ) < w 2 (p 2 ). Thus, the number of non-dominated paths is usually low. However, when the weights are negatively-correlated, a path taking a low value for a weight is likely to take a large value for the other constraint. Thus, there are usually more non-dominated paths with negatively-correlated weights than with positively-correlated weights. A higher number of non-dominated paths has a negative effect on the complexity of the path computation algorithms, because more paths need to be memorized.

We compare the results in Table 5 and in Table 2. In the LatticeSL topology, the difference of cost between the results of the exact methods and the results of the heuristics is significantly larger with negatively-correlated weights than with positively-correlated weights. This increased difference certainly comes from the larger number of non-dominated paths with negatively-correlated weights. In addition, the value α and NP for exact methods are much larger with negatively-correlated weights than with positively-correlated weights. In fact, α(ID-MCP) is multiplied by seven and α(pID-MCP) by three, which increases the difference of complexity between these algorithms. Thus, pID-MCP is significantly faster than IP-MCP in this configuration. The difference on α has an effect on the cost of the paths returned by the heuristics too. First, the relative difference of cost between kpID-MCP, k=3 and ID-MCP, k=1 rises from about 1% with positively-correlated weights to 3% with negatively-correlated weights, for the requests considered. Second, the relative

PI n 1902

Bertrand & Lahoud & Molnár & Texier difference of cost between ID-MCP, k=1 and exact algorithms rises from about 2% with positively-correlated weights to 5% with negatively-correlated weights, for the requests considered.

With pID-MCP and kpID-MCP, the segments computed in a domain are combined with the virtual segments of the preceding VSPT. Thus, in the initial queue considered by a domain, the number of paths attached to a virtual node may exceed the maximum value of α allowed. Thus, NP can exceed the number of maximum number of segments attached to the source node (e.g., 3) multiplied by the maximum number of segments attached to the ingresses (e.g., 3) multiplied by the number of ingresses (e.g., 1). This explains why the number of paths (NP=11) returned by kpID-MCP, k=3 in LatticeSL with negativelycorrelated weights and loose constraints exceeds the square of the maximum value of α allowed (3 2 = 9) multiplied by the number of ingresses (1) in the second domain crossed.

The same value of the constraints is usually much stricter with negatively-correlated weights than with positively-correlated weights. For instance, with the loose constraints of the reference scenario, C is approximately 25% larger with negatively-correlated weights than with positively-correlated weights in the LatticeSL topology. This difference is even larger in the LatticeFM topology: C is multiplied by approximately two when negatively-correlated weights are simulated. Moreover, with the strict constraints of the reference scenario no solution exists in the simulation runs performed with negatively-correlated weights.

SR [%]

C Last, we simulate a scenario in the topology REAL [START_REF] Farrel | RFC 4655: A Path Computation Element (PCE)-Based Architecture[END_REF], which represents the topology in the USA of some of the largest operators in the world [START_REF] Liljenstam | Development of an Internet backbone topology for large-scale network simulations[END_REF]. These simulations are used as a demonstration of the applicability of our heuristics on a realistic example. The requests simulated are constrained by a maximum value of the end-to-end one-way speed-of-light propagation delay equal to 100 ms and a maximum number of hops equal to 30. The constraint of 100 ms is feasible according to the service level agreements advertised by Sprint for the USA [START_REF]Sprint. Service Level Agreements[END_REF] and seems reasonable for voice traffic, for example (see Reference [12]). The value of the constraint on the number of hops is set arbitrarily, so that this constraint is loose. The number of hops represents a traffic engineering metric equal to one for every link, which used by operators to minimize the amount of resources used by each request. The two link-weights considered are relatively static11 and thus, segments can be precomputed for the class of service considered. We consider a source-destination domain-pair and we generate twenty source-destination node-pairs. The domain pair considered in the simulations considered leads to a sequence of two domain. In average, the domains are made up of approximately 1000 nodes and 3500 undirected edges. They are connected through eleven undirected links. We compare the quality of the paths computed with kID-MCP, k=1 and kpID-MCP, k=3. In another simulation we compare the results provided by kID-MCP, k=1 and kpID-MCP, k=8. 7: Results of simulations on a realistic topology with a limit on α equal to eight Table 6 and Table 7 describe the results of the simulations. The slight difference between the cost of kID-MCP, k=1 in Table 6 and in Table 7 comes from the relatively low number of random requests simulated. This number is not problem as we are mainly intersted into comparing both heuristics for a common set of requests. In both simulations, the paths computed by kpID-MCP have a slightly higher cost (C and MC) than the paths computed by kID-MCP, k=1. This comes certainly from the relatively large inter-domain connectivity for the sequence of domains considered. The difference of cost between the solutions computed by kpID-MCP and kID-MCP, k=1 decreases slightly when kpID-MCP considers a limit on Bertrand & Lahoud & Molnár & Texier α equal to eight instead of three. More precisely, for the requests considered, the difference of C between kpID-MCP and kID-MCP, k=1 is divided by two when kpID-MCP considers a limit on α equal to eight instead of three. A larger limit on α is required to approach the optimal solutions more accurately. On the one hand, in the simulations, the signaling overhead for the precomputation of the segments with kpID-MCP, k=3 and kpID-MCP, k=8 represent the signaling overhead for three and ten requests with kID-MCP, k=1. On the other hand, in average, kpID-MCP, k=3 and kpID-MCP, k=8 compute eight and forty-nine feasible paths whereas kID-MCP, k=1 returns a single feasible path.

SR [%] C [%] MC

Inter-Area Scenario

We have simulated hundred random requests in the SYM-CORE topology with strict constraints. The results of these simulations are presented in Table 8. They confirm the conclusions presented in previous sections. The path diversity is smaller in this inter-area topology compared to larger inter-domain topologies. Thus, α and NP take low values. In addition, ASR is quite low whereas C is lower than 80%. The simulation scenarios simulated illustrate important trade-offs between the algorithms and heuristics of Section 5. First, the exact algorithms ID-MCP and pID-MCP are adapted to different topologies (Section 6.2.1): pID-MCP usually has a larger complexity (alpha is significantly larger) than ID-MCP when the number of ingresses is large. However, in more usual topologies, the complexity of pID-MCP is usually lower (α is lower) than the one of ID-MCP. Both algorithms are exact, thus, they return the same non-dominated feasible paths. However, pID-MCP can be used to precompute the path segments inside each domain for each class of service and combine these segments in a later step. The algorithm pID-MCP has two desirable properties, considering that the problem Inter-MCP is NP-complete. First, it divides the path computation operations into per-domain computations. Second, it reuses the path segments computed, independently of the sequence of domains crossed.

SR [%] C [%] MC [%] α NP Correlation + - + - + - + -+ - ID-MCP 60

Irisa

The networks of the largest operators contain several thousands of nodes. In so large networks, the exact computation of inter-domain multi-constrained paths is impracticable. In this context, heuristics provide a useful alternative to exact algorithms. The on-demand shortest-path based heuristic ID-MCP, with k=1 provides good results in most situations and has the lowest complexity among the solutions tested. However it provides at most a single solution and is not adapted for precomputing paths. As explained in Section 5.4.2, kpID-MCP can provide worst solutions than kID-MCP, k=1 in certain situations, when the number of paths to memorizes exceeded the limit on α. Nevertheless, the heuristic kpID-MCP, k>1 approaches optimal computations, depending on the limit on α and its complexity increases with this limit. The limit on α should be adapted to the level of accuracy required for the computations and to the maximum time allowed for the computations.

We have evaluated kpID-MCP with a low value of the limit on α (α ≤ 3). With this limit, kpID-MCP performs better than kID-MCP, k=1 in all simulations on LatticeSL but worse in all simulations on LatticeFM. Even with a low limit on α, kpID-MCP returns several times more solutions than kID-MCP, in most simulations, which is an important feature for balancing the load on several paths. As the precomputation of the segments is not triggered by the arrival of every request, the signaling overhead per request is expected to be lower when segments are precomputed than otherwise. In our opinion, kpID-MCP is a good choice for the precomputation of inter-domain multi-constrained paths approaching optimal solutions.

Related Works

Many recent works have studied the problems of QoS routing and path computation in the inter-domain context. Some approaches are based on extensions of BGP, the de facto inter-domain routing protocol, in order to deliver QoS services. The work in [START_REF] Zhang | Scalable BGP QoS Extension with Multiple Metrics[END_REF] investigates the extension of BGP to support multiple metrics. This necessitates advertising multiple routes for each destination. The authors propose to reduce the number of advertised paths using the dominance properties. For this purpose, they introduce one optimal approach and one heuristic approach for reducing the algorithm complexity. Similarly, the authors of the work in [2] investigate the enhancements to the BGP protocol in order to support the discovery of multiple paths per destination with associated QoS attributes. They present a dominant path selection algorithm that allows nodes to discover the minimum set of paths needed to make QoS routing decisions. In [START_REF] Beben | EQ-BGP: an efficient inter-domain QoS routing protocol[END_REF] an extension for BGP, called EQ-BGP, is introduced. EQ-BGP enables to establish end-to-end paths that offer the most suitable QoS guarantees taking into account both the QoS capabilities of particular domains as well as inter-domain links. EQ-BGP uses QoS components such as a path attribute for QoS information, a QoS aggregation function for combining path segments, a QoS aware decision algorithm for selecting the best path, and multiple routing tables that allow border routers to keep separate paths that are optimised for different QoS objectives.

Other approaches take advantage of the emerging PCE architecture for computing interdomain paths. In [START_REF] Torab | On cooperative inter-domain path computation[END_REF] the authors study the cooperation between domains in order to com-

PI n 1902

Bertrand & Lahoud & Molnár & Texier pute end-to-end paths. They demonstrate that by distributing information about blocking in each domain, end-to-end PCE-based path computation can be made more efficient in terms of the overall path computation effort. The work in [START_REF] Pelsser | Path Selection Techniques to Establish Constrained Interdomain MPLS LSPs[END_REF] study the establishment of constrained inter-domain MPLS LSPs subject to end-to-end delay constraint. The authors present and evaluate path computation techniques using the default BGP route or relying on PCEs with global or local visibility. When local visibility is used, the selection of the exit BN relies on two heuristics: the selection of the nearest BN based on the routing protocol metrics or based on an estimation of the end-to-end delay.

Alternative approaches introduce new architectures for enabling the inter-domain path computation. [START_REF] Norden | Inter-domain routing: Algorithms for QoS guarantees[END_REF] presents an overlay architecture that enables QoS routing with no required changes to BGP. The authors introduce two algorithms: the first uses a shortest-path framework, using a cost metric that accounts for both the intrinsic cost of each link and the amount of bandwidth that the link has available for use. The second dynamically probes several paths in parallel, in order to find a path capable of handling the flow. In [START_REF] King-Shan | Topology aggregation and routing in bandwidth-delay sensitive networks[END_REF], the authors introduce a method of aggregating networks considering two QoS parameters: bandwidth and delay. They use line segments in the delay-bandwidth plane instead of points to represent the QoS parameters of logical links. They also present a corresponding QoS routing protocol combining an inter-domain and an intra-domain routing step.

Conclusion

The present paper analyzes the problem of computing inter-domain paths subject to multiple constraints. We describe the information required by the domains for solving this problem exactly. In particular, our work shows that the virtual shortest-path tree structure for exchanging information between the domains does not guarantee optimal solutions. We explain why the solutions to the intra-domain problem are not applicable to the inter-domain problem. Consequently, we extend these solutions: we describe two exact algorithms, called ID-MCP and pID-MCP, which respect the confidentiality constraints of the domains. Remarkably, pID-MCP allows the precomputation of segments inside the domains crossed. As the problem considered is NP-complete, we propose several heuristics approaching optimal solutions. A simulation study considering both extreme and realistic topologies reveals that the simplest heuristic, a shortest path computation with respect to a non-linear path length, provides excellent results in most configurations. However, this heuristic provides at most a single feasible path. A second heuristic, named kpID-MCP, approximates with tunable accuracy the exact algorithm pID-MCP. We describe the particular situations in which it performs worse than the simplest heuristic. The heuristic kpID-MCP returns several paths in most configurations, which is a desirable feature for balancing the load on the paths precomputed.

There are different ways to extend the results we have obtained. First, shortest paths could be computed with respect to each link-weight considered and their weight could be used as a minimum-weight prediction to exclude segments on infeasible paths. It would be interesting to study how to extend the algorithms described in the present paper with this Irisa Inter-Domain Path Computation with Multiple Constraints 35 mechanism, without breaking confidentiality constraints. Second, kpID-MCP memorizes the paths with the lowest cost, however, other criteria could be used. For example, kpID-MCP could memorize preferably a path improving significantly one of the weights, compared to the paths already memorized, even if the cost of this new path is higher. Finally, path computations with pID-MCP use only a subset of the segments available in each domain for each class of service. It would be of interest to characterize this subset more precisely.

Figure 1 :

 1 Figure 1: General scenario for path computation across multiple domains

Figure 2 :

 2 Figure 2: Per-domain path computation steps

Figure 3 :

 3 Figure 3: BRPC steps for computing a path between s and t with the minimum number of hops

Figure 6 :

 6 Figure 6: The BRPC procedure with an extended VSPT

Figure 7 :

 7 Figure 7: Problem Inter-MCP for an intermediate domain ID-MCP is described in Algorithm 5.1.Computations are performed from the destination domain V D to the source domain V 1 as is performed by the BRPC procedure. In the destination domain, the queue is initialized with a white element corresponding to a path to the destination t with a cost equal to zero (line 3). In any other domain V i , the queue is initialized with the paths extracted from the leaves of the VSPT transmitted by the downstream domain V i+1 and a virtual topology is constructed. This virtual topology includes the virtual nodes and virtual links of the VSPT, aggregated to the graph of V i (line 5 of Algorithm 5.1, step 1 of the example in Figure8). In each domain, the algorithm loops while there is at least one white element in the queue (line 7). During each execution of this loop, a white path with minimum cost is extracted from the queue (line 8) and marked gray (line 9). Then, this path is relaxed (line 10), which means that the neighbors of the node to which this path is attached are visited, and the paths from the neighbors to the destination t are memorized if and only if they are feasible and non-dominated by the ones already in the queue. If some paths in the queue are dominated by a path newly discovered, then, these paths are marked black. Finally, the VSPT is extracted from the queue and transmitted to V i-1 , which means that the paths from the ingresses of V i are transmitted to the upstream domain V i-1 in accordance with the policy of domain V i . In the source domain, extracting the VSPT means that one or several end-to-end paths are retrieved from the final VSPT.An example appears in Figure8and helps to understand the principle of ID-MCP. For more clarity, in this example, only two additive metrics are considered (K=2) and they take integer values. An intermediate domain V i receives a VSPT containing three feasible, nondominated virtual paths to the destination t. V i concatenates this VSPT with its topology (step 1 ) and initializes the computation queue. The paths extracted from the VSPT are initially white. Then, the algorithm enters the loop (steps 2 to 9 ). The path computation operations end when no more white elements are present in the queue. Finally, the VSPT to be transmitted to the upstream domain is extracted and forwarded.ID-MCP considers the end-to-end constraints for the path segment calculations in each domain to guarantee the optimality of the paths computed. Splitting the constraints between the domains would make more intermediate paths be detected as non-feasible and thus, decrease the complexity of the path computation operations. However, the optimality could not be guaranteed anymore.

  PI n 1902Bertrand & Lahoud & Molnár & Texier Algorithm 5.1 ID-MCP 1: for all domain i from D to 1 do 2:

⇒Figure 8 :

 8 Figure 8: Example of inter-domain multi-constrained path computation with W 1 = 15 and W 2 = 15

Figure 9 :Figure 10 :

 910 Figure 9: Initial (left) and last (right) state of ID-MCP

min x∈Ea w 1

 1 (x), . . . , min x∈Ea w K (x)T

Figure 11 :

 11 Figure 11: Example where kID-MCP, k=2 provides no feasible results whereas kID-MCP, k=1 provides a feasible solution. W = (5, 5) T

PI n 1902 7 8 34 PI n 1902

 19028341902 Discussion and Related Works 32 7.1 Trade-Offs Among the Solutions . . . . . . . . . . . . . . . . . . . . . . . . . 32 7.2 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 Conclusion

Table 2 :

 2 Results of simulations in the reference scenario (positive correlation) with loose constraints ((49100, 49100) T for LatticeSL and (3000, 3000) T for LatticeFM)

				[%]	MC [%]	α	NP
	Lattice	SL FM	SL	FM	SL	FM SL FM SL FM
	ID-MCP	100 100 19.2 13.9 18.7 11.4 10 7	7	3
	pID-MCP	100 100 19.2 13.9 18.7 11.4 5	52	7	3
	kpID-MCP, k=3 100 100 19.3 26.8 18.8 23.8 3	3	6	1
	kID-MCP, k=1	100 100 19.5 13.9 19	11.9 1	1	1	1
		SR [%]	C [%]	MC [%]	α	NP
	Lattice	SL FM	SL FM	SL	FM SL FM SL FM
	ID-MCP	66 56	89.3 72	86.5 60.1 8	2	5	1
	pID-MCP	66 56	89.3 72	86.5 60.1 5	8	5	1
	kpID-MCP, k=3 66 50	89.4 72	86.5 60.1 3	3	4	1
	kID-MCP, k=1	64 56	89.8 72	87.9 60.1 1	1	1	1

Table 3 :

 3 Results of simulations in the reference scenario (positive correlation) with strict constraints ((9800, 9800)

Table 4

 4

				[%]	MC [%]	α	NP
	Lattice	SL FM	SL	FM	SL	FM SL FM SL FM
	ID-MCP	100 100 23.3 27.9 17.4 22.6 67 8	64 5
	pID-MCP	100 100 23.3 27.9 17.4 22.6 14 57	64 5
	kpID-MCP, k=3 100 100 23.3 33.2 17.4 26.1 3	3	11 2
	kID-MCP, k=1	100 100 23.3 28	17.5 23.5 1	1	1	1
	: Results of simulations with negatively-correlated weights and asymmetric con-straints ((147000, 37000) T for LatticeSL and (9000, 1000) T for LatticeFM)
		SR [%]	C [%]	MC [%]	α	NP
	Lattice	SL FM	SL	FM	SL	FM SL FM SL FM
	ID-MCP	100 100 24.3 28.6 24	24.6 69 13	65 8
	pID-MCP	100 100 24.3 28.6 24	24.6 15 74	65 8
	kpID-MCP, k=3 100 100 24.9 48.1 24.4 41.3 3	3	11 2
	kID-MCP, k=1	100 100 25.6 28.6 25.1 26.8 1	1	1	1

Table 5 :

 5 Results of simulations with negatively-correlated weights and loose constraints ((48100, 48100) T for LatticeSL and (3000, 3000) T for LatticeFM)

	Irisa

Table 6 :

 6 Results of simulations on a realistic topology with a limit on α equal to three

	[%] α NP SO

Table

Table 8 :

 8 Results of simulations with strict constraints in the SYM-CORE topology

	7 Discussion and Related Works
	7.1 Trade-Offs Among the Solutions

In this document, the set of the strictly positively-valued real numbers and the set of the positively-valued real numbers are denoted as R + * and R + , respectively.PI n 1902

Henceforth, we call the entry border nodes of a domain the ingresses of the domain.Irisa

The path that is selected and the paths that are dominated by the paths explored during the relaxation stage.Irisa

A bound for α is derived in Reference[START_REF] Van Mieghem | Hop-by-hop quality of service routing[END_REF].Irisa

or memorize

As mentioned before, the complexity of pID-MCP is expected to be significantly lower than the one of ID-MCP in certain network configurations.

More precisely, they find that the exact solution is found by HbHDBO routing in 89.4% of the cases.PI n 1902

And, typically, also their spatial complexity.Irisa

The absolute worst-case topology considering the number of paths is a topology in which any node is connected to any other node inside or outside its domain.PI n 1902

They can change if the topology is modified. PI n 1902

Bertrand & Lahoud & Molnár & Texier