A Longest Match Table Look-up Method Using Pointer Cache

Masanori UGA  Kohei SHIOMOTO  

Publication
IEICE TRANSACTIONS on Communications   Vol.E84-B   No.6   pp.1664-1673
Publication Date: 2001/06/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8516
Type of Manuscript: PAPER
Category: Internet
Keyword: 
longest match,  CAM,  IPv6,  gigabit router,  

Full Text: PDF(1.1MB)
>>Buy this Article


Summary: 
We propose a fast and compact longest match table look-up method for very long network addresses like IP version 6. This method uses two ideas for a routing-table arranged in a tree-structure. The first idea is to make table look-up fast by caching pointers to intermediate nodes in the tree, reducing the number of node traversals. The second idea is to reduce the memory size required for each node in the tree by one-third by eliminating common parts of addresses of adjacent nodes. Evaluating the performance of this method by using actual routing table data of an IP backbone network, we found it was five to ten times faster than a conventional method.