IP 주소 검색 구조는 라우터 시스템에서 고속 네트워크 기술의 중요한 이슈가 되고 있으며 패킷 전달의 성능을 좌우하는 주요한 문제 요소로 지적되고 있다. 본 논문에서는 복수 해슁의 적응적인 적용과 프리픽스 그룹화를 이용하여 효율적인 고속 IP 주소 검색 구조를 제안한다. 여러 라우팅 데이터의 엔트리 분포를 분석하여 프리픽스를 그룹화하고 그룹별로 적용되는 해쉬함수의 개수를 적응적으로 적용하여 해슁에 의한 충돌(collision)을 줄일 수 있었으며 이를 통해 테이블의 수를 최적화하고 메모리 효율을 높일 수 있었다. 또한 제안하는 구조는 단 한 번의 메모리 접근만으로 포워딩 테이블의 구성 및 검색 과정을 수행할 수 있는 고속 구조이다.
IP address lookup has become a major bottleneck of packet forwarding and a critical issue for high-speed networking techniques in routers. In this paper, we propose an efficient high-speed IP address lookup scheme using adaptive multiple hashing and prefix grouping. According to our analysis results based on routing data distributions, we grouped prefix lengths and selected the number of hash functions in each group adaptively. As a result, we can reduce collisions caused by hashing. Accordingly, a forwarding table of our scheme has good memory efficiency, and thus is organized with the proper number of memory modules. Also, the proposed scheme has the fast building and searching mechanisms to develop the forwarding table only during a single memory access.
