| 摘要 |
<p>A system and method for performing longest prefix matching processing, such as that employed for IP destination address lookups, is disclosed. The technique, referred as the Optimized Multi-bit Trie (OMT) approach, maps a routing table having prefix entries and next hop identification (NHID) values into a compact and readily searchable data structure. LPM searches of the OMT data structure can be performed without backtracking and without loops on the trie level. LPM searches of the OMT data structure can be performed without performing condition checks. The OMT data structure is constructed for a routing table so that the LPM searches are performed according to a fixed number of levels. The OMT technique reduces the number of memory accesses required for identifying LPM matches and is fast and memory efficient.</p> |
