TY - JOUR
T1 - Fast IP routing lookups for high performance routers
AU - Kijkanjanarat, T.
AU - Chao, H. J.
PY - 1999/9/25
Y1 - 1999/9/25
N2 - The key to the success of the next generation IP networks to provide good services 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 lookups using a so-called two-trie structure. The two-trie structure provides the advantages in that less memory space is required for representing a routing table than the standard trie while it still provides fast IP lookups. Based 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 the 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 lengths in routing tables. Thus, increasing the lengths from 32 to 128 bit (from IPv4 to IPv6) does not affect the main structure.
AB - The key to the success of the next generation IP networks to provide good services 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 lookups using a so-called two-trie structure. The two-trie structure provides the advantages in that less memory space is required for representing a routing table than the standard trie while it still provides fast IP lookups. Based 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 the 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 lengths in routing tables. Thus, increasing the lengths from 32 to 128 bit (from IPv4 to IPv6) does not affect the main structure.
UR - http://www.scopus.com/inward/record.url?scp=0033359817&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0033359817&partnerID=8YFLogxK
U2 - 10.1016/S0140-3664(99)00099-7
DO - 10.1016/S0140-3664(99)00099-7
M3 - Article
AN - SCOPUS:0033359817
SN - 0140-3664
VL - 22
SP - 1415
EP - 1422
JO - Computer Communications
JF - Computer Communications
IS - 15
ER -