Applied Sciences · 2019 · 16 citations · 24 references
ComputingComputer ScienceComputer SystemsComputer NetworksData StructuresDatabasesLookup TablesMemory Hierarchy OptimizationRoutingBloom FiltersInternet ArchitectureLookup Table ArchitecturesLut ArchitectureNetworkingOff-chip Memory SystemsOn-chip Memory DesignOn-chip Memory Hierarchies
Network traffic has increased rapidly in recent years, mainly associated with the massive growth of various applications on mobile devices. Named data networking (NDN) technology has been proposed as a future Internet architecture for effectively handling this ever-increasing network traffic. In order to realize the NDN, high-speed lookup algorithms for a forwarding information base (FIB) are crucial. This paper proposes a level-priority trie (LPT) and a 2-phase Bloom filter architecture implementing the LPT. The proposed Bloom filters are sufficiently small to be implemented with on-chip memories (less than 3 MB) for FIB tables with up to 100,000 name prefixes. Hence, the proposed structure enables high-speed FIB lookup. The performance evaluation result shows that FIB lookups for more than 99.99% of inputs are achieved without needing to access the database stored in an off-chip memory.
24
Space/time trade-offs in hash coding with allowable errors
Burton H. Bloom · Communications of the ACM · 1970 · 7.5K citations · Full text
Van Jacobson, Diana K. Smetters, James D. Thornton et al. · 2009 · 4K citations
Lixia Zhang, Alexander Afanasyev, Jeffrey A Burke et al. · ACM SIGCOMM Computer Communication Review · 2014 · 2.2K citations · Full text
Network Applications of Bloom Filters: A Survey
Andrei Broder, Michael Mitzenmacher · Internet Mathematics · 2004 · 2K citations · Full text