디시전 트리를 선택적으로 병합한 영역분할 사분-트라이에 의한 패킷분류 (Packet Classification Using an Area-based Quad-Trie Conditionally Merged with Decision Trees)

서지정보

· 발행기관 : 한국정보과학회
· 수록지 정보 : 정보과학회논문지 : 시스템 및 이론 / 41권 / 1호 / 33 ~ 47페이지
· 저자명 : 임혜숙, 최영주, 심미란

초록

패킷분류는 인터넷 라우터가 수행하는 가장 어려운 기능 중 하나로서 들어오는 모든 패킷에 대하여 선속도로 처리되어야 한다. 영역분할 패킷분류 알고리즘은 패킷분류에 사용되는 5개의 패킷 헤더 필드 정보인 근원지 주소 프리픽스, 목적지 주소 프리픽스, 근원지 포트 넘버, 목적지 포트 넘버, 프로토콜 등의 정보를 동시에 검색할 수 있는 효율적인 알고리즘이다. 영역분할 패킷분류 알고리즘의 대표적인 예로는 영역분할 사분 트라이(area-based quad-trie, AQT), 하이컷(hierarchical intelligent cuttings, HiCuts), 하이퍼컷(HyperCuts) 등이 있다. AQT는 영역분할 패킷분류 알고리즘 중에서 메모리 요구량이 가장 적은 알고리즘이지만, 특정 크로싱 필터 셋(crossing filter set, CFS)에 저장된 룰이 많은 경우 빠른 검색을 보장하지 못한다. HiCuts은 입력과 비교되는 룰의 수를 특정 값 이하로 줄일 수 있기 때문에 빠른 검색을 보장한다. 하지만 디시전 트리(decision trees)를 구성하기 위해 룰 복사가 불가피하여 과도한 메모리가 소요되기 때문에 실용화에 어려움이 있다. 본 논문에서는 AQT에 미리 정해진 수 이상의 룰이 존재하는 크로싱 필터 셋에 대해서 HiCuts을 추가로 구성하는 알고리즘을 제안한다. 그러므로 제안하는 알고리즘에서는 입력과 비교되는 룰의 수가 AQT보다 줄어들 뿐 아니라, 추가로 구성된 HiCuts 트리에 속한 룰들로 룰 복사가 제한되기 때문에 검색 성능과 메모리 요구량 모두에 있어 합리적인 성능을 보인다.

영어초록

As one of the most challenging tasks in designing Internet routers, packet classification is required to achieve wire-speed processing for every incoming packet. Algorithms based on area decomposition are efficient packet classification algorithms since they can examine 5 different fields (source IP prefix, destination IP prefix, source port number, destination port number, and protocol type) at the same time. As well-known area-based algorithms, an area-based quad-trie(AQT), a hierarchical intelligent cutting(HiCuts), and an HyperCuts algorithm have been studied. The AQT algorithm requires the smallest memory amount among the area-based packet classification algorithms, but it does not provide high-speed search performance in case when many rules belong to the crossing filter set of a node. The HiCuts algorithm provides high-speed search since the number of rules compared with each input can be controlled by a limited number. However, the HiCuts is not practical because of huge memory requirement caused by rule replication which cannot be avoided in constructing the HiCuts decision tree. This paper proposed a new algorithm which primarily constructs an area-based quad trie(AQT) and then applies the HiCuts tree for crossing filter sets with more number of rules than a pre-defined number. Hence the proposed algorithm shows reasonable performance in both the search speed and the memory requirement since the number of rule comparison is reduced compared to AQT algorithm as well as the rule replication is limited by a small set of rules belonged to the constructed HiCuts trees.

참고자료

· 없음