Abstract
The fundamental Quality of Service (QoS) routing problem, which consists in determining paths subject to multiple QoS constraints, has been extensively investigated in the intra-domain context. However, few solutions exist for the inter-domain case, despite the importance of this problem to enable the delivery of services with QoS across domain boundaries. We propose a method that distributes the operations to compute inter-domain constrained paths. This method relies on a per-domain formulation that is compatible with the path computation element framework. It enables us to propose the first algorithm that guarantees to find optimal paths subject to an arbitrary number of constraints. These paths ensure the best QoS performance with respect to the constraints.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Vasseur, J., Zhang, R., Bitar, N., Roux, J.L.: A Backward-Recursive PCE-Based Computation (BRPC) Procedure to Compute Shortest Constrained Inter-Domain Traffic Engineering Label Switched Paths. RFC 5441, IETF (2009)
Vasseur, J., Roux, J.L.: Path Computation Element (PCE) Communication Protocol (PCEP). RFC 5440 (2009)
Korkmaz, T., Krunz, M.: Multi-constrained optimal path selection. In: IEEE INFOCOM, vol. 2, pp. 834–843 (2001)
Yuan, X.: Heuristic algorithms for multiconstrained quality-of-service routing. IEEE/ACM Trans. Netw. 10(2), 244–256 (2002)
Van Mieghem, P., Kuipers, F.A.: Concepts of exact QoS routing algorithms. IEEE/ACM Trans. Netw. 12(5), 851–864 (2004)
Xue, G., Sen, A., Zhang, W., Tang, J., Thulasiraman, K.: Finding a path subject to many additive QoS constraints. IEEE/ACM Trans. Netw. 15, 201–211 (2007)
Saad, T., Mouftah, H., Nouroozifar, A.: Constraint-based routing across multi-domain optical WDM networks. In: Canadian Conference on Electrical and Computer Engineering, vol. 4, pp. 2065–2068 (2004)
Bradford, R., Vasseur, J.P., Farrel, A.: Preserving Topology Confidentiality in Inter-Domain Path Computation Using a Key-Based Mechanism. draft-ietf-pce-path-key-06, work in progress, IETF (2009)
Wang, Z., Crowcroft, J.: Quality-of-Service Routing for Supporting Multimedia Applications. IEEE J. Sel. Areas Commun. 14, 1228–1234 (1996)
Garey, M.R., Johnson, D.S.: Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)
Kuipers, F., Van Mieghem, P.: The impact of correlated link weights on QoS routing. In: IEEE INFOCOM, vol. 2, pp. 1425–1434 (2003)
Ahuja, R., Magnanti, T., Orlin, J.: Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Inc., New Jersey (1993)
Le Roux, J.L., Vasseur, J.P., Lee, Y.: Encoding of Objective Functions in the Path Computation Element Communication Protocol (PCEP). draft-ietf-pce-of, work in progress, IETF (2008)
Bertrand, G., Lahoud, S., Molnár, M., Texier, G.: Inter-Domain Path Computation with Multiple Constraints. Technical Report 1902, IRISA (2008), http://hal.inria.fr
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bertrand, G., Lahoud, S., Texier, G., Molnár, M. (2009). A Distributed Exact Solution to Compute Inter-domain Multi-constrained Paths. In: Oliver, M., Sallent, S. (eds) The Internet of the Future. EUNICE 2009. Lecture Notes in Computer Science, vol 5733. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-03700-9_3
Download citation
DOI: https://doi.org/10.1007/978-3-642-03700-9_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-03699-6
Online ISBN: 978-3-642-03700-9
eBook Packages: Computer ScienceComputer Science (R0)