A Distance-Encoded Bloom Filter for Fast NDN Name Lookup

Abstract

Named data networking (NDN) is a content-centric network architecture that requires efficient name lookup to forward packets based on hierarchical content names. Whereas IP lookup operates on fixed-length addresses, NDN name lookup must identify the longest matching prefix (LMP) from a variable-length name space, making it computationally challenging. Hash table-based approaches provide O (1) search complexity but often require multiple accesses due to the unknown LMP length. To mitigate excessive off-chip memory accesses, Bloom filter-assisted pre-checking is commonly employed. However, conventional Bloom filter-based approaches can only perform membership tests and do not provide information about the next search range, which limits their ability to effectively reduce Bloom filter accesses. This paper proposes a distance-encoded Bloom filter to improve name lookup efficiency. It encodes two distance values into the Bloom filter, enabling a more refined search range compared to binary search-based methods. By utilizing these encoded distances, the proposed scheme not only reduces the number of Bloom filter queries but also ensures that only prefix nodes need to be stored in the hash table. This helps reduce hash collisions and minimize off-chip memory accesses. Experimental evaluation using large-scale FIB datasets shows that the proposed approach reduces both Bloom filter accesses and hash table lookups, which contributes to improving overall lookup performance.

Keywords

• named data networking
• name lookup
• longest matching prefix
• Bloom filter
• distance encoding
• hash table