About what is the smallest size we can compress an IP Forwarding Information
Base (FIB) down to, while still guaranteeing fast lookup? Is there some notion
of FIB entropy that could serve as a compressibility metric? As an initial
step in answering these questions, we present a FIB data structure, called
Multibit Burrows-Wheeler transform (MBW), that is fundamentally pointerless,
can be built in linear time, guarantees theoretically optimal longest prefix
match, and compresses to higher-order entropy. Measurements on a Linux
prototype provide a first glimpse of the applicability of MBW.
http://dl.acm.org/citation.cfm?id=2390232
Rétvári Gábor, tudományos munkatárs, Kőrösi Attila, tanszéki mérnök, BME Távközlési és Médiainformatikai Tanszék, retvari,korosi@tmit.bme.hu
2013. február 28.