1 |
1
IP 패킷의 라우팅을 위한 세그먼트 트리를 구성하는 장치로서,IP 주소 범위 목적지에 따라 구분된 인터벌을 갖는 다수의 리프 노드를 구성하여 메모리에 저장하는 리프 노드 구성 모듈과,상기 IP 패킷의 목적지 주소 검색 시 상기 메모리에 저장된 상기 각 리프 노드들과 리프가 아닌 노드들의 액세스 빈도를 산출하는 액세스 빈도 산출 모듈과,상기 액세스 빈도 산출 모듈에서 산출된 상기 리프 노드들의 액세스 빈도에 의거하여 리프가 아닌 노드들과 그 인터벌을 정의한 후 이를 토대로 임시 세그먼트 트리를 형성하여 상기 메모리에 저장하는 임시 트리 구성 모듈과,상기 액세스 빈도 산출 모듈에서 산출된 상기 임시 세그먼트 트리 내 각 노드들에 대한 액세스 빈도에 의거하여 상기 임시 세그먼트 트리 내 노드들의 레벨을 변경시켜 상기 라우팅에 적용될 세그먼트 트리를 구성하는 노드 레벨 변경 모듈을 포함하는 IP 패킷의 라우팅을 위한 세그먼트 트리 구성 장치
|
2 |
2
제 1 항에 있어서,상기 임시 트리 구성 모듈은, 상기 리프 노드들간 액세스 빈도를 비교하여 상기 리프 노드들 중 상기 액세스 빈도가 상대적으로 낮은 두개의 리프 노드들의 합집합을 이용하여 상기 리프가 아닌 노드의 인터벌을 정의하고, 상기 두개의 리프 노드를 제외한 나머지 리프 노드들의 액세스 빈도를 비교하여 상기 나머지 리프 노드들 중 액세스 빈도가 상대적으로 가장 낮은 리프 노드와 상기 인터벌이 정의된 리프가 아닌 노드간의 합집합을 이용하여 상기 임시 세그먼트 트리에서 리프가 아닌 노드의 인터벌을 정의하는 방법으로 상기 임시 세그먼트 트리를 구성하는 것을 특징으로 하는 IP 패킷의 라우팅을 위한 세그먼트 트리 구성 장치
|
3 |
3
제 1 항에 있어서,상기 노드 레벨 변경 모듈은, 임의의 노드에 대한 상기 액세스 빈도가 수학식(log(1+2k/n)/k, k=임의의 노드의 현재 레벨, n=리프 노드 수)보다 큰 경우 상기 임의의 노드 레벨을 변경시킴으로서, 상기 라우팅에 적용될 세그먼트 트리를 구성하는 것을 특징으로 하는 IP 패킷의 라우팅을 위한 세그먼트 트리 구성 장치
|
4 |
4
IP 패킷의 라우팅을 위한 세그먼트 트리를 구성하는 방법으로서,(a) IP 주소 범위 목적지에 따라 구분된 인터벌을 갖는 다수의 리프 노드를 구성하는 단계와,(b) 상기 리프 노드들의 액세스 빈도를 토대로 상기 세그먼트 트리에서 리프가 아닌 노드들의 인터벌을 정의하여 임시 세그먼트 트리를 형성하는 단계와,(c) 상기 임시 세그먼트 트리에서 각 노드들의 액세스 빈도를 산출하는 단계와,(d) 상기 산출된 액세스 빈도에 의거하여 상기 노드들의 레벨을 변경시켜 상기 라우팅에 적용될 세그먼트 트리를 구성하는 단계를 포함하는 IP 패킷의 라우팅을 위한 세그먼트 트리 구성 방법
|
5 |
5
제 4 항에 있어서,상기 (b) 단계는, 상기 리프 노드들간 액세스 빈도를 비교하여 상기 리프 노드들 중 액세스 빈도가 상대적으로 낮은 두개의 리프 노드들의 합집합을 이용하여 상기 리프가 아닌 노드의 인터벌을 정의하는 단계와,상기 두개의 리프 노드를 제외한 나머지 리프 노드들의 액세스 빈도를 비교하여 상기 나머지 리프 노드들 중 액세스 빈도가 상대적으로 가장 낮은 리프 노드와 상기 인터벌이 정의된 리프가 아닌 노드간의 합집합을 이용하여 상기 임시 세그먼트 트리에서 리프가 아닌 노드의 인터벌을 정의하는 단계를 반복적으로 수행하여 상기 임시 세그먼트 트리의 최상위 노드까지 형성하는 것을 특징으로 하는 IP 패킷의 라우팅을 위한 세그먼트 트리 구성 방법
|
6 |
6
제 4 항에 있어서,상기 (d) 단계는, 임의의 노드에 대한 상기 액세스 빈도가 수학식(log(1+2k/n)/k, k=임의의 노드의 현재 레벨, n=리프 노드 수)보다 큰 경우 상기 임의의 노드 레벨을 위로 올리는 것을 특징으로 하는 IP 패킷의 라우팅을 위한 세그먼트 트리 구성 방법
|