| 1 |
1
다중 탐색 트리의 노드 구조를 이용한 트리 검색 시스템에 적용되는 트리 검색 방법에 있어서, 목적지 IP 주소의 상위 비트 세그먼트를 이용하여 초기의 비트 어레이를 검색하여 노드 포인터가 지시하는 루트 노드로 이동하여 상기 목적지 IP 주소의 하위 비트 오프셋으로 다중 경로를 검색하여 리프 노드가 도달하기 전에 완전 정합(Exact Matching)이 되는지를 판단하는 제 1 단계; 상기 제 1 단계의 판단 결과, 리프 노드가 도달하기 전에 완전 정합이 될 경우에는 해당 포트를 반환하고 룩업을 종료하는 제 2 단계; 및 상기 제 1 단계의 판단 결과, 리프 노드가 도달하기 전에 완전 정합이 되지 않을 경우에는 검색이 도달한 노드에 따라 키의 영역 포트를 레지스터에 반환 또는 저장하는 제 3 단계 를 포함하는 다중 탐색 트리의 노드 구조를 이용한 트리 검색 방법
|
| 2 |
2
제 1 항에 있어서, 상기 목적지 IP 주소의 상위 비트 세그먼트를 이용하여 초기의 비트 어레이를 검색하여 노드 포인터가 존재하지 않을 경우에 해당 포트를 레지스터에 반환하고 룩업을 종료하는 제 4 단계 를 더 포함하는 다중 탐색 트리의 노드 구조를 이용한 트리 검색 방법
|
| 3 |
3
제 2 항에 있어서, 상기 3 단계는, 검색의 도달이 가지 노드인지 리프 노드인지를 판단하는 제 5 단계; 상기 제 5 단계의 판단 결과, 검색의 도달이 리프 노드일 경우에는 해당하는 키의 영역 포트를 반환하고, 키가 존재하지 않으면 레지스터에 저장된 포트 영역을 반환하는 제 6 단계; 및 상기 제 5 단계의 판단 결과, 검색의 도달이 가지 노드일 경우에는 가지 노드를 통과할때마다 통과하는 키의 영역 포트 값을 레지스터에 저장하고 다음 노드로 이동하여 다중 경로를 검색하는 제 7 단계 를 포함하는 다중 탐색 트리의 노드 구조를 이용한 트리 검색 방법
|
| 4 |
4
제 1 항 내지 제 3 항 중 어느 한 항에 있어서, 상기 다중 탐색 트리의 노드 구조는, 다음 노드의 주소를 알려주기 위한 한 개의 노드 포인터(Po)와, 키의 개수에 대한 정보를 표시하기 위한 넘(num), 루트 노드에서 사용되는 루트 포트(Root Port), 다수 개의 키 및 다수 개의 영역 포트를 포함하는 다중 탐색 트리의 노드 구조를 이용한 트리 검색 방법
|
| 5 |
5
제 4 항에 있어서, 상기 노드 포인터는 하위 노드의 주소를 표시하고, 리프 노드일 경우에는 널(Null)을 나타내며, 상기 루프 포트는 비트 어레이의 엔트리에 해당하는 포트 번호를 표시하는 것을 특징으로 하는 다중 탐색 트리의 노드 구조를 이용한 트리 검색 방법
|
| 6 |
6
제 4 항에 있어서, 상기 키는, 검색을 요청한 IP 하위 오프셋과 노드내의 키 값과, 상기 키 값과 동일한 값의 완전 정합(Exact Matching)인 경우에 사용되는 포트와, 상기 키 값과 가장 근접하게 큰 키 값의 최대 유효 정합(Longest Prefix Marching)인 경우에 사용되는 영역포트와, 키의 프리픽스 길이에 따라 설정되는 플래그, 및 해당 엔트리의 IP 주소 범위에서 시작점인지 아니면 종료점인지를 나타내는 플래그를 포함하는 것을 특징으로 하는 다중 탐색 트리의 노드 구조를 이용한 트리 검색 방법
|
| 7 |
7
다중 탐색 트리의 노드 구조를 이용한 트리 업데이트 시스템에 적용되는 트리 업데이트 방법에 있어서, 해당 엔트리의 프리픽스 길이에 따라 초기의 어레이에서 업데이트를 수행하거나, 노드 포인터가 루트 노드를 지시하는지를 판단하는 제 1 단계; 상기 제 1 단계의 판단 결과, 노드 포인터가 루트 노드를 지시하지 않는 경우에 삭제가 아님을 확인한 후에 새로운 루트 노드를 생성하여 그 생성된 루트 노드에 새로운 키 값을 삽입하는 제 2 단계; 상기 제 1 단계의 판단 결과, 노드 포인터가 루트 노드를 지시할 경우에는 해당 엔트리의 루트 노드로 이동하여 해당 키 값이 존재하는지를 판단하는 제 3 단계; 상기 제 3 단계의 판단 결과, 키 값이 존재하지 않으면 삭제가 아님을 확인한 후에 새로운 키의 쌍을 삽입하고 입력된 IP 경로보다 더 큰 범위의 IP 프리픽스의 포트 번호를 검색하여 해당하는 IP 경로 범위 내에서 트리의 업데이트를 수행한 후에 키 쌍을 트리에서 삭제하는 제 4 단계; 및 상기 제 3 단계의 판단 결과, 키 값이 존재하면 업데이트의 수정 및 삭제에 따라 검색한 키 값에서부터 해당하는 키 쌍이 발견될때까지 트리 업데이트를 수행한 후에 키 쌍을 트리에서 삭제하는 제 5 단계 를 포함하는 다중 탐색 트리의 노드 구조를 이용한 트리 업데이트 방법
|
| 8 |
8
제 7 항에 있어서, 상기 5 단계는, 해당 키 값이 존재하여 업데이트가 수정일 경우에는 검색한 키 값에서부터 해당하는 키 쌍이 발견될때까지 트리 업데이트를 수행한 후에 키 쌍을 트리에서 삭제하는 제 6 단계; 및 해당 키 값이 존재하여 업 데이터가 삭제일 경우에는 입력된 IP 경로보다 더 큰 범위의 IP 프리픽스의 포트 번호를 검색하여 해당하는 키 쌍까지 트리 업데이트를 수행한 후에 키 쌍을 트리에서 삭제하는 제 7 단계 를 포함하는 다중 탐색 트리의 노드 구조를 이용한 트리 업데이트 방법
|
| 9 |
9
제 7 항 또는 제 8 항에 있어서, 상기 다중 탐색 트리의 노드 구조는, 다음 노드의 주소를 알려주기 위한 한 개의 노드 포인터(Po)와, 키의 개수에 대한 정보를 표시하기 위한 넘(num), 루트 노드에서 사용되는 루트 포트(Root Port), 다수 개의 키 및 다수 개의 영역 포트를 포함하는 다중 탐색 트리의 노드 구조를 이용한 트리 업데이트 방법
|
| 10 |
10
제 9 항에 있어서, 상기 노드 포인터는 하위 노드의 주소를 표시하고, 리프 노드일 경우에는 널(Null)을 나타내며, 상기 루프 포트는 비트 어레이의 엔트리에 해당하는 포트 번호를 표시하는 것을 특징으로 하는 다중 탐색 트리의 노드 구조를 이용한 트리 업데이트 방법
|
| 11 |
11
제 9 항에 있어서, 상기 키는, 검색을 요청한 IP 하위 오프셋과 노드내의 키 값과, 상기 키 값과 동일한 값의 완전 정합(Exact Matching)인 경우에 사용되는 포트와, 상기 키 값과 가장 근접하게 큰 키 값의 최대 유효 정합(Longest Prefix Marching)인 경우에 사용되는 영역포트와, 키의 프리픽스 길이에 따라 설정되는 플래그, 및 해당 엔트리의 IP 주소 범위에서 시작점인지 아니면 종료점인지를 나타내는 플래그를 포함하는 것을 특징으로 하는 다중 탐색 트리의 노드 구조를 이용한 트리 업데이트 방법
|
| 12 |
12
다중 탐색 트리를 검색하기 위하여, 프로세서를 구비한 다중 탐색 트리 검색 시스템에, 목적지 IP 주소의 상위 비트 세그먼트를 이용하여 초기의 비트 어레이를 검색하여 노드 포인터가 지시하는 루트 노드로 이동하여 상기 목적지 IP 주소의 하위 비트 오프셋으로 다중 경로를 검색하여 리프 노드가 도달하기 전에 완전 정합(Exact Matching)이 되는지를 판단하는 제 1 기능; 상기 제 1 기능에서의 판단 결과, 리프 노드가 도달하기 전에 완전 정합이 될 경우에는 해당 포트를 반환하고 룩업을 종료하는 제 2 기능; 및 상기 제 1 기능에서의 판단 결과, 리프 노드가 도달하기 전에 완전 정합이 되지 않을 경우에는 검색이 도달한 노드에 따라 키의 영역 포트를 레지스터에 반환 또는 저장하는 제 3 기능 을 실현시키기 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체
|
| 13 |
13
다중 탐색 트리를 업데이트하기 위하여, 프로세서를 구비한 다중 탐색 트리 업데이트 시스템에, 해당 엔트리의 프리픽스 길이에 따라 초기의 어레이에서 업데이트를 수행하거나, 노드 포인터가 루트 노드를 지시하는지를 판단하는 제 1 기능; 상기 제 1 기능에서의 판단 결과, 노드 포인터가 루트 노드를 지시하지 않는 경우에 삭제가 아님을 확인한 후에 새로운 루트 노드를 생성하여 그 생성된 루트 노드에 새로운 키 값을 삽입하는 제 2 기능; 상기 제 1 기능에서의 판단 결과, 노드 포인터가 루트 노드를 지시할 경우에는 해당 엔트리의 루트 노드로 이동하여 해당 키 값이 존재하는지를 판단하는 제 3 기능; 상기 제 3 기능에서의 판단 결과, 키 값이 존재하지 않으면 삭제가 아님을 확인한 후에 새로운 키의 쌍을 삽입하고 입력된 IP 경로보다 더 큰 범위의 IP 프리픽스의 포트 번호를 검색하여 해당하는 IP 경로 범위 내에서 트리의 업데이트를 수행한 후에 키 쌍을 트리에서 삭제하는 제 4 기능; 및 상기 제 3 기능에서의 판단 결과, 키 값이 존재하면 업데이트의 수정 및 삭제에 따라 검색한 키 값에서부터 해당하는 키 쌍이 발견될때까지 트리 업데이트를 수행한 후에 키 쌍을 트리에서 삭제하는 제 5 기능 을 실현시키기 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체
|
