Longest Name Prefix Match on Multi-Core Processor

As a new Interest architecture, Named Data Networking (NDN) focuses on data itself rather than where it locates, and thus uses the data names rather than host addresses to forward network packets. As such, longest name prefix lookup becomes one of the key component of NDN's forwarding plane, which is more challenging than IP prefix lookup because the constitution of names is much more complex than IP addresses. The state-of-the-art approach adopts binary search over name prefix lengths with counting bloom filters employed to reduce unnecessary probes, and has achieved desirable comprehensive performance. However, it requires incremental computation and thus can benefit few from multi-core processors. In this paper, we propose the Parallel Binary Search scheme, with a series of designated mechanisms from algorithmic and systematic perspectives, for fast and memory-efficient name lookup on multi-core processors. Our extensive evaluations show that PBS can gain a speedup around 3 times over the state-of-the-art approach when multiple cores are utilized, at the cost of slightly more memory consumption.