맞춤기술찾기

홈으로 가기
맞춤기술찾기
이전대상기술
프린트하기

이전대상기술

파이프라인 이진 트리를 이용한 ＩＰ 어드레스 검색 방법,하드웨어 구조 및 기록매체

  • 기술번호 : KST2014022360
  • 담당센터 : 인천기술혁신센터
  • 전화번호 : 032-420-3580
상담신청 PDF 받기
요약, Int. CL, CPC, 출원번호/일자, 출원인, 등록번호/일자, 공개번호/일자, 공고번호/일자, 국제출원번호/일자, 국제공개번호/일자, 우선권정보, 법적상태, 심사진행상태, 심판사항, 구분, 원출원번호/일자, 관련 출원번호, 기술이전 희망, 심사청구여부/일자, 심사청구항수의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 서지정보 표입니다.
요약 본 발명은 파이프라인 이진 트리를 이용한 IP 어드레스 검색 방법, 하드웨어 구조 및 기록매체에 관한 것이다. 본 발명은 인클로저 프리픽스를 루트 노드로 하여 이진 트리를 구성하되, 본 발명의 이진 트리에서는 인클로저들의 서브 트리들을 메인 트리에서 분리하여 독립된 트리로 존재시켜, 입력된 어드레스의 프리픽스와 메인 트리의 노드 및 서브 트리의 노드에 포함되어 있는 프리픽스를 파이프라인 기법을 이용하여 비교함으로써 입력된 어드레스를 검색하기 위한 방법, 하드웨어 구조 및 기록매체에 관한 것이다. 본 발명에 의하면, 이진 프리픽스 트리 구조가 갖는 최대 장점인 트리 내에 빈 노드가 없다는 점, 그리고 이진 탐색은 파이프라인을 사용하여 구현되어 질 수 있는 점 등을 살려서 메모리를 효율적으로 사용할 수 있게 한다는 장점이 있다. 또한, 최대 한 번의 내용 주소화 메모리 엑세스 또는 한 번의 메모리 엑세스를 통하여 어드레스 검색을 수행할 수 있는 실용적이면서도 우수한 구조를 제공한다. IP 어드레스, 트리, 프리픽스, 노드, 파이프라인, 이진 탐색, 내용 주소화메모리
Int. CL G06F 15/16 (2006.01)
CPC
출원번호/일자 1020040082326 (2004.10.14)
출원인 임혜숙
등록번호/일자 10-0586461-0000 (2006.05.26)
공개번호/일자 10-2005-0036794 (2005.04.20) 문서열기
공고번호/일자 (20060608) 문서열기
국제출원번호/일자
국제공개번호/일자
우선권정보 대한민국  |   1020030071928   |   2003.10.15
법적상태 소멸
심사진행상태 수리
심판사항
구분
원출원번호/일자
관련 출원번호
심사청구여부/일자 Y (2004.10.14)
심사청구항수 39

출원인

번호, 이름, 국적, 주소의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 인명정보 - 출원인 표입니다.
번호 이름 국적 주소
1 임혜숙 대한민국 서울특별시 강남구

발명자

번호, 이름, 국적, 주소의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 인명정보 - 발명자 표입니다.
번호 이름 국적 주소
1 임혜숙 대한민국 서울특별시 서대문구

대리인

번호, 이름, 국적, 주소의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 인명정보 - 대리인 표입니다.
번호 이름 국적 주소
1 권혁성 대한민국 대구광역시 중구 국채보상로***, *층 에이호(동인동*가, 종각빌딩)(특허법인 이룸리온(대구분사무소))
2 이노성 대한민국 경기도 안산시 단원구 산단로 ***, **동 ***호(원곡동, 원곡유통상가)(제이아이피컨설팅)
3 남승희 대한민국 서울특별시 강남구 역삼로 ***, *층(역삼동, 청보빌딩)(아인특허법률사무소)

최종권리자

