Ahmed Frikha
email: afrikha@irisa.fr

Samer Lahoud
email: slahoud@irisa.fr

Pre-computation Based Heuristic for Inter-Domain QoS Routing

In the present paper, we propose a novel fast heuristic for inter-domain QoS routing, named ID-PPPA. ID-PPPA is based on a pre-computation scheme. The pre-computation scheme attempts to solve the QoS routing problem while keeping a low response time by computing in advance a set of QoS paths. Our solution preserves domain confidentiality and solves the scaling problem related to inter-domain routing by distributing computations over the domains. Theoretical analysis proves that the ID-PPPA algorithm has a low computational complexity, which is very necessary for a pre-computation algorithm to deal with dynamic changes of the network link state information. Moreover, extensive simulations confirm the efficiency of our algorithm in terms of success rate and quality of the computed path.

I. INTRODUCTION

Quality of Service (QoS) routing, also known as multiconstraint routing, is one of the primary mechanisms for providing guaranteed performance to IP-based applications such as Video on Demand (VoD), and Voice over IP (VoIP). It consists in the computation of a path which satisfies multiple QoS constraints such as the cost, the delay, etc. Two schemes for path computation are proposed in the literature. First, the on-demand scheme that consists in the computation of a path which satisfies the QoS constraints upon the reception of a QoS request. Second, the pre-computation scheme that consists in preparing in advance a set of paths satisfying predetermined QoS requests. Then, at the reception of a QoS request, it attempts to rapidly provide a feasible path among the pre-computed paths. Unlike the on-demand computation, the pre-computation allows to speed up the response time while solving the QoS routing problem.. Extending the QoS routing to an inter-domain level faces essentially two challenges: confidentiality and scalability. First, information about internal topology or available resources in the network is confidential, as the operators can be in competition. Hence, complete routing information throughout a multi-domain network is unvailable. Second, computing the path which satisfies the QoS constraints throughout a sequence of domains is more complex because of the large number of nodes involved in the computation. Currently, the inter-domain routing protocol is BGP. This protocol does not take into account QoS constraints. Many extensions for BGP are proposed to support QoS routing [START_REF] Knoll | BGP Extended Community Attribute for QoS Marking[END_REF]- [START_REF] Griffin | Interdomain routing through QoS-class planes[END_REF]. However, the QoS capabilities of these propositions remain limited [START_REF] Mahajan | Towards coordinated interdomain traffic engineering[END_REF]. The research community has recently been exploring the use of distributed architectures, such as the PCE (Path Computation El-ement) architecture [START_REF] Farrel | Path Computation Element (PCE)-Based Architecture[END_REF], to solve the inter-domain QoS routing problem. Distributing the computation over domains preserves the confidentiality across domains and reduces the response time. Therefore, our proposed solution for inter-domain QoS routing relies on the use of a distributed architecture, such as the PCE architecture. Precisely, we propose a novel fast and distributed heuristic for the inter-domain QoS routing based on pre-computation, named ID-PPPA (Inter-Domain Primary Path-based Pre-computation Algorithm). ID-PPPA has a low theoretical computational complexity. Furthermore, it can reduce the time to establish the connection since it is based on pre-computation. It preserves the domain confidentiality clauses and overcomes the scaling problem since it relies on a distributed architecture. We also strengthen the analysis of our novel algorithm by performing exhaustive simulations.

II. PROBLEM FORMULATION

Before formally defining the problem, we first introduce some notations. Let G(N, E) denote a network topology graph, where N is the set of nodes (routers) and E the set of links. Let m be the number of constraints. In our study, we consider additive constraints. An m-dimensional weight vector is associated with each link e ∈ E. This vector consists of m non-negative QoS weights w i (e), i = 1..m. Let p be a path in the graph G(N, E) and w i (p) be the weight of p corresponding to the additive metric i. Thus, w i (p) is given by the sum of the i th weights of its component links:

w i (p) = ej ∈p (w i (e j )). Let → W (p) = (w 1 (p), w 2 (p), ..., w m (p)) denote the weight vector of the path p.
Definition 1: The MCP problem. Given a source node s and a destination node d and a set of constraints given by the constraint vector → C= (c 1 , c 2 , .., c m ), the Multi-Constraint Path (MCP) computation problem consists of finding a path p which satisfies w i (p) ≤ c i , ∀i ∈ 1..m. Such a path p is called a feasible path. The MCP problem is N P complete [START_REF] Wang | Quality-of-Service Routing for Supporting Multimedia Applications[END_REF], consequently the computational time for solving this problem is high.

A feasible path p is called non-dominated if there does not exist a path p ′ which satisfies: (1) w i (p ′ ) ≤ w i (p), ∀i ∈ 1..m and (2) ∃j ∈ 1..m for which w j (p ′ ) ≺ w j (p). To speed up the computation, dominated paths can be discarded from the computation search space of the algorithms without affecting neither the success rate of the algorithm nor the quality of the computed path, according to [START_REF] Van Mieghem | Concepts of exact QoS routing algorithms[END_REF].

III. THE ID-PPPA ALGORITHM

In this section, we present our novel inter-domain multiconstraint pre-computation algorithm. ID-PPPA consists of two phases: an offline phase and an online phase. In the offline phase, named per-domain pre-computation, ID-PPPA pre-computes a set of QoS paths in each domain satisfying a set of pre-determined QoS request. In the second phase, named inter-domain path computation, ID-PPPA attempts to compute an end-to-end path by combining the paths pre-computed in each domain.

A. The offline phase

In this phase, each domain pre-computes a set of internal QoS paths. These paths will be used later at the online phase to compute an end-to-end path.

In practice, some QoS metrics are more critical for certain applications, such as the delay for the VoIP-based applications. Therefore, we pre-compute for each QoS metric the path which minimizes the weight corresponding to this metric. For example, it pre-computes the path which minimizes the delay; this path can be useful for the VoIP-based applications. Let us consider a domain D. ID-PPPA pre-computes a set of paths from each border node of the domain D toward the other node of D as well as the entry border nodes of the neighbor domains. Let m be the number of the QoS metrics, n 1 be a border node of D, and n 2 be a node of D or an entry border node of a neighbor domain, ID-PPPA computes m shortest paths from n 1 to n 2 . Each shortest path minimizes a single QoS metric and is called primary path. Hence, from each border node of D, ID-PPPA computes m shortest path trees. Each shortest path tree, also called a primary path tree, is computed using the Dijkstra algorithm and considering a single weight component w i , where i ∈ 1..m. Therefore, ID-PPPA exectutes the Dijkstra algorithm m times per border node. Consequently, the complexity of the offline phase of ID-PPPA is then given by: O(B * m(N log(N ) + E)), where B is the number of border nodes of the domain. After computing these paths, ID-PPPA filters all dominated paths. The remaining paths are stored in a database to be used in the online phase.

After an eventual change in the network state, the precomputed paths may be not valid. Therefore, executing the offline phase of ID-PPPA periodically or using a network state-dependent threshold is required. The low theoritical complexity of this phase enables to cope with a dynamic change in the network state information since it allows domains to rapidly pre-compute new valid paths. Setting a period or a threshold for the execution of the offline phase depends on the variability of the traffic in the network. This issue goes beyond the problem considered in this work.

B. The online phase

This phase is triggered upon the reception of a QoS request. Our algorithm attempts to compute an end-to-end path by combining the pre-computed paths in each domain. When receiving a QoS request, the service provider computes the best domain sequence that links the source and the destination domain according to the cooperation policy [START_REF] Farrel | Path Computation Element (PCE)-Based Architecture[END_REF]. The end-toend path computation starts at the destination domain toward the source domain following the selected domain sequence. Note that, without loss of generality, we rely on backward computation according to the PCE architecture.

