| Method and apparatus for longest prefix matching in processing a forwarding information database -> Monitor Keywords |
|
|
 
Method and apparatus for longest prefix matching in processing a forwarding information databaseRelated Patent Categories: Data Processing: Database And File Management Or Data Structures, Database Or File Accessing, Query Processing (i.e., Searching)Method and apparatus for longest prefix matching in processing a forwarding information database description/claimsThe Patent Description & Claims data below is from USPTO Patent Application 20070192303, Method and apparatus for longest prefix matching in processing a forwarding information database. Brief Patent Description - Full Patent Description - Patent Application Claims
[0001] This application is a divisional of U.S. application Ser. No. 10/692,425 filed Oct. 23, 2003 and claims the benefit of U.S. Application Provisional Ser. No. 60/432,168 filed on Dec. 10, 2002 and U.S. Provisional Application Ser. No. 60/436,960 filed on Dec. 30, 2002, all of which are incorporated by reference herein in their entirety. [0002] U.S. application Ser. No. 10/653,762 entitled "Methods and Apparatus for Data Storage and Retrieval" filed on Sep. 3, 2003 and U. S. application Ser. No. 10/654,501 entitled "Methods and Apparatus for Modular Reduction Circuits" filed on Sep. 3, 2003 are also incorporated by reference herein in their entirety. FIELD OF THE INVENTION [0003] The present invention relates generally to improved methods and apparatus for storing and retrieving data in computer memory where a longest prefix key is matched, and more particularly, to advantageous techniques for looking up data, for example, such as Internet protocol (IP) forwarding information database (FIB) lookup associated with Internet packet routing when a packet is processed in a high speed network. BACKGROUND OF THE INVENTION [0004] The growing network of packet based routers and bridges used in the Internet and other packet networks in addition to the increased network speeds of routing packets, such as 10 Gigabits per second, as specified in Optical Carrier standard document OC-192, require more efficient handling of the task of looking up forwarding information stored in a FIB table. These FIB tables are found in routers and bridges, for example, and are used to determine how to route an outgoing packet. [0005] Looking up the outgoing port number upon receipt of an incoming packet in a FIB table is typically complex because variable length prefix keys are utilized to determine if an entry in the FIB table matches a unique key extracted from the incoming packet. Considering that the incoming packet contains an IP destination address which has 32 bits, typical variable length prefixes have lengths ranging from 1 to 32 bits. When a prefix has a length less than 32 bits, a 32 bit word is still typically stored in the FIB table and only the prefix bits are matched against the IP destination address and the unused bits are considered operationally as "don't cares", meaning those bits are not compared to the incoming packet's destination address. [0006] Adding to the complexity of looking up data in a FIB table, shorter length prefixes may be subsets of longer length prefixes which would typically result in multiple matches. To resolve multiple matches, the Internet protocol specifies that the longest length mask which matches the incoming key's destination address should be chosen. [0007] Considering the expanding Internet network and the speed at which data travels through the network, the FIB table lookup problem often requires the capability for achieving a sustained packet forwarding rate of at least 25 million packets per second (MPPS), while maintaining an update rate of at least 2000-3000 updates per second. Any solution further requires handling burst FIB table update rates that can be up to 10 times higher than steady state rates. Also the FIB table should be available for lookup at all times in order to minimize the packet drop rate. [0008] There have been many solutions to the FIB table lookup problem. Typical software approaches usually employ radix tree techniques. As a result, software approaches are relatively slow and do not scale well with the increasing size of the Internet and the speed at which data travels through the Internet. To achieve the desired speeds, a typical hardware approach employs ternary content addressable memory (TCAM) device which is based on a special circuit design. A typical TCAM device requires approximately 16 transistors to store one bit of information. Since the current manufacturing technology and state of the art circuit design limits TCAM chips to 18 megabits per chip, assuming 128 k entries with a table entry size of 144 bits, a single TCAM chip may consume up to 300 million transistors, thus pushing the limits of the state of the art silicon manufacturing process. [0009] To address the specific FIB table lookup problem of multiple matches of differing length prefixes, one TCAM approach requires shorter length prefixes that are subsets of longer length prefixes to be stored physically together in a group and in descending order from longest length prefix to shorter length prefix. The longer length prefix is returned because upon matching an incoming packet's key, the approach finds the prefix group and steps through comparing each prefix, starting with the longest prefix and progressing through to the shortest prefix until a first match is found. This typical sequential progression requires that the FIB table maintain its table entries in sorted order to ensure the longest prefix match is always returned. [0010] A ternary content addressable memory approach to solving the longest prefix match problem has been previously described. One recent approach is described in Nataraj et al. U.S. Pat. No. 6,499,081 ("Nataraj"), where an attempt has been made to eliminate the prefix ordering and also to decrease the device power consumption at the expense of more complex logic circuits related to prioritizing matched results and extracting the longest prefix match. However, the circuit based approach of a TCAM device remains a major challenge in actual silicon implementation with respect to both power consumption and density, especially if a large number of wide table entries need to be supported. Further, since TCAM devices require multiple transistors to store one bit of information, real estate on a TCAM device is limited. Due to the real estate limitation and the fact that TCAM automatically compares stored entries with incoming keys, typical TCAM devices only store prefix keys, and any data related to a stored key is then typically stored on an external, non-TCAM memory, requiring multiple levels of indirection to access such related data. [0011] There exists a need for an improved solution to the FIB table lookup problem which is algorithmic and may suitably employ less expensive, embedded, dynamic random access memory (DRAM) devices readily available in multiple silicon manufacturing processes. [0012] The present invention addresses the ever expanding speeds and capacity requirements of today's Internet packet routers by providing an advantageous approach that efficiently utilizes embedded DRAM devices as its underlying technology for the search engine, thus reducing power consumption along with increased memory density and resulting in reduced costs when compared to TCAM approaches. SUMMARY OF THE INVENTION [0013] Among its several aspects, the present invention provides methods and apparatus for storing a prefix key of a certain length. To achieve the high rates required by routers when routing packets, the present invention advantageously stores prefix keys of a specified length in a prefix search engine. The prefix search engine has been programmably assigned to store prefix keys having a certain length. The prefix search engine includes a format module, an n-dimensional memory as disclosed in U.S. Ser. No. 10/653,762, and a conversion module. The format module masks out one or more bits from an incoming key formed, for example, from selected fields extracted from an IP packet header. The number of bits masked is determined by the prefix key length assigned to the prefix search engine. The n-dimensional memory includes a number of memory banks, the number determined by at least the number of ordinates within an n-dimension representation of a search key. Each memory bank is associated with one of the ordinates within the n-dimension key representation. Each memory bank has a number of memory locations at least equal to the largest valid value for its associated ordinate. The conversion module converts the masked key into an n-dimension representation. The conversion module then optionally stores the masked key with other data into one of the memory locations referenced by an ordinate of the n-dimension representation. [0014] Another aspect of the present invention includes methods and apparatus for storing and retrieving data in computer memory where a longest prefix key is matched with an incoming key. Prefix search engines are assigned to store prefix keys which may vary in length. Each prefix search engine stores prefix keys which match a preassigned length. When a packet arrives, a unique key is extracted from the packet's header. Each prefix search engine masks the unique key according to its preassigned length and converts the masked key into an n-dimension representation. In parallel, each prefix search engine compares its memory locations according to the n-dimension representation and outputs a match indication and a match result, if the masked key successfully compares with one of the stored prefix keys. [0015] A programmable priority controller maintains the pre-assignment information for each search engine and receives all the match indications from the prefix search engines. The priority controller indicates to a resulting index multiplexer the prefix search engine which stores the longest matched prefixed key. The resulting index multiplexer selects the match result corresponding to the prefix search engine indicated by the priority controller and forwards this result for further processing. [0016] A more complete understanding of the present invention, as well as further features and advantages of the invention, will be apparent from the following detailed description and the accompanying drawings. BRIEF DESCRIPTION OF THE DRAWINGS [0017] FIG. 1 illustrates an exemplary packet routing network in which the present invention may be advantageously employed. [0018] FIG. 2 shows a table listing prefix lengths, a notation used to refer to masks having a certain prefix length, and illustrates relevant bits in a corresponding prefix key. [0019] FIG. 3 illustrates a 144 bit FIB table entry based on information extracted from an IP version 4 packet header to compose an 80 bit search key with associated 64 utility bits. [0020] FIG. 4 illustrates an exemplary embodiment of a routing card in accordance with the present invention. Continue reading about Method and apparatus for longest prefix matching in processing a forwarding information database... Full patent description for Method and apparatus for longest prefix matching in processing a forwarding information database Brief Patent Description - Full Patent Description - Patent Application Claims Click on the above for other options relating to this Method and apparatus for longest prefix matching in processing a forwarding information database patent application. ###  How KEYWORD MONITOR works... a FREE service from FreshPatents1. Sign up (takes 30 seconds). 2. Fill in the keywords to be monitored. 3. Each week you receive an email with patent applications related to your keywords. Start now! - Receive info on patent apps like Method and apparatus for longest prefix matching in processing a forwarding information database or other areas of interest. ### Previous Patent Application: Managing the execution of a query Next Patent Application: Method and device for processing data of a plurality of different products Industry Class: Data processing: database and file management or data structures ### FreshPatents.com Support Thank you for viewing the Method and apparatus for longest prefix matching in processing a forwarding information database patent info. IP-related news and info Results in 0.13413 seconds Other interesting Feshpatents.com categories: Daimler Chrysler , DirecTV , Exxonmobil Chemical Company , Goodyear , Intel , Kyocera Wireless , 174 |
 * Protect your Inventions * US Patent Office filing 
PATENT INFO |
|
