Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2001-04-04
2004-02-10
Corrielus, Jean M. (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06691124
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to compact data structures, such as for example those used for message forwarding.
2. Related Art
In forwarding messages in a computer network, it is desirable to match lookup search keys (including header information from packets in which those messages are embodied) with routing information indicating how to process those packets and message. It is particularly desirable that the matching operation be performed as rapidly as possible. This has led to a desire for data structures for storing and retrieving information regarding those lookup search keys, so that data elements associated with those lookup search keys can be rapidly stored and retrieved.
In known methods for storage and retrieval of information regarding lookup search keys, the data structures used are relatively large. Thus, the data structures are often stored in a relatively slow and expensive memory-(such as an off-chip memory for a routing circuit integrated onto a single chip), thus slowing each access to the data structures themselves, and providing a limit to accesses due to the nature of the off-chip memory.
Accordingly it would be desirable to have a technique for storing and retrieving information associated with lookup search keys that is simultaneously relatively fast and inexpensive, while allowing for relatively large amounts of data, and is not subject to the drawbacks of the known art. The following features would be advantageous:
It would be advantageous if that technique has all of the features of including a relatively compact data structure, one that is easy to read from (that is, to perform lookup operations), and easy to write to (that is, to perform update operations).
It would be advantageous if that technique were not specific to any particular application, any particular format or size of lookup search keys and associated data.
It would be advantageous if that technique were able to include multiple matching data elements for any selected lookup search key, where those multiple matching data elements can be ordered with regard to their priority. This is particularly advantageous with regard to the “longest prefix match” problem, as further described in the incorporated disclosure (described below).
It would be advantageous if that technique were well adapted to pipelined operation, such as further described in the incorporated disclosure.
These advantages and others are provided in an embodiment of the invention, described herein, including a hybrid trie data structure in which distinct types of nodes (such as a search node or a branch/search node, as described below) are substituted for sub-tries in response to a number of prefixes in those sub-tries.
SUMMARY OF THE INVENTION
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.
In a first aspect of the invention, 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-search 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-search node, or a branch-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).
In a second aspect of the invention, the hybrid trie is recorded in a sequence of SRAM memories, disposed so that each stride of the hybrid trie includes a lookup within a single memory, whereby a corresponding sequence of lookup requests can be processed in a pipelined manner with all the memories performing concurrent lookups, whereby complete lookups can be performed at a rate substantially equal to their arrival rate (even though each lookup takes a sequence of memory references to complete). Each branch node and each leaf node is recorded in a single memory. Each search node can be striped across a plurality of memories, whereby search of a search node can be distributed across those memories, and completion of lookups involving a search node operates within the pipeline paradigm of completion of lookups involving only reference to branch nodes and leaf nodes.
The invention has general applicability to compact memory storage and retrieval, to update of information recorded in relatively compact form, and to applications having utility for data lookup. None of these applications are limited specifically to lookup for message header information, nor are they necessarily related to the specific applications disclosed herein. For example, embodiments of the invention can include one or more of, or some combination of, the following applications:
Routers and switches at all levels of the ISO/OSI networking model, including without limitation: bridges, network gateways, network routers and switches;
Data storage and retrieval for arbitrary data in a relatively large database.
REFERENCES:
patent: 5414836 (1995-05-01), Baer et al.
patent: 6018741 (2000-01-01), Howland et al.
patent: 6029170 (2000-02-01), Garger et al.
patent: 6052693 (2000-04-01), Smith et al.
patent: 6209020 (2001-03-01), Angle et al.
patent: 6343072 (2002-01-01), Bechtolsheim et al.
patent: 6523042 (2003-02-01), Milleker et al.
patent: 6546391 (2003-04-01), Tsuruoka
patent: 2002/0009076 (2002-01-01), Engbersen et al.
patent: 2002/0107860 (2002-08-01), Gobeille et al.
patent: 2002/0147721 (2002-10-01), Gupta et al.
patent: 2002/0184231 (2002-12-01), Baskins et al.
patent: 2002/0194184 (2002-12-01), Baskins et al.
Gupta Pankaj
Venkatachary Srinivasan
Cypress Semiconductor Corp.
Daffer Kevin L.
LandOfFree
Compact data structures for pipelined message forwarding... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Compact data structures for pipelined message forwarding..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Compact data structures for pipelined message forwarding... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3348248