이름 기반 데이터 네트워킹(Named Data Networking, NDN)을 구현하는 핵심 구성 요소로서, 보류 이자 테이블(Pending Interest Table, PIT)은 확장 가능하고 빠른 PIT 조회를 위해 효율적인 정확 일치(exact-matching) 알고리즘을 필요로 한다. 블룸 필터(Bloom filter, BF)는 정확 일치 연산을 수행하는 데 메모리 효율적인 자료구조이다. 본 논문에서는 BF 기반 PIT 아키텍처 3가지를 제안한다. 즉 기능적 블룸 필터(PIT using functional Bloom filters, FBF-PIT)를 사용하는 PIT, 반환 값을 갖는 카운팅 블룸 필터(PIT using counting Bloom filters with return values, rCBF-PIT)를 사용하는 PIT, 서명이 포함된 정제 rCBF-PIT(R-rCBF-PIT)이다. 제안된 BF 기반 PIT는 동일한 콘텐츠 이름을 갖는 Interest 패킷의 다중 수신 얼굴(face)을 저장하기 위해, 새로운 BF를 점진적으로 할당한다. Data 패킷 조회를 위해, 제안된 PIT 아키텍처는 일치하는 얼굴을 찾기 위해 모든 BF 구조에 동시에 접근하고(즉, 일치하는 Interest 패킷 정보), 그 얼굴을 삭제한다. FBF-PIT에 사용되는 기능적 블룸 필터(FBF)는 키 없이 값만 저장하는 키-값 자료구조이다. 그러나 FBF-PIT에서 저장되는 패킷 수가 증가함에 따라 FBF의 재사용 불가능한 충돌 셀(non-reusable conflict cells) 수가 증가하므로, 판별 불가능률(indeterminable rate)이 증가한다. 판별 불가능률을 낮추기 위해, 재사용 가능한 충돌 셀을 허용하는 반환 값을 갖는 카운팅 블룸 필터(rCBFs)를 사용하는 rCBF-PIT를 제안한다. Interest 패킷에 대한 오탐(false positive)은 잘못된 삭제를 초래하여, 수신 Data 패킷에 대한 오탐(즉 false negatives)을 유발할 수 있다. 대부분의 오탐은 첫 번째 BF 구조에서 발생하므로, 최종적으로 첫 번째 rCBF를 서명 필드가 포함된 rCBF로 대체한 R-rCBF-PIT를 제안한다. 또한 제안된 PIT는 항목 만료를 위한 유효 비트(valid bit)와 히트 비트(hit bit)를 사용하여 에이징(aging) 메커니즘을 제공한다. 시뮬레이션 결과, rCBF-PIT와 R-rCBF-PIT 모두 FBF-PIT에 비해 판별 불가능률을 81% 이상 감소시키는 것으로 나타났다. 또한 R-rCBF-PIT는 첫 번째 rCBF에 서명 필드를 포함함으로써, 잘못된 삭제로 인해 발생하는 false negatives를 해결함을 보여준다.

*본 초록은 AI를 통해 원문을 번역한 내용입니다. 정확한 내용은 하기 원문에서 확인해주세요.