MECHANISM FOR REDUCING LOOKUP LATENCY IN PIPELINED HARDWARE IMPLEMENTATION OF TRIE-BASED IP LOOKUP ALGORITHM

摘要

PROBLEM TO BE SOLVED: To provide an improved multi-bit trie network search engine.

SOLUTION: A series of hardware pipeline units each processing a stride during prefix search operations on a multi-bit trie includes, within at least one pipeline unit other than the last pipeline unit, a mechanism for retiring search results from the respective pipeline unit rather than passing the search results through the remaining pipeline units. Early retirement may be triggered by either the absence of subsequent strides to be processed or completion of the search ( a miss or end node match ), together with an absence of active search operations in subsequent pipeline units. Worst-case and/or average latency for prefix search operations is reduced.

COPYRIGHT: (C)2004,JPO&NCIPI