인터넷 트래픽의 급증과 포워딩 테이블 항목의 빠른 증가로 인해, 인터넷 라우터에서 와이어 속도의 패킷 포워딩을 달성하기 위해서는 알고리즘적 개선과 하드웨어 혁신이 모두 요구된다. 본 논문에서는 리프-푸싱 trie에 접두사를 저장하는 Bloom filter를 결합한 longest-first 탐색 알고리즘을 제안한다. 제안하는 방법은 on-chip Bloom filter를 활용하여 trie 내 접두사의 존재 여부를 표시하고, off-chip 해시 테이블을 통해 각 접두사에 대한 대응 출력 포트 정보를 저장한다. 유입되는 각 IP 주소에 대해 Bloom filter 질의는 최장 길이부터 시작하며, 음성 결과가 나올 때마다 질의되는 비트 수를 1씩 감소시킨다. Bloom filter에 대한 질의 결과가 양성일 때만 off-chip 해시 테이블에 접근하므로, 합리적인 Bloom filter 크기를 가정하면 느린 off-chip 메모리에 대한 접근이 최대 한 번으로 최소화된다. 제안하는 접근은 C++를 사용해 시뮬레이션하였고, 필드 프로그래머블 게이트 어레이(field programmable gate array, FPGA) 구현을 위해 Verilog로 구성하였다. 실험 결과에 따르면, 제안하는 방법은 100MHz의 클록 주파수에서 초당 0.8백만 패킷의 처리량을 달성한다.

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