Scalable, Memory-efficient Pending Interest Table of Named Data Networking

Named Data Networking (NDN) is a future Internet paradigm which allows user to retrieve and distribute content using their application names. Each NDN router maintains the state of each request packet in the Pending Interest Table (PIT) until corresponding data packet returns. The use of application name, i.e., variable-length key of unbounded length for communication instead of IP address increases memory consumption and lookup cost at the router. Therefore, the PIT should be able to store millions/billions of entries into on-chip memory. However, traditional hash and trie based methods cannot meet these requirements separately. In this paper, we present a scalable and memory-efficient name encoding based lookup scheme (CRT-PIT) leveraging the benefits of both hash and trie data structures for implementing the PIT at NDN forwarding daemon. In CRT-PIT, we calculate the fixed-length encoded names of the content name and then, encoded names are stored in the concurrent path-compressed trie to reduce the storage and lookup latency requirement by not maintaining the redundant information. Extensive experiments show that CRTPIT consumes only 4.84 MB memory for one million names which is an order of magnitude improvement over the baseline solutions.