US 2004/0111439 A1 · Method for increasing average storage capacity in a bit-mapped tree-based storage engine by using remappable prefix representations and a run-length encoding scheme that defines multi-length fields to compactly store IP prefixes

Abstract

Sparsely distributed prefixes within a bitmapped multi-bit trie are compressed by: replacing a single entry table string terminating with a single prefix end node with a parent table entry explicitly encoding a prefix portion; replacing a table with only two end nodes or only an end node and an internal node with a single parent table entry explicitly encoding prefix portions; replacing two end nodes with a single compressed child entry at a table location normally occupied by an internal node and explicitly encoding prefix portions; and/or replacing a plurality of end nodes with a prefix-only entry located at the table end explicitly encoding portions of a plurality of prefixes. The compressed child entry and the prefix-only entry, if present, are read by default each time the table is searched. Run length encoded allows variable length prefix portions to be encoded.

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 one or more compressed table entries selected from:
a compressed end node (cnode) entry containing one or more encoded portions of prefixes for one or two end nodes and a data pointer;
a prefix-only node (pnode) entry containing one or more encoded portions of prefixes;
a compressed single prefix (CSP) node entry containing an encoded portion of a prefix for a string of single entry child tables terminating in a single prefix end node and a data pointer;
and
a compressed double prefix (CDP) node entry containing encoded portions of prefixes for a child table containing only two entries and a data pointer,
wherein use of the one or more compressed entries saves at least one prefix table or prefix table entry.

4 more elements

Dependencies are inferred from the claim text.

Method for increasing average storage capacity in a bit-mapped tree-based storage engine by using remappable prefix representations and a run-length encoding scheme that defines multi-length fields to compactly store IP prefixes

Life of this patent

Method for increasing average storage capacity in a bit-mapped tree-based storage engine by using remappable prefix representations and a run-length encoding scheme that defines multi-length fields to compactly store IP prefixes

Life of this patent

Abstract

Claims24