Narzędzia help

Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
first last
cannonical link button


Journal of Telecommunications and Information Technology

Tytuł artykułu

A new algorithm for calculating the most reliable pair of disjoint paths in a network

Autorzy Gomes, T.  Craveirinha, J.  Violante, A. 
Treść / Zawartość
Warianty tytułu
Języki publikacji EN
EN In various types telecommunication networks, namely mobile ad hoc networks, WDM networks and MPLS networks, there is the necessity of calculating disjoint paths for given node to node connections in order to increase the reliability of the services supported by these networks. This leads to the problem of calculating a pair of disjoint paths (or a set of disjoint paths) which optimises some measure of performance in those networks. In this paper we present an algorithm, designated as OptDP, for obtaining the most reliable pair of disjoint paths based on the loopless version of MPS, a very efficient k-shortest path algorithm, and on Dijkstra algorithm. Since to the best of our knowledge there is no other proposal of an algorithm capable of solving exactly the same problem we perform a comparison with the application to this problem of the DPSP algorithm which calculates a set of disjoint paths with high reliability. Also a comparison with a simplified version (designated as NopDP) of the proposed algorithm, which stops after a maximal number F of candidate pairs of paths have been found, is presented. The comparison also includes the percentage of cases in which both algorithms were not capable of finding the optimal pair.
Słowa kluczowe
EN reliability   OR in telecommunications   routing  
Wydawca Instytut Łączności - Państwowy Instytut Badawczy
Czasopismo Journal of Telecommunications and Information Technology
Rocznik 2006
Tom nr 4
Strony 31--38
Opis fizyczny Bibliogr. 11 poz., rys., tab.
autor Gomes, T.
autor Craveirinha, J.
autor Violante, A.
  • Department of Electrical and Computer Engineering, Pólo II of Coimbra University 3030-290 Coimbra, Portugal. INESC Coimbra, Rua Antero de Quental 199, 000-033 Coimbra, Portugal,
[1] R. Bhandari, Survivable Networks, Algorithms for Diverse Routing. Boston [etc.]: Kluwer, 1999.
[2] T. Gomes and J. Craveirinha, “Efficient calculation of the most reliable pair of link disjoint paths in telecommunication networks”, in Proc. Conf. DSTIS 2004, Warsaw, Poland, 2004 (accepted for publication in Eur. J. Oper. Res.).
[3] T. Gomes, L. Martins, and J. Craveirinha, “An algorithm for calculating the k-shortest paths with a maximum number of arcs”, Invest. Oper., vol. 21, no. 2, pp. 235–244, 2001.
[4] P. Laborczi, J. Tapolcai, P.-H. Ho, T. Cinkler, A. Recski, and H. T. Mouftah, “Algorithms for assymetrically wheigted pair of disjoint paths in survivable networks”, in Proc. Des. Rel. Commun. Netw. DCRN 2001, Budapest, Hungary, 2001, pp. 220–227.
[5] C.-L. Li, S. T. McCormick, and D. Simchi-Levi, “Finding disjoint paths with different path costs: complexity and algorithms”, Networks, vol. 22, pp. 653–667, 1992.
[6] E. Martins, M. Pascoal, and J. Santos, “An algorithm for ranking loopless paths”, Tech. Rep. 99/007, CISUC, 1999,˜marta/Publicacoes/
[7] E. Martins, M. Pascoal, and J. Santos, “Deviation algorithms for ranking shortest paths”, Int. J. Found. Comput. Sci., vol. 10, no. 3, pp. 247–263, 1999.
[8] H. T. Mouftah and P.-H. Ho, Optical Networks – Architecture and Survivability. Boston [etc.]: Kluwer, 2003.
[9] P. Papadimitratos, Z. J. Hass, and E. G. Sirer, “Path selection in mobile ad hoc networks”, in Proc. 3rd ACM Int. Symp. Mob. Ad Hoc Netw. Comput., Lausanne, Switzerland, 2002, pp. 1–11.
[10] J. W. Suurballe, “Disjoint paths in networks”, Networks, vol. 4, pp. 125–145, 1974.
[11] J. W. Suurballe and R. E. Tarjan, “A quick method for finding shortest pairs of disjoint paths”, Networks, vol. 14, no. 2, pp. 325–336, 1984.
Kolekcja BazTech
Identyfikator YADDA bwmeta1.element.baztech-article-BAT8-0001-0005