Analiza in simulacija pokritosti hitrega preusmerjanja prometa

Zvonc, Maks (author), Pustišek, Matevž (mentor)

Ob okvari povezave ali vozlišča v omrežju IP mora usmerjevalni protokol okvaro zaznati, razširiti posodobljene podatke o stanju povezav in ponovno izračunati najkrajše poti. Ta postopek traja od nekaj sto milisekund do več sekund, kar je za sodobne storitve v realnem času predolgo. Težavo rešujejo metode hitrega preusmerjanja prometa (angl. IP Fast Reroute, IP FRR), ki rezervne poti izračunajo vnaprej. Med njimi se najpogosteje pojavijo metode LFA (angl. Loop-Free Alternate), Remote LFA (angl. Remote Loop-Free Alternate), Directed LFA (angl. Directed Loop-Free Alternate) in TI-LFA (angl. Topology Independent Loop-Free Alternate). Delež poti, ki jih te metode lahko zaščitijo, je močno odvisen od topologije omrežja, zato operater potrebuje orodje, ki pokritost izračuna za njegovo specifično omrežje. V diplomskem delu smo razvili simulator v programskem jeziku Python. Simulator omrežje predstavi z uteženim usmerjenim grafom, najkrajše razdalje izračuna z Dijkstrovim algoritmom in nato za vsak primer okvare (S, D, E), kjer je S računajoči usmerjevalnik, D cilj, E pa primarni zaščiteni naslednji skok, po pogojih iz dokumentov RFC 5286, RFC 7490 in RFC 8102 preveri, ali rezervno pot zagotavljajo ECMP, LFA, Remote LFA (z osnovnim in razširjenim P-prostorom ter zaščito vozlišč), Directed LFA in TI-LFA. Topologijo prebere iz zapisa YAML ali iz izvoza baze stanja povezav protokola OSPF. Pokritost smo ovrednotili na treh referenčnih in dveh operaterskih topologijah s 112 oziroma 240 usmerjevalniki. Glavno primerjavo smo izvedli brez robnih vozlišč, da vozlišča brez alternativnih poti do jedra omrežja ne bi zakrila razlik med metodami. Rezultati so pokazali, da je pokritost metod LFA, Remote LFA in Directed LFA odvisna od značilnosti topologije in metrik povezav. V glavni primerjavi brez robnih vozlišč je metoda TI-LFA na vseh obravnavanih topologijah dosegla popolno pokritost, zato značilnosti topologije in vrednosti metrik povezav na njeno pokritost niso vplivale.

• Language: Slovenian
• Keywords: usmerjanje, hitro preusmerjanje prometa, IP FRR, LFA, Remote LFA, Directed LFA, TI-LFA, pokritost zaščite, simulacija
• Work type: Bachelor thesis/paper
• Typology: 2.11 - Undergraduate Thesis
• Organization: FE - Faculty of Electrical Engineering
• Year: 2026
• PID: 20.500.12556/RUL-186423
• COBISS.SI-ID: 290187011
• Publication date in RUL: 01.09.2026

Secondary language

• Language: English
• Title: Analysis and Simulation of IP Fast Reroute Coverage

Abstract

When a link or node fails in an IP network, the routing protocol must detect the failure, flood updated link-state information, and recompute the shortest paths. This process can take from several hundred milliseconds to several seconds, which is too long for modern real-time services. This problem is addressed by IP Fast Reroute (IP FRR) methods, which compute backup paths in advance. The most common methods include LFA (Loop-Free Alternate), Remote LFA (Remote Loop-Free Alternate), Directed LFA (Directed Loop-Free Alternate), and TI-LFA (Topology Independent Loop-Free Alternate). The proportion of paths that these methods can protect depends strongly on the network topology. An operator therefore needs a tool that calculates the protection coverage for a specific network. In this thesis, we developed a simulator in Python. The simulator represents the network as a weighted directed graph, calculates shortest-path distances using Dijkstra's algorithm, and then, for each failure case (S, D, E), where S is the computing router, D is the destination, and E is the primary protected next hop, determines whether ECMP, LFA, Remote LFA (using the basic and extended P-space and node protection), Directed LFA, or TI-LFA provides a backup path according to the conditions defined in RFC 5286, RFC 7490, and RFC 8102. The topology is read from either a YAML description or an export of the OSPF link-state database. We evaluated the protection coverage using three reference topologies and two operator-network topologies containing 112 and 240 routers, respectively. The primary comparison excluded edge nodes so that nodes without alternative paths to the network core would not obscure the differences between the methods. The results showed that the protection coverage provided by LFA, Remote LFA, and Directed LFA depends on the characteristics of the topology and the link metrics. In the primary comparison excluding edge nodes, TI-LFA achieved full coverage in all evaluated topologies; consequently, neither the topology characteristics nor the link metric values affected its protection coverage.

• Keywords: routing, IP fast reroute, IP FRR, loop-free alternates, LFA, remote LFA, directed LFA, TI-LFA, protection coverage, simulation