Fast IP routing lookups for high performance routers

The key to the success of the next generation IP networks to provide good s ervices relies on the deployment of high performance routers to do fast IP routing lookups. In this paper, we propose a new algorithm for fast IP look ups using a so-called two-trie structure. The two-trie structure provides t he advantages in that less memory space is required for representing a rout ing table than the standard hie while it still provides fast IP lookups. Ba sed on the simulation result, the memory space can be saved around 27% over the standard trie while a lookup operation takes 1.6 memory accesses in th e average case and 8 memory accesses in the worst case. Also, the structure is not based on any assumptions about the distribution of the prefix lengt hs in routing tables. Thus, increasing the lengths from 32 to 128 bit (from IPv4 to TPv6) does not affect the main structure. (C) 1999 Elsevier Scienc e B.V. All rights reserved.