Metoda szybkiego wyznaczania par węzłowo-rozłącznych tras dla ochrony transmisji unicast

• Autorzy: Myslitski K. , Rak J.

Identyfikatory

DOI

10.15199/59.2015.8-9/6

Warianty tytułu

EN

A method of fast computation of node-disjoint path pairs for protection of unicast traffic

• Języki publikacji: PL

Abstrakty

PL

W celu ochrony transmisji przed awarią węzłów/łączy wykorzystuje się alternatywne trasy transmisji. Jednakże złożoność obliczeniowa dostępnych algorytmów doboru tras rozłącznych często istotnie wstrzymuje producentów sprzętu od implementacji tychże rozwiązań. Przedstawiono nowe podejście do wyznaczania par rozłącznych tras, oparte na transformacji grafu sieci w metastrukturę. Wyniki badań dotyczące czasu wyznaczania tras pokazują istotną przewagę opisanej metody (~20%) nad podejściem referencyjnym (algorytmem) Bhandariego.

EN

Alternate (backup) paths are commonly utilized in communication networks to provide protection against failures of network nodes/links. However, computational complexity of available algorithms of disjoint paths calculation frequently prevents the vendors of network equipment from implementing such solutions. In this work, we present a new approach to disjoint paths calculation based on transformation of the original network graph into the respective meta-structure. Results of analysis referring to the computational time show a significant advantage of our method (about 20%), compared to the respective characteristics of the reference Bhandari's algorithm.

Słowa kluczowe

PL

niezawodność sieci teleinformatycznych; przeżywalność sieci teleinformatycznych; trasy rozłączne; czas obliczeń

EN

network resilience; network survivability; disjoint paths; computational time

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne
• Rocznik: 2015
• Tom: nr 8-9
• Strony: 717--723
• Opis fizyczny: Bibliogr. 10 poz., rys., tab.

Twórcy

autor

Myslitski K.

• Katedra Teleinformatyki, Wydział Elektroniki, Telekomunikacji i Informatyki, Politechnika Gdańska

autor

Rak J.

• Katedra Teleinformatyki, Wydział Elektroniki, Telekomunikacji i Informatyki, Politechnika Gdańska

Bibliografia

• [1] Bhandari A R.: Survivable networks: algorithms for diverse routing. Kluwer Academic Publishers, 1999
• [2] Chołda R, Mykkeltveit A., Helvik B., Wittner O., Jajszczyk A.: A survey of resilience differentiation frameworks in communication networks, IEEE Communications Surveys & Tutorials, vol. 9, no. 4,2007
• [3] Dijkstra E.W.: A note on two problems in connexion with graphs, Numerische Mathematik, vol. 1,1959
• [4] Dikbiyik R, Tornatore M., Mukherjee B.: Exploiting excess capacity for survivable traffic grooming in optical backbone networks, IEEE/OSA Journal of Optical Communications and Networking, vol. 6, no. 2,2014
• [5] lqbal R, Kuipers F.A.: Disjoint paths in networks, to appear in Wiley Encyclopedia of Electrical and Electronics Engineering, 2015
• [6] Oki E.: Linear programming and algorithms for communication networks: a practical guide to network design, control, and management, CRC Press, 2012
• [7] Zmodyfikowany schemat sieci PIONIER: http://www.pionier.net.pl/on-line/pl/projekty/, dostęp: 24 kwietnia 2015
• [8] Pióro M., Medhi D.: Routing, flow, and capacity design in communication and computer networks, Elsevier, 2004
• [9] Rak J.: Fast service recovery under shared protection in WDM networks, IEEE/OSA Journal of Lightwave Technology, vol. 30, no. 1, 2012
• [10]Suurballe J.W., Tarjan R.E.: A quick method for finding shortest pairs of disjoint paths, Networks, vol. 14, no. 2,1984