Hirochika Asai

Poptrie: A Compressed Trie with Population Count for Fast and Scalable Software IP Routing Table Lookup

By: 
Hirochika Asai, Yasuhiro Ohara
Appears in: 
CCR August 2015

Internet of Things leads to routing table explosion. An inexpensive approach for IP routing table lookup is required against ever growing size of the Internet. We contribute by a fast and scalable software routing lookup algorithm based on a multiway trie, called Poptrie. Named after our approach to traversing the tree, it leverages the population count instruction on bit-vector indices for the descendant nodes to compress the data structure within the CPU cache.

Syndicate content