IP 주소 검색은 인터넷 라우터의 필수적인 기능의 하나로서, 라우터 전체의 성능을 결정하는 중요한 요소이다. 소프트웨어에 기반한 IP 주소 검색 방식의 성능 평가 기준 중 가장 중요한 것은 라우터의 처리 속도를 보장해 주는 의미를 갖는 최대 메모리 접근 횟수이다. 이진 프리픽스 트리 방식(BPT)은 최대 메모리 접근 횟수에 있어서 기존의 다른 소프트웨어에 기반한 방식 중 우수한 방식이지만, 트리의 구조가 불균형적이 되는 단점이 있다. 본 논문에서는 기존의 BPT 방식의 트리 생성 과정에 가중치 개념을 추가하여, 완전 균형 트리에 매우 근접하는 트리를 생성하는 가중 이진 프리픽스 트리 (WBPT) 방식을 제안한다. 제안하는 WBPT 방식은 기존의 소프트웨어에 근거한 방식들에 비교하여 최대 메모리 접근 횟수에 있어서 가장 적은 성능을 보인다. 또한 3만 개 정도의 프리픽스에 대해서 L2 캐쉬에 저장이 가능한 정도의 작은 메모리 크기를 요구하구 프리픽스의 추가, 삭제가 용이하므로 실제적인 라우터의 IP 검색을 위하여 사용될 수 있는 방식이다.
IP address lookup is one of the essential functions on internet routers, and it determines overall router performance. The most important evaluation factor for software-based IP address lookup is the number of the worst case memory accesses. Binary prefix tree (BPT) scheme gives small number of worst case memory accesses among previous software-based schemes. However the tree structure of BPT is normally unbalanced. In this paper, we propose weighted binary prefix tree (WBP) scheme which generates nearly balanced tree, through combining the concept of weight to the BPT generation process. The proposed WBPT gives very small number of worst case memory accesses compared to the previous software-based schemes. Moreover the WBPT requires comparably small size of memory which can be fit within L2 cache for about 30,000 prefixes, and it is rather simple for prefix addition and deletion. Hence the proposed WBPT can be used for software-based If address lookup in practical routers.
