IP address lookup is to determine incoming packet’s next hop destination in the router. The lookup is a major bottleneck in high performance router due to the increased routing table sizes, increased traffic, higher speed links, and the migration to 128 bit IPv6 addresses. IP lookup time is dependent on data structure of lookup table and search scheme.
In this paper, we propose a new way to build an optimal lookup table. The design of lookup table is formulated as an optimization problem. The objective is to minimize average depth for lookup. We assume that the frequencies with which prefixes are accessed are known and the data structure is level compressed trie. Thus, the problem is to determine the branching factor at each level. Procedures based on heuristics are proposed. Experimental results show that lookup table based on the proposed has better average depth for lookup and worst-case. The procedure has scalability from IPv4 to IPv6 by considering memory.
인터넷 수요의 급증은 더 이상 인터넷 서비스가 Best effort Service가 아닌, 일정 수준 이상의 QoS를 유지하는 안정적인 서비스를 제공하는 방향으로 흐르고 있다. 이에 따라 보다 고속화 되고 안정적인 네트워크가 필요하게 되었다. 그러나 네트워크의 고속화는 WDM (Wavelength Division Multiplexing) 등의 방법으로 회선의 고속화가 이루어진 반면, 이를 뒷받침 할 수 있는 라우터의 성능이 보조를 맞추어 개선되지 않아 고속화의 Bottleneck 이 되고 있다. 특히 라우터로 들어오는 팻킷의 주소를 찾아 패킷의 다음 주소로 매칭시켜주는 ‘주소 참조 과정’ (IP lookup) 이 주 요인으로서 해결되어야 할 문제점이다.
이 논문에서는 효과적인 주소 참조테이블을 만들기 위한 알고리즘을 제시하였다. 이를 위해서 Prefix들을 저장하는 자료구조로써 LC-Trie를 도입하였고, 이에 덧붙여 IPv6로의 변환의 경우 늘어나는 Prefix 들의 양을 효과적으로 한정된 메모리에 저장할 수 있도록 메모리 제약을 추가하였다. 기존의 연구가 complete tree인 경우만 level compression을 하여 메모리 측면에서 유동적이지 못했던 반면, 이 논문에서는 complete tree가 아닌 경우에도 메모리 제약의 여유에 따라 level compression을 하는 알고리즘을 제시하였다. 또한 라우터에 들어오는 Prefix들의 확률을 고려하여 주어진 메모리 자원 내에서 들어온 패킷의 다음 주소를 찾아내는 시간을 줄이도록 하는 알고리즘을 제시하였다. 실험 결과 기존의 주소 참조과정보다 주소를 참조하는 데 걸리는 평균과 최대 시간 모두 적게 나타났으며, 또한 메모리를 최대로 사용하는 방향으로 결과가 나오고 있음을 알 수 있다.
