TU Berlin

Internet Network ArchitecturesAll Publications

Page Content

to Navigation

All publications

On the Compressibility of Forwarding Tables in the Internet
Citation key G-OTCOFTITI-11
Author Golovatenko, Roman
Year 2011
Address Berlin, Germany
Month June
School Technische Universit├Ąt Berlin
Abstract This thesis presents a study of the compressibility of forwarding tables in the Internet. The size of the forwarding tables that routers need to keep increases steadily. This leads to pressure on the forwarding plane and high memory requirements on routers. We studied the compressibility of forwarding tables based on the state-of-the-art algorithm, called Optimal Routing Table Constructor (ORTC). The evaluation of the algorithm contains two parts. In the first part, we analyze the compressibility of BGP table snapshots. In the second part, we study the compression behavior of the algorithm for incremental updates as well as the efficiency of the algorithm. Our analysis is based on publicly available BGP data. Our results show that the size of the output forwarding tables can be reduced down to 30\% of the original size, while guaranteeing the same forwarding behavior as with uncompressed input table. Our study shows that applying changes incrementally to the compressed forwarding table leads to much less changes compared to a complete re-computation of the forwarding table. This suggests that BGP updates can be applied in such a way that minimizes the re-computation time as well as the changes to the forwarding table.
Bibtex Type of Publication Diplomarbeit
Link to publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe