1 |
1
커팅 방식을 이용하여 패킷을 분류하는 패킷 분류 방법에 있어서,(1) 판별 트리 노드에 속한 정책 집합에 대해 등간격 커팅이 적용되어 각각의 파티션으로 분할되는 단계;(2) 상기 단계 (1)에서 분할된 각각의 파티션과 매칭되는 포인터 배열에서 중복되는 엔트리가 제거되는 단계;(3) 상기 단계 (1)에서 분할된 파티션에 대해 피벗을 기준으로 커팅하는 피벗 기반 커팅이 적용되어 서브-파티션으로 분할되는 단계;(4) 상기 단계 (2)에서 제거된 상기 포인터 배열의 중복된 엔트리에 상기 단계 (3)에서 상기 피벗 기반 커팅에 사용된 피벗과 상기 피벗에 의해 분할된 서브-파티션과 매칭되는 포인터가 저장되는 단계; 및(5) 상기 단계 (4)에서 상기 피벗과 상기 피벗에 의해 분할된 서브-파티션과 매칭되는 포인터가 저장되는 포인터 배열이 캐시 라인에 저장되는 단계를 포함하는 것을 특징으로 하는, 하이브리드 커팅을 이용한 고속 패킷 분류 방법
|
2 |
2
제1항에 있어서, 상기 단계 (3)은,상기 등간격 커팅이 적용되어 가장 많은 수로 커팅된 파티션을 가지는 차원에 대해서 상기 피벗 기반 커팅이 적용되는 것을 특징으로 하는, 하이브리드 커팅을 이용한 고속 패킷 분류 방법
|
3 |
3
제2항에 있어서, 상기 단계 (3)은,상기 단계 (1)에서 분할된 각각의 파티션에 대해 중복되는 정책 집합의 수를 최소화하는 피벗을 기준으로 상기 피벗 기반 커팅이 적용되는 것을 특징으로 하는, 하이브리드 커팅을 이용한 고속 패킷 분류 방법
|
4 |
4
제1항에 있어서, 상기 단계 (3)은,상기 단계 (1)에서 분할된 각각의 파티션에 대해 피벗 기반 커팅이 적어도 한 번 이상 적용되는 것을 특징으로 하는, 하이브리드 커팅을 이용한 고속 패킷 분류 방법
|
5 |
5
제1항에 있어서, 상기 단계 (2)는,상기 포인터 배열에 중복되지 않은 파티션과 매칭되는 고유 포인터만 저장되는 것을 특징으로 하는, 하이브리드 커팅을 이용한 고속 패킷 분류 방법
|
6 |
6
제5항에 있어서, 상기 포인터 배열은,각각의 엔트리가 인덱스가 저장되는 인덱스 필드와, 포인터 또는 피벗이 저장되는 공유 필드로 구성되는 것을 특징으로 하는, 하이브리드 커팅을 이용한 고속 패킷 분류 방법
|
7 |
7
제6항에 있어서, 상기 포인터 배열은,상기 공유 필드에 상기 피벗 기반 커팅에 사용된 피벗과 상기 피벗에 의해 분할된 서브-파티션과 매칭되는 포인터가 저장되는 것을 특징으로 하는, 하이브리드 커팅을 이용한 고속 패킷 분류 방법
|
8 |
8
제6항에 있어서, 상기 단계 (4)는,상기 포인터 배열에서 상기 고유 포인터가 첫 엔트리부터 연속적으로 배치된 후, 상기 피벗 기반 커팅에 사용된 피벗과 상기 피벗에 의해 분할된 서브-파티션과 매칭되는 포인터가 배치되는 것을 특징으로 하는, 하이브리드 커팅을 이용한 고속 패킷 분류 방법
|
9 |
9
제6항에 있어서, 상기 포인터 배열은,상기 피벗에서 상기 파티션 또는 서브-파티션의 시작값을 뺀 오프셋을 저장하여 32bit 피벗을 28bit의 공유 필드에 저장하는 것을 특징으로 하는, 하이브리드 커팅을 이용한 고속 패킷 분류 방법
|
10 |
10
제1항에 있어서, 상기 단계 (5)는,상기 포인터 배열이 하나의 캐시 라인에 저장되되, 상기 포인터 배열의 크기가 상기 하나의 캐시 라인 사이즈를 초과하는 경우, 하나의 캐시 라인 사이즈마다 새로운 헤더가 사용되는 것을 특징으로 하는, 하이브리드 커팅을 이용한 고속 패킷 분류 방법
|
11 |
11
커팅 방식을 이용하여 패킷을 분류하는 패킷 분류 시스템에 있어서,판별 트리 노드에 속한 정책 집합에 대해 등간격 커팅을 적용하여 각각의 파티션으로 분할하는 등간격 커팅 모듈;상기 등간격 커팅 모듈에 의해 분할된 각각의 파티션과 매칭되는 포인터 배열에서 중복되는 엔트리를 제거하는 중복 엔트리 제거 모듈;상기 등간격 커팅 모듈에 의해 분할된 파티션에 대해 피벗을 기준으로 커팅하는 피벗 기반 커팅을 적용하여 서브-파티션으로 분할하는 피벗 기반 커팅 모듈;상기 중복 엔트리 제거 모듈에 의해 제거된 상기 포인터 배열의 중복된 엔트리에 상기 피벗 기반 커팅 모듈의 상기 피벗 기반 커팅에 사용된 피벗과 상기 피벗에 의해 분할된 서브-파티션과 매칭되는 포인터를 저장하는 포인터 배열 저장 모듈; 및상기 피벗과 상기 피벗에 의해 분할된 서브-파티션과 매칭되는 포인터가 저장되는 포인터 배열을 캐시 라인에 저장하는 캐시 라인 저장 모듈을 포함하는 것을 특징으로 하는, 하이브리드 커팅을 이용한 고속 패킷 분류 시스템
|
12 |
12
제11항에 있어서, 상기 피벗 기반 커팅 모듈은,상기 등간격 커팅이 적용되어 가장 많은 수로 커팅된 파티션을 가지는 차원에 대해서 상기 피벗 기반 커팅이 적용되는 것을 특징으로 하는, 하이브리드 커팅을 이용한 고속 패킷 분류 시스템
|
13 |
13
제12항에 있어서, 상기 단계 피벗 기반 커팅 모듈은,상기 등간격 커팅 모듈에서 분할된 각각의 파티션에 대해 중복되는 정책 집합의 수를 최소화하는 피벗을 기준으로 상기 피벗 기반 커팅이 적용되는 것을 특징으로 하는, 하이브리드 커팅을 이용한 고속 패킷 분류 시스템
|
14 |
14
제11항에 있어서, 상기 피벗 기반 커팅 모듈은,상기 피벗 기반 커팅 모듈에서 분할된 각각의 파티션에 대해 피벗 기반 커팅이 적어도 한 번 이상 적용되는 것을 특징으로 하는, 하이브리드 커팅을 이용한 고속 패킷 분류 시스템
|
15 |
15
제11항에 있어서, 상기 중복 엔트리 제거 모듈은,상기 포인터 배열에 중복되지 않은 파티션과 매칭되는 고유 포인터만 저장하는 것을 특징으로 하는, 하이브리드 커팅을 이용한 고속 패킷 분류 시스템
|
16 |
16
제15항에 있어서, 상기 포인터 배열은,각각의 엔트리가 인덱스가 저장되는 인덱스 필드와, 포인터 또는 피벗이 저장되는 공유 필드로 구성되는 것을 특징으로 하는, 하이브리드 커팅을 이용한 고속 패킷 분류 시스템
|
17 |
17
제16항에 있어서, 상기 포인터 배열은,상기 공유 필드에 상기 피벗 기반 커팅에 사용된 피벗과 상기 피벗에 의해 분할된 서브-파티션과 매칭되는 포인터가 저장되는 것을 특징으로 하는, 하이브리드 커팅을 이용한 고속 패킷 분류 시스템
|
18 |
18
제16항에 있어서, 상기 포인터 배열 저장 모듈은,상기 포인터 배열에서 상기 고유 포인터를 첫 엔트리부터 연속적으로 배치한 후, 상기 피벗 기반 커팅에 사용된 피벗과 상기 피벗에 의해 분할된 서브-파티션과 매칭되는 포인터를 배치하는 것을 특징으로 하는, 하이브리드 커팅을 이용한 고속 패킷 분류 시스템
|
19 |
19
제16항에 있어서, 상기 포인터 배열은,상기 피벗에서 상기 파티션 또는 서브-파티션의 시작값을 뺀 오프셋을 저장하여 32bit 피벗을 28bit의 공유 필드에 저장하는 것을 특징으로 하는, 하이브리드 커팅을 이용한 고속 패킷 분류 시스템
|
20 |
20
제11항에 있어서, 상기 캐시 라인 저장 모듈은,상기 포인터 배열이 하나의 캐시 라인에 저장되되, 상기 포인터 배열의 크기가 상기 하나의 캐시 라인 사이즈를 초과하는 경우, 하나의 캐시 라인 사이즈마다 새로운 헤더가 사용되는 것을 특징으로 하는, 하이브리드 커팅을 이용한 고속 패킷 분류 시스템
|