First, the destination domain selects the pre-computed paths that lead to the up-stream domain following to the selected domain sequence. Then, these paths will be sent to the upstream domain using a novel compact structure named VSPH (Virtual Shortest Path Hierarchy1 ). This structure contains only the end nodes of the paths (the destination node and the entry border nodes of the up-stream domain) and the weight vector of each path. This structure allows the confidentiality of the domains to be preserved. When receiving a VSPH, an intermediate domain combines the paths in the VSPH with the internally pre-computed paths. Then, it selects the feasible paths by comparison with the constraint vector, computes a new VSPH and sends it to the up-stream domain. Finally, the computation is stopped when a feasible path linking the source and destination is found, or when no feasible path is found. In this case, the QoS request is rejected.

Let D denotes an intermediate domain, n be an entry border node of D, and B max denote the maximum number of border nodes between two domains. There are at most m paths in the VSPH from the destination to n and at most mB max precomputed paths to reach the upstream domain from n. Hence, the complexity of combining the pre-computed paths with the received paths at the level of the entry border node n is given by O(m 2 B max ). Considering all entry border nodes of D, the global complexity of this phase is given by O(m 2 B 2 max ).

IV. SIMULATION AND ANALYSIS

In this section, we evaluate the performance of our novel algorithm ID-PPPA by comparison with the exact precomputation algorithm pID-MCP [START_REF] Bertrand | Recent Advances in Providing QoS and Reliability in the Future Internet Backbone[END_REF]. The exact algorithm pID-MCP finds a feasible path, whenever such a path exists. However, the drawback of this algorithm is its high computational complexity. The simulations are performed using the realistic topology SYM-CORE [START_REF] Dasgupta | Performance analysis of inter-domain path computation methodologies[END_REF]. We associate with each link three additive weights generated independently following a uniform distribution [10,1023]. The QoS constraints are also randomly generated in the constraint generation space Z shown in figure 1. This space is deduced by computing p 1 , p 2 , and p 3 the three shortest paths which minimize the first, the second, and the third metric, respectively. The problem is not N P-Hard outside Z, i.e. either infeasible or trivial. As shown in figure 1, we select ten zones Z i , i = 1..10 from this space and we browse them from the strictest constraint zone Z 1 to the loosest constraint zone Z 10 . Then, we assess the performance of our algorithm according to these zones.

In the following, we compare our algorithm ID-PPPA with the exact algorithm pID-MCP according to two performance Figure 2 shows the success rate of ID-PPPA and pID-MCP according to the strictness of the QoS constraints. The success rate of the algorithms increases when the constraints become less strict. In fact, the probability to find a feasible path is higher when the constraints are looser. The fundamental result deduced from figure 2 is that the success rate of our novel heuristic ID-PPPA is very close to that of the exact algorithm pID-MCP, which is advantageous considering that its complexity is reduced.

Figure 3 shows the cost C of the best paths computed by our heuristic ID-PPPA and the exact algorithm pID-MCP according to the strictness of the QoS constraints. The cost C of the algorithms decreases when the constraints are less strict. In such cases, the quality of the best computed path becomes better for two reasons. First, the number of feasible paths is higher when constraints are not strict. Hence, the probability to find a path with better quality increases. Second, when constraints are looser, the values of the weight vector components of the best path are far below the values of the constraint vector components. The most relevant result of this figure is that the cost C of the path computed by ID-PPPA is slightly higher than that of the one computed by the exact algorithm. This proves the efficiency of our algorithm in term of computed path quality.

V. CONCLUSION In this paper, we presented a new fast inter-domain path computation heuristic based on primary path pre-computation, called ID-PPPA. Our heuristic relies on a distributed architecture, such as the PCE architecture, which allows domain confidentiality to be preserved. Furthermore, ID-PPPA has a fast response time since it is based on a pre-computation scheme. The low computational complexity of the offline phase allows pre-computations to be executed rapidly to deal with eventual changes in the network load. Extensive simulations prove that our heuristic has a high success rate, very close to that of the exact algorithm pID-MCP. Moreover, the quality of the path computed by our heuristic is very close to the optimal path.

Fig. 1 .

 1 Fig. 1. Constraint generation zones for m = 3 criteria. First, the Success Rate (SR) given by the percentage of the requests for which a feasible path is found. Second, the Cost (C) given by the value of the path length function c(p) = 100 * max i∈1..m ( wi(p)ci ) for the best path computed. The cost (C) is considered only for the request for which ID-PPPA finds a feasible path. This performance criteria indicates the quality of the computed path since it gives a measure of the distance between the path weights and the constraints.

Fig. 2 .

 2 Fig. 2. Success rate according to the constraint generation zones for m = 3

Fig. 3 .

 3 Fig. 3. The cost C according to the constraint generation zones for m = 3

The hierarchy is a structure which enables the storage of multiple paths between any two nodes[START_REF] Molnar | Hierarchies for Constrained Partial Spanning Problems in Graphs[END_REF].


Ahmed Frikha
email: afrikha@irisa.fr

Samer Lahoud
email: slahoud@irisa.fr

Performance Evaluation of Pre-computation Algorithms for Inter-Domain QoS Routing

Inter-domain QoS routing is a very challenging problem area. This problem combines the complexity of QoS routing, with the limitations of inter-domain routing, such as domain heterogeneity and information confidentiality. The precomputation offers a very promising solution for addressing this problem. Although the pre-computation scheme has been investigated in several previous studies for a single routing domain, applying pre-computation on an inter-domain level is not straightforward and necessitates deeper investigation. In this work, we study different algorithms for QoS routing based on pre-computation. First, we investigate an exact algorithm. This algorithm provides an optimal solution for the QoS routing problem. However, its application in large scale networks is not always practical. Second, heuristic solutions are also investigated in this work. Particularly, a detailed study of the ID-MEFPA and the ID-PPPA heuristics is provided. Analytical studies and extensive simulations confirm that the exact algorithm achieves the best success rate, but has a very high computational complexity. The ID-MEFPA heuristic has a lower complexity and provides a success rate always close to the exact algorithm. When inter-domain connectivity is high, the ID-PPPA heuristic is the most appropriate with the lowest computation complexity and a success rate very close to the exact algorithm.

I. INTRODUCTION

Diverse new applications such as multimedia data transfer, telephony, and video broadcast are becoming more common over wide area networks. These applications require more and more extensive and varied quality of service (QoS) guarantees. Providing QoS in terms of propagation time, loss rate, bandwidth or jitter to these applications over a multidomain network is a very challenging problem area. Most research on QoS routing has focused on routing within a single domain. Addressing this problem in an inter-domain context is also strategic as it is required to ensure the endto-end QoS guarantees. In this case the problem becomes more complex because of the domain heterogeneity and information confidentiality. Content providers, network providers or transport network operators, manage different domains or autonomous systems and implement heterogeneous policies that consolidate their economic interests and confidentiality clauses. Hence, ensuring end-to-end QoS guarantees is a very hard task. Besides, selecting a route that meets the resource needs of such applications is more difficult in an interdomain level because of the number of nodes involved in the computation. Consequently, the route selection requires more 978-1-4577-0024-8/11/$26.00 c 2011 IEEE computational time and the response time become longer.

There are two alternatives for path computation. The first is the on-demand computation which consists in the computation of a path which satisfies the constraints upon the reception of the QoS request. The second variant is based on precomputation. Pre-computation consists in computing a set of suitable paths a priori for a pre-determined set of possible constraints. These constraints illustrate different classes of service of application requirements. Then, when a QoS request arrives it attempts to rapidly provide a feasible solution. This alternative provides a rapid response time for the path provisioning.

