US 2004/0111440 A1 · Method for increasing storage capacity in a multi-bit trie-based hardware storage engine by compressing the representation of single-length prefixes

Abstract

Prefixes terminating with end node entries each containing identical length prefix portions in a single child table are compressed by replacing the end node entries with one or more compressed single length (CSL) prefix entries in the child table that contain a bitmap for the prefix portions for the end node entries. A different type parent table trie node entry is created for the child table. Where the prefix portions are of non-zero length, the parent table contains a bitmap indexing the end node entries. Where the prefix portions are of length zero, the parent table may optionally contain a bitmap for the prefix portions, serving as an end node. The number of prefix portions consolidated within the CSL node entry is based upon the prefix portion length.

Claims24

Dependent claims

A system for utilizing a bitmapped multi-bit trie comprising:

a search engine maintaining or utilizing prefix tables for a multi-bit trie including at least one compressed single length (CSL) prefix entry in a child table originally containing a plurality of end node entries, each of the plurality of end nodes containing a prefix portion of identical length,
wherein the one or more compressed single length prefix entries replacing the plurality of end node entries contains prefix portions for the plurality of end node entries.

Dependencies are inferred from the claim text.

Method for increasing storage capacity in a multi-bit trie-based hardware storage engine by compressing the representation of single-length prefixes

Life of this patent

Method for increasing storage capacity in a multi-bit trie-based hardware storage engine by compressing the representation of single-length prefixes

Life of this patent

Abstract

Claims24