An Algorithm for Enumerating SRLG Diverse Path Pairs

• Autorzy: Gomes T. , Craveirinha J.
• Języki publikacji: EN

Abstrakty

EN

Telecommunication networks are intrinsically multi-layered, a single failure at a lower level usually corresponds to a multi-failure scenario at an upper layer. In this context, the concept of shared risk link group (SRLG) allows an upper layer to select, for a given active path (AP), a backup path (BP), which avoids every SRLG that may involve the selected AP, in the event of a failure. That is a SRLG diverse path set maybe defined as a set of paths, between an origin and a destination, such that no pair of paths can be simultaneously affected by any given failure (or risk) in a single failure scenario. Firstly we present the formulation of the SRLG di- verse path pair calculation problem in a directed network. An algorithm for enumerating SRLG diverse paths, by non decreasing cost of their total (additive) cost will be presented, which is based on an algorithm proposed for generating minimal cost node disjoint path pairs. The SRLG diverse path pairs may be node or arc disjoint, with or without length constraints. Computational results will be presented to show the efficiency of the proposed algorithm for obtaining node or arc disjoint SRLG diverse path pairs in undirected networks.

Słowa kluczowe

EN

routing; SRLG disjoint shortest paths; telecommunication networks

• Wydawca: Instytut Łączności - Państwowy Instytut Badawczy
• Czasopismo: Journal of Telecommunications and Information Technology
• Rocznik: 2010
• Tom: nr 3
• Strony: 5--12
• Opis fizyczny: Bibliogr. 17 poz., rys., tab.

Twórcy

autor

Gomes T.

autor

Craveirinha J.

• Department of Electrical Engineering and Computers, University of Coimbra, Pinhal de Marrocos, 3030-290 Coimbra, Portugal,

Bibliografia

• [1] J. Q. Hu, “Diverse routing in optical mesh networks”, IEEE Trans. Commun., vol. 51, no. 3, pp. 489–494, 2003.
• [2] M. J. Rostami, S. Khorsandi, and A. A. Khodaparast, “CoSE: ASRLG-disjoint routing algorithm”, in Proc. Fourth Eur. Conf. Univ. Multiserv. Netw. ECUMN’07, Toulouse, France, 2007.
• [3] D. Xu, Y. Chen, Y. Xiong, C. Qiao, and X. He, “On finding disjoint paths in single and dual link cost networks”, in IEEE INFOCOM 2004 Conf., Hong Kong, 2004.
• [4] A. K. Todimala and B. Ramamurthy, “IMSA: an algorithm for SRLG diverse routing in WDM mesh networks”, in Proc. Int. Conf. Comput. Commun. Netw. ICCCN 2004, Chicago, USA, 2004, pp. 199–204.
• [5] 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.
• [6] R. Bhandari, Survivable Networks, Algorithms for Diverse Routing. Norwell: Kluwer, 1999.
• [7] A. K. Todimala and B. Ramamurthy, “A heuristic with bounded guarantee to compute diverse paths under shared protection in WDM mesh networks”, in Proc. IEEE Globlecom 2005 Conf., St. Louis, USA, 2005, pp. 1915–1919.
• [8] P. Laborczi, J. Tapolcai, P.-H. Ho, T. Cinkler, A. Recski, and H. T. Mouftah, “Algorithms for asymmetrically weighted pair of disjoint paths in survivable networks”, in Proc. Des. Rel. Commun. Netw. DCRN 2001, Budapest, Hungary, 2001, pp. 220–227.
• [9] X. Pan and G. Xiao, “Algorithms for the diverse routing problem in WDM networks with shared risk link groups”, in Int. Conf. Comput. Sci. ICCS 2004, Krakow, Poland, 2004, pp. 381–385.
• [10] X. Pan and G. Xiao, “Heuristics for diverse routing in wavelengthrouted networks with shared risk link groups”, Phot. Netw. Commun., vol. 11, no. 1, pp. 29–38, 2006.
• [11] D. Xu, Y. Xiong, C. Qiao, and G. Li, “Trap avoidance and protection schemes in networks with shared risk link groups”, J. Lightw. Technol., vol. 21, no. 11, pp. 2683–2693, 2003.
• [12] J. C. N. Cl´ımaco and M. M. B. Pascoal, “Finding non-dominated bicriteria shortest pairs of disjoint simple paths”, Comput. Oper. Res., vol. 36, no. 11, pp. 2892–2898, 2009.
• [13] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, Springer Monographs in Mathematics. Great Britain: Springer, 2002.
• [14] 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.
• [15] E. Martins, M. Pascoal, and J. Santos, “An algorithm for ranking loopless paths”, Tech. Rep. 99/007, CISUC, 1999 [Online]. Available:http://www.mat.uc.pt/∼marta/Publicacoes/mps2.ps
• [16] D. Eppstein, “Finding the k shortest paths”, SIAM J. Comput., vol. 28, no. 2, pp. 652–673, 1999.
• [17] R. Dial, F. Glover, D. Karney, and D. Klingman, “A computational analysis of alternative algorithms and labeling techniques for finding shortest path trees”, Networks, vol. 9, no. 3, pp. 215–348, 1979.