| 1 |
1
IP 어드레스의 프리픽스 길이별로 각각 구성된 주 테이블과 보조 테이블에 엔트리가 저장되는 형태로 생성되는 SRAM으로 구성된 해슁 테이블을 이용하여 IP 어드레스를 검색하는 방법에 있어서, (a) 입력된 어드레스의 프리픽스 길이별로 구성된 해슁 하드웨어를 이용하여 상기 어드레스를 상기 어드레스의 프리픽스 길이별로 각각 해슁하는 단계; (b) 상기 주 테이블의 상기 해슁의 결과값이 가리키는 지점에 저장된 프리픽스와 상기 어드레스의 프리픽스를 비교하여, 상기 어드레스의 프리픽스와 일치하는 프리픽스를 가지는 상기 주 테이블의 상기 엔트리를 상기 어드레스의 프리픽스 길이별로 각각 검색하여 일치된 엔트리의 정보를 전송하는 단계; (c) 상기 (b) 단계의 검색 결과, 상기 일치하는 프리픽스를 검색하지 못한 경우, 상기 보조 테이블에서 상기 주 테이블의 포인터가 가리키는 지점부터 시작하여, 상기 어드레스의 프리픽스와 일치하는 프리픽스를 가지는 상기 보조 테이블의 상기 엔트리를 상기 어드레스의 프리픽스 길이별로 각각 검색하여 일치된 엔트리의 정보를 전송하는 단계; 및 (d) 상기 (b) 단계 및 상기 (c) 단계에서 전송받은 상기 정보를 이용하여 상기 어드레스의 프리픽스 길이별로 각각 검색된 상기 엔트리 중 프리픽스의 비트 수가 가장 길게 일치하는 엔트리를 검색하는 단계 를 포함하는 것을 특징으로 하는 SRAM과 해슁을 이용한 IP 어드레스 검색 방법
|
| 2 |
2
제 1 항에 있어서, 상기 해슁 하드웨어, 상기 주 테이블 및 상기 보조 테이블은 상기 어드레스의 프리픽스 길이별로 각각 생성되는 것을 특징으로 하는 SRAM과 해슁을 이용한 IP 어드레스 검색 방법
|
| 3 |
3
제 1 항에 있어서, 상기 주 테이블 및 상기 보조 테이블은 상기 어드레스의 프리픽스 길이별로 하나의 SRAM에 저장되는 것을 특징으로 하는 SRAM과 해슁을 이용한 IP 어드레스 검색 방법
|
| 4 |
4
제 1 항에 있어서, 상기 어드레스 검색은 상기 어드레스의 프리픽스 길이별로 병렬적으로 동시에 수행되는 것을 특징으로 하는 SRAM과 해슁을 이용한 IP 어드레스 검색 방법
|
| 5 |
5
제 1 항에 있어서, 상기 해슁 하드웨어는 상기 프리픽스의 비트 수를 상기 해슁의 결과로 나오기를 원하는 비트 수만큼씩 묶어서 배타적 논리합(Exclusive OR)을 수행하는 것을 특징으로 하는 SRAM과 해슁을 이용한 IP 어드레스 검색 방법
|
| 6 |
6
제 1 항에 있어서, 상기 단계 (c)에서, 상기 어드레스의 프리픽스와 일치하는 프리픽스를 가지는 상기 보조 테이블의 상기 엔트리 검색은 이진 검색(Binary Search) 방법을 적용하여 검색하는 것을 특징으로 하는 SRAM과 해슁을 이용한 IP 어드레스 검색 방법
|
| 7 |
7
제 1 항에 있어서, 상기 주 테이블의 엔트리는 상기 검색에 사용되는 프리픽스, 다음 홉 어드레스, 출력 포트, 상기 보조 테이블을 가리키는 포인터 및 상기 엔트리에 해당하는 충돌 횟수를 포함하고, 상기 보조 테이블의 엔트리는 상기 검색에 사용되는 프리픽스, 다음 홉 어드레스 및 출력 포트를 포함하는 것을 특징으로 하는 SRAM과 해슁을 이용한 IP 어드레스 검색 방법
|
| 8 |
8
제 1 항에 있어서, 상기 주 테이블의 엔트리는 상기 검색에 사용되는 프리픽스, 포워딩 램(Forwarding RAM)을 가리키는 포인터, 상기 보조 테이블을 가리키는 포인터 및 상기 엔트리에 해당하는 충돌 횟수를 포함하고, 상기 보조 테이블의 엔트리는 상기 검색에 사용되는 프리픽스, 상기 포워딩 램을 가리키는 포인터를 포함하는 것을 특징으로 하는 SRAM과 해슁을 이용한 IP 어드레스 검색 방법
|
| 9 |
9
제 8 항에 있어서, 상기 포워딩 램은 다음 홉 어드레스 및 출력 포트를 포함하는 것을 특징으로 하는 SRAM과 해슁을 이용한 IP 어드레스 검색 방법
|
| 10 |
10
제 1 항에 있어서, 상기 주 테이블 및 상기 보조 테이블은 상기 어드레스의 프리픽스 길이별로 별개의 SRAM에 저장되는 것을 특징으로 하는 SRAM과 해슁을 이용한 IP 어드레스 검색 방법
|
| 11 |
11
제 1 항에 있어서, 상기 일치된 엔트리의 정보는 다음 홉 어드레스 정보 및 출력 포트 정보 또는 포워딩 램을 가리키는 포인터를 포함하는 것을 특징으로 하는 SRAM과 해슁을 이용한 IP 어드레스 검색 방법
|
| 12 |
12
SRAM과 해슁을 이용한 IP 어드레스 검색을 위한 하드웨어 구조에 있어서, 입력된 어드레스의 프리픽스를 해슁하는 해슁 하드웨어; 상기 어드레스의 프리픽스 길이에 따라 해슁 테이블 형태로 엔트리가 저장되는 주 테이블을 구비하며, 상기 주 테이블의 상기 해슁의 결과값이 가리키는 지점에 저장된 프리픽스와 상기 어드레스의 프리픽스를 비교하여, 상기 어드레스의 프리픽스와 일치하는 프리픽스를 가지는 상기 주 테이블의 상기 엔트리를 검색하고 일치된 엔트리의 정보를 전송하는 메인 프로세서; 상기 어드레스의 프리픽스 길이에 따라 해슁 테이블 형태로 엔트리가 저장되는 보조 테이블을 구비하며, 상기 보조 테이블에서 상기 주 테이블의 포인터가 가리키는 지점부터 시작하여, 상기 어드레스의 프리픽스와 일치하는 프리픽스를 가지는 상기 보조 테이블의 상기 엔트리를 검색하고 일치된 엔트리의 정보를 전송하는 보조 프로세서; 및 상기 일치된 엔트리의 정보를 전송받아 상기 어드레스의 프리픽스 길이별로 각각 검색된 상기 엔트리 중 프리픽스의 비트 수가 가장 길게 일치하는 엔트리를 검색하는 Priority 인코더(Encoder) 를 포함하는 것을 특징으로 하는 SRAM과 해슁을 이용한 IP 어드레스 검색을 위한 하드웨어 구조
|
| 13 |
13
제 12 항에 있어서, 상기 해슁 하드웨어, 상기 주 테이블 및 상기 보조 테이블은 상기 어드레스의 프리픽스 길이별로 각각 생성되는 것을 특징으로 하는 SRAM과 해슁을 이용한 IP 어드레스 검색을 위한 하드웨어 구조
|
| 14 |
14
제 12 항에 있어서, 상기 주 테이블 및 상기 보조 테이블은 상기 어드레스의 프리픽스 길이별로 하나의 SRAM에 저장되는 것을 특징으로 하는 SRAM과 해슁을 이용한 IP 어드레스 검색을 위한 하드웨어 구조
|
| 15 |
15
제 12 항에 있어서, 상기 어드레스 검색은 상기 어드레스의 프리픽스 길이별로 병렬적으로 동시에 수행되는 것을 특징으로 하는 SRAM과 해슁을 이용한 IP 어드레스 검색을 위한 하드웨어 구조
|
| 16 |
16
제 12 항에 있어서, 상기 해슁 하드웨어는 상기 프리픽스의 비트 수를 상기 해슁의 결과로 나오기를 원하는 비트 수만큼씩 묶어서 배타적 논리합(Exclusive OR)을 수행하는 것을 특징으로 하는 SRAM과 해슁을 이용한 IP 어드레스 검색을 위한 하드웨어 구조
|
| 17 |
17
제 12 항에 있어서, 상기 어드레스의 프리픽스와 일치하는 프리픽스를 가지는 상기 보조 테이블의 상기 엔트리 검색은 이진 검색(Binary Search) 방법을 적용하여 검색하는 것을 특징으로 하는 SRAM과 해슁을 이용한 IP 어드레스 검색을 위한 하드웨어 구조
|
| 18 |
18
제 12 항에 있어서, 상기 주 테이블의 엔트리는 상기 검색에 사용되는 프리픽스, 다음 홉 어드레스, 출력 포트, 상기 보조 테이블을 가리키는 포인터 및 상기 엔트리에 해당하는 충돌 횟수를 포함하고, 상기 보조 테이블의 엔트리는 상기 검색에 사용되는 프리픽스, 다음 홉 어드레스 및 출력 포트를 포함하는 것을 특징으로 하는 SRAM과 해슁을 이용한 IP 어드레스 검색을 위한 하드웨어 구조
|
| 19 |
19
제 12 항에 있어서, 상기 주 테이블의 엔트리는 상기 검색에 사용되는 프리픽스, 포워딩 램(Forwarding RAM)을 가리키는 포인터, 보조 테이블을 가리키는 포인터 및 상기 엔트리에 해당하는 충돌 횟수를 포함하고, 상기 보조 테이블의 엔트리는 상기 검색에 사용되는 프리픽스, 상기 포워딩 램을 가리키는 포인터를 포함하는 것을 특징으로 하는 SRAM과 해슁을 이용한 IP 어드레스 검색을 위한 하드웨어 구조
|
| 20 |
20
제 19 항에 있어서, 상기 포워딩 램은 다음 홉 어드레스 및 출력 포트를 포함하는 것을 특징으로 하는 SRAM과 해슁을 이용한 IP 어드레스 검색을 위한 하드웨어 구조
|
| 21 |
21
제 12 항에 있어서, 상기 주 테이블 및 상기 보조 테이블은 상기 어드레스의 프리픽스 길이별로 별개의 SRAM에 저장되는 것을 특징으로 하는 SRAM과 해슁을 이용한 IP 어드레스 검색을 위한 하드웨어 구조
|
| 22 |
22
제 12 항에 있어서, 상기 일치된 엔트리의 정보는 다음 홉 어드레스 정보 및 출력 포트 정보 또는 포워딩 램을 가리키는 포인터를 포함하는 것을 특징으로 하는 SRAM과 해슁을 이용한 IP 어드레스 검색을 위한 하드웨어 구조
|
| 23 |
22
제 12 항에 있어서, 상기 일치된 엔트리의 정보는 다음 홉 어드레스 정보 및 출력 포트 정보 또는 포워딩 램을 가리키는 포인터를 포함하는 것을 특징으로 하는 SRAM과 해슁을 이용한 IP 어드레스 검색을 위한 하드웨어 구조
|
