Skip to Main content Skip to Navigation

Inter-Domain Path Computation with Multiple Constraints

Abstract : 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 informa- tion 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.
Complete list of metadatas

Cited literature [35 references]  Display  Hide  Download
Contributor : Anne Jaigu <>
Submitted on : Monday, September 8, 2008 - 1:32:06 PM
Last modification on : Wednesday, June 24, 2020 - 4:18:36 PM
Long-term archiving on: : Friday, June 4, 2010 - 11:02:28 AM


Files produced by the author(s)


  • HAL Id : inria-00319401, version 1


Gilles Bertrand, Samer Lahoud, Miklos Molnar, Géraldine Texier. Inter-Domain Path Computation with Multiple Constraints. [Research Report] PI 1902, 2008, pp.40. ⟨inria-00319401⟩



Record views


Files downloads