Compact data structures for pipelined message forwarding lookups
Number of patents in Portfolio can not be more than 2000
United States of America Patent
Stats
-
Feb 10, 2004
Grant Date -
Oct 10, 2002
app pub date -
Apr 4, 2001
filing date -
Apr 4, 2001
priority date (Note) -
In Force
status (Latency Note)
Importance
Abstract
The invention provides a method and system for lookup (such as for example, lookup of message header information) that records information in a relatively large database in a relatively compact structure, while still providing for relatively rapid lookup and update. A relatively large but compact database includes a hybrid tree (or hybrid trie) structure, whereby information in denser portions of the database can be stored and retrieved from an identifiable leaf in the hybrid trie. The hybrid trie includes at least one leaf node marked to include a different data structure, whereby information in sparser portions of the database can be stored and retrieved from a more densely packed table. In a preferred embodiment, each hybrid trie node is marked as one of: a branch node, a leaf node, or a search node; each search node includes information for a sparser portion of the hybrid trie, packed into a structure capable of linear search in response to a set of packet header information (such as a destination IP address).
First Claim
Family
International Classification(s)
Cited Art Landscape
Patent Citation Ranking
Advertisement
Advertisement
Advertisement
Recipient Email Address
Recipient Email Address
Comment
Recipient Email Address
Add to Portfolio(s)
To add this patent to one, or more, of your portfolios, simply click the add button.
This Patent is in these Portfolios:
Add to additional portfolios:
Last Refreshed On:
Changes done successfully