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.
Type de document :
Rapport
[Research Report] PI 1902, 2008, pp.40
Liste complète des métadonnées

Littérature citée [35 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00319401
Contributeur : Anne Jaigu <>
Soumis le : lundi 8 septembre 2008 - 13:32:06
Dernière modification le : vendredi 16 novembre 2018 - 01:31:30
Document(s) archivé(s) le : vendredi 4 juin 2010 - 11:02:28

Fichiers

PI-1902.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

355

Téléchargements de fichiers

142