번호, 이름, 국적, 주소의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 인명정보 - 최종권리자 표입니다.
번호 이름 국적 주소
1 이화여자대학교 산학협력단 서울특별시 서대문구
번호, 서류명, 접수/발송일자, 처리상태, 접수/발송일자의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 행정처리 표입니다.
번호 서류명 접수/발송일자 처리상태 접수/발송번호
1 특허출원서
Patent Application		 2004.10.14 수리 (Accepted) 1-1-2004-0467414-04
2 선행기술조사의뢰서
Request for Prior Art Search		 2006.02.08 수리 (Accepted) 9-1-9999-9999999-89
3 출원인정보변경(경정)신고서
Notification of change of applicant's information		 2006.02.14 수리 (Accepted) 4-1-2006-5018771-24
4 선행기술조사보고서
Report of Prior Art Search		 2006.03.18 수리 (Accepted) 9-1-2006-0017514-17
5 등록결정서
Decision to grant		 2006.05.12 발송처리완료 (Completion of Transmission) 9-5-2006-0273985-17
번호, 청구항의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 청구항 표입니다.
번호 청구항
1 1
인클로저 프리픽스를 루트 노드로 하여 구성되는 한 개 이상의 파이프라인 이진 트리를 이용한 IP 어드레스 검색 방법에 있어서, (a) 입력된 어드레스의 프리픽스와 상기 인클로저 프리픽스를 비교하는 단계; (b) 상기 (a) 단계의 비교 결과, 상기 어드레스의 프리픽스와 매치되는 상기 인클로저 프리픽스가 검색된 경우, 검색된 상기 인클로저 프리픽스 중 상기 어드레스의 프리픽스와 비트 수가 가장 길게 매치되는 상기 인클로저 프리픽스의 포워딩 램 포인터를 임시 저장하는 단계; (c) 상기 어드레스의 프리픽스의 비트 수가 가장 길게 매치되는 상기 인클로저 프리픽스를 루트 노드로 하는 서브 트리의 프리픽스와 상기 어드레스의 프리픽스를 비교하는 단계; (d) 상기 (c) 단계의 비교 결과, 상기 서브 트리에서 새로이 매치되는 상기 프리픽스가 검색된 경우, 검색된 상기 프리픽스의 포워딩 램 포인터를 출력하는 단계; (e) 상기 (c) 단계의 비교 결과, 상기 서브 트리에서 새로이 매치되는 상기 프리픽스가 검색되지 않은 경우, 상기 (b) 단계에서 임시 저장된 상기 포워딩 램 포인터를 출력하는 단계; (f) 상기 (a) 단계의 비교 결과, 상기 어드레스의 프리픽스와 매치되는 상기 인클로저 프리픽스가 검색되지 않은 경우, 메인 트리의 프리픽스와 상기 어드레스의 프리픽스를 비교하는 단계; (g) 상기 (f) 단계의 비교 결과, 상기 메인 트리에서 매치되는 프리픽스가 검색된 경우, 검색된 상기 프리픽스의 포워딩 램 포인터를 출력하는 단계; 및 (h) 상기 (f) 단계의 비교 결과, 상기 메인 트리에서 매치되는 프리픽스가 검색되지 않은 경우, 디폴트 포워딩 램 포인터를 출력하는 단계 를 포함하는 것을 특징으로 하는 파이프라인 이진 트리를 이용한 IP 어드레스 검색 방법
2 2
제 1 항에 있어서, 상기 단계 (a), 상기 단계 (c) 및 상기 단계 (f)에서의 상기 비교는 이진 검색(Binary Search) 방법을 적용하여 비교하는 것을 특징으로 하는 파이프라인 이진 트리를 이용한 IP 어드레스 검색 방법
3 3
제 1 항에 있어서, 상기 메인 트리 및 서브 트리는 디스조인트 프리픽스만으로 구성되는 것을 특징으로 하는 파이프라인 이진 트리를 이용한 IP 어드레스 검색 방법
4 4
제 1 항에 있어서, 한 개 이상의 상기 이진 트리의 각 깊이에 속하는 모든 노드는 각 깊이 별로 하나의 메모리에 저장되는 것을 특징으로 하는 파이프라인 이진 트리를 이용한 IP 어드레스 검색 방법
5 5
제 1 항에 있어서, 상기 이진 트리의 각 깊이에서의 메모리 검색은 파이프라인 기법을 이용하여 수행되는 것을 특징으로 하는 파이프라인 이진 트리를 이용한 IP 어드레스 검색 방법
6 6
제 1 항에 있어서, 한 개 이상의 상기 루트 노드는 내용 주소화 메모리(CAM : Content Addressable Memory)에 저장되는 것을 특징으로 하는 파이프라인 이진 트리를 이용한 IP 어드레스 검색 방법
7 7
제 1 항에 있어서, 상기 루트 노드의 엔트리는 상기 프리픽스의 정보, 포워딩 램 포인터 및 서브 트리로 가는 포인터를 저장하는 것을 특징으로 하는 파이프라인 이진 트리를 이용한 IP 어드레스 검색 방법
8 8
제 1 항에 있어서, 상기 루트 노드를 제외한 노드의 엔트리는 상기 프리픽스의 정보, 포워딩 램 포인터 및 상기 노드의 자식(Child) 노드로 가는 포인터를 저장하는 것을 특징으로 하는 파이프라인 이진 트리를 이용한 IP 어드레스 검색 방법
9 9
첫 레벨 인클로저 프리픽스만을 루트 노드로 하여 구성되는 한 개 이상의 파이프라인 이진 트리를 이용한 IP 어드레스 검색 방법에 있어서, (a) 입력된 어드레스의 프리픽스와 상기 인클로저 프리픽스를 비교하는 단계; (b) 상기 (a) 단계의 비교 결과, 상기 어드레스의 프리픽스와 매치되는 상기 인클로저 프리픽스가 검색된 경우, 상기 인클로저 프리픽스의 포워딩 램 포인터를 임시 저장하는 단계; (c) 상기 인클로저 프리픽스를 루트 노드로 하는 서브 트리의 프리픽스와 상기 어드레스의 프리픽스를 비교하는 단계; (d) 상기 (c) 단계의 비교 결과, 상기 서브 트리에서 새로이 매치되는 상기 프리픽스가 검색되고 검색된 상기 프리픽스가 서브 트리 포인터를 가지면, 서브 트리 포인터가 가리키는 서브 트리의 프리픽스와 상기 어드레스의 프리픽스를 비교하되, 서브 트리 포인터를 가지지 않는 프리픽스가 검색될 때까지 반복하는 단계; (e) 상기 (d) 단계의 비교 결과, 상기 서브 트리에서 새로이 매치되는 상기 프리픽스가 검색되고 검색된 상기 프리픽스가 상기 서브 트리 포인터를 가지지 않거나, 상기 서브 트리에서 새로이 매치되는 상기 프리픽스가 검색되지 않으면, 상기 (d) 단계에서 최종으로 검색된 상기 프리픽스의 포워딩 램 포인터를 출력하는 단계; (f) 상기 (c) 단계의 비교 결과, 상기 서브 트리에서 새로이 매치되는 상기 프리픽스가 검색되지 않은 경우, 상기 (b) 단계에서 임시 저장된 상기 포워딩 램 포인터를 출력하는 단계; (g) 상기 (a) 단계의 비교 결과, 상기 어드레스의 프리픽스와 매치되는 상기 인클로저 프리픽스가 검색되지 않은 경우, 메인 트리의 프리픽스와 상기 어드레스의 프리픽스를 비교하는 단계; (h) 상기 (g) 단계의 비교 결과, 상기 메인 트리에서 매치되는 프리픽스가 검색된 경우, 검색된 상기 프리픽스의 포워딩 램 포인터를 출력하는 단계; 및 (i) 상기 (g) 단계의 비교 결과, 상기 메인 트리에서 매치되는 프리픽스가 검색되지 않은 경우, 디폴트 포워딩 램 포인터를 출력하는 단계 를 포함하는 것을 특징으로 하는 첫 레벨 인클로저 프리픽스만을 루트 노드로 하여 구성되는 한 개 이상의 파이프라인 이진 트리를 이용한 IP 어드레스 검색 방법
10 10
제 9 항에 있어서, 상기 단계 (a), 상기 단계 (c), 상기 단계 (d) 및 상기 단계 (g)에서의 상기 비교는 이진 검색(Binary Search) 방법을 적용하여 비교하는 것을 특징으로 하는 첫 레벨 인클로저 프리픽스만을 루트 노드로 하여 구성되는 한 개 이상의 파이프라인 이진 트리를 이용한 IP 어드레스 검색 방법
11 11
제 9 항에 있어서, 상기 메인 트리 및 서브 트리는 디스조인트 프리픽스만으로 구성되는 것을 특징으로 하는 첫 레벨 인클로저 프리픽스만을 루트 노드로 하여 구성되는 한 개 이상의 파이프라인 이진 트리를 이용한 IP 어드레스 검색 방법
12 12
제 9 항에 있어서, 한 개 이상의 상기 이진 트리의 각 깊이에 속하는 모든 노드는 상기 각 깊이별로 하나의 메모리에 저장되는 것을 특징으로 하는 첫 레벨 인클로저 프리픽스만을 루트 노드로 하여 구성되는 한 개 이상의 파이프라인 이진 트리를 이용한 IP 어드레스 검색 방법
13 13
제 9 항에 있어서, 한 개 이상의 상기 루트 노드는 내용 주소화 메모리(CAM : Content Addressable Memory)에 저장되는 것을 특징으로 하는 첫 레벨 인클로저 프리픽스만을 루트 노드로 하여 구성되는 한 개 이상의 파이프라인 이진 트리를 이용한 IP 어드레스 검색 방법
14 14
인클로저 프리픽스를 루트 노드로 하여 구성되는 한 개 이상의 파이프라인 이진 트리를 이용한 IP 어드레스 검색을 위한 하드웨어 구조에 있어서, 상기 한 개 이상의 이진 트리의 루트 노드를 저장하는 내용 주소화 메모리(CAM : Content Addressable Memory); 상기 루트 노드를 제외한 노드를 저장하는 메모리; 및 상기 인클로저 프리픽스를 루트 노드로 하여 메인 트리 및 서브 트리를 구성하고 입력된 어드레스의 프리픽스와 상기 메인 트리의 노드 및 상기 서브 트리의 노드에 포함되어 있는 프리픽스를 비교하여 상기 입력된 어드레스의 상기 검색을 수행하는 처리부 를 포함하는 것을 특징으로 하는 인클로저 프리픽스를 루트 노드로 하여 구성되는 한 개 이상의 파이프라인 이진 트리를 이용한 IP 어드레스 검색을 위한 하드웨어 구조
15 15
제 14 항에 있어서, 상기 메인 트리 및 서브 트리는 디스조인트 프리픽스만으로 구성되는 것을 특징으로 하는 인클로저 프리픽스를 루트 노드로 하여 구성되는 한 개 이상의 파이프라인 이진 트리를 이용한 IP 어드레스 검색을 위한 하드웨어 구조
16 16
제 14 항에 있어서, 한 개 이상의 상기 이진 트리의 각 깊이에 속하는 모든 노드는 상기 각 깊이 별로 하나의 메모리에 저장되는 것을 특징으로 하는 인클로저 프리픽스를 루트 노드로 하여 구성되는 한 개 이상의 파이프라인 이진 트리를 이용한 IP 어드레스 검색을 위한 하드웨어 구조
17 17
제 14 항에 있어서, 상기 이진 트리의 각 깊이에서의 메모리 검색은 파이프라인 기법을 이용하여 수행되는 것을 특징으로 하는 인클로저 프리픽스를 루트 노드로 하여 구성되는 한 개 이상의 파이프라인 이진 트리를 이용한 IP 어드레스 검색을 위한 하드웨어 구조
18 18
제 14 항에 있어서, 상기 루트 노드의 엔트리는 상기 프리픽스의 정보, 포워딩 램 포인터 및 서브 트리로 가는 포인터를 저장하는 것을 특징으로 하는 인클로저 프리픽스를 루트 노드로 하여 구성되는 한 개 이상의 파이프라인 이진 트리를 이용한 IP 어드레스 검색을 위한 하드웨어 구조
19 19
제 14 항에 있어서, 상기 루트 노드를 제외한 노드의 엔트리는 상기 프리픽스의 정보, 포워딩 램 포인터 및 상기 노드의 자식(Child) 노드로 가는 포인터를 저장하는 것을 특징으로 하는 인클로저 프리픽스를 루트 노드로 하여 구성되는 한 개 이상의 파이프라인 이진 트리를 이용한 IP 어드레스 검색을 위한 하드웨어 구조
20 20
제 14 항에 있어서, 상기 내용 주소화 메모리는 상기 메인 트리의 루트 노드 및 한 개 이상의 상기 서브 트리의 루트 노드 중 첫 레벨 인클로저 프리픽스만을 루트 엔트리로 하고 있는 상기 서브 트리의 루트 노드를 포함하는 것을 특징으로 하는 인클로저 프리픽스를 루트 노드로 하여 구성되는 한 개 이상의 파이프라인 이진 트리를 이용한 IP 어드레스 검색을 위한 하드웨어 구조
21 21
IP 어드레스 검색을 위한 파이프라인 이진 트리를 생성하는 시스템에 있어서, (a) 상기 검색을 위한 프리픽스 리스트에서 인클로저 프리픽스를 검색하는 기능; (b) 검색된 상기 인클로저 프리픽스를 상기 프리픽스 리스트로부터 제거하여 메인 트리 리스트를 생성하고, 검색된 상기 인클로저 프리픽스가 포함된 인클로저 집합을 생성하는 기능; (c) 상기 인클로저 프리픽스 집합에 속한 한 개 이상의 상기 인클로저 프리픽스마다 서브 트리 리스트를 생성하는 기능; (d) 상기 메인 트리 리스트 및 상기 서브 트리 리스트에 포함되어 있는 한 개 이상의 상기 프리픽스를 크기 별로 정렬하는 기능; (e) 상기 메인 트리 리스트 및 상기 서브 트리 리스트에 포함되어 있는 한 개 이상의 상기 프리픽스를 엔트리에 포함하여 메인 트리 및 한 개 이상의 서브 트리를 생성하는 기능; 및 (f) 상기 파이프라인 이진 트리에 엔트리를 추가, 제거 또는 갱신하는 기능 을 실현시키기 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체
22 22
제 21 항에 있어서, 상기 메인 트리 리스트 및 상기 서브 트리 리스트의 생성과 상기 정렬은 재귀적 서브루틴(Recursive Subroutine)을 사용하여 수행되는 것을 특징으로 하는 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체
23 23
제 21 항에 있어서, 상기 메인 트리 및 서브 트리는 디스조인트 프리픽스만으로 구성되는 것을 특징으로 하는 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체
24 24
제 21 항에 있어서, 상기 메인 트리 및 한 개 이상의 상기 서브 트리의 각 깊이에 속하는 모든 노드는 상기 각 깊이 별로 하나의 메모리에 저장되는 것을 특징으로 하는 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체
25 25
제 21 항에 있어서, 상기 메인 트리 및 한 개 이상의 상기 서브 트리의 루트 노드는 내용 주소화 메모리(CAM : Content Addressable Memory)에 저장되는 것을 특징으로 하는 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체
26 26
제 21 항에 있어서, 상기 이진 트리의 각 깊이에서의 메모리 검색은 파이프라인 기법을 이용하여 수행되는 것을 특징으로 하는 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체
27 27
제 21 항에 있어서, 상기 루트 노드의 엔트리는 상기 프리픽스의 정보, 포워딩 램 포인터 및 서브 트리로 가는 포인터를 저장하는 것을 특징으로 하는 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체
28 28
제 21 항에 있어서, 상기 루트 노드를 제외한 노드의 엔트리는 상기 프리픽스의 정보, 포워딩 램 포인터 및 상기 노드의 자식(Child) 노드로 가는 포인터를 저장하는 것을 특징으로 하는 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체
29 29
제 21 항에 있어서, 상기 메인 트리의 루트 노드 및 한 개 이상의 상기 서브 트리의 루트 노드 중 첫 단계에서 생성된 인클로저 프리픽스를 루트 엔트리에 포함하고 있는 상기 서브 트리의 루트 노드는 내용 주소화 메모리(CAM : Content Addressable Memory)에 저장되는 것을 특징으로 하는 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체
30 30
제 21 항에 있어서, 상기 파이프라인 이진 트리에 엔트리 추가시, 추가하려는 프리픽스를 인클로저로 하는 프리픽스가 발견되고 발견된 상기 프리픽스가 인클로저 프리픽스가 아닌 경우, 발견된 상기 프리픽스만을 추가하려는 상기 프리픽스의 서브 트리로 만들고 발견된 상기 프리픽스 엔트리를 제거하는 것을 특징으로 하는 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체
31 31
제 21 항에 있어서, 상기 파이프라인 이진 트리에 엔트리 추가시, 추가하려는 프리픽스를 인클로저로 하는 인클로저 프리픽스가 발견된 경우 인클로저의 집합에 추가하려는 상기 프리픽스 및 상기 프리픽스의 포워딩 램 포인터를 추가하는 것을 특징으로 하는 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체
32 32
제 21 항에 있어서, 상기 파이프라인 이진 트리에 엔트리 추가시, 추가하려는 프리픽스가 다른 모든 프리픽스에 디스조인트한 경우, 추가하려는 상기 프리픽스를 메인 트리의 새로운 리프로서 추가하는 것을 특징으로 하는 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체
33 33
제 21 항에 있어서, 상기 파이프라인 이진 트리의 엔트리 제거는, 제거하고자 하는 프리픽스를 검색한 후 상기 프리픽스의 포워딩 램 포인터가 무효함을 표시하는 것을 특징으로 하는 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체
34 34
IP 어드레스 검색을 위해 생성된 파이프라인 이진 트리에 엔트리를 추가하는 방법에 있어서, (a) 추가하려는 프리픽스와 매치되는 프리픽스가 있는지 여부를 판단하는 단계; (b) 상기 (a) 단계의 판단 결과, 매치되는 프리픽스가 발견된 경우, 추가하려는 상기 프리픽스가 다른 인클로저 프리픽스의 인클로저인지 여부를 판단하는 단계; (c) 상기 (b) 단계의 판단 결과, 추가하려는 상기 프리픽스가 다른 인클로저 프리픽스의 인클로저인 경우, 인클로저의 집합에 추가하려는 상기 프리픽스 및 포워딩 램 포인터를 추가하는 단계; (d) 상기 (b) 단계의 판단 결과, 추가하려는 상기 프리픽스가 다른 인클로저 프리픽스의 인클로저가 아닌 경우, 추가하려는 상기 프리픽스가 다른 프리픽스의 인클로저인지 여부를 판단하는 단계; (e) 상기 (d) 단계의 판단 결과, 추가하려는 상기 프리픽스가 다른 프리픽스의 인클로저인 경우, 발견된 상기 프리픽스만을 추가하려는 상기 프리픽스의 서브 트리로 만들고, 발견된 상기 프리픽스 엔트리를 제거하고, 추가하려는 상기 프리픽스를 상기 인클로저 집합에 추가하는 단계; (f) 상기 (d) 단계의 판단 결과, 추가하려는 상기 프리픽스가 다른 프리픽스의 인클로저가 아닌 경우, 발견된 상기 프리픽스를 상기 인클로저 집합에 추가하고 발견된 상기 프리픽스가 포함되어 있는 트리에서 제거하며, 추가하려는 상기 프리픽스를 발견된 상기 프리픽스의 서브 트리로 만드는 단계; 및 (g) 상기 (a) 단계의 판단 결과, 매치되는 프리픽스가 발견되지 않은 경우, 추가하려는 상기 프리픽스를 메인 트리의 새로운 리프 노드로서 추가하는 단계 를 포함하는 것을 특징으로 하는 IP 어드레스 검색을 위해 생성된 파이프라인 이진 트리에 엔트리를 추가하는 방법
35 35
제 34 항에 있어서, 상기 엔트리 제거는 제거하고자 하는 프리픽스를 검색한 후 상기 프리픽스의 포워딩 램 포인터가 무효함을 표시하는 것을 특징으로 하는 IP 어드레스 검색을 위해 생성된 파이프라인 이진 트리에 엔트리를 추가하는 방법
36 36
프리픽스들이 레벨별로 분리되어 메인트리 프리픽스와 서브트리 프리픽스로 구분되어 저장된 메인 테이블과 상기 메인트리 프리픽스에 대한 정보를 담고 있는 레인지 테이블로 구성되는 한 개 이상의 파이프라인 이진 트리를 이용한 IP 어드레스 검색 방법에 있어서, (a) 입력된 어드레스의 프리픽스의 초기 비트를 이용하여 레인지 테이블에서 메인테이블의 검색범위 정보를 찾는 단계; (b) 상기 검색범위 정보에 해당하는 메인 테이블에서 첫 번째 레벨의 인클로저 프리픽스와 디스조인트 프리픽스에 대한 바이너리 검색을 하여 비교하는 단계; (c) 상기 (b) 단계의 비교 결과, 상기 어드레스의 프리픽스와 매치되는 상기 인클로저 프리픽스가 검색된 경우, 검색된 인클로저 프리픽스의 포워딩 램 포인터를 저장하는 단계; (d) 상기 매치된 인클로저 프리픽스를 루트 노드로 하는 서브 트리의 프리픽스를 검색하여 상기 어드레스의 프리픽스와 비교하는 단계; (e) 상기 (d) 단계의 비교 결과, 상기 서브 트리에서 새로이 매치되는 상기 프리픽스가 검색되고 검색된 상기 프리픽스가 인클로저 프리픽스이면, 상기 인클로저 프리픽스의 포워딩 램 포인터를 저장하고, 상기 인클로저 프리픽스의 서브 트리에서 새로이 매치되는 상기 프리픽스를 검색하고 상기 어드레스의 프리픽스와 매치여부 및 매치된 프리픽스가 인클로저인지를 비교하며, 검색된 상기 프리픽스가 인클로저 프리픽스가 아니거나 상기 서브 트리에서 새로이 매치되는 프리픽스가 검색되지 않을 때까지 반복하는 단계; (f) 상기 (d) 단계 또는 (e) 단계의 비교 결과, 상기 서브 트리에서 새로이 매치되는 상기 프리픽스가 검색되고 검색된 상기 프리픽스가 인클로저 프리픽스가 아니면, 최종으로 검색된 상기 프리픽스의 포워딩 포인터를 저장하고 출력하는 단계; (g) 상기 (d) 단계 또는 (e) 단계의 비교 결과, 상기 서브 트리에서 새로이 매치되는 상기 프리픽스가 검색되지 않으면, 최종으로 검색된 상기 프리픽스의 포워딩 포인터를 출력하는 단계; (h) 상기 (b) 단계의 비교 결과, 매치되는 디스조인트 프리픽스가 검색된 경우, 검색된 상기 프리픽스의 포워딩 포인터를 저장하고 출력하는 단계; 및 (i) 상기 (b) 단계의 비교 결과, 매치되는 디스조인트 프리픽스가 검색되지 않은 경우, 디폴트 포워딩 포인터를 저장하고 출력하는 단계 를 포함하는 것을 특징으로 하는 한 개 이상의 파이프라인 이진 트리를 이용한 IP 어드레스 검색 방법
37 37
제 36 항에 있어서, 상기 단계 (b), 상기 단계 (d) 및 상기 단계 (e) 에서의 상기 비교는 이진 검색(Binary Search) 방법을 적용하여 비교하는 것을 특징으로 하는 한 개 이상의 파이프라인 이진 트리를 이용한 IP 어드레스 검색 방법
38 38
제 36 항에 있어서, 한 개 이상의 상기 이진 트리의 각 레벨에 속하는 모든 노드는 하나의 메모리에 저장되는 것을 특징으로 하는 첫 레벨 인클로저 프리픽스만을 루트 노드로 하여 구성되는 한 개 이상의 파이프라인 이진 트리를 이용한 IP 어드레스 검색 방법
39 39
프리픽스들이 레벨별로 분리되어 메인트리 프리픽스와 서브트리 프리픽스로 구분되어 저장된 메인 테이블과 상기 메인트리 프리픽스에 대한 정보를 담고 있는 레인지 테이블로 구성되는 파이프라인 이진 트리에 엔트리를 추가하는 방법에 있어서, (a) 추가하려는 프리픽스와 메인 테이블의 첫 번째 레벨의 모든 프리픽스 및 첫 번째 레벨 인클로저 프리픽스의 서브트리에 대하여 매치되는 프리픽스가 있는지 여부를 판단하는 단계; (b) 상기 (a) 단계의 판단 결과, 매치되는 프리픽스가 발견된 경우, 매치되는 프리픽스가 인클로저 프리픽스 인지 여부를 판단하는 단계; (c) 상기 (b) 단계의 판단 결과, 매치되는 상기 프리픽스가 인클로저 프리픽스인 경우, 레벨을 한단계 증가하여 레벨이 증가된 인클로저 프리픽스의 서브트리를 검색하고 추가하려는 프리픽스와의 매치 여부 및 매치된 프리픽스가 인클로저 프리픽스인지 여부를 판단하되, 매치되는 프리픽스가 발견되지 않거나 매치된 프리픽스가 인클로저 프리픽스가 아닐 때까지 검색을 반복하는 단계; (d) 상기 (a) 단계 또는 (c) 단계의 판단 결과, 매치되는 프리픽스가 없으면, 현재 레벨의 프리픽스에 추가하려는 프리픽스를 추가하여 크기 순서에 따라 나열하고 저장하는 단계; (e) 상기 (b) 단계 또는 (c) 단계의 판단 결과, 추가하려는 상기 프리픽스가 다른 프리픽스의 인클로저가 아닌 경우, 매치된 프리픽스와 추가하려는 프리픽스를 비교하여 짧은 길이의 프리픽스는 현재 레벨의 인클로저로 저장되고, 긴길이의 프리픽스는 레벨을 한단계 증가한 디스조인트 프리픽스로 저장하는 단계 (f) 메인 테이블에 프리픽스가 추가되어 변경됨에 따라, 레인지 테이블을 경신하는 단계 를 포함하는 것을 특징으로 하는 파이프라인 이진 트리에 프리픽스를 추가하는 방법
40 39
프리픽스들이 레벨별로 분리되어 메인트리 프리픽스와 서브트리 프리픽스로 구분되어 저장된 메인 테이블과 상기 메인트리 프리픽스에 대한 정보를 담고 있는 레인지 테이블로 구성되는 파이프라인 이진 트리에 엔트리를 추가하는 방법에 있어서, (a) 추가하려는 프리픽스와 메인 테이블의 첫 번째 레벨의 모든 프리픽스 및 첫 번째 레벨 인클로저 프리픽스의 서브트리에 대하여 매치되는 프리픽스가 있는지 여부를 판단하는 단계; (b) 상기 (a) 단계의 판단 결과, 매치되는 프리픽스가 발견된 경우, 매치되는 프리픽스가 인클로저 프리픽스 인지 여부를 판단하는 단계; (c) 상기 (b) 단계의 판단 결과, 매치되는 상기 프리픽스가 인클로저 프리픽스인 경우, 레벨을 한단계 증가하여 레벨이 증가된 인클로저 프리픽스의 서브트리를 검색하고 추가하려는 프리픽스와의 매치 여부 및 매치된 프리픽스가 인클로저 프리픽스인지 여부를 판단하되, 매치되는 프리픽스가 발견되지 않거나 매치된 프리픽스가 인클로저 프리픽스가 아닐 때까지 검색을 반복하는 단계; (d) 상기 (a) 단계 또는 (c) 단계의 판단 결과, 매치되는 프리픽스가 없으면, 현재 레벨의 프리픽스에 추가하려는 프리픽스를 추가하여 크기 순서에 따라 나열하고 저장하는 단계; (e) 상기 (b) 단계 또는 (c) 단계의 판단 결과, 추가하려는 상기 프리픽스가 다른 프리픽스의 인클로저가 아닌 경우, 매치된 프리픽스와 추가하려는 프리픽스를 비교하여 짧은 길이의 프리픽스는 현재 레벨의 인클로저로 저장되고, 긴길이의 프리픽스는 레벨을 한단계 증가한 디스조인트 프리픽스로 저장하는 단계 (f) 메인 테이블에 프리픽스가 추가되어 변경됨에 따라, 레인지 테이블을 경신하는 단계 를 포함하는 것을 특징으로 하는 파이프라인 이진 트리에 프리픽스를 추가하는 방법
지정국 정보가 없습니다
순번, 패밀리번호, 국가코드, 국가명, 종류의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 패밀리정보 - 패밀리정보 표입니다.
순번 패밀리번호 국가코드 국가명 종류
1 US20050083937 US 미국 FAMILY

DOCDB 패밀리 정보

순번, 패밀리번호, 국가코드, 국가명, 종류의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 패밀리정보 - DOCDB 패밀리 정보 표입니다.
순번 패밀리번호 국가코드 국가명 종류
1 US2005083937 US 미국 DOCDBFAMILY
국가 R&D 정보가 없습니다.