Fast IP forwarding with compressed prefix trees

OData support
Dr. Rétvári Gábor Ferenc
Department of Telecommunications and Media Informatics

Due to the continuous growth of the internet, in recent years the size and load of the IP routers' FIB (Forwarding Information Base) have increased significantly. The cause of this – apart from the growing - is the spreading use of mobile telecommunication devices, and IPv6 based technology. In modern routers the most widely used FIB data structure is the prefix tree, which can serve millions of complex lookup queries and update commands, but its memory consumption is significantly high.

In this work I introduce some of the algorithms that aim to compress this data structure, especially examining in detail the so-called trie folding algorithm. This algorithm needs an auxiliary data structure, for which I also introduce different ways to implement, including a novel approach to the problem. However, effectively compressing the FIB is only the first step towards a real world application, because this data structure also needs to support update and delete commands in its compressed state. For this task I introduce an algorithm.

In order to evaluate the effectiveness of these algorithms, I implemented a simulation software. After describing this software in detail, I move on to the results of my measurements. During the analysis I asked questions like 'what is the effectiveness of these compression methods?', or 'how much time does it take to run the algorithm?' I also examined the time and memory consumption of the aforementioned auxiliary data structure. Finally I ran simulations and made measurements in dynamic environment, after which I found that the trie folding algorithm could be a good FIB compression method in real IP routers.


Please sign in to download the files of this thesis.