Optimized Binary-Search-on- Range Architecture for IP Address Lookup

Internet routers forward an incoming packet to an output port toward its final destination through IP address lookup. Since each incoming packet should be forwarded in wire-speed, it is essential to provide the high-speed search performance. In this paper, IP address lookup algorithms using binary search are studied. Most of the binary search algorithms do not provide a balanced search, and hence the required number of memory access is excessive so that the search performance is poor. On the other hand, binary-search-on-range algorithm provides high-speed search performance, but it requires a large amount of memory. This paper shows an optimized binary-search-on-range structure which reduces the memory requirement by deleting unnecessary entries and an entry field. By this optimization, it is shown that the binary-search-on-range can be performed in a routing table with a similar or lesser number of entries than the number of prefixes. Using real backbone routing data, the optimized structure is compared with the original binary-search-on-range algorithm in terms of search performance. The performance comparison with various binary search algorithms is also provided.