일반기술

비트-벡터 테이블을 이용한 ＩＰ 주소 검색방법

본 발명은 라우터의 IP 주소검색을 위해 사용되는 포워딩(forwarding) 테이블을 Gbps(Giga bit per second)급 초고속 라우터에서 적용할 수 있도록 고속으로 검색할 수 있도록 트라이(trie) 구조를 변경하여 트라이의 단계를 압축하고, 압축된 정보는 별도의 필드 값으로 표현하여 트라이 검색경로를 짧게 하는 IP 주소검색방법에 관한 것이다.본 발명에 의한 비트-벡터 테이블을 이용한 IP주소검색방법은 (a)IP 주소 검색시 사용되는 라우팅 테이블을 프리픽스트라이로 표현되는 비트-벡터 테이블로 구성하는 단계; (b)상기 비트-벡터 테이블에서 검색할 IP주소를 m비트 단위로 나누는 단계; (c)상기 m비트로 나누어진 값을 인덱스로 비트-벡터 테이블에서 자식노드의 개수와 프리픽스 비트의 개수를 구하는 단계; 및 (d)상기 프리픽스 비트 개수를 누적한 누적치를 라우팅 인덱스로 사용하여 IP주소를 검색하는 단계를 포함함을 특징으로 한다.본 발명에 의하면, 소프트웨어만으로 빠른 IP 주소 검색이 가능하다. 5기가비트급 고속 라우터는 평균 512바이트 크기의 패킷을 800x10-9 초 이내에 처리할 수 있는 속도를 지원하여야 하는데, 본 발명에서는 실제 라우팅 테이블을 사용하여 실험한 평균 패킷 처리속도가 320x10-9 ~530x10-9 초가 소요되어 5 Gbps급 이상의 고속 라우터를 구현할 수 있다.본 발명에 의하면, 소프트웨어만으로 빠른 IP 주소 검색이 가능하다. 5기가비트급 고속 라우터는 평균 512바이트 크기의 패킷을 800x10-9 초 이내에 처리할 수 있는 속도를 지원하여야 하는데, 본 발명에서는 실제 라우팅 테이블을 사용하여 실험한 평균 패킷 처리속도가 320x10-9 ~530x10-9 초가 소요되어 5 Gbps급 이상의 고속 라우터를 구현할 수 있다.