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

https://hal.inria.fr/inria-00319401
Contributor : Anne Jaigu <>
Submitted on : Monday, September 8, 2008 - 1:32:06 PM
Last modification on : Thursday, October 17, 2019 - 12:34:45 PM
Long-term archiving on: Friday, June 4, 2010 - 11:02:28 AM

Files

PI-1902.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00319401, version 1

Citation

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⟩

Share

Metrics

Record views

370

Files downloads

155