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

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.

---

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.