Dynamically Allocated Bloom Filter-Based PIT Architectures
- 주제(키워드) Faces , Information filters , Matched filters , Programming , Indexes , Hash functions , Filtering algorithms , Bloom filter , dynamic data structure , named data networking , pending Interest table
- 주제(기타) Computer Science, Information Systems
- 주제(기타) Engineering, Electrical & Electronic
- 주제(기타) Telecommunications
- 설명문(일반) [Jang, Saeyoung; Lim, Hyesook] Ewha Womans Univ, Dept Elect & Elect Engn, Seoul 03760, South Korea; [Byun, Hayoung] Myongji Univ, Dept Elect Engn, Yongin 17058, South Korea
- 등재 SCIE, SCOPUS
- OA유형 gold
- 발행기관 IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
- 발행년도 2022
- 총서유형 Journal
- URI http://www.dcollection.net/handler/ewha/000000191043
- 본문언어 영어
- Published As https://doi.org/10.1109/ACCESS.2022.3158368
초록/요약
As a key component in implementing Named Data Networking (NDN), Pending Interest Table (PIT) requires an efficient exact-matching algorithm for a scalable and fast PIT lookup. A Bloom filter (BF) is a memory-efficient data structure for performing exact matching operations. In this paper, three different BF-based PIT architectures are proposed: PIT using functional Bloom filters (FBF-PIT), PIT using counting Bloom filters with return values (rCBF-PIT), and a refined rCBF-PIT with signatures (R-rCBF-PIT). The proposed BF-based PITs incrementally allocate a new BF for storing multiple incoming faces of Interest packets with the same content name. For a Data packet lookup, the proposed PIT architectures simultaneously access every BF structure to find matching faces and delete the faces (i.e., matching Interest packet information). The functional Bloom filter (FBF) used in an FBF-PIT is a key-value data structure that stores values only without keys. However, because the number of non-reusable conflict cells in the FBF increases as the number of stored packets increases in the FBF-PIT, the indeterminable rate increases. To decrease the indeterminable rate, we propose the rCBF-PIT, which uses counting Bloom filters with return values (rCBFs), allowing reusable conflict cells. False positives for Interest packets lead to incorrect deletions that can cause false negatives for incoming Data packets. Because most of the false positives occur in the first BF structure, we finally propose the R-rCBF-PIT, in which the first rCBF is replaced with an rCBF with a signature field. The proposed PITs also provide an aging mechanism using a valid bit and a hit bit for entry expiration. Simulation results show that rCBF-PIT and R-rCBF-PIT both reduce the indeterminable rate by more than 81% compared with FBF-PIT. The results also show that R-rCBF-PIT resolves false negatives caused by incorrect deletions by including the signature fields in the first rCBF.
more