고성능 라우터, 스위치 및 네트워크 보안 장비에서 패킷 포워딩 기능을 고속으로 수행하기 위해서는 효과적인 패킷 분류 기술이 필수적인데, 최근에는 TCAM과 검색엔진 등, 고속의 컨텐트 기반 검색 하드웨어를 이용하는 방법들이 사용되고 있다. 패킷 분류 시에는 트래픽 차단, 트래픽 모니터링 등의 목적을 위해서 많은 규칙들이 사용될 수 있고, 삽입과 삭제가 시스템 운용 중에 발생할 수 있다. 특히, 고속의 네트워크 환경에서 패킷 포워딩의 성능을 저하시키지 않기 위해서는 동적으로 변화하는 규칙들을 효과적으로 갱신하는 방법이 필요하다. 본 논문에서는 TCAM을 이용한 패킷 분류시 효과적인 갱신이나 재배치를 위해서 순서화된 부분 정렬 알고리즘을 제안하고, 실험을 통하여 TCAM의 이용률이 70$\%$까지 높은 상황에서도 갱신으로 인한 재배치가 거의 일어나지 않도록 하여 재배치로 인한 패킷 처리의 지연을 줄일 수 있다는 결과를 보인다.
Generally, it is essential that high-speed routers, switches, and network security appliances should have an efficient packet classification scheme in order to achieve the high-speed packet forwarding capability. For the multi-gigabit packet-processing network equipment the high-speed content search hardware such as TCAM and search engine is recently used to support the content-based packet inspection. During the packet classification process, hundreds and thousands of rules are applied to provide the network security policies regarding traffic screening, traffic monitoring, and traffic shaping. In addition, these rules could be dynamically changed during operations of systems if anomaly traffic patterns would vary. Particularly, in the high-speed network, an efficient algorithm that updates and reorganizes the packet classification rules is critical so as not to degrade the performance of the network device. In this paper, we have proposed an efficient update algorithm using a partial-ordering that can relocate the dynamically changing rules at the TCAM. Experimental results should that our algorithm does not need to relocate existing rules feature until 70$\%$ of TCAM utilization.
