|
|
Framework for Analysis of Changes in Data Structures of Core Routers
Bednářová, Marie ; Martínek, Tomáš (oponent) ; Matoušek, Jiří (vedoucí práce)
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.
|
host ::
RSS.