블룸필터와 리프-푸싱 트라이 기반 IP 주소 롱기스트 프리픽스 매칭 및 FPGA 구현 연구

IP Longest Prefix Matching with Bloom Filter and Leaf-Pushing Trie

연구 내용

온칩 Bloom filter와 오프칩 해시 테이블을 결합해 롱기스트 프리픽스 매칭을 와이어스피드에 가깝게 수행하는 연구

라우터에서 IP 주소 롱기스트 프리픽스 매칭은 포워딩 테이블 조회의 핵심 기능입니다. 본 연구는 trie에서 프리픽스가 리프에 집중되도록 leaf-pushing 절차를 적용한 뒤, on-chip Bloom filter로 프리픽스 존재 여부를 빠르게 판정하여 off-chip 해시 테이블 접근을 최소화합니다. 음성 판정은 조회 비트를 단계적으로 줄이는 longest-first 탐색과 결합되어, 실제 데이터 구간에서 느린 메모리 접근을 줄이는 구조를 사용합니다. 또한 C++ 검증과 함께 Verilog 기반 FPGA 구현으로 처리량 특성을 확인하여 알고리즘-하드웨어 매핑 관점의 설계 절차를 제공합니다.

관련 프로젝트

1건

연구 흐름

초기에는 leaf-pushing trie에 모든 프리픽스를 배치하고, Bloom filter의 negative 결과를 이용해 longest-first 탐색을 수행하는 IP address lookup 알고리즘을 제안했습니다. 이후 실제 백본 라우터 라우팅 데이터로 검증 범위를 확장하면서, on-chip Bloom filter가 불필요한 off-chip 해시 테이블 접근을 줄인다는 동작 특성을 확인했습니다. 최근에는 동일한 접근을 FPGA 구현으로 옮겨 Verilog로 로직을 구성하고, 시뮬레이션 기반 처리량 특성을 제시하는 방향으로 하드웨어 친화성을 강화했습니다. 병행하여 도메인특화 반도체 설계 역량을 활용한 구현 기반 후속 연구를 수행합니다.

활용 가능성

활용 가능성은 알앤디써클 특화 AI 에이전트가 생성한 내용으로, 실제 연구 가능 여부는 연구실과의 논의가 필요합니다.

차세대 라우터 포워딩 엔진
전력 효율형 프리픽스 검색
온칩-오프칩 하이브리드 조회 구조
FPGA 기반 네트워크 가속
대용량 라우팅 테이블 처리
TCAM 의존도 축소 설계
데이터센터 네트워크 스위칭
CIDR 프리픽스 매칭 처리
저지연 패킷 처리 파이프라인
블룸필터 크기 설계 가이드