인터넷 트래픽의 급증과 포워딩 테이블 항목의 빠른 증가로 인해, 인터넷 라우터에서 와이어 속도의 패킷 포워딩을 달성하기 위해서는 알고리즘적 개선과 하드웨어 혁신이 모두 요구된다. 본 논문에서는 리프-푸싱 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백만 패킷의 처리량을 달성한다.

본 논문은 라우터가 유입되는 각 패킷에 대해 적절한 출력 링크를 결정하기 위한 핵심 작업인 IP 주소 조회를 위한 새로운 알고리즘을 제안한다. 클래스리스 인터도메인 라우팅(CIDR) 체계의 도입과 함께, IP 주소 조회 문제는 와이어 속도에서 최장 일치 접두사(LMP)를 효율적으로 찾는 데 어려움을 수반한다. 이를 위해 오프칩 삼중치 콘텐츠 주소 지정 메모리(TCAM)가 흔히 사용되지만, 전력 소비와 큰 비용 측면에서 단점이 있다. 이에 대응하여 본 연구는 온칩 메모리에 저장된 블룸 필터(BF)와 오프칩 메모리에 저장된 해시 테이블을 활용하는 데 초점을 맞춘 알고리즘적 대안을 탐구한다. 우리는 각 접두사를 리프 푸싱(trie)에서 저장하는 방식으로 블룸 필터에 대해 최장 우선(longest-first) 탐색을 수행할 것을 제안한다. 리프 푸싱 절차에 따라 trie의 리프에만 접두사가 위치하므로, trie의 최장 수준부터 BF를 조회하는 것이 매우 효과적이다. 온칩 BF는 존재하지 않는 노드에 대해 음성 결과를 생성함으로써 불필요한 오프칩 해시 테이블 접근을 회피하는 역할을 한다. 제안한 알고리즘은 C++ 코드로 구현하였고 백본 라우터의 실제 라우팅 데이터에 대해 시험하였다. 그 결과, 충분한 크기의 블룸 필터가 주어지면 제안한 알고리즘은 각 IP 주소 조회마다 평균적으로 오프칩 해시 테이블 접근을 단 한 번만 요구함을 보여준다.