Scalable name-based packet forwarding: From millions to billions

Named-based packet forwarding represents a core characteristic of many information-centric networking architectures. IP-inspired forwarding methods are not suitable because a) name-based forwarding must support variable-length keys of unbounded length, and b) namespaces for data are substantially larger than the global address prefix rulesets used in today's Internet. In this paper, we introduce and evaluate an approach that can realistically scale variable-length name forwarding to billions of prefixes. Our methods are driven by two key insights. First, we show that, represented by binary strings, a name-based forwarding table of several millions of entries can be notably compressed by a Patricia trie to fit in contemporary fast memory of a line card. Second, we show that it is possible to design and optimize the data structure to make its size dependent only upon the number of rules in a ruleset, rather than the length of rules. We reduce our designs to practice and experimentally evaluate memory requirements and performance. We demonstrate that a ruleset with one million rules based on the Alexa dataset only needs 5.58 MiB memory, which can easily fit in fast memory like SRAM, and with one billion synthetic rules it takes 7.32 GiB memory, which is within the range of DRAM in a line card. These are about an order of magnitude improvement over the state-of-the-art solutions. The above efficient memory size produces high performance. Estimated throughput of the SRAM-and DRAM-based solutions are 284 Gbps and 62 Gbps respectively.