Today's larger network makes the routing table in the router to become large and complex, and the increment of users in network causes the packets and the information in network to overflow. In addition, new multi-media services require high-speed transmission and real-time processing capability.
IP routing table lookup is one of the most significant item in high speed routers. The subnetting/supernetting of IP protocol generates best matching prefix problem in IP routing table lookup. The hash algorithm, which is the fastest lookup algorithm, can find just the element of table which exactly matches input data. Therefore, it cannot be used for lookup of longest prefix.
BSD-radix trie (Patricia tree) algorithm is used conventionally for IP routing table lookup because of its simplicity. At first, it is revised from binary search tree algorithm for BSD kernel and can be used for previous network environments handling just non-real time packets. But, it takes too long time to route voices, moving pictures, and other time critical packets. When IPv6 address is routed based on BSD-radix trie algorithm, the performance becomes worse because of 128-bits address length. So far, many algorithms were proposed to solve the above problems, but IP protocol characteristics were not considered. They were just the solutions of longest prefix lookup.
This paper proposes the IP routing table lookup algorithm based on the IP protocol characteristics and table distribution. This algorithm can get the lookup result in $log_2S$ iteration, where S is the number of subnetwork ID in a class ID. Construction of tree among the related network ID reduces memory requirement, memory usage, and lookup time.
For IPv6, there is no information related with table distribution yet. Perhaps, table distribution and IP protocol characteristics of IPv6 will be similar to those of IPv4. Therefore, proposed algorithm could be applied to IPv6 routers.
네트워크가 점점 방대해 짐에 따라, 라우터의 경로테이블 또한 점점 방대해 지고, 인터넷에 대한 수요가 급증함에 따라, 네트워크의 트래픽이 점차 증가하고 있다. 또, 새로운 멀티미디어 서비스들이 생겨남에 따라 네트워크의 속도는 고속화와 실시간 처리능력을 요구하게 되었다.
라우터를 고속화 하는데 중요한 요소 중 하나가 IP 라우터의 경로 테이블 검색이다. IP 경로테이블의 검색은 IP 프로토콜의 subnetting/supernetting 특성으로 인하여 best matching prefix를 찾아내는 문제를 풀어야한다. 현재 제안된 검색 알고리즘 중 가장 빠른 해쉬 알고리즘은 입력 data와 데이터베이스의 데이터가 정확히 일치해야만 찾을 수 있기 때문에 해쉬 알고리즘 만으로는 문제를 해결할 수 없다. 현재 제안된 IP 주소 검색 알고리즘 중 널리 쓰이는 BSD-radix trie(patricia tree)는 binary search tree를 개선한 방법으로 이전의 데이터 통신만을 목표로 하는 네트워크 환경에서는 시간적인 제약없이 사용되어 왔지만 고속 라우팅과 실시간 처리를 하는 데에는 성능이 부족하다. 또, 현재의 IP version 4에서 사용하는 32-bit 길이의 주소 환경에서 부족한 IP 주소 자원을 보충하기위해 제안된 IPv6의 128-bit IP 주소를 다룬다면, 더욱 성능이 저하된다. 이러한 문제를 해결하기 위해 많은 알고리즘들이 제안되었지만, 네트워크 상의 IP 프로토콜의 특성을 배제한 best prefix matching 문제를 해결하기 위한 알고리즘들 이었다.
본 논문에서는 IP 프로토콜의 특성과 라우터의 데이터 베이스의 네트워크 데이터 분포를 고려한 IP 라우터의 테이블 검색 알고리즘을 제안한다. 제안한 알고리즘은 $log_2S$의 반복 검색으로 결과를 얻을 수 있는 성능을 나타낸다. 이 때, S는 임의의 클래스 ID가 가지고 있는 서브네트워크의 개수이다. 이처럼 관련된 노드들끼리 트리를 형성해 줌으로서 불필요한 메모리의 사용을 줄일 수 있고, 빠른 검색 시간을 얻을 수 있다.
IPv6에 대해서는 아직 프로토콜 및 네트워크의 성질을 알 수 없어 결과를 알 수는 없지만, IPv4와 비슷한 환경(CIDR)이 될 것이라 예상하면, 마찬가지의 결과를 얻을 수 있을 것이다.
