1 |
1
패킷 분류 방법에 있어서,(a) 입력 패킷의 하나 이상의 필드에 대해 필드별 검색을 수행하여 상기 하나 이상의 필드 각각의 필드값과 룰 셋에 저장된 대응하는 필드의 필드값이 서로 일치하는 길이(이하, "일치 길이"라 함)를 판단하고, 상기 하나 이상의 필드 각각에 대한 상기 일치 길이의 조합(Combination)으로 이루어진 튜플(Tuple) 리스트를 생성하는 단계(b) 상기 튜플 리스트에서 상기 룰 셋에 존재하는 튜플만을 선별하는 단계(c) 블룸 필터(Bloom Filter)를 이용하여 선별된 튜플 각각에 대해 필터링을 수행하는 단계 및(d) 필터링 결과가 양성(Positive)인 튜플만을 검색 대상으로 하여 최우선 룰(BMR: Best Matching Rule)을 검색하는 단계를 포함하는 블룸 필터를 이용한 패킷 분류 방법
|
2 |
2
제 1 항에 있어서, 상기 (c) 단계는,(c1) 상기 선별된 튜플 각각에 대해 해싱 인덱스(Hashing Index)를 생성하는 단계(c2) 상기 해싱 인덱스가 가리키는 상기 블룸 필터의 엔트리에 접근하여 상기 블룸 필터의 엔트리의 비트 벡터를 확인하는 단계 및(c3) 상기 비트 벡터가 양성인 튜플만을 상기 검색 대상으로 선별하는 단계를 포함하는 것을 특징으로 하는 블룸 필터를 이용한 패킷 분류 방법
|
3 |
3
제 2 항에 있어서,상기 (d) 단계는, 상기 해싱 인덱스가 가리키는 해싱 테이블의 엔트리에 접근하여 상기 해싱 테이블의 엔트리에 저장된 룰을 검색하고, 검색된 룰 중에서 상기 최우선 룰을 결정하는 것을 특징으로 하는 블룸 필터를 이용한 패킷 분류 방법
|
4 |
4
제 2 항에 있어서, 상기 (c1) 단계는, 상기 선별된 튜플이 나타내는 상기 일치 길이만큼의 상위 비트를 상기 하나 이상의 필드 각각에서 추출하여 서로 연결(Concatenation)함으로써 생성된 스트링(String)으로부터 상기 해싱 인덱스를 생성하는 것을 특징으로 하는 블룸 필터를 이용한 패킷 분류 방법
|
5 |
5
제 2 항에 있어서, 상기 (c1) 단계는, 상기 선별된 튜플이 나타내는 상기 일치 길이만큼의 상위 비트를 상기 하나 이상의 필드 각각에서 추출하고 추출된 값 각각에 소정의 비트 패턴을 부가하여 고정길이 값으로 패딩(Padding)한 후 패딩된 값들을 서로 연결하여 생성한 스트링(String)으로부터 상기 해싱 인덱스를 생성하는 것을 특징으로 하는 블룸 필터를 이용한 패킷 분류 방법
|
6 |
6
제 4 항 또는 제 5 항에 있어서, 상기 (c1) 단계는, 상기 스트링을 CRC 생성기(Cyclic Redundancy Check Generator)에 입력하여 고정 길이 스트링을 생성하는 단계 및상기 고정 길이 스트링으로부터 복수의 상기 해싱 인덱스를 생성하는 단계를 포함하는 것을 특징으로 하는 블룸 필터를 이용한 패킷 분류 방법
|
7 |
7
제 1 항에 있어서,상기 하나 이상의 필드는 근원지 프리픽스(Source Prefix) 필드와 목적지 프리픽스(Destination Prefix) 필드인 것을 특징으로 하는 블룸 필터를 이용한 패킷 분류 방법
|
8 |
8
제 1 항에 있어서,상기 (a) 단계에서의 상기 필드별 검색은 Binary Search on Level을 이용한 1차원 검색인 것을 특징으로 하는 블룸 필터를 이용한 패킷 분류 방법
|
9 |
9
제 2 항에 있어서, 상기 (d) 단계는,(d1) 상기 검색 대상에 속한 튜플에 대해 해싱 테이블용 해싱 인덱스를 생성하는 단계 및(d2) 상기 해싱 테이블용 해싱 인덱스가 가리키는 해싱 테이블의 엔트리에 접근하여 상기 해싱 테이블의 엔트리에 속한 룰을 검색하는 단계 및(d3) 검색된 룰 중에서 상기 최우선 룰을 결정하는 단계를 포함하는 것을 특징으로 하는 블룸 필터를 이용한 패킷 분류 방법
|
10 |
10
패킷 분류 장치에 있어서,패킷 분류를 위한 룰을 구비한 해싱 테이블을 저장하는 메모리입력 패킷의 하나 이상의 필드에 대해 필드별 검색을 수행하여 상기 하나 이상의 필드 각각의 필드값과 룰 셋에 저장된 대응하는 필드의 필드값이 서로 일치하는 길이(이하, "일치 길이"라 함)를 판단하고, 상기 하나 이상의 필드 각각에 대한 상기 일치 길이의 조합으로 이루어진 튜플(Tuple) 리스트를 생성하며, 상기 튜플 리스트에서 상기 룰 셋에 존재하는 튜플만을 선별하는 튜플 생성부 및상기 튜플 생성부에 의해 선별된 튜플 각각에 대해 블룸 필터를 이용하여 필터링을 수행하고 필터링 결과가 양성(Positive)인 튜플만을 검색 대상으로 하여 상기 해싱 테이블에 접근하여 최우선 룰(BMR: Best Matching Rule)을 검색하는 패킷 분류 제어부를 포함하는 블룸 필터를 이용한 패킷 분류 장치
|
11 |
11
제 10 항에 있어서, 상기 패킷 분류 제어부는,상기 선별된 튜플 각각에 대해 해싱 인덱스를 생성하는 해싱부상기 해싱 인덱스가 가리키는 엔트리의 비트 벡터를 확인하여 상기 비트 벡터가 양성인 튜플만을 상기 검색 대상으로 선별하는 블룸 필터 및상기 검색 대상에 속한 튜플에 대응하는 상기 해싱 인덱스를 이용하여 상기 해싱 테이블의 엔트리에 접근하여 상기 해싱 테이블의 엔트리에 저장된 룰을 검색하고, 검색된 룰 중에서 상기 최우선 룰을 결정하는 룰 검색부를 포함하는 것을 특징으로 하는 블룸 필터를 이용한 패킷 분류 장치
|
12 |
12
제 11 항에 있어서, 상기 해싱부는,상기 선별된 튜플이 나타내는 상기 일치 길이만큼의 상위 비트를 상기 하나 이상의 필드 각각에서 추출하여 서로 연결(Concatenation)함으로써 생성된 스트링(String)을 입력받아 고정 길이 스트링을 생성하는 CRC 생성기(Cyclic Redundancy Check Generator); 및상기 고정 길이 스트링으로부터 복수의 상기 해싱 인덱스를 생성하는 해싱 인덱스 생성부를 포함하는 것을 특징으로 하는 블룸 필터를 이용한 패킷 분류 장치
|
13 |
13
제 11 항에 있어서, 상기 해싱부는,상기 선별된 튜플이 나타내는 상기 일치 길이만큼의 상위 비트를 상기 하나 이상의 필드 각각에서 추출하고 추출된 값 각각에 소정의 비트 패턴을 부가하여 고정길이 값으로 패딩(Padding)한 후 패딩된 값들을 서로 연결하여 생성한 스트링(String)을 입력받아 고정 길이 스트링을 생성하는 CRC 생성기(Cyclic Redundancy Check Generator); 및상기 고정 길이 스트링으로부터 복수의 상기 해싱 인덱스를 생성하는 해싱 인덱스 생성부를 포함하는 것을 특징으로 하는 블룸 필터를 이용한 패킷 분류 장치
|
14 |
14
제 10 항에 있어서, 상기 패킷 분류 제어부는,상기 선별된 튜플 각각에 대해 블룸 필터용 해싱 인덱스와 해싱 테이블용 해싱 인덱스를 생성하는 해싱부상기 블룸 필터용 해싱 인덱스가 가리키는 엔트리의 비트 벡터를 확인하여 상기 비트 벡터가 양성인 튜플만을 검색 대상으로 선별하는 블룸 필터 및상기 검색 대상에 속한 튜플에 대응하는 상기 해싱 테이블용 해싱 인덱스를 이용하여 상기 해싱 테이블의 엔트리에 접근하여 상기 해싱 테이블의 엔트리에 저장된 룰을 검색하고, 검색된 룰 중에서 상기 최우선 룰을 결정하는 룰 검색부를 포함하는 것을 특징으로 하는 블룸 필터를 이용한 패킷 분류 장치
|
15 |
15
제 14 항에 있어서, 상기 해싱부는,상기 선별된 튜플이 나타내는 상기 일치 길이만큼의 상위 비트를 상기 하나 이상의 필드 각각의 필드값에서 추출하여 서로 연결(Concatenation)함으로써 생성된 스트링(String)을 입력받아 고정 길이 스트링을 생성하는 CRC 생성기(Cyclic Redundancy Check Generator); 및상기 고정 길이 스트링으로부터 복수의 상기 블룸 필터용 해싱 인덱스 및 하나의 상기 해싱 테이블용 해싱 인덱스를 생성하는 해싱 인덱스 생성부를 포함하는 것을 특징으로 하는 블룸 필터를 이용한 패킷 분류 장치
|
16 |
16
제 14 항에 있어서, 상기 해싱부는,상기 선별된 튜플이 나타내는 상기 일치 길이만큼의 상위 비트를 상기 하나 이상의 필드 각각에서 추출하고 추출된 값 각각에 소정의 비트 패턴을 부가하여 고정길이 값으로 패딩(Padding)한 후 패딩된 값들을 서로 연결하여 생성한 스트링(String)을 입력받아 고정 길이 스트링을 생성하는 CRC 생성기(Cyclic Redundancy Check Generator); 및상기 고정 길이 스트링으로부터 복수의 상기 블룸 필터용 해싱 인덱스 및 하나의 상기 해싱 테이블용 해싱 인덱스를 생성하는 해싱 인덱스 생성부를 포함하는 것을 특징으로 하는 블룸 필터를 이용한 패킷 분류 장치
|
17 |
17
제 10 항에 있어서,상기 하나 이상의 필드는 근원지 프리픽스(Source Prefix) 필드와 목적지 프리픽스(Destination Prefix) 필드인 것을 특징으로 하는 블룸 필터를 이용한 패킷 분류 장치
|
18 |
18
제 10 항에 있어서,상기 하나 이상의 필드는 근원지 포트 넘버 필드와 목적지 포트 넘버 필드인 것을 특징으로 하는 블룸 필터를 이용한 패킷 분류 장치
|
19 |
19
제 10 항에 있어서,상기 튜플 생성부에서 수행되는 상기 필드별 검색은 Binary Search on Level을 이용한 1차원 검색인 것을 특징으로 하는 블룸 필터를 이용한 패킷 분류 장치
|