The fast growth of digital networks has motivated various internet services such as e-eommerce, Voice over IP(VoIP), streaming audio/video, and security services. To provide those services, switching devices conventionally working in link layer are requested to have more intelligence and ability for observing content in application layer. Decision on the level of service and switching depends on the result of the content-based packet classification. To classify a packet with content inspection, it is essential to process multiple string searches in real time, which has been an obstacle with a conventional network processor architecture.
In this dissertation, we discuss a packet classification engine architecture which supports gigabit-rate content-based classification and consumes less memory. First, an area-efficient architecture for concurrent pattern matching and classification is proposed for application to content-based packet switching. The proposed architecture mainly consists of two modules; 1) a finite state machine(FSM) where the cycle-by-cycle state transition occurs and 2) a prefix table for matching the prefix part of the rules to reduce the memory space for storing the information on state transistion. Additional memory compaction schemes such as word sharing and nonbranching state memory chaining are exploited to yield an overall scheme for storing the state transition data. With this architecture, about 3,000 rules can be compiled into a 145 kbyte SRAM, which can be easily embedded in a network processor.
Second, a method for content-based classification using results from a string search and a layer 3-4 lookup is proposed. Content-based classification has to make its classification decision based on all of the matching results of each field and, therefore, a fast and cost-effective method for colligating results from layer 3-4 lookup and string search is also necessary. Encoding of the intermediate result value from layer 3-4 lookup enables wire-speed processing while reducing the memory by over 70% compared to the dependent search scheme. To reduce the encoding time at rule compile step, rule partitioning by range types is also suggested. The rule partitioning scheme helps to encode ranges within a minute for an intrusion-detection rule set having about one thousand rules.
디지털 네트웍의 빠른 성장은 전자상거래, Voice over IP, 스트리밍 음성/영상, 그리고 보안 같은 여러 가지 서비스들의 발전을 가져왔다. 이러한 서비스들을 제공하기 위해서, 예전의 링크 레이어에서 동작하던 스위치들은 어플리케이션 레이어의 컨텐트까지 볼 수 있도록 더 많은 지능과 능력을 가지도록 발전하고 있으며, 서비스에 대한 레벨과 스위칭 목표를 정하기 위해서 컨텐트 기반의 패킷 분류가 필요하게 되었다. 컨텐트 기반의 패킷 분류를 위해서는 여러 번의 문자열 검색을 빠른 시간 내에 하는 것이 중요하지만, 현재 네트웍 프로세서 아키텍쳐에서는 이러한 동작을 잘 지원해 주지 못하고 있다.
이 논문에서는 적은 메모리를 사용하면서 기가비트 속도의 컨텐트 기반 패킷 분류를 지원하는 분류기의 아키텍쳐를 제시한다. 먼저, 컨텐트 기반 패킷 스위칭을 위한 작은 면적의 스트링 패턴 비교기에 대해 제안한다. 이 제안된 아키텍쳐는 크게 두가지의 모듈로 구성되어있다; 1)매 사이클마다 스테이트의 천이가 일어나는 FSM과 2)각 스트링들의 앞부분만을 모아서 들어오는 데이터와 비교하는 접두어 테이블. 접두어 테이블을 이용하는 경우, 많은 스테이트들로부터 일어나는 천이에 대한 데이터들을 공유할 수 있어서 많은 양의 메모리를 줄일 수 있다. 또한 부가적인 메모리 압축 기법으로워드 공유와 분기하지 않는 스테이트들의 연속 배치를 통하여 효율적인 데이터 저장을 구현하였다. 이 아키텍쳐를 이용하여, 약 3,000개의 룰이 145kbyte의 SPAM에 저장되었으며, 이러한 용량은 네트웍 프로세서 내에 집적이 가능한 크기이다.
두 번째로 제안된 기법은 컨텐트 기반 분류를 위하여 스트링 패턴 비교기와 레이어 3/4 검색의 결과를 합치는 과정에 관한 긱법이다. 컨텐트 기반의 패킷 분류는 각 필드에 해당되는 값들이 모두 일치하는 경우에 그에 해당하는 결과값을 갖게 되므로, 이 결과들을 모두 합칠 수 있는 빠르고, 비용이 적게 드는 방법이 필요하게 된다. 레이어 3/4검색에서 나오는 중간 결과 값의 부호화를 통하여 빠른 결과를 내어주면서도 메모리를 70%까지 줄일 수 있는 방법을 제안한다. 또한, 이러한 중간 결과 값의 부호화는 컴파일 시에 부가적인 시간이 필요하게 되는데, 이러한 시간을 줄이기 위해 룰을 영역의 유형에 따라 분할하는 방법에 대해서 제안한다. 이러한 룰의 분할 기법을 통하여 1,000여개의 룰을 가지는 침입 탐지 시스템에 대하여 1분 내로 부호화할 수 있다.
