패킷 분류근 인터넷 망에서 QoS(Quality of Service)보장, VPN(Virtual Private Network)등과 같은 사용자들의 다양한 서비스를 수용하기 위한 중요한 요소이다. 패킷 헤더는 기본적으로 IP(Internet Protocol) 패킷 헤더 내의 목적지 주소뿐만 아니라 발신지 주소, 프로토콜, TCP(Transmission Control Protocol)포트 번호 등 여러 필드들을 조합하여 룰 테이블로부터 best matching 룰을 찾는 것이다. 본 논문에서는 멀티 비트 트라이 구조의 트리 비트맵을 이용하여 하드웨어적인 룰 검색이 가능한 패킷 분류 기법을 제안한다. 검색 대상 필드 및 패킷 분류 룰을 구성하는 프레픽스를 비교 단위가 되는 일정한 비트 크기의 멀티 비트로 나누고, 이와 같이 구분된 멀티 비트 단위로 트리 비트맵 기반의 룰 검색 기능을 수행한다. 제안한 기법은 프레픽스의 일정한 상위 비트들에 대해서는 인덱싱 키로 사용하여 룰 검색을 위한 메모리 액세스 횟수를 줄이도록 하였다. 또한 룰 검색시 성능 저하를 초래하는 백트랙킹이 발생하지 않도록 하기 위하여 룰 테이블 구축시 마커 프레픽스에 대한 처리 기법을 제안하였다 그리고 본 논문에서는 IPMA(Internet Performance Measurement Analysis) 프로젝트에서 제공하는 라우팅 테이블의 프레픽스들을 이용하여 2차원 즉, 목적지 주소와 발신지 주소의 2필드로 구성되는 랜덤 룰 셋을 생성하고 제안한 기법에 대한 메모리 소요량 및 성능 비교를 하였다.
Packet classification is an important factor to support various services such as QoS guarantee and VPN for users in Internet. Packet classification is a searching process for best matching rule on rule tables by employing multi-field such as source address, protocol, and port number as well as destination address in If header. In this paper, we propose hardware based packet classification algorithm by employing tree bitmap of multi-bit trio. We divided prefixes of searching fields and rule into multi-bit stride, and perform a rule searching with multi-bit of fixed size. The proposed scheme can reduce the access times taking for rule search by employing indexing key in a fixed size of upper bits of rule prefixes. We also employ a marker prefixes in order to remove backtracking during searching a rule. In this paper, we generate two dimensional random rule set of source address and destination address using routing tables provided by IPMA Project, and compare its memory usages and performance.
