Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2001-05-22
2004-11-30
Robinson, Greta (Department: 2777)
Data processing: database and file management or data structures
Database design
Data structure types
C709S238000
Reexamination Certificate
active
06826561
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to a method and apparatus for searching an electronically stored table of information including a plurality of table entries, and more specifically to a method and apparatus for facilitating high speed searching of a table to provide a longest matching entry.
2. Description of the Related Art
In the fields of electronic data communications and data processing, electronically stored tables of information are used in vast variety of applications to provide a mapping between two or more information spaces. The tables of information, which include a plurality of entries, may be searched in accordance with many different methods.
Generally, a search is performed using a search key, and may read one or more tables entries to determine an exact match or a best match depending on the particular application requirements. Many algorithms and devices have been developed to efficiently search tables of information.
A basic brute force method is linear searching wherein a device searches a table linearly one entry at a time. Linear searching is the simplest search method, and it is ideal for searching small tables in applications having slow search requirements. However, linear searching becomes impractical as the table sizes increase because the maximum search time is proportional to the table size.
In order to shorten the table search time, binary searching methods may be used wherein all entries of the table are sorted in a particular order, and the search times are equal to log
2
(table size). Binary searching methods are particularly desirable for searching large tables using software, but sorting the table entries in a particular order is not a simple task. Due to this high maintenance requirement, binary searching is sometimes not feasible to implement in hardware.
One of the quickest methods of table searching uses content addressable memory (CAM) searching wherein all table entries are compared against a search key at the same time, and the search result is delivered to an output instantly. However, CAM searching provides high search performance at the expense of implementing greater logic using a greater amount of silicon real estate. Moreover, there is typically a limit to the size of comparison fields (i.e. data width) and the size of payload fields which may be used in CAM searching.
Some of the most common methods of table search employ hashing algorithms in which table entries are grouped into different buckets in accordance with the particular type of hashing algorithm (i.e. crc32). Searching systems employing hashing algorithms are capable of narrowing the searching area to a specific location (a bucket), and this limits the maximum searching time. The maximum table searching time is based on the size of the bucket, and the table search time remains constant as the number of buckets increases. As the number of the table entries increase, the possibility that two or more entries are hashed to a same bucket also increases. If the maximum table entry (the size of table) is considerably larger than the typical number of entries used at the same time and the hash algorithm spreads the entries evenly, there is a good chance that only one or two entries are in a bucket. In this case, the average search time will be rather short (one or two clock cycles per search). A good hash algorithm scatters table entries evenly over the search table, but there is a possibility that many table entries may hashed into the same bucket. Thus, using 100 percent of a table is not practical, and the size of the table often needs to be much larger than the typical number of table entries.
In routing and switching devices, a table of information is often used to provide a mapping mechanism for forwarding data, typically in the form of a packet (e.g., an Ethernet Packet), from one location to another location. As packets arrive at each of a plurality of associated ports of a switch or router device, the information stored in the table must be searched to determine an appropriate action.
For example, if the table includes an entry providing a direction for the arrived packet, the device forwards the packet in the direction indicated. If the table does not include an entry providing a direction for the arrived packet, the device may handle the packet based on a default setting. Examples of default settings include sending the packet to all available ports (broadcasting), sending the packet to a central processing unit (CPU) for analysis in accordance with a predefined set of rules, or dropping the packet. For Ethernet routing applications, a table of information is typically organized based on particular fields (e.g., a medium access control (MAC) Address, an IP Address, a Virtual LAN ID, etc.) of a packet. When particular fields of the packet match particular fields of the table, the device utilizes the corresponding information in the table to forward the packet.
Presently, worldwide networking is undergoing a shift. Internet Protocol Version 6 (Ipv6) is being implemented. IPv6 is the “next generation” protocol designed by the IETF (The Internet Engineering Task Force) to replace the current version Internet Protocol, IP Version 4 (“IPv4”). Most of today's internet uses IPv4, which is now nearly twenty years old. IPv4 has been stable and resilient, but it has several problems. Most importantly, there is a growing shortage of IPv4 addresses, which are needed by all new machines added to the Internet. IPv6 addresses the limited number of available IPv4 addresses and adds other improvements to IPv4 in areas such as routing and network autoconfiguration. IPv6 is expected to gradually replace IPv4, with the two coexisting for a number of years during a transition period.
A recent enhancement to Internet addressing is Classless Inter-Domain Routing (CIDR). With the advent of CIDR, the original class-based scheme has mostly been discarded. Instead, subnetting is used to divide “CIDR blocks” of arbitrary size into smaller “CIDR blocks”, a process that can be repeated.
Faced with exhaustion of class B address space and the explosion of routing table growth triggered by a flood of new class Cs, IETF began implementing CIDR, in the early 1990s. The primary requirement for CIDR is the use of routing protocols that support it, such as RIP Version 2, OSPF Version 2, and BGP Version 4.
The Optical Carrier system provides international standards for data rates. For OC-192, the data rate is 9.6 Gbs/second. At the heart of a wire speed OC-192 router is a lookup engine, capable of providing the destination information based on an Internet Protocol Destination Address (IPDA) every 50 ns. As discussed above, CIDR requires a lookup to be based on longest match. For a backbone router, the size of the lookup database is in the order of 256K to 512K entries.
In the prior art, there is no system or method to accomplish these tasks and that is capable of being scaled to work on both Ipv4 and Ipv6 environment, where the IPDA is 32-bit and 128-bit respectively.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide a method and apparatus for facilitating high speed linear searching of a table of information by expanding each terminating node to the lowest level. It is also an object of the present invention to provide a high performance and cost effective method and apparatus for facilitating high speed longest-prefix-match searching of a table.
In one embodiment, the present invention is directed a table searching method that uses at least one memory unit having a table of information including a plurality of data entries. The table of information has a plurality of search keys associated with the plurality of data entries and the plurality of search keys form a tree structure based on a prefix length for each of the search keys. The plurality of search keys are expanded such that each of the plurality of search keys has two lowest level search keys associated therewith that cover a lowest level of the tree
Cao Jun
Ng Eric
Smith Brandon Carl
Broadcom Corporation
Robinson Greta
Squirel Sanders & Dempsey LLP
LandOfFree
Method and apparatus for performing a binary search on an... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for performing a binary search on an..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for performing a binary search on an... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3289225