일반기술

우선순위 트라이를 이용한 ＩＰ 주소 검색 방법 및 이를제공하는 패킷 중계 장치

본 발명은 패킷 포워딩을 위한 IP 주소 검색 방법에 관한 것으로, 본 발명에 따른 IP 주소 검색 방법은, 수신된 패킷의 목적지 IP 주소를 추출하는 단계와, 네트워크 주소에 따른 출력 포트가 지정된 라우팅 테이블로부터 추출된 주소와 가장 길게 일치하는 네트워크 주소를 검색하는 단계와, 검색된 네트워크 주소에 대응하는 출력 포트를 수신된 패킷을 전송할 출력 포트로 지정하는 단계를 포함하며, 상기 검색하는 단계는 라우팅 테이블에 포함된 네트워크 주소들에 기초하여 생성된 우선순위 트라이(priority-trie) 구조를 이용하여 이루어지는 것을 특징으로 한다. 여기서, 우선순위 트라이 구조는 길이가 긴 프리픽스 일수록 먼저 비교되도록 일반 트라이 구조의 빈 내부 노드를 이용하여 길이가 긴 프리픽스를 높은 레벨에 할당함으로써 구축되는 것이 바람직하다. 이에 따라, 검색 시간이 적고 소요되는 메모리의 크기도 줄일 수 있는 효과적인 IP 주소 검색 방법을 제공할 수 있다.