초록 ▼

본 발명은 인터넷 라우터에서 IP 주소 검색 방식에 관한 것으로, 주소 검색 시 트리 레벨을 사용하여 이진 검색을 위한 메모리 구조와 데이터 구조에 관한 것이다.인터넷 트래픽의 급속한 성장으로 인하여, 인터넷 라우터에서는 보다 빠른 주소 검색을 지원하면서도 매우 큰 라우팅 데이터에 대하여도 잘 동작하는 인터넷 줏소 검색 구조를 요구하고 있다. 기존에 연구되어온 대부분의 이진 검색 구조들은 프리픽스의 값에 따르는 이진 검색을 수행하는 구조로서 프리픽스 개수의 로그 함수에 비례하는 검색 소도를 보인다. 한편 프리픽스 길이에 따르는 이진

본 발명은 인터넷 라우터에서 IP 주소 검색 방식에 관한 것으로, 주소 검색 시 트리 레벨을 사용하여 이진 검색을 위한 메모리 구조와 데이터 구조에 관한 것이다.인터넷 트래픽의 급속한 성장으로 인하여, 인터넷 라우터에서는 보다 빠른 주소 검색을 지원하면서도 매우 큰 라우팅 데이터에 대하여도 잘 동작하는 인터넷 줏소 검색 구조를 요구하고 있다. 기존에 연구되어온 대부분의 이진 검색 구조들은 프리픽스의 값에 따르는 이진 검색을 수행하는 구조로서 프리픽스 개수의 로그 함수에 비례하는 검색 소도를 보인다. 한편 프리픽스 길이에 따르는 이진 검색 구조가 연구되어 검색 성능에 있어서는 매우 우수한 성질을 보이나, 순수한 의미의 이진 검색이 불가능하여, 이진 검색시 접근되는 노드에 특수 목적의 마커를 저장하고, 또한 가장 잘 일치하는 프리픽스를 미리 계산하여 저장하는 방식을 통하여 해결하였다. 이러한 복잡한 선계산은 라우팅 테이블의 구성을 매우 어렵게 할 뿐 아니라 프리픽스의 부가적 추가를 불가능하게 만드는 단점이 있다. 본 발명에서는 이러한 복잡한 선계산 없이 리프-푸슁만을 통하여 프리픽스 길이에 대하여 이진 검색을 수행하는 매우 효율적인 구조를 발명하였다.

대표청구항

IP 주소 검색을 위한 이진 검색 방법에 있어서,리프-푸슁을 사용하여 프리픽스간의 상관 관계를 제거하는 단계.

IP 주소 검색을 위한 이진 검색 방법에 있어서,리프-푸슁을 사용하여 프리픽스간의 상관 관계를 제거하는 단계.