A lookup algorithm based on multiple tables for high-speed routers

Article type: Research Article

Authors: Kim, Kyungjun | Han, Kijun

Affiliations: Department of Computer Engineering, Kyungpook National University, Daegu, Korea

Note: [] Corresponding author. Tel.: +82 53 940 8697; Fax: +82 53 957 4846; E-mail: [email protected].

Abstract: The IP address lookup in the communication link technologies is becoming a major bottleneck by exploring the exact matching and the parallel hashing in each prefix length. In this paper, we present an algorithm for IP address lookup and collision resolution to reduce memory space and solve collision for high speed routing based on multiple table indexing structure. Our scheme makes possible direct access in a designated IP prefix without replicating the forwarding table entries, and provides efficient collision resolution for fast route lookup with only small memory. Simulation results indicate that our algorithm provides a faster lookup than the conventional lookup schemes.

Keywords: IP lookup algorithm, high speed router, packet forwarding, routing

Journal: Journal of High Speed Networks, vol. 14, no. 3, pp. 227-234, 2005