인터넷 라우터에서의 패킷 분류는 들어오는 모든 패킷에 대하여 패킷이 입력되는 속도와 같은 속도로 수행되어야 하는데, 여러 헤더 필드에 대해 다차원 검색을 수행하여야 하므로, 라우터 설계에 있어 가장 어려운 문제중의 하나이다. 계층적 패킷 분류 구조는 하나의 필드 검색이 끝날 때마다 검색 영역이 현저하게 줄어듦으로 매우 효율적이다. 그러나 계층적 구조들은 빈 노드와 역추적이라는 두가지 문제를 내재하고 있다. 본 논문에서는 두가지 문제를 동시에 해결하는 새로운 계층적 패킷분류 구조를 제안한다. 역추적 문제는 셋-프루닝 기법을 이용하여 해결하였으며, 이진 검색트리를 적용하여 빈노드를 제거하였다. 시뮬레이션 결과 제안된 알고리즘은 메모리 요구량의 증가 없이 검색 성능을 현저히 향상시킴을 확인하였다. 또한 셋-프루닝에 있어 제한된 룰의 복사를 적용하는 최적화 기법을 제안한다.
Packet classification in the Internet routers requires multi-dimensional search for multiple header fields for every incoming packet in wire-speed, hence packet classification is one of the most important challenges in router design. Hierarchical packet classification is one of the most effective solutions since search space is remarkably reduced every time a field search is completed. However, hierarchical structures have two intrinsic issues; back-tracking and empty internal nodes. In this paper, we propose a new hierarchical packet classification algorithm which solves both problems. The back-tracking is avoided by using the set-pruning and the empty internal nodes are avoided by applying the binary search tree. Simulation result shows that the proposed algorithm provides significant improvement in search speed without increasing the amount of memory requirement. We also propose an optimization technique applying controlled rule copy in set-pruning.
