Hybrid longest prefix match and fixed match searches

Details Hybrid longest prefix match and fixed match searches Hybrid longest prefix match and fixed match searches

2000-11-28

2004-09-14

Rones, Charles (Department: 2175)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000, C709S238000

Reexamination Certificate

active

06792423

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates in general to prefix matching searches and, in particular to combining fixed matching with longest prefix matching techniques to improve search efficiency. More particularly, the present invention relates to utilizing a non-uniform statistical distribution of prefix length values within a network routing prefix table to divide the prefix table into two or more direct tables from which longest prefix searches can be performed.
2. Description of the Related Art
Many data processing or networking tasks require finding the longest matching binary sequence from a collection of stored binary strings. Specifically, such tasks require comparing an input keyword to a keyword that is stored in a database to find the longest match. The database that stores the keywords often includes a lookup table that, after establishing a match between an input keyword and a data string within the database, either retrieves information or executes a program linked to the data string.
In packet-based communication networks, which consists of multiple interconnected nodes, data in the form of packets can be sent from one node to any other node. Specialized nodes called routers are responsible for or “forwarding” a packet to its destination. By analogy, routers act as post offices. As letters, any of the data packets sent through a communication network contain information about the destination address, generally as part of a header. Each router compares this information or at least part of it with a list of addresses stored internally. If a match between a stored address 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 packet is either directly forwarded to its destination or sent to another router, very much the same way a letter is passed through several post offices until reaching its final address.
One method for constructing large networks is promulgated by the International Organization for Standardization (ISO). Under this method, 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 dictates that a router send a packet to the best matching partial address within its database. Implementing this standard requires building 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 digits assigned to the level of hierarchy to which a packet is to be sent. The ISO is thus a good example for illustrating the utility of having partial prefix matching ability.
Other useful applications of prefix matching include assigning an access/security level to a user of shared computer and network equipment, directory look-ups in a telephone context, on-line dictionaries, spelling checkers, and searching for reference numbers in large organizations, such as social security, health or other insurances, banking applications and the like.
The use of prefixes introduces a lookup problem in which multiple stored prefixes may match a given packet address. If a packet matches multiple stored prefixes, it is intuitive that the packet should be forwarded in accordance with instructions associated with the most specific or longest matching prefix.
Prefix matching lookup is particularly essential for high-speed packet forwarding over the Internet. As utilized herein, “the Internet” refers to the worldwide collection of networks that utilize the Transmission Control Protocol/Internet Protocol (TCP/IP) suite of protocols to communicate with one another. It is reasonable to expect further increases in users, hosts, domains, and thus to expect greater traffic management problems on the Internet.
IP currently supports a network routing protocol called IPv4 (Internet Protocol Version 4) that utilizes a 32-bit address in the header of each packet. For each packet received through an input link interface, a router reads the address field to determine the identity of the device (such as another router or host) to which the packet should be forwarded before reaching its final destination. routing table is typically utilized by a router to provide a searchable index between a packet address and the correct forwarding instruction. Exact matching is not feasible due to the resulting requirement of a routing table having 2
32
entries for a 32-bit address. The routing table contains an array of address prefixes that each represent an address that is reachable from the router. After determining the optimum destination node, the router encodes the corresponding destination address into the address field of the packet and delivers the packet to a particular output link interface according to the encoded destination address.
This method of IP address lookup has become an increasingly critical delay bottleneck for Internet traffic. The problem will only get worse if IP addressing adopts longer addresses such as the 128-bit address required for the proposed IPv6 protocol.
From the foregoing, it can be appreciated that a need exists for an improved longest prefix matching technique in which statistical parameters associated with a given prefix length are advantageously utilized to simplify a search for a longest prefix match.
SUMMARY OF THE INVENTION
A method and system for finding a longest matching prefix for an input keyword from among multiple prefixes are disclosed herein. The prefixes are data strings of varying lengths wherein prefixes of length n or greater are probabilistically the longest prefix match. The method of the present invention begins by mapping the prefixes of length greater than or equal to n
1
into a first lookup system. Remaining prefixes of length less than n
1
but greater than or equal to n
2
are mapped into a second index utilizing a second hash function, wherein n
2
is less than n
1
.
In a second embodiment, additional trees of even shorter prefixes are tested in additional lookups. Thus, there can be a third lookup mechanism used when prefixes of length shorter than n
2
exits, and so on.
All objects, features, and advantages of the present invention will become apparent in the following detailed written description.


REFERENCES:
patent: 4255796 (1981-03-01), Gabbe et al.
patent: 4558302 (1985-12-01), Welch
patent: 4899147 (1990-02-01), Schiavo et al.
patent: 5201048 (1993-04-01), Coulter et al.
patent: 5493607 (1996-02-01), Arumainayagam et al.
patent: 5692173 (1997-11-01), Chew
patent: 5781772 (1998-07-01), Wilkinson, III et al.
patent: 5787430 (1998-07-01), Doeringer et al.
patent: 5813001 (1998-09-01), Bennett
patent: 5920900 (1999-07-01), Poole et al.
patent: 5946679 (1999-08-01), Ahuja et al.
patent: 5983223 (1999-11-01), Perlman
patent: 6011795 (2000-01-01), Varghese et al.
patent: 6014659 (2000-01-01), Wilkinson, III et al.
patent: 6018524 (2000-01-01), Turner et al.
patent: 6243720 (2001-06-01), Munter et al.
patent: 6460120 (2002-10-01), Bass et al.
patent: 6631419 (2003-10-01), Greene
“A Simple Algorithm for the Longest-Prefix-Matching Problem,” Research Disclosure—Sep. 1998/1281.
“IP Lookups Using Multiway and Multicolumn Search,” Butler Lampson, Venkatachary Srinivasan and George Varghese, Associate Member, IEEE, IEEE/ACM Transactions on Networking, vol. 7, No. 3, Jun. 1999.
“Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing,” Sponsored by: ACM Special Interest Group for Automata and Computability Theory and ACM Special Interest Group for Operating System Principles, ACM Press, Puerto Vallarta, Mexico, Jun. 28-Jul. 2, 1998.

Affiliated with

Also associated with

Rating

Hybrid longest prefix match and fixed match searches does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Hybrid longest prefix match and fixed match searches, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hybrid longest prefix match and fixed match searches will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3270625