We propose an efficient binary search algorithm for IP address lookup in the Internet routers. While most of the previous binary search algorithms do not provide a balanced search, the proposed algorithm provides a perfectly balanced search, and hence it provides excellent search performance and scalability toward large routing tables.
Bibliographical noteFunding Information:
Paper approved by T.-S. P. Yum, the Editor for Packet Access and Switching of the IEEE Communications Society. Manuscript received October 25, 2007. This research was supported by the Ministry of Information and Communications under a HNRC-ITRC support program supervised by IITA. H. Lim and H. G. Kim are with the Department of Electronics Engineering, Ewha W. University, Seoul, Korea (e-mail: email@example.com). C. Yim is with the Department of Internet and Multimedia Engineering, Konkuk University, Seoul, Korea (e-mail: firstname.lastname@example.org). Digital Object Identifier 10.1109/TCOMM.2009.03.070146
- Binary search tree
- Binary trie
- IP address lookup