In this paper, we focus on the pre-computation scheme for inter-domain QoS routing. Different QoS routing algorithms based on pre-computation are studied in this paper. First, the inter-domain pre-computation algorithm pID-MCP [START_REF] Bertrand | Inter-Domain Path Computation with Multiple QoS Constraints[END_REF]- [START_REF] Bertrand | Inter-Domain Path Computation with Multiple Constraints[END_REF] is investigated in this paper. pID-MCP is an exact algorithm. This algorithm was reported to be the most efficient in term of success rate since it can find a feasible path for each QoS request, whenever such path exists. However, the computational complexity of this algorithm is very high. This limits its application is large scale networks. Second, heuristic solutions, such as the ID-PPPA [START_REF] Frikha | Pre-computation Based Heuristic for Inter-Domain QoS Routing[END_REF] algorithm, are also investigated in this work. In our previous work [START_REF] Frikha | Pre-computation Based Heuristic for Inter-Domain QoS Routing[END_REF], we showed that ID-PPPA is a very fast algorithm and has a high success rate. This algorithm is suitable for high speed networks. The MEFPA algorithm [START_REF] Yong | Precomputation for multiconstrained qos routing in high-speed networks[END_REF] was reported to be the most efficient intra-domain precomputation algorithm. In this paper, we extend MEFPA for an inter-domain routing level; we name it ID-MEFPA. Our studies confirm that pID-MCP has the best success rate, but has a very high computational complexity compared to the heuristic algorithms. ID-MEFPA has a lower computational complexity and has a success rate very close to that of pID-MCP. ID-MEFPA always outperforms ID-PPPA. However, when inter-domain connectivity is high, ID-PPPA presents the most appropriate solution with the lowest computational complexity and a success rate very close to the exact algorithm pID-MCP.

The rest of the paper is organized as follows. In section 2, a detailed description of the inter-domain QoS routing problem is presented. Section 3 presents several pre-computation algorithms and gives a detailed analysis of their complexities. Simulation results are presented in detail in section 4. Finally, conclusions are given in section 5.

II. THE INTER-DOMAIN QOS ROUTING PROBLEM

Inter-domain QoS routing, also known as inter-domain multi-constraint routing, consists of computing a path subject to multiple QoS constraints between a source and a destination node of a multi-domain network. Computing such a path requires knowledge of the topology of each domain in the network, as well as the QoS metrics on network links. As the operators can be in competition, information about the internal topology or the available resources in the network is confidential. This complicates the computation especially when using a centralized method.

Let us introduce the requisite notation to formally define the problem. Let G(N, E, D) denote a network of D domains, N is the set of nodes and E the set of links. Let m be the number of QoS constraints. Note that, in our study, we consider only additive metrics, such as cost and delay, without loss of generality. In fact, multiplicative metrics, such as loss rate, can be translated into additive metrics using the logarithm function; and bottleneck metrics, such as bandwidth, can be resolved by omitting all links which violate the constraints and then computing the path on the residual graph. An mdimensional weight vector is associated with each link e ∈ E. This vector consists of m non-negative QoS weights w i (e), i = 1..m. Let p be a path in the graph G(N, E, D) and w i (p) be the weight of p corresponding to the metric i. As metrics are additive, w i (p) is given by the sum of the i th weights of the component links of path p: w i (p) = ej ∈p (w i (e j )). Let → W (p) = (w 1 (p), w 2 (p), ..., w m (p)) denote the weight vector of the path p.

Definition 1

Given a source node s and a destination node d and a set of constraints given by the constraint vector → C= (c 1 , c 2 , .., c m ), the Inter-Domain Multi-Constraint Path (ID-MCP) computation problem consists of finding a path p which satisfies w i (p) ≤ c i , ∀i ∈ 1..m. Such a path p is called a feasible path.

The ID-MCP problem is N P-hard [START_REF] Wang | Quality-of-Service Routing for Supporting Multimedia Applications[END_REF] and may have zero, one, or multiple solutions. A feasible path p is called nondominated if there does not exist a path p ′ which satisfies:

(1) w i (p ′ ) ≤ w i (p), ∀i ∈ 1..m and (2) ∃j ∈ 1..m for which w j (p ′ ) ≺ w j (p). To speed up the computation, dominated paths can be discarded from the computation search space of the QoS routing algorithms without affecting their performance, according to [START_REF] Van Mieghem | Concepts of exact QoS routing algorithms[END_REF].

Currently, the inter-domain routing protocol is BGP. This protocol cannot solve the ID-MCP problem since it does not take into account QoS constraints. Many extensions for BGP are proposed to support QoS routing [START_REF] Knoll | BGP Extended Community Attribute for QoS Marking[END_REF]- [START_REF] Griffin | Interdomain routing through QoS-class planes[END_REF]. However, the QoS capabilities of these propositions remain limited. Solving the ID-MCP problem using a centralized method is a very complex problem, for the aforementioned reasons. Therefore, the research community has recently been exploring the use of distributed architectures to solve this problem, such as the PCE (Path Computation Element) architecture [START_REF] Farrel | Path Computation Element (PCE)-Based Architecture[END_REF]. Distributing the computation over domains preserves confidentiality across domains and solves the scaling problem. To our knowledge, few works have been proposed to solve the ID-MCP problem using distributed methods. ID-MCP [START_REF] Bertrand | A Distributed Exact Solution to Compute Inter-domain Multi-constrained Paths, The Internet of the Future[END_REF] is a distributed algorithm which extends the exact algorithm SAMCRA [START_REF] Van Mieghem | Concepts of exact QoS routing algorithms[END_REF] to an inter-domain level to solve the ID-MCP problem. The drawback of this algorithm is its high complexity. Also, work in [START_REF] Esmaeili | Enhanced crankback signaling for multi-domain IP/MPLS networks[END_REF] proposes a promising distributed solution with crankback mechanisms for inter-domain routing. However this solution cannot take into account more than one QoS metric. Besides, these solutions are based on an on-demand computation scheme which presents some serious limitations with the emerging applications in the Internet. As explained, the ID-MCP problem is N P-hard, consequently, the performance of the on-demand routing algorithms in terms of response time are severely affected.

In this work, we focus on the pre-computation scheme to solve the ID-MCP problem while speeding up the response time. The pre-computation proceeds in two phases: It prepares in advance a set paths satisfying predetermined QoS requests in a first phase. Then, at the reception a of QoS request, it seeks to rapidly provide a feasible path among the precomputed paths. Ideally, the second phase needs only to select one of the pre-computed solutions. However, some additional computations may be performed. For instance, when handling QoS requests with delay constraints, the first phase may precompute feasible paths for a wide range of possible delay constraints, while the second phase just needs to select a suitable path from the pre-computed set, i.e., one that satisfies the particular delay constraints of the request. The execution time of the second phase has an immediate impact on network performance; hence, it is highly desirable to keep its computational complexity as low as possible. In the above example, the less time is consumed in finding the proper path, the less time is spent in establishing the new request.

Up to now, most research on inter-domain QoS routing are based on an on-demand computation scheme, but rarely on a pre-computation scheme. Work in [START_REF] Bertrand | Inter-Domain Path Computation with Multiple QoS Constraints[END_REF] proposes a precomputation based algorithm to solve the ID-MCP problem. This algorithm, named pID-MCP, relies on a distributed architecture. However, its response time remains high, and its applicability is not practical because of the high complexity of its pre-computation phase.

III. PRE-COMPUTATION ALGORITHMS FOR INTER-DOMAIN QOS ROUTING

