Variable length data sequence backtracking a trie structure

Details Variable length data sequence backtracking a trie structure Variable length data sequence backtracking a trie structure

1996-12-17

1998-07-28

Lintz, Paul R.

Data processing: database and file management or data structures

Database design

Data structure types

707 3, G06F 1730

Patent

active

057874301

DESCRIPTION:

BRIEF SUMMARY
The invention relates to a method and an apparatus for searching the longest matching digital sequence, particularly in routing devices of communication networks. More specifically, the invention concerns the building, maintenance, and use of a dynamic data structure which permits a rapid retrieval of the longest matching sequence stored in this data structure. Even more particularly, the invention describes a compact tree data structure (Patricia trie), including only nodes which either contain at least one stored data sequence (key) or at which the tree branches.


BACKGROUND OF THE INVENTION

A large number of computing or networking tasks require recognizing keywords from a database, such as a lookup table in a computer network or dictionaries in general. After establishing a match between the input keyword and a data sequence from the database, either the information linked to this keyword is retrieved or a program driven by this keyword is executed.
In communication networks, consisting of a number of interconnected users or nodes, data can be sent from one node to any other. Specialized nodes called routers are responsible for delivering or "forwarding" the data to their destination. By analogy, the routers act as post offices. As letters, any of the data sent through a communication network contains information about the destination address, generally as part of a so-called header. Each router compares this information or at least part of it with a list of addresses stored internally. If a match between stored addresses and the destination address is found, the router establishes a path leading to the destination node. Depending on the size of the network and its structure, the data are either directly forwarded to their destination or sent to another (intermediate) router, very much the same way a letter is passed through several post offices until reaching its final address (if ever).
One method for constructing large networks is promulgated by the International Organization for Standardization (ISO). Under this standard, each router does not store routing information for every possible address in the network. Rather, it stores routing information for partial addresses. The ISO standard, then, states that the router should send the packet to the best matching partial address it has in its database. The standard allows to build up a hierarchical structure of nodes using a given number of digits or a given header length: Main routers are addressed by the initial part of the address, subrouters by the middle part, and final destination by the last digits of the address. It is then sufficient for any router to read the digits assigned to the level of hierarchy to which the data are to be sent.
Thus, the ISO routing standard gives an excellent example for the necessity of having partial or prefix matching ability within a data structure for retrieving keywords.
The current invention can equally be applied to link different network communication protocols. As known, a network is at its most basic level a wire or a fiber that connects a number of computers and other equipment. To make use of the physical connection, procedures - or protocols - are necessary to ensure the reliable transfer of data by means of such functions as addressing, setting up and taking down connections, and similar administrative services. These various functions, or services, are typically assigned to individual protocol layers, which together constitute a protocol stack. The number of protocol layers may vary, but conceptually the functions are typically regarded as forming seven layers, a definition introduced by the Open Systems Interconnection (OSI) reference model. Today many different types of protocols exist, for example the ones known under the abbreviations and/or trademarks NETBIOS for personal computers, TCP/IP for UNIX/INTERNET connections, OSI, or SNA/APPN for host or mainframe communication. The exchange of data from one type of protocol to another requires so-called protocol converters or adapters. As is evident,

REFERENCES:
patent: 5153591 (1992-10-01), Clark
patent: 5519858 (1996-05-01), Walton et al.
patent: 5640551 (1997-06-01), Chu et al.
patent: 5655129 (1997-08-01), Ito
Robert L. Kruse, Data Structures & Program Design 379-384 (Prentice-Hall, Inc.) (New Jersey), 1984.

Affiliated with

Also associated with

Rating

Variable length data sequence backtracking a trie structure does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Variable length data sequence backtracking a trie structure, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Variable length data sequence backtracking a trie structure will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-34852