IP lookup by scalable multi-way search on prefix lengths

Abstract

IP routing table lookup is an essential technology for supporting high-speed routers. To achieve high speed IP routing table lookup, in this paper, we propose an efficient and scalable algorithm, called multi-way search on prefix lengths. The multi-way search scheme is derived from binary search on prefix lengths which groups route prefixes of identical lengths into individual tables and applies hashing technique in these tables to find matching prefixes. However, the multi-way search scheme significantly improves the average look-lip performance of binary search scheme without any loss of its worst-case lookup performance. Further the proposed scheme is so simple that it basically does not increase the complexity in constructing the search tree and in memory requirement. Through experiments on real backbone routing tables, we found that the improvement can be more than 37% for all routing tables.