Original title:
Framework pro analýzu změn v datových strukturách páteřních směrovačů
Translated title:
Framework for Analysis of Changes in Data Structures of Core Routers
Authors:
Bednářová, Marie ; Martínek, Tomáš (referee) ; Matoušek, Jiří (advisor) Document type: Master’s theses
Year:
2024
Language:
eng Publisher:
Vysoké učení technické v Brně. Fakulta informačních technologií Abstract:
[eng][cze]
Páteřní směrovače jsou síťová zařízení, která v kontextu výkonnosti musejí držet krok s požadavky nových internetových služeb a aplikací. Jeden z faktorů, který výkonnost směrovače ovlivňuje, je klasifikační algoritmus, který je součástí procesu přeposílání příchozích paketů na základě jejich cílové IP adresy. Každá adresa je předložena Forwarding Information Base (FIB), která implementuje algoritmus Longest Prefix Matching (LPM) - hledání nejdelšího shodného prefixu. FIB tabulka obsahuje prefixy všech dosažitelných sítí z daného směrovače a na základě poskytnuté IP adresy pak rozhodne, kam daný paket dále přeposlat, aby dorazil na místo určení. Existuje několik LPM algoritmů s různými vlastnostmi, jako je rychlost vyhledávání, náročnost na paměť, náročnost na aktualizaci, a další. FIB tabulka se v průběhu provozu směrovače aktualizuje na základě změn ve Routing Information Base (RIB). Tyto změny jsou prováděny na základě směrovacích informací, které si mezi sebou směrovače vyměňují. Z těchto poznatků vychází téma této práce, které se věnuje tomu jak, dynamické jsou změny datových struktur FIB tabulek v páteřních směrovačích. Tato práce se věnuje návrhu a implementaci frameworku, který je možné použít jako pomocný nástroj pro vyhodnocování LPM algoritmů, na základě toho, jak daný algoritmus mění datové struktury FIB tabulek v páteřních směrovačích. Test je prováděn pomocí simulace, kdy LPM algoritmus je nejprve umístěn do zjednodušeného modelu směrovače jako implementace FIB tabulky. Poté, na základě zpráv protokolu BGP (Border Gateway Protocol), bude algoritmus aktualizovat datovou strukturu FIB tabulky. Celá simulace je monitorována a účinky změn jsou zaznamenávány. Na konci simulace jsou poskytnuty výsledné statistiky. Framework dále umožňuje změnit implementaci LPM algoritmu a také nastavení samotné simulace. Nakonec je funkčnost frameworku prověřena na základě experimentů.
Core routers have to be able to work at high speed to keep up with the demands of new Internet services and applications. One of the factors is the classification algorithm utilized in a router in the process of forwarding incoming packets based on their destination IP addresses. Each address is provided to the Forwarding Information Base (FIB) table, which implements the Longest Prefix Matching algorithm (LPM). The FIB table stores prefixes which represents reachable networks. Based on the provided IP address, the FIB table can decide in which way the packet should continue to reach the final destination. There are many LPM algorithms, and each can provide different properties, such as search speed, storage requirements, complexity of updates, etc. The FIB table is constructed from Routing Information Base (RIB) and during the operation of the router, both structures are updated based on the routing information exchanged between routers. In this sense, the thesis focuses on how the data structures of the FIB tables are changed in core routers. The thesis proposes a benchmark framework that helps to show how different LPM algorithms behave in the context of changes of the FIB data structures. The benchmark is done by simulation, where the LPM algorithm is put in the simplified router model. Then, using the Border Gateway Protocol (BGP) messages, the algorithm modifies the FIB data structure. The whole simulation is monitored and the effects of changes are stored. At the end of the simulation, statistical results are generated. Finally, the framework provides a functionality to change the LPM algorithm and other simulation parameters. The final result is then verified by multiple experiments.
Keywords:
BGP; Binary Trie; FIB; framework; LPM; Přepínací tabulka; RIB; Router; Směrovací tabulka; statistiky; Tree Bitmap; BGP; Binary Trie; FIB; Forwarding table; framework; LPM; RIB; Router; Routing table; statistics; Tree Bitmap
Institution: Brno University of Technology
(web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library. Original record: https://hdl.handle.net/11012/248338
guest ::
