| 1 |
1
다수의 그룹으로 나뉘며, 각 그룹 내에서 MAC 주소 값 순으로 정렬되어 저장되는 다수의 포워딩 엔트리, 상기 각 그룹 및 포워딩 엔트리에 대응되는 해쉬키를 가지는 다수의 포워딩 데이터베이스로 이루어지는 포워딩 테이블을 저장하는 데이터 저장부;
외부로부터 입력된 MAC 주소를 해쉬키로 변환한 후, 기설정된 개수의 상기 해쉬키의 상위 비트들을 이용하여 하나의 검색 그룹을 선택하고, 상기 상위 비트들을 제외한 상기 해쉬키의 나머지 하위 비트들을 이용하여 상기 검색 그룹내에서 하나의 검색 포워딩 엔트리를 선택하는 해싱부; 및
상기 입력된 MAC 주소가 상기 검색 포워딩 엔트리로부터 추출된 MAC 주소와 동일하면 상기 검색 포워딩 엔트리의 출력 포트 정보를 출력하고, 상이하면 상기 검색 그룹 내에서 검색 영역을 분할해가면서 상기 입력된 MAC 주소를 가지는 포워딩 엔트리를 검색 및 획득한 후 출력 포트 정보를 출력하는 포트 정보 출력부를 포함하는 포워딩 테이블 검색 장치
|
| 2 |
2
제1항에 있어서, 상기 포트 정보 출력부는
상기 입력된 MAC 주소가 상기 추출된 MAC 주소와 동일하면 상기 검색 포워딩 엔트리의 출력 포트 정보를 출력하는 등식 비교기;
상기 입력된 MAC 주소가 상기 추출된 MAC 주소와 상이하면 상기 검색 그룹 내 검색 영역을 분할하여 새로운 검색 포워딩 엔트리를 획득하는 부등식 비교기; 및
상기 새로운 검색 포워딩 엔트리로 이동하는 검색 위치 이동부를 포함하는 것을 특징으로 하는 포워딩 테이블 검색 장치
|
| 3 |
3
제2항에 있어서, 상기 부등식 비교기는
상기 입력된 MAC 주소가 상기 추출된 MAC 주소 보다 크면, 상기 추출된 MAC 주소를 인덱스 초기값(index_init)으로 설정하고, 작으면 상기 추출된 MAC 주소를 인덱스 최종값(index_final)로 설정한 후, "index_init + (index_final - index_init)/2"의 식에 따라 계산되는 인덱스(index_cur)를 가지는 상기 새로운 검색 포워딩 엔트리를 검색하는 것을 특징으로 하는 포워딩 테이블 검색 장치
|
| 4 |
4
제1항에 있어서,
상기 입력된 MAC 주소를 가지는 포워딩 엔트리를 새로이 추가하는 경우에는 상기 새로이 추가한 포워딩 엔트리 보다 큰 인덱스 값을 가지는 포워딩 엔트리의 인덱스 값을 한 단위씩 증가시키고, 상기 다수의 포워딩 엔트리 중 특정된 어느 하나를 삭제하는 경우에는 상기 삭제한 포워딩 엔트리 보다 큰 인덱스 값을 가지는 포워딩 엔트리의 인덱스 값을 한 단위씩 감소시키는 포워딩 엔트리 정렬부를 더 포함하는 것을 특징으로 하는 포워딩 테이블 검색 장치
|
| 5 |
5
제1항에 있어서, 상기 다수의 포워딩 데이터베이스 각각은
포워딩 데이터베이스 아이디; 및
하나의 그룹 및 하나의 포워딩 엔트리에 대응되는 해쉬키로 인덱싱된 해쉬 테이블을 포함하는 것을 특징으로 하는 포워딩 테이블 검색 장치
|
| 6 |
6
제1항에 있어서, 상기 다수의 포워딩 엔트리 각각은
MAC 주소, 정보의 유효 여부를 나타내는 정보, 출력 포트 정보, 가상랜 아이디, 및 다음 포워딩 엔트리의 위치를 알려주는 포인터에 대한 정보를 포함하는 것을 특징으로 하는 포워딩 테이블 검색 장치
|
| 7 |
7
다수의 그룹으로 나뉘며, 각 그룹 내에서 MAC 주소 값 순으로 정렬되어 저장되는 다수의 포워딩 엔트리와, 상기 각 그룹 및 포워딩 엔트리에 대응되는 해쉬키를 가지는 다수의 포워딩 데이터베이스를 구성하는 구성 단계;
외부로부터 MAC 주소가 입력되면, 상기 입력된 MAC 주소를 해쉬키로 변환한 후, 기설정된 개수의 상기 해쉬키의 상위 비트들을 이용하여 하나의 검색 그룹을 선택하고, 상기 상위 비트들을 제외한 상기 해쉬키의 나머지 하위 비트들을 이용하여 상기 검색 그룹내에서 하나의 검색 포워딩 엔트리를 선택하는 선택 단계;
상기 검색 포워딩 엔트리로부터 MAC 주소를 추출하여, 상기 추출된 MAC 주소가 상기 입력된 MAC 주소와 동일하면, 상기 검색 포워딩 엔트리의 출력 포트 정보를 추출하여 출력하는 제1 출력 단계; 및
상기 추출된 MAC 주소가 상기 입력된 MAC 주소와 상이하면, 상기 검색 그룹 내 검색 영역을 분할해가면서 상기 입력된 MAC 주소를 가지는 포워딩 엔트리를 새로이 검색한 후 출력 포트 정보를 출력하는 제2 출력 단계를 포함하는 포워딩 정보 검색 방법
|
| 8 |
8
제7항에 있어서, 상기 제2 출력 단계는
상기 입력된 MAC 주소가 상기 추출된 MAC 주소 보다 크면, 상기 추출된 MAC 주소를 인덱스 초기값(index_init)으로 설정하고, 작으면 상기 추출된 MAC 주소를 인덱스 최종값(index_final)로 설정하는 설정 단계;
"index_init + (index_final - index_init)/2"의 식에 따라 계산되는 인덱스를 가지는 포워딩 엔트리를 새로이 선택하는 재선택 단계; 및
상기 새로이 선택한 포워딩 엔트리의 MAC 주소가 상기 입력된 MAC 주소와 동일하면 상기 새로이 선택한 포워딩 엔트리의 출력 포트 정보를 출력하고, 상이하면 상기 설정 단계로 재진입하는 비교 단계를 포함하는 것을 특징으로 하는 포워딩 정보 검색 방법
|
| 9 |
9
제8항에 있어서, 상기 제2 출력 단계는
상기 새로이 선택한 포워딩 엔트리가 무효하면, 상기 입력된 MAC 주소를 가지는 포워딩 엔트리를 추가하거나 상기 새로이 선택한 포워딩 엔트리를 삭제하는 정렬 단계를 더 포함하는 것을 특징으로 하는 포워딩 정보 검색 방법
|
| 10 |
10
제9항에 있어서, 상기 정렬 단계는
상기 입력된 MAC 주소를 가지는 포워딩 엔트리를 추가할 것인지, 상기 새로이 선택한 포워딩 엔트리를 삭제할 것인지를 선택하는 단계;
상기 입력된 MAC 주소를 가지는 포워딩 엔트리를 추가하는 경우, 인덱스 최종값을 수정 인덱스로 설정하고 상기 수정 인덱스보다 큰 인덱스 값을 가지는 포워딩 엔트리의 인덱스 값을 한 단위씩 증가시킨 후, 최종 인덱스 위치에 상기 입력된 MAC 주소를 가지는 포워딩 엔트리를 추가하는 단계; 및
상기 새로이 선택한 포워딩 엔트리를 삭제하는 경우, 상기 인덱스 최종값을 상기 수정 인덱스로 설정한 후 상기 새로이 선택한 포워딩 엔트리를 삭제하고, 상기 수정 인덱스보다 큰 인덱스 값을 가지는 포워딩 엔트리의 인덱스 값을 한 단위씩 감소시키는 단계를 포함하는 것을 특징으로 하는 포워딩 정보 검색 방법
|
| 11 |
11
제8항에 있어서, 상기 제2 출력 단계는
상기 추출된 MAC 주소가 상기 검색 그룹 내 첫 번째 포워딩 엔트리의 MAC 주소 보다 작으면 한 단위 작은 그룹 아이디 값을 가지는 그룹으로 이동하고, 상기 검색 그룹 내 마지막 포워딩 엔트리의 MAC 주소 보다 크면 한 단위 큰 그룹 아이디 값을 가지는 그룹으로 이동한 후, 상기 제1 출력 단계로 재진입하는 그룹별 이동 단계를 더 포함하는 것을 특징으로 하는 포워딩 정보 검색 방법
|
