| 1 |
1
데이터 패턴을 기술하는 정규수식을 TCAM (Ternary Content Addressable Memory)에 표현하는 방법에 있어, 상기 정규수식(Regular Expression)에 나타나는 메타문자나 문자 클래스들의 반복 또는 메타문자나 문자 클래스들을 포함한 패턴의 반복을 적정 개수의 TCAM 엔트리 및 TCAM 연관데이터(associate data)로 구성하여 표현하는 것을 특징으로 하는 효율적인 패턴검색을 위한 TCAM에서의 정규수식 표현방법
|
| 2 |
2
제1항에 있어서, 상기 TCAM 엔트리는 패턴의 시작 또는 패턴의 일부 다음에 오는 패턴임을 의미하는 이전 식별자(previous identifier)를 포함하는 것을 특징으로 하는 효율적인 패턴검색을 위한 TCAM에서의 정규수식 표현방법
|
| 3 |
3
제1항에 있어서, 상기 TCAM 연관데이터(associate data)는 패턴의 끝이나 계속 이어지는 패턴임을 의미하는 다음 식별자(next identifier)를 포함하는 것을 특징으로 하는 효율적인 패턴검색을 위한 TCAM에서의 정규수식 표현방법
|
| 4 |
4
제2항 또는 제3항에 있어서, 상기 TCAM 연관데이터(associate data)는 매치된 TCAM 엔트리에 의해 몇 바이트만큼을 이동하여 다음 패턴을 검사할지를 나타내는 이동값(shift) 및 몇 번 반복되어야 매치되는지를 판단할 수 있는 반복 수량 값(quantifier)을 더 포함하는 것을 특징으로 하는 효율적인 패턴검색을 위한 TCAM에서의 정규수식 표현방법
|
| 5 |
5
제4항에 있어서, 상기 TCAM 엔트리 및 TCAM 연관데이터의 구성은 메타문자나 문자 클래스들 또는 특정한 문자들을 포함하지 않음을 나타내는 메타문자나 부정을 의미하는 문자를 포함한 문자 클래스들을 TCAM의 돈케어-비트(don't care bit)를 이용하는 것을 특징으로 하는 효율적인 패턴검색을 위한 TCAM에서의 정규수식 표현방법
|
| 6 |
6
제5항에 있어서, 실제 매치하고자 하는 문자 클래스 대신에 매치하고자 하는 문자의 부정을 이용한 매치되지 않는 문자 클래스를 이용하여 TCAM 엔트리를 구성함으로써 TCAM 엔트리 수를 줄이고 최대 TCAM 엔트리 크기만큼 이동하면서 검색하는 것을 특징으로 하는 효율적인 패턴검색을 위한 TCAM에서의 정규수식 표현방법
|
| 7 |
7
제5항에 있어서, TCAM 엔트리 크기를 넘는 정규수식의 패턴에 대해서는 특정패턴의 연속임을 의미하는 식별자(identifier)와 이동값(shift)을 이용하여 최대 TCAM 엔트리 크기만큼 이동하면서 대상의 내용을 검색하는 것을 특징으로 하는 효율적인 패턴검색을 위한 TCAM에서의 정규수식 표현방법
|
| 8 |
8
제1항 내지 제7항 중 어느 한 항에 있어서, 상기 정규수식은 컴퓨터 바이러스와 웜, 그리고 파일 공유를 위한 P2P (Peer-to-Peer) 트래픽 등을 식별하기 위한 데이터 패턴인 것을 특징으로 하는 효율적인 패턴검색을 위한 TCAM에서의 정규수식 표현방법
|
| 9 |
9
TCAM에서의 정규수식 표현방법을 이용한 패턴 검색방법에 있어, (a) 패턴의 시작을 의미하는 이전 식별자를 엔트리의 제일 앞에 포함하여 TCAM에서 검색하는 단계; (b) 상기 (a) 단계에서 매치되는 TCAM 엔트리가 있다면, 그 엔트리에 해당하는 TCAM 연관데이터를 읽고 다음 식별자를 검사하는 단계; (c) 상기 (b) 단계에서 패턴이 계속 이어진다면, 반복 수량 값과 이동값의 차를 이용하여 남은 수량 값(remained quantity)을 계산하고 이동값만큼 대상의 검색할 위치를 오른쪽으로 조정하고 다음 식별자를 다음 검색할 대상의 이전 식별자로 대치하는 단계; (d) 상기 (b) 단계에서 패턴의 끝이라면, 남은 수량 값 중 최소값이 0보다 작거나 같은지 그리고 최대값이 0보다 크거나 같은지를 조사하여 반복해야할 범위 안에 있는지를 검사하여 최종적으로 매치가 되는지를 검사하는 단계를 포함하여 메타문자나 문자 클래스들을 포함한 패턴이나 그 패턴의 반복을 찾아내는 단계;로 이루어지고 제1항의 정규수식 표현방법을 이용한 패턴 검색방법
|
