SCIENCE@home

A Distance-Encoded Bloom Filter for Fast NDN Name Lookup

Junghwan Kim,Myeong-Cheol Ko

Published 2025 in Applied Sciences

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.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-24 of 24 references · Page 1 of 1

CITED BY