선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 게다가 멀티 해슁을 적용하면 사용하는 해슁 함수의 수에 따라 테이블의 수가 2배, 3배로 증가하기 때문에 더 큰 문제가 된다. 따라서 본 논문에서는 프리픽스 그룹화를 제안하였다. 그림 1은 라우터의 프리픽스 분포를 나타낸 표로서, 본 논문에서는 대부분의 라우터 데이터가 이와 같은 분포를 보임을 이용하여 여러 프리픽스를 적당한 길이로 묶어서 하나의 테이블에 저장함으로써 테이블 수를 줄 일 수 있게 하였다.
- 본 논문에서는 검색 시간에 있어서는 TCAM 과 같은 성능을 보이면서도, 요구되는 메모리 크기에 있어서나, 메모리의 수에 있어서, 전적으로 TCAM을 사용하는 것보다 매우 우수한 성능을 보이는 구조를 제안한다.
- 본 논문에서는 효율적인 주소 검색 구조를 제안하였다. 멀티플해쉬를 이용하여 충돌 현상을 줄이^, 프리픽스 그룹화를 이용하여 적은 수의 테이블을 요구하는 구조이다.
제안 방법
- 먼저 목적지 프리픽스를 그에 해당하는 그룹의 CRC 함수를 통과시켜서 두 개의 해쉬 인덱스를 얻는다. 그렇게 얻어진 해쉬 인덱스를 통해 각각의 테이블에 접근하고, 두 개의 테이블의 Number of Items 필드를 비교하여 더 적은 수의 로드가" 걸려 있는 테이블에 프리픽스를 저장한다. 만약 두 개 테이블에 모든 엔트리가 저장되어 있다면 그 프리픽스는 오버플로 우 테이블에 저장된다.
- 이러한 단점을 보완하기 위해 CIDR (classless inter-domain routing)이라는 IP 주소 체계를 도입하게 되었다. CIDRe IP 주소의 클래스를 없애고 임의의 필요한 길이만큼의 프리픽스를 네트워크 부분으로 하게 함으로써 IP 주소를 효율적으로 할당 할 수 있게 하였다. 그러나 IP 주소의 클래스가 없어짐에 따라 라우터에서는 단순 exact 매치가 아니라 가능한 모든 프리픽스 길이 중에 가장 길게 매치하는 프리픽스 (longest prefix matching)를 검색하여 포트를 결정짓게 된다.
- [10] 은 프리픽스 길이별 테이블을 갖고 그것을 동시에 검색하고 길이별 테이블 저장 시 충돌이 일어나면 그것을 작은 크기의 TCAM에 저장하는 방식을 제안하였다. TCAM에 저장함으로써 길이별 테이블과 TCAM을 동시에 검색 할 수 있고 그리하여 한 번의 메모리 접근 시간으로 주소 검색을 마칠 수 있게 하였다. 그러나 이 방법은 가능한 프리픽스 길이 종류에 해당하는 개수만큼의 메모리를 가져야 한다.
- [8] 은 해슁과 바이너리 검색을 결합한 구 조로써 프리픽스 길이에 대해 바이너리 검색을 하고 같은 프리픽스 길이를 갖는 엔트리에 대해 해슁을 수행하여 검색을 하는 방법이다. 그러나 프리픽스에 대해서는 일반적인 바이너리 검색이 불가능하므로 그것을 위해 마커와 BMP를 계산하여 테이블 엔트 리에 저장해 놔야 한다. 이것은 메모리 크기를 증가시키고 계산량을 커지게 하는 단점을 갖는다.
- 프리픽스 검색을 위해 길이에 따라 몇 개의 그룹으로 해슁 그룹을 나누었는데 병렬 CRC 함수를 사용함으로써 각 해슁 그룹마다 하나의 CRC 함수가 필요하게 되고 이 그룹들에 대해 동시에 해 슁을 하여 검색하는 병렬 검색을 적용하였다. 그룹은 프리픽스 길이에 따라 8, 16, 20, 24의 4개로 나누었으며 그룹 8, 16, 24는 길이에 맞는 CRC-8, CRC-16, CRC-24 함수를 이용하였고, 그룹 20의 경우는 길이에 맞는 CRC함수가 없으므로 CRC-24를 이용하여 20비트까지만 들어간 결과를 구하였다. 그림 3은 parallel CRC-8을 사용한 경우 해쉬 함수 연산식을 나타낸 것이다.
- 따라서 본 논문에서는 프리픽스 그룹화를 제안하였다. 그림 1은 라우터의 프리픽스 분포를 나타낸 표로서, 본 논문에서는 대부분의 라우터 데이터가 이와 같은 분포를 보임을 이용하여 여러 프리픽스를 적당한 길이로 묶어서 하나의 테이블에 저장함으로써 테이블 수를 줄 일 수 있게 하였다. 다음의 표를 보면 프리픽스가 특정 프리픽스 길이에 대해 많이 분포해 있는 것을 볼 수 있다.
- 그러나 이런 방식으로 해쉬 값을 구하면 로직 구현이 간단하다는 장점이 있지만, CRC 함수에 한 비트씩 들어가기 때문에, 해슁 입력이 모두 들어갈 때까지 여러 클럭 사이클 (clock cycle)0] 필요하게 된다. 때문에 본 논문에서는 모든 비트가 동시에 함수의 인풋으로 들어갈 수 있는 병렬 CRC 함수를 이용하여 거기에 필요한 시간을 단축 할 수 있게 하였다. 병렬 CRC는 정해진 비트 수에 맞게 구현하였다.
- 표 2는 본 논문에서 제안하는 구조와 다른 알고리즘들의 성능을 비교한 표이다 30000여 개의 프리픽스를 저장한 것에 대해 실험하였으며 제안하는 알고리즘은 MaeWestl 데이터를 비교하였다. 메모리 접근 횟수와 메모리 크기를 비교하였는데 본 논문에서 제안한 구조는 메모리 접근 횟수에서 TCAM과 같은 1, 1로 매우 우수한 성능을 보이며 메모리 크기도 다른 알고리즘과 비교했을 때 비슷한 크기를 필요로 한다. 단 본 논문에서 제안하는 구조는 약 414개의 TCAM 엔트리를 필요로 하게 된다
- [10] 에서 CRC-32 해슁 함수 하나를 이용하여 모든 테이블의 인덱스를 얻는 방법을 소개하였다. 목적지 주소를 한 클럭 (clock)마다 상위 비트부터 한 비트씩 CRC 하드웨어에 들어가게 하고 D 클럭 사이클마다 CRC 레지스터로부터 프리픽스 길이 D에 해당하는 해쉬 값을 구하게 하였다. 그러나 이런 방식으로 해쉬 값을 구하면 로직 구현이 간단하다는 장점이 있지만, CRC 함수에 한 비트씩 들어가기 때문에, 해슁 입력이 모두 들어갈 때까지 여러 클럭 사이클 (clock cycle)0] 필요하게 된다.
- 본 논문에서 제안하는 구조는 병렬 복수 해슁 (parallel multiple hashing)과 프리픽스 그룹화 (prefix grouping)를 이용한 검색 방법으로 검색 시간이 빠르고 효율적인 메모리 크기를 갖는 구조이다. 본 논문의 구성은 다음과 같다.
- 이러한 단점을 보완하기 위해 CIDR (classless inter-domain routing)이라는 IP 주소 체계를 도입하게 되었다. CIDRe IP 주소의 클래스를 없애고 임의의 필요한 길이만큼의 프리픽스를 네트워크 부분으로 하게 함으로써 IP 주소를 효율적으로 할당 할 수 있게 하였다.
- 이 방식은 가장 긴 프리픽스를 검색하는데 매우 유용한 방식이지만, 트리를 구성함에 있어 빈 노드가 있게 되어 메모리 효율이 떨어질 뿐 아니라, 메모리 검색 횟수가 트리의 최대 높이인 32까지 되는 단점이 있다. 이런 바이너리 트리의 단점을 개선하기 위해 트리의 높이를 줄일 수 있는 방법이 연구 되었는더〕, 하나의 차일드를 가지면서 비어 있는 노드를 제거한 방법'기과 한 번에 한 비트 (bit) 씩 보는 것이 아니라 비트를 확장하여 저장한 후 한 번에 다수의 비트를 비교하면서 트리 검색을 진행하는 알고리즘, 또는 이 두 가지를 결합한 방식间이 제안되었다. 그러나 기본적으로 트리 구조는 빈 노드를 가지게 되는 단점을 극복할 수는 없다.
- 각 데이터에 대해 3가지 경우를 실험하였다. 테이블 수를 1, 2, 3개로 했을 경우에 대해 실험하였는데, N 개의 프리픽스를 저장하기 위해 N개의 버켓을 사용하였고 각 버켓에 는 3개의 로드를 저장하므로 각 실험의 메모리 효율은 1/3로 같게 하였다.
- 그림 2는 본 논문에서 사용된 CRC 함수의 polynomial이다. 프리픽스 검색을 위해 길이에 따라 몇 개의 그룹으로 해슁 그룹을 나누었는데 병렬 CRC 함수를 사용함으로써 각 해슁 그룹마다 하나의 CRC 함수가 필요하게 되고 이 그룹들에 대해 동시에 해 슁을 하여 검색하는 병렬 검색을 적용하였다. 그룹은 프리픽스 길이에 따라 8, 16, 20, 24의 4개로 나누었으며 그룹 8, 16, 24는 길이에 맞는 CRC-8, CRC-16, CRC-24 함수를 이용하였고, 그룹 20의 경우는 길이에 맞는 CRC함수가 없으므로 CRC-24를 이용하여 20비트까지만 들어간 결과를 구하였다.
- 프리픽스를 최대 길이로 확장하고, 한 프리픽스당 최대 두 개의 엔트리를 차지하게 함으로서 IP 주소 검색에서의 길이 차원을 없앤 방식으로 매우 우수한 구조이다. 프릭픽스를 시작 점과 끝점으로 확장한 후 크기순으로 정렬하여 바이 너리 검색을 수행하게 하였다. 이렇게 함으로써 바이 너리 검색이 가능하여 검색 횟수를 줄 일 수 있지만, 모든 엔트리에 해당하는 best matching prefix (BMP)를 미리 계산하여 저장하여야 하는 단점이 있다.
- 먼저 들어오는 패킷의 목적지 주소를 해쉬 함 수에 통과시킨다. 해쉬 함수를 통과시키면 두 개의 테 이블 인덱스가 나오고 그 인덱스에 따라 두 개의 테 이블에 접근하여 엔트리를 비교한다. 엔트리를 비교하여 매치하는 엔트리가 있으면 그곳에 저장된 포트 넘버가 priority 인코더로 전해진다.
대상 데이터
- 메모리 접근 횟수와 메모리 크기를 비교하였는데 본 논문에서 제안한 구조는 메모리 접근 횟수에서 TCAM과 같은 1, 1로 매우 우수한 성능을 보이며 메모리 크기도 다른 알고리즘과 비교했을 때 비슷한 크기를 필요로 한다. 단 본 논문에서 제안하는 구조는 약 414개의 TCAM 엔트리를 필요로 하게 된다
- 본 논문에서는 실제 라우터의 8개 데이터를 이용해 시뮬레이션을 수행하였다. 각 데이터에 대해 3가지 경우를 실험하였다.
데이터처리
- 표 2는 본 논문에서 제안하는 구조와 다른 알고리즘들의 성능을 비교한 표이다 30000여 개의 프리픽스를 저장한 것에 대해 실험하였으며 제안하는 알고리즘은 MaeWestl 데이터를 비교하였다. 메모리 접근 횟수와 메모리 크기를 비교하였는데 본 논문에서 제안한 구조는 메모리 접근 횟수에서 TCAM과 같은 1, 1로 매우 우수한 성능을 보이며 메모리 크기도 다른 알고리즘과 비교했을 때 비슷한 크기를 필요로 한다.
이론/모형
- [8]에서는 완전 해슁 함수 (perfect hashing func- tion)를 가정하였지만 완전 해슁 함수를 찾는 것은 시간이 매우 많이 걸리기 때문에, 실제적으로 이용하기는 어렵다고 볼 수 있다. 본 논문에서는 해슁 함 수로 완전 해슁 함수에 가까운 성능을 낸다고 알려진 CRC 함수를 이용하였다. [10] 에서 CRC-32 해슁 함수 하나를 이용하여 모든 테이블의 인덱스를 얻는 방법을 소개하였다.
성능/효과
- TCAM으로 구성하기 때문에 이 테이블의 검색은 한 번의 메모리 접근으로 가능하게 된다. TCAMe 특수한 메모리로 가격이 비싸고 저장 용량도 크기에 비해 효율적이지 않지만 본 논문에서 제안한 구조는 오버플로우가 발생한 엔트리만을 저장함으로 효율적이다. 다음 장에서 보이려는 바와 같이 41584개의 프리픽스를 저장하기 위해 약 389개의 TCAM 엔트 리 정도만 있으면 오버플로우 테이블을 구성 할 수 있다.
후속연구
- 멀티플해쉬를 이용하여 충돌 현상을 줄이^, 프리픽스 그룹화를 이용하여 적은 수의 테이블을 요구하는 구조이다. 본 구조는 메모리 접근횟수가 1로 매우 우수한 성능을 보이며 메모리 크기 면에서도 459KB로 좋은 성능을 보인다 본 구조에서는 적은 엔트리의 TCAM이 사용되는데, 고속포워딩을 위해 설계된 스위치 ASIC 에 매크로셀의 형태로 들어갈 수 있는 크기이다 또한 업데이트를 프리픽스 검색과 같은 방식으로 진행할 수 있어 추가적 업데이트 (incremental update)가 가능한 구조이다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.