IP' routing table lookup has been considered as a major bottleneck for high-speed routers. In the past few years, several data structures and related algorithms have been developed to accomplish high-speed routing table lookup. In particular, an efficient algorithm, called binary search on prefix lengths, was designed by grouping prefixes of identical lengths into individual tables and applying hashing technique in these tables to find matching prefixes. The time complexity of binary search on prefix lengths is [log(W +1)] assuming W-bit address. In this paper, we propose a multi-way search algorithm on prefix lengths to improve the average lookup performance of the binary search scheme without sacrificing its worst-case search performance. 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 most tables and 21% for one table.
|Number of pages||8|
|Journal||Journal of the Chinese Institute of Electrical Engineering, Transactions of the Chinese Institute of Engineers, Series E/Chung KuoTien Chi Kung Chieng Hsueh K'an|
|State||Published - 1 Feb 2004|
- Binary search on prefix lengths
- Routing table lookup