For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Longest Match Table Look-up Method Using Pointer Cache
Masanori UGA Kohei SHIOMOTO
IEICE TRANSACTIONS on Communications
Publication Date: 2001/06/01
Print ISSN: 0916-8516
Type of Manuscript: PAPER
longest match, CAM, IPv6, gigabit router,
Full Text: PDF(1.1MB)
>>Buy this Article
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.