| 1 |
1
TCAM(Ternary Contents Address Memory) 테이블 관리 방법에 있어서,룩업 테이블을 구성하기 위하여 TCAM의 메모리 영역을 우선순위에 따라 일정한 영역의 블록들로 구분하는 구분 단계;상기 룩업 테이블로 입력되는 모든 라우팅 엔트리 각각에 프리픽스의 길이에 따라 우선순위를 할당하는 우선순위 할당 단계;상기 우선순위를 할당한 라우팅 엔트리를 해당되는 우선순위의 룩업 테이블 블록에 저장하는 단계; 및상기 룩업 테이블의 변경 발생에 따라, 롱기스트 프리픽스 매치(Longest Prefix Match)를 위한 정렬 상태가 유지되도록 상기 룩업 테이블을 변경하는 룩업 테이블 변경 단계를 포함하는 TCAM 테이블 관리 방법
|
| 2 |
2
제 1 항에 있어서,상기 구분 단계는,라우팅 시스템 초기화 시에 모든 우선순위 블록들을 우선순위가 할당되지 않은 상태로 설정하는 과정; 및우선순위의 라우팅 엔트리의 입력이 필요한 경우에 비어있는 임의의 블록을 해당하는 우선순위 블록으로 할당하여 해당하는 우선순위 번호를 설정하는 과정을 포함하는 TCAM 테이블 관리 방법
|
| 3 |
3
제 1 항에 있어서,상기 우선순위 할당 단계는,상기 룩업 테이블과 관련된 각 라우팅 엔트리의 프리픽스 길이에 따라 체인-조상-트리를 구성하는 체인-조상-트리 구성 과정; 및상기 구성한 체인-조상-트리의 레벨 높이에 따라 우선순위를 할당하는 우선순위 할당 과정을 포함하는 TCAM 테이블 관리 방법
|
| 4 |
4
제 3 항에 있어서,상기 체인-조상-트리 구성 과정은,상기 룩업 테이블과 관련된 각 라우팅 엔트리의 프리픽스 정보를 이용하여 라우팅 엔트리 상호 간의 프리픽스-조상-관계를 조사하는 프리픽스-조상-관계 조사 과정; 및상기 프리픽스-조상-관계 조사 결과에 따라 프리픽스-조상-관계가 성립되는 두 라우팅 엔트리에 대하여, 프리픽스 엔트리가 짧은 라우팅 엔트리를 부모 위치에 삽입하고, 프리픽스 길이가 긴 라우팅 엔트리를 자식 위치에 삽입하는 과정을 포함하는 TCAM 테이블 관리 방법
|
| 5 |
5
제 4 항에 있어서,상기 프리픽스-조상-관계 조사 과정은,상기 두 개의 상이한 라우팅 엔트리에서 각각의 프리픽스 길이를 비교하여 그 중에서 짧은 프리픽스를 비교 프리픽스 길이로 설정하는 과정;상기 비교 프리픽스 길이만큼 상기 두 라우팅 엔트리를 비교하여 일치함에 따라 프리픽스-조상-관계에 있다고 설정하는 과정; 및프리픽스-조상-관계에 있는 상기 두 라우팅 엔트리에서 프리픽스의 길이가 짧은 라우팅 엔트리를 긴 라우팅 엔트리의 조상이라 설정하는 과정을 포함하는 TCAM 테이블 관리 방법
|
| 6 |
6
제 3 항에 있어서,상기 우선순위 할당 과정은,체인-조상-트리의 높이에 따라 동일한 높이에 해당되는 모든 노드의 그룹을 동일한 레벨로 설정하는 과정;체인-조상-트리의 루트 노드를 높이 0, 레벨 0으로 설정하는 과정; 및체인-조상-트리의 높이가 한 단계 증가할 때마다 레벨도 1씩 증가시키는 과정을 포함하는 TCAM 테이블 관리 방법
|
| 7 |
7
제 1 항 내지 제 6 항 중 어느 한 항에 있어서,상기 룩업 테이블 변경 단계는,새로운 라우팅 엔트리가 입력됨에 따라, 새로운 체인-조상-트리 노드를 생성하고, 체인-조상-트리의 해당 위치에 새로운 라우팅 엔트리를 삽입하며, 상기 TCAM의 룩업 테이블에 저장하는 제 1 처리 과정; 및기존의 라우팅 엔트리를 삭제하고자 함에 따라, 체인-조상-트리에서 삭제하고자하는 라우팅 엔트리를 검색하여 삭제하고, 상기 TCAM의 룩업 테이블에서 삭제하는 제 2 처리 과정을 포함하는 TCAM 테이블 관리 방법
|
| 8 |
8
제 7 항에 있어서,상기 제 1 처리 과정은,체인-조상-트리의 루트에서부터 한 레벨씩 증가시켜 가면서 새롭게 입력되는 라우팅 엔트리와 프리픽스-조상-관계를 검사하는 검사 과정;상기 검사 결과, 프리픽스-조상-관계가 성립하지 않는 경우 새로운 노드를 생성하여 체인-조상-트리의 현재 비교하고 있는 레벨에 삽입하고, 새롭게 입력되는 라우팅 엔트리에 그 레벨에 해당되는 우선순위를 할당하는 과정;상기 검사 결과, 프리픽스-조상-관계가 성립하는 경우, 새롭게 입력되는 라우팅 엔트리가 조상인지를 확인하는 과정;상기 확인 결과, 새롭게 입력되는 라우팅 엔트리가 조상이면, 현재 비교하고 있는 체인-조상-트리의 노드 및 현재 노드의 모든 후손을 한 레벨씩 증가시켜 현재 위치를 비어 있도록 만들고, 그 빈 위치에 새롭게 입력되는 라우팅 엔트리의 노드를 삽입하는 과정;상기 확인 결과, 새롭게 입력되는 라우팅 엔트리가 조상이 아니면, 새롭게 입력되는 라우팅 엔트리를 현재 비교하고 있는 체인-조상-트리의 노드의 아들 노드로 설정한 후에 상기 검사 과정으로 진행하여 비교해 나가는 과정; 및새롭게 입력되는 라우팅 엔트리가 체인-조상-트리에서의 위치가 결정되고 우선순위를 부여받음에 따라, 해당되는 우선순위 TCAM 블록의 빈 공간의 엔트리에 저장하는 과정을 포함하는 TCAM 테이블 관리 방법
|
| 9 |
9
제 8 항에 있어서,새롭게 입력되는 라우팅 엔트리에 의해 체인-조상-트리에서 다른 노드들의 이동이 발생함에 따라, 그 이동 노드에 해당되는 라우팅 엔트리를 상기 TCAM의 라우팅 테이블 우선순위 블록에서 삭제하였다가 다시 변경 위치의 레벨에 해당되는 우선순위 블록에 저장하는 과정을 더 포함하는 TCAM 테이블 관리 방법
|
| 10 |
10
제 7 항에 있어서,상기 제 2 처리 과정은,체인-조상-트리의 루트 노드에서부터 한 레벨씩 차례대로 증가시켜 가면서 삭제하고자하는 라우팅 엔트리와 일치할 때까지 비교하는 과정;상기 비교 결과로 일치하는 라우팅 엔트리가 존재함에 따라, 체인-조상-트리에서 삭제하는 과정; 및상기 삭제한 노드의 자식 노드가 있음에 따라, 해당하는 자식 노드를 상기 삭제한 노드의 부모 노드의 자식으로 설정하는 과정을 포함하는 TCAM 테이블 관리 방법
|
| 11 |
11
제 10 항에 있어서,삭제되는 라우팅 엔트리에 의해 체인-조상-트리에서 다른 노드들의 이동이 발생함에 따라, 그 이동 노드에 해당되는 라우팅 엔트리를 상기 TCAM의 라우팅 테이블 우선순위 블록에서 삭제하였다가 다시 변경 위치의 레벨에 해당되는 우선순위 블록에 저장하는 과정을 더 포함하는 TCAM 테이블 관리 방법
|
| 12 |
12
프로세서를 구비한 라우팅 시스템에,룩업 테이블을 구성하기 위하여 TCAM의 메모리 영역을 우선순위에 따라 일정한 영역의 블록들로 구분하는 기능;상기 룩업 테이블로 입력되는 모든 라우팅 엔트리 각각에 프리픽스의 길이에 따라 우선순위를 할당하는 기능;상기 우선순위를 할당한 라우팅 엔트리를 해당되는 우선순위의 룩업 테이블 블록에 저장하는 기능; 및상기 룩업 테이블의 변경 발생에 따라, 롱기스트 프리픽스 매치(Longest Prefix Match)를 위한 정렬 상태가 유지되도록 상기 룩업 테이블을 변경하는 기능을 실현시키기 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체
|