In this section, we investigate different pre-computation algorithms for inter-domain QoS routing. Precisely, we detail the operations performed by the exact pre-computation algorithm pID-MCP [START_REF] Bertrand | Inter-Domain Path Computation with Multiple QoS Constraints[END_REF]- [START_REF] Bertrand | Inter-Domain Path Computation with Multiple Constraints[END_REF], our algorithm ID-PPPA proposed in [START_REF] Frikha | Pre-computation Based Heuristic for Inter-Domain QoS Routing[END_REF], and our novel pre-computation algorithm, named ID-MEFPA. Note that these pre-computation algorithms rely on a distributed architecture, such as the PCE architecture. These algorithms consist of two phases: an offline phase and an online phase. In the offline phase, the algorithms pre-compute a set of QoS paths in each domain separately and satisfying a set of predetermined QoS requests. In the second phase, the algorithms attempt to compute an end-to-end path by combining the paths pre-computed in each domain.

A. The offline phase

This phase is executed in each domain separately. Each algorithm pre-computes a set of paths from each border node of the considered domain toward the other nodes in the domain as well as the entry border nodes of the neighbor domains. These paths will be used later at the online phase to compute an end-to-end path. Note that after an eventual change in the network state, the pre-computed paths may be not valid. Therefore, executing the offline phase periodically or using a network state-dependent threshold is required in each domain. A low complexity of this phase enables to cope with a dynamic change in the network state information since it allows domains to rapidly pre-compute new valid paths. Therefore, in the following we investigate the operations performed by each algorithm during this phase, and compare their offline complexity.

For now, let us introduce the requisite notation. Let D k be the considered domain, B the number of border nodes of D k , n 1 a border node of D k , n 2 a node of D k or an entry border node of a neighbor domain, and m the number of the QoS metrics. Operations performed by each algorithm during this phase are detailed in the following.

1) The ID-PPPA algorithm: ID-PPPA pre-computes m shortest paths between each pair of nodes (n 1 , n 2 ). Each shortest path minimizes a single QoS metric and is called primary path. Hence, from each border node of D k , ID-PPPA computes m shortest path trees. Each shortest path tree, also called a primary path tree, is computed using the Dijkstra algorithm and considering a single weight component w i , where i ∈ 1..m. Therefore, ID-PPPA executes the Dijkstra algorithm m times per border node. For one border node, ID-PPPA is in O(m(N log(N ) + E)). Consequently, the complexity of the offline phase of ID-PPPA is in O(Bm(N log(N ) + E)).

2) The ID-MEFPA algorithm: ID-MEFPA is our novel proposed algorithm. It is based on the MEFPA proposal [START_REF] Yong | Precomputation for multiconstrained qos routing in high-speed networks[END_REF]. ID-MEFPA computes multiple shortest paths between each pair of nodes (n 1 , n 2 ). Each shortest path minimizes a different linear weighting given by g a (e) = m i=1 a i w i (e) where w i (e) is the i th weight of link e and → a = (a 1 , a 2 , .., a m ) is a coefficient vector. Therefore, ID-MEFPA exectutes at each entry border node n 1 the Dijkstra algorithm and considering the linear weighting g a . An ideal algorithm would use a continuous variation of → a in order to cover all the coefficient values. However, a practical algorithm cannot continuously vary 3) The pID-MCP algorithm: pID-MCP is an exact precomputation algorithm; it finds a feasible path, whenever such a path exists. It pre-computes all feasible paths between each pair of nodes (n 1 , n 2 ) by executing the SAMCRA algorithm at each entry border node n 1 of D k . This computation takes into account a set of C v predetermined class of service expressed by a set of constraint vectors.

The drawback of this algorithm is its high computational complexity. In fact, the complexity of executing pID-MCP in each domain corresponds to the complexity of executing SAMCRA at each border node of the domain for each class of service. Hence, the complexity of pID-MCP in its offline phase is in

O(BC v (K max N log(K max N ) + K 3 max mE)), where K max = min(exp(N -2)!, m i=1 ci maxj cj ) [12]
. This complexity is very high comparing with that of our proposed algorithms ID-MEFPA and ID-PPPA.

B. The online phase 1) Concepts:

This phase is triggered upon the reception of a QoS request. The algorithms attempt to compute an endto-end path by combining the pre-computed paths in each domain. When receiving a QoS request, the service provider computes the best domain sequence that links the source and the destination domain according to the cooperation policy [START_REF] Farrel | Path Computation Element (PCE)-Based Architecture[END_REF]. The end-to-end path computation starts at the destination domain toward the source domain following the selected domain sequence. Note that, without loss of generality, we rely on backward computation according to the PCE architecture.

First, the destination domain selects the pre-computed paths that lead to the up-stream domain following to the selected domain sequence. Then, these paths will be sent to the upstream domain using a novel compact structure named VSPH (Virtual Shortest Path Hierarchy1 ). This structure contains only the end nodes of the paths (the destination node and the entry border nodes of the up-stream domain) as well as the weight vector of each path. This structure allows the confidentiality of the domains to be preserved. When receiving a VSPH, an intermediate domain combines the paths in the VSPH with the internally pre-computed paths. Then, it selects the feasible paths by comparison with the constraint vector, computes a new VSPH and sends it to the up-stream domain. Finally, the computation is stopped when a feasible path linking the source and destination is found, or when no feasible path is found. In this case, the QoS request is rejected.

2) Complexity: Let Seq = {D 1 , D 2 , .., D r } denote the selected domain sequence, where D 1 is the destination domain and D r the source domain. Let α be the upper bound on the number of pre-computed paths between node n 1 and node n 2 in an intermediate domain D k , k = 2..r -1. Note that α ≤ m for ID-PPPA, α ≤ V for ID-MEFPA and all feasible paths for pID-MCP. Let B k denote the number of border nodes between domains D k-1 and D k , k = 2..r -1. At the level of domain D k , there are at most α k-1 paths in the VSPH from the destination d to the node n 1 and at most αB k+1 precomputed paths to reach the upstream domain D k+1 from n 1 . Hence, the complexity of combining the pre-computed paths with the received paths at the level of the entry border node n 1 is in O(α k B k+1 ). Considering all entry border nodes between D k and D k-1 , the global complexity of this phase is given by

O(α k B k+1 B k ).
We note that the complexity of the online phase depends on the number of pre-computed paths α: The lower the number of pre-computed paths is, the lower is the number of combination operations. Therefore, the complexity of the ID-PPPA and ID-MEFPA algorithms in the online phase is lower than that of pID-MCP.

IV. SIMULATION AND ANALYSIS

In this section, we evaluate the performance of the precomputation algorithms ID-PPPA, pID-MCP, and our novel algorithm ID-MEFPA. We consider the following topologies:

• LatticeFM(N, D) is a chain of D identical domains.
Each domain is a grid made up of N nodes and E = 2 √ N ( √ N -1) undirected links. This topology represents the worst-case for the complexity of the algorithms. Precisely, each node of an intermediate domain is connected to each node in the next and in the previous domain of the chain.

• LatticeSL(N, D) is similar to the LatticeFM topology.

The only difference between these two topologies is the inter-domain connectivity. In LatticeSL, only the bottomright node of each domain is connected to the top-left node of the next-domain.

• SYM-CORE is an inter-area topology. This topology consists of five interconnected areas and is taken from the work [START_REF] Calvert | Modelling Internet Topology[END_REF]. In the simulations, we select a number of node N equal to 25 nodes and a number of domains D equal to 3. The LatticeFM(25,3) and LatticeSL(25,3) topologies allow us to evaluate the effect of inter-domain connectivity on our algorithms. In fact, in the LatticeFM (25,3) topology, the number of links that connect two domains is equal to 625, while in the LatticeSL (25,3) topology this number is equal to 1. The SYM-CORE topology is a realistic topology and represents an intermediate case of inter-domain connectivity degree.

We associate with each link three additive weights generated independently following a uniform distribution [START_REF] Bertrand | A Distributed Exact Solution to Compute Inter-domain Multi-constrained Paths, The Internet of the Future[END_REF]1023]. The QoS constraints are also randomly generated in the constraint generation space Z shown in figure 1. This space is deduced by computing p 1 , p 2 , and p 3 the three shortest paths which minimize the first, the second, and the third metric, respectively. The problem is not N P-Hard outside Z, i.e. either infeasible or trivial. As shown in figure 1, we select ten zones Z i , i = 1..10 from this space and we browse them from the strictest constraint zone Z 1 to the loosest constraint zone Z 10 . Then, we assess the performance of the algorithms according to these zones. In the following, we evaluate the pre-computation algorithms according to two performance criteria. First, the Success Rate (SR) given by the percentage of the requests for which a feasible path is found. Second, the Cost (C) given by the value of the path length function c(p) = 100 * max i∈1..m ( wi(p) ci ) for the best path computed. The cost (C) is considered only for the request for which all the algorithms find a feasible path. This performance criteria indicates the quality of the computed path since it gives a measure of the distance between the path weights and the constraints.

Figures 2, 3 and 4 illustrate the variation of the success rate according to the strictness of the QoS constraints in the LatticeSL(25,3), LatticeFM (25,3) and SYM-CORE topologies, respectively. The number of constraints m is equal to 3. The figures show that the success rate measured on the LatticeFM (25,3) topology increases faster than the one measured on the SYM-CORE and LatticeSL(25,3) topologies when the constraints are increasingly loose. As the number of border nodes depends on the inter-domain connectivity, the number of pre-computed paths by each algorithm increases when inter-domain connectivity is high. Thus, the number of feasible paths communicated among domains increases. Therefore, the probability to find an inter-domain path which satisfies the QoS constraints is higher when inter-domain connectivity is high. This is why the success rate of the ID-MEFPA and ID-PPPA algorithms is equal to the success rate of the exact algorithm pID-MCP in the LatticeFM(25,3) topology. We remark that in the LatticeSL(25,3) and SYM-CORE topologies, the success rate of ID-PPPA is lower than that of ID-MEFPA and pID-MCP. In fact, the number of paths pre-computed by ID-MEFPA and pID-MCP is higher than that of ID-PPPA. An important result deduced from these figures is that in all the used topologies the success rate of our proposed algorithm ID-MEFPA is equals or slightly lower than that of the exact algorithm. This is can be considered as a promising result since the computational comlexity of ID-MEFPA is very low comparing with that of pID-MCP. Now we focus on the quality of the computed path by each algorithm. Figures 5,6 and 7 illustrate the variation of the cost C depending on the strictness of the QoS constraints in the LatticeSL(25,3), LatticeFM (25,3) and SYM-CORE topologies, respectively. The quality of paths computed by pID-MCP is almost the best in all used topologies. In fact, pID-MCP inherently minimize the cost C when pre-computing paths. Comparing these three figures illustrates the effect of inter-domain connectivity on the path quality for each algorithm. The higher the inter-domain connectivity is, the better the quality of paths is. The quality of paths is almost the same for all the algorithms in LatticeFM(25,3) topology. However, in LatticeSL(25,3) and SYM-CORE topologies the quality of paths computed by ID-MEFPA is slightly better than that of ID-PPPA. This difference in the quality of paths between algorithms is due to the number and the quality of the pre-computed paths.

V. CONCLUSION

In this paper, we have investigated and evaluated performance of several pre-computation algorithms for interdomain QoS routing. These algorithms rely on a distributed architecture, such as the PCE architecture, which allows domain confidentiality to be preserved. The pID-MCP is an exact algorithm and has the best success rate. However, the complexity of this algorithm in its offline phase is very high. Thus, the time required for pre-computing new paths in each domain is high and this limits the application of pID-MCP in a very dynamic traffic load. In contrast with pID-MCP, ID-PPPA has a low complexity in its offline phase and this allows pre-computations to be executed rapidly to deal with eventual changes in the network load. However, the success rate of ID-PPPA is lower than that of pID-MCP especially when the interdomain connectivity is very low. The ID-MEFPA algorithm has a success rate very close to that of the exact algorithm pID-MCP in all the considered topologies. Moreover, its offline complexity is very low comparing with pID-MCP. Besides, the complexity of the online phase of ID-PPPA and ID-MEFPA is lower than that of pID-MCP. Thus the response time of ID-MEFPA and ID-PPPA is lower than that of pID-MCP.

  MEFPA uses V vectors → a uniformly distributed in S m , where S = { 0 (b-1) , 1 (b-1) , .., b-1 (b-1) }; b is a parameter of the algorithm. The complexity of ID-MEFPA depends on the parameter b and the number of constraints m. For one border node, ID-MEFPA is in O (V (N log(N ) + E)) corresponding to V times the complexity of a Dijkstra algorithm, where V = C m-1 b+m-2 . The global complexity is in O(BV (N log(N ) + E)).

Fig. 1 .

 1 Fig. 1. Constraint generation zones for m = 3

Fig. 2 .Fig. 3 .Fig. 4 .

 234 Fig. 2. The success rate according to the constraint generation zones in the LatticeSL(25,3) topology

Fig. 5 .Fig. 6 .Fig. 7 .

 567 Fig. 5. The cost C according to the constraint generation zones in the LatticeSL(25,3) topology

The hierarchy is a structure which enables the storage of multiple paths between any two nodes[START_REF] Molnar | Hierarchies for Constrained Partial Spanning Problems in Graphs[END_REF].


Ahmed Frikha
email: ahmed.frikha@irisa.fr

Samer Lahoud
email: samer.lahoud@irisa.fr

Bernard Cousin
email: bernard.cousin@irisa.fr

Hybrid Inter-Domain QoS Routing with Crankback Mechanisms

Keywords: QoS routing, inter-domain routing, crankback mechanisms, pre-computation, on-demand computation

In this paper we tackle the challenging problem of Quality of Service (QoS) routing in multiple domains. We propose a novel inter-domain QoS routing algorithm named HID-MCP. HID-MCP benefits from two major concepts that ensure high performance in terms of success rate and computational complexity. First, HID-MCP is a hybrid algorithm that combines the advantages of pre-computation and on-demand computation to obtain end-to-end QoS paths. Second, HID-MCP integrates crankback mechanisms for improving the path computation results in a single domain or in multiple domains. Extensive simulations confirm the efficiency of our algorithm on randomly generated topologies.

Introduction

Nowadays, diverse advanced applications are provided over IP-based networks (e.g. IPTV, video-on-demand, and VoIP). Guaranteeing the Quality of Service (QoS) to such applications is a difficult problem, especially when service delivery requires crossing heterogeneous domains under the responsibility of different operators. Inter-domain QoS routing, also known as Inter-Domain Multi-Constraint Path (ID-MCP) computation problem is one of the primary mechanisms for providing QoS. It consists of computing a path subject to multiple QoS constraints between a source and a destination node of a multi-domain network. Let us introduce some notations to formally define the ID-MCP problem. Let G(N, E, D) denote a network of D domains, N is the set of nodes and E the set of links. Let m be the number of QoS constraints. In our study, we consider only additive metrics, such as cost and delay, without loss of generality [START_REF] Frikha | Hybrid Inter-Domain QoS Routing based on Look-Ahead Information[END_REF]. An m-dimensional weight vector is associated with each link e ∈ E. This vector consists of m nonnegative QoS weights w i (e), i = 1..m. Let p be a path in the graph G(N, E, D) and w i (p) be the weight of p corresponding to the metric i. As metrics are additive, w i (p) is given by the sum of the weights of the i th metric of the links of the path p: w i (p) = ej ∈p (w i (e j )). Let → W (p) = (w 1 (p), w 2 (p), ..., w m (p)) denote the weight vector of the path p.

Definition 1

Given a source node s, a destination node d and a set of constraints given by the constraint vector → C= (c 1 , c 2 , .., c m ), the Inter-Domain Multi-Constraint Path (ID-MCP) computation problem consists in finding a path p which satisfies w i (p) ≤ c i , ∀i ∈ 1..m. Such a path p is called a feasible path.

The ID-MCP problem is N P-hard [START_REF] Wang | Quality-of-Service Routing for Supporting Multimedia Applications[END_REF] and may have zero, one or multiple solutions (feasible paths). Computing such a path requires knowledge of the topology of each domain in the network, as well as the QoS metrics on network links. As the operators can be in competition, information about the internal topology or the available resources in the network is confidential. Hence, computing such a path using a centralized method is a hard task. Currently, the inter-domain routing protocol is BGP. This protocol cannot solve the ID-MCP problem since it does not take into account QoS constraints. Many extensions for BGP are proposed to support QoS routing [START_REF] Knoll | BGP Extended Community Attribute for QoS Marking[END_REF]- [START_REF] Griffin | Interdomain routing through QoS-class planes[END_REF]. However, the QoS capabilities of these propositions remain limited. Furthermore, solving the ID-MCP problem using a centralized method is a very complex problem. Therefore, the research community has recently been exploring the use of distributed architectures to solve this problem, such as the PCE (Path Computation Element) architecture [START_REF] Farrel | Path Computation Element (PCE)-Based Architecture[END_REF]. Distributing the computation over domains preserves confidentiality of each domain and solves the scaling problem. To our knowledge, few works have been proposed to solve the ID-MCP problem using distributed methods. The algorithm proposed in [START_REF] Bertrand | A Distributed Exact Solution to Compute Inter-domain Multi-constrained Paths, The Internet of the Future[END_REF] extends the exact algorithm SAMCRA [START_REF] Van Mieghem | Concepts of exact QoS routing algorithms[END_REF] to an interdomain level to solve the ID-MCP problem. The drawback of this algorithm is its high complexity. Work in [START_REF] Esmaeili | Enhanced Crankback Signaling for Multi-Domain IP/MPLS Networks[END_REF] proposes also a promising distributed solution with crankback mechanisms for inter-domain routing. However this solution cannot take into account several QoS metrics.

In this paper, we propose a novel inter-domain QoS routing algorithm, named HID-MCP. HID-MCP is based on a hybrid computation scheme that combines path pre-computation and on-demand path computation. HID-MCP consists of two phases: An offline phase and an online phase. In the offline phase, HID-MCP pre-computes a set of QoS paths. In the online phase, HID-MCP combines the pre-computed paths to obtain an end-to-end path that fulfills the QoS constraints. Combining the pre-computed paths does not lead always to an endto-end path. In such a case, a crankback mechanism is executed to perform on demand computations. Combining pre-computation and on-demand computation using crankback mechanisms improves the computation results and allows computational complexity to be reduced. Besides, our solution relies on a distributed architecture to overcome the limitations related to inter-domain routing. Extensive simulations confirm the efficiency of our algorithm in terms of success rate and computational complexity.

The rest of this paper is organized as follows. In Section 2, we present the concept of the HID-MCP algorithm and its operations. Simulation results are presented in detail in Section 3 and a conclusion is given in Section 4.

The HID-MCP Algorithm

In this paper, we propose a novel inter-domain QoS routing algorithm based on a hybrid computation scheme and named HID-MCP (Hybrid ID-MCP). The HID-MCP algorithm consists of two phases. In the first phase, named the offline path computation phase, the algorithm executes an intra-domain precomputation algorithm and computes look-ahead information for each domain. The pre-computed intra-domain paths and the look-ahead information are stored in a database for later use. The second phase, named online path computation phase, is triggered upon the reception of a QoS request. In this phase, HID-MCP computes an end-to-end path that spans multiple domains and fulfills the QoS constraints. The end-to-end path computation benefits from the stored precomputed intra-domain paths and the look-ahead information to speed up the computational time of the algorithm.

The Offline Path Computation Phase

The offline computation phase consists of computing in advance a set of intradomain paths subject to multiple predetermined QoS constraints. It also computes look-ahead information at the level of each entry border node of the corresponding domain. In the following, we detail the operations involved in these two computations.

The Path Segment Computation Procedure This procedure pre-computes a set of paths from each entry border node of the domain toward the other nodes of this domain as well as the entry border nodes of the neighbor domains. These paths satisfy a set of predetermined additive QoS constraints. In practice, some QoS metrics are more critical for certain applications, such as the delay for the VoIP-based applications. Therefore, our procedure pre-computes for each single QoS metric the path which minimizes the weight corresponding to this metric. For example, it pre-computes the path which minimizes the delay; this path can be useful for the VoIP-based applications.

Let D q be the considered domain, n 1 be a border node of D q , n 2 be a node of D q or an entry border node of a neighbor domain, and m be the number of the QoS metrics, our procedure computes m shortest paths from n 1 to n 2 . Each shortest path minimizes a single QoS metric. Hence, from each entry border node n 1 of D q , this procedure computes m shortest path trees. Each shortest path tree is computed using the Dijkstra algorithm and considering a single metric. Therefore, our procedure executes Dijkstra m times per border node.

Theorem 1

The complexity of the path segment computation procedure is in O(B * m(N log(N ) + E)), where B is the number of the entry border nodes of the domain. Proof: The complexity of this procedure depends on the number of constraints m. For one border node, this procedure is in O (m(N log(N ) + E)) corresponding to m times the complexity of Dijkstra, which is O((N log(N ) + E)). Considering the B entry border nodes of the domain, the global complexity is then given by: O(B * m(N log(N ) + E)).

Look-Ahead Information Computation Procedure During the offline phase of HID-MCP, we propose the computation of look-ahead information in each domain. This information gives a measure of the best QoS performance that can be provided by the domain. Particularly, it allows the computation search space of a potential on-demand path computation procedure to be reduced. For instance, this information allows infeasible paths to be discarded from the search space of the procedure before exploring these paths. Therefore, look-ahead information reduces the computational complexity of the online phase and contributes to maintain a reasonable response time. Look-ahead information is inferred from the result of the pre-computation algorithm. Let n 1 be a border node of the domain, and n 2 be a node of the domain or an entry border node of a neighbor domain, and p * n1 →n2;i denotes the pre-computed shortest path between node n 1 and node n 2 considering the metric i. The weight w i (p * n1 →n2;i ) is the lowest possible path weight between n 1 and n 2 . Similarly, let us denote by

→ W * n1 →n2 = (w * 1 , .., w * m ) the vector where w * i = w i (p * n1 →n2;i ). Then, → W * n1 →n2
represents the lowest weights to reach n 2 from n 1 for each single metric. We note that a path does not necessarily exist with this lowest weights for all the metrics simultaneously. However, this vector can be used in the online path computation phase to discard infeasible paths from the search space.

Theorem 2

The complexity of the look-ahead information computation procedure is in O(m * N * B). Proof: Look-ahead information is inferred from the result of the path segment computation. At each entry border node of the domain, there are at most m * N stored pre-computed paths. Hence, at the level of an entry border node n the complexity of computing the N vectors → W * n →nj , where n j ∈ N , is in O(m * N ). Therefore, the complexity of computing the look-ahead information for all the entry border nodes of the domain is in O(m * N * B).

The Online Path Computation Phase

The online path computation consists in finding a feasible end-to-end path using the pre-computed paths and taking advantage of the look-ahead information. Upon the reception of a QoS request, the source and the destination domains are determined. According to the cooperation policy, the service provider computes the best domain sequence that links the source and the destination domain [START_REF] Farrel | Path Computation Element (PCE)-Based Architecture[END_REF]. The path computation is triggered in the destination domain toward the source domain following the selected domain sequence. Note that, without loss of generality, we rely on backward computation according to the PCE architecture. Let Seq = {D 1 , D 2 , .., D r } denote the selected domain sequence, where D 1 is the destination domain and D r the source domain. Let d be the destination node and s be the source node. Algorithm 1 illustrates the operations performed in the online phase of HID-MCP. First, our algorithm attempts to compute an inter-domain path by combining the pre-computed paths in each domain D q in Seq starting from the destination domain D 1 : the path combination procedure Algorithm 1 Online Phase of HID-MCP (Seq,s,d) 1: q ← 1; H ← φ; reject request ← f alse; 2: while (q ≤ r) and not(reject request) do 3:

H ← Path combination procedure(Dq, H, s, d); 4:

if H = φ then 5:

q ← q + 1; 6:

else if intra domain crankback then 7:

H ← On demand computation(Dq, H, s, d); 8:

if H = φ then 9:

q ← q + 1; end if 24: end while 25: Return reject request == f alse is called (line 3). Operations performed by this procedure are detailed in section 2.2. The result of the combination procedure in each domain D q is a set of subpaths linking the destination node to the entry border nodes of the up-stream domain D q+1 . These sub-paths are sent to domain D q+1 to combine them with the pre-computed segments in domain D q+1 . To preserve domain confidentiality, sub-paths are communicated between domain under a novel compact structure named VSPH (Virtual Shortest Path Hierarchy1 ) [START_REF] Frikha | Hybrid Inter-Domain QoS Routing based on Look-Ahead Information[END_REF]. This structure contains only the end nodes of the paths (the destination node and the entry border nodes of the up-stream domain) as well as the weight vector of each path. Combining the pre-computed paths in each domain can lead to an end-toend path, as detailed in section 2.2. However in some cases, no feasible path is found, i.e. the returned VSPH is empty. We introduce in the following two novel approaches using crankback mechanisms in order to overcome this limitation. The first approach executes an intra-domain crankback while the second approach executes an inter-domain crankback. Both of these approaches perform an on-demand path computation. The aim of the on-demand path computation procedure is to provide better results than the pre-computed ones. Operations performed by this procedure are detailed in section 2.2.

The intra-domain crankback approach (lines 6-12) executes the on-demand path computation procedure in the current domain, i.e. where the combination has failed. Then, if a feasible path is found in the current domain, this path is sent to the up-stream domain which will resume the path combination procedure. Otherwise, if the algorithm does not find a solution in the current domain, i.e. H = φ, the request is rejected.

The inter-domain crankback approach (lines 13-23) executes the on-demand path computation procedure starting from the destination node d. Each domain executes the on-demand path computation procedure and sends the computed VSPH to the up-stream domain. The computation stops when an end-to-end path is found or when the on-demand path computation procedure does not find a solution, i.e. the returned VSPH is empty. In the latter case, the request is rejected.

Path Combination Procedure The aim of this procedure is to combine the paths in the received VSPH with the internally pre-computed one. Algorithm 2 illustrates the operations performed by the path combination procedure. First, the combination procedure selects the pre-computed paths linking nodes in the set I to nodes in the set E, where I is the ingress node set and E the egress node set (lines 1-13). Then, these paths are combined with the aggregated paths received in the VSPH (line 17). Finally, feasible paths are aggregated and added to the new VSPH which will be sent to the upstream domain. Notes that at the level of the destination domain D 1 there is no received VSPH (H = φ), the procedure selects the feasible pre-computed paths linking the destination d to the entry border nodes of domain D 2 , and aggregates them in a VSPH to be sent to domain D 2 . Figure 1 illustrates an example of path combination with two constraints (m = 2) in an intermediate domain D q . Theorem 3

The complexity of the pre-computed path combination procedure at the level of an intermediate domain

D q ∈ {D 2 , .., D r-1 } is in O(m q * B 2 max )
, where B max denotes the maximum number of border nodes between two domains.

Proof: There are at most m q-1 paths from the destination to each entry border node of the domain D q . In addition, at each entry border node, there are at most m * B max stored pre-computed paths to reach the upstream domain D q+1 . Hence, the complexity of combining the pre-computed paths and the received paths at the level of an entry border node is in O(m q * B max ). This operation is performed at each entry border node between the domain D q and the downstream domain D q-1 . Therefore, the global complexity of this procedure at each domain is in O(m q * B 2 max ). The On-demand Path Computation Procedure When the pre-computed path combination procedure does not lead to a feasible path, the on-demand path computation procedure is called in the current domain or starting from the destination domain according to the two aforementioned approaches. We propose a modified version of the TAMCRA algorithm to perform the on-demand computation. Work in [START_REF] Van Mieghem | Hop-by-hop quality of service routing[END_REF] shows that TAMCRA is an efficient tunable heuristic for the MCP problem. TAMCRA introduces a new parameter k that limits the maximum number of stored paths at each intermediate node when searching for a feasible path. This parameter allows TAMCRA's performance to be tuned: the success rate can be improved by increasing k at the expense of increased computational complexity. Algorithm 3 illustrates the operations performed by the on-demand path computation procedure. First of all, our proposed procedure computes a prediction for the lowest weight vector to reach domain D q+1 through each path in the received VSPH (lines 11-19). We define for each aggregated path d, n, → W (p d→n ) in the VSPH and for each node n k in E, a weight vector → W * (d → n j → n k ) that represents the sum of the weight vector of the computed segment p d →nj and the lowest weight vector to reach n k from n j (line 13).

Domain Dq

Therefore,

→ W * (d → n j → n k ) = → W (p d →nj )+ → W * nj →n k , where → W * nj →n k is
given by the look-ahead information. Note that the weight vector

→ W * (d → n j → n k
) is not necessarily associated to an existing path. Next, we discard infeasible paths from the VSPH. For that, we define a new score for each path p given by: S(p

d →nj ) = min n k ∈E max i∈1..m w * i (d →nj →n k ) ci
. This score represents the lowest score to reach d through p d →nj . A path p, that has a score S(p) > 1, is infeasible since it cannot lead to any node in E while meeting the QoS constraints. Then, we classify the remaining paths in VSPH according to the score S. We select the l shortest paths having the l lowest scores, where l is a parameter of HID-MCP. The parameter l of HID-MCP is very important to Algorithm 2 Path combination procedure (D q ,H,s,d) reduce the computational complexity of the on-demand computation procedure and to decrease the number of paths exchanged between domains. After that, for each selected shortest path p d →nj , we initialize the node n j by the corresponding weight vectors → W (p d →nj ) and we execute the TAMCRA algorithm starting from node n j to reach the nodes in E. We note that at the destination domain, i.e. where the computations start, there is no received VSPH. Hence, the on-demand procedure executes TAMCRA starting from the destination node. Finally, we aggregate the feasible paths computed by TAMCRA in a new VSPH.

Theorem 4

The complexity of the on-demand path computation procedure at the level of

an intermediate domain is in O(l(k * N log(k * N ) + k 3 * m * E)).
Algorithm 3 On demand computation procedure (D q ,H,s,d) Proof The most significant point that determines the complexity of the ondemand path computation procedure is the number of executions of the TAM-CRA algorithm. Knowing that the number of initialized node is less or equal to l, the complexity of this operation is in O(l(k * N log(k * N ) + k 3 m * E)), corresponding to l times the complexity of TAMCRA.

1: temp paths ← φ; f easible paths ← φ; 2: Ψ ← → W * / → W * look-
L ← → W * n j →n k ∈ Ψ, nj ∈ I, n k ∈ E ; 11: for d, nj , → W (p d→n j ) ∈ H do 12: for → W * n j →n k ∈ L do 13: → W * (d → nj → n k ) ← → W (p d→n j )+ → W *

Simulation and analysis

In this section, we evaluate the performance of our novel algorithm HID-MCP by comparasion with the exact on-demand algorithm ID-MCP introduced in [START_REF] Bertrand | A Distributed Exact Solution to Compute Inter-domain Multi-constrained Paths, The Internet of the Future[END_REF]. This algorithm has the best success rate, i.e. no other algorithm can have a success rate higher than that of ID-MCP, because ID-MCP finds a feasible path whenever a such path exists. However, the complexity of executing ID-MCP in each domain corresponds to the complexity of the SAMCRA algorithm given by: O((K max * N log(K max * N ) + K 3 max m * E)), where K max = min(exp(N -2)!, m i=1 ci maxj cj ) [START_REF] Van Mieghem | Hop-by-hop quality of service routing[END_REF]. This complexity is very high comparing with that of our proposed algorithm. The simulations are performed using a network of three domains where each domain is built based on Waxman's model with 50 nodes in each domain. The probability that two nodes of the network are connected by an edge is expressed in [START_REF] Calvert | Modelling Internet Topology[END_REF]. We associate with each link two additive weights generated independently following a uniform distribution [START_REF] Van Mieghem | Hop-by-hop quality of service routing[END_REF]1023]. The QoS constraints are also randomly generated according to the following: Let p 1 and p 2 denote the two shortest paths which minimize the first and the second metric, respectively. Let Z = [w 1 (p 1 ), w 1 (p 2 )]×[w 2 (p 2 ), w 2 (p 1 )] be the constraint generation space. The problem is not N P-Hard outside Z, i.e. either infeasible or trivial. As shown in figure 2, we divide this space into ten zones Z i , i = 1..10 and we browse the space from the strictest constraint zone Z 1 to the loosest constraint zone Z 10 . Then, we assess the performance of the algorithms according to these zones. We evaluate the algorithms based on the following performance -GSR: the global success rate given by the ratio of the number of the requests for which a feasible path is found and the total number of QoS requests. -CSR: the efficiency of the combination procedure at a specific domain given by the ratio of the number of requests where the combination procedure is successful (e.g. leading to at least one feasible segment between the destination and the border nodes of the upstream domain) and the total number of received requests.

In the following, each figure measures the variation of one performance metric according to the constraint generation zones Z i , i ∈ 1..10, with a 95% confidence interval. We focus on the success rate of the combination procedure (CSR) in a given domain. The complement of CSR corresponds to the percentage of executions of the on-demand computation procedure. Figure 3 illustrates the variation of the CSR in each domain according to strictness of the QoS constraints. In the destination domain, the combination procedure is always successful. In the intermediate domain the success rate of this procedure is high and equals 100% when constraints are not very strict. However, we note that the CSR in the source domain is low, specifically when the constraints are strict. Nonetheless, this procedure performs well when the constraints are less strict. From this figure, we deduce that the probability of executing the on-demand computation is high only in the source domain when the constraints are very strict. This proves that the global empirical complexity of HID-MCP remains reasonable.

Figure 4 illustrates the variation of the global success rate (GSR) of HID-MCP with intra-domain crankback mechanism, HID-MCP with inter-domain crankback mechanism, and the exact algorithm ID-MCP, according to the strictness of the QoS constraints. We remark that the success rate of HID-MCP with inter-domain crankback when l = 2 and k = 2 is very close to the success rate of ID-MCP. As explained in section 2, k is a parameter of TAMCRA and l is the maximum number of paths selected from the VSPH. As expected, the success rate of HID-MCP with intra-domain crankback when l = 2 and k = 2 is lower than that of HID-MCP with inter-domain crankback with the same parameters, especially in the middle of the constraint generation space. In fact, when the combination procedure fails, HID-MCP with inter-domain crankback executes the on-demand computation procedure starting from the destination domain, while HID-MCP with intra-domain crankback executes it only in the current domain. Consequently, the quality of the paths computed by the inter-domain crankback approach in each domain is better than the ones computed by the intra-domain crankback approach. Thus, the probability that a feasible path is found using HID-MCP with inter-domain crankback is higher. However, its computational complexity is high compared to HID-MCP with intra-domain crankback, but remains acceptable compared to ID-MCP. The fundamental result deduced from this figure is that HID-MCP has a slightly lower global success rate compared to the exact algorithm, while having a very low complexity.

Conclusion

In this paper, we studied the inter-domain QoS routing problem. We proposed a novel inter-domain QoS routing algorithm based on a hybrid computation scheme, named HID-MCP. We introduced two different mechanisms for improving the success rate. The first mechanism performs local improvement using an intra-domain crankback, while the second mechanism executes a global improvement using an inter-domain crankback. Extensive simulations showed that HID-MCP with both of the aforementioned approaches provides a high success rate and maintains a low complexity time. In particular, the inter-domain crankback improvement-based HID-MCP has a success rate very close to that of the exact solution, while the intra-domain crankback improvement-based HID-MCP provides lower computational complexity. This gives operators the choice to execute either of the approaches, depending on the computation policy and the priority of the request.

  The VSPH is denoted by H in algorithm 1. A virtual path p d→n is represented in the VSPH by d, n, → W (p d→n ) , where d is the destination node, n is an entry border node of the upstream domain D q+1 , and → W (p d→n ) is the weight vector of p d→n .

Fig. 1 .

 1 Fig. 1. Combining the pre-computed paths in domain Dq with the VSPH

Fig. 2 .

 2 Fig. 2. Constraint generation zones for m = 2

Fig. 3 .

 3 Fig. 3. Success rate of the combination procedure in each domain.

Fig. 4 .

 4 Fig. 4. Comparison of the global success rate of the algorithms.

  Selected paths ← pn j →n k /pn j →n k ∈ P, nj ∈ I, n k ∈ E ; 14: if Dq = D1 then 15:for p d→n j ∈ H do 16:for pn j →n k ∈ Selected paths do

	1: P ← {p/p pre-computed path in domain Dq};
	2: H ′ ← φ;
	3: if Dq == D1 then
	4:	I ← {d};
	5: else
	6:	I ← {nj /nj leaf node in H};
	7: end if
	8: if Dq == Dr then
	9:	E ← {s};
	10: else
	11:	E ← {n k /n k entry border node of domain Dq+1};
	12: end if
	13: 17:
	20:	end if
	21:	end for
	22:	end for
	23: else
	24:	for p d→n k ∈ Selected paths do
	25:	if p d→n k is feasible then
	26:	Add d, n k ,	→ W (p d→n k ) to H ′ ;
	27:	end if
	28:	end for
	29: end if
	30: Return H ′ ;

→ W (p d→n k ) ← → W (p d→n j )+ → W (pn j →n k ); 18: if p d→n k is feasible then 19: Add d, n k , → W (p d→n k ) to H ′ ;

  ahead information in domain Dq ;

	3: if Dq = D1 then
	4:	I ← {nj /nj leaf node in H};
	5:	if Dq == Dr then
	6:	E ← {s};
	7:	else
	8:	E ← {n k /n k entry border node of domain Dq+1};
	9:	end if
	10:

The hierarchy is a structure which enables the storage of multiple paths between any two nodes[START_REF] Molnar | Hierarchies for Constrained Partial Spanning Problems in Graphs[END_REF].