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

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