Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2001-06-28
2004-02-03
Jung, David (Department: 2175)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C711S100000, C709S200000
Reexamination Certificate
active
06687715
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to retrieval of data records. More specifically, the present invention relates to a system, method and apparatus for performing parallel lookups of data records each associated with a frame in a stream of frames, where the lookups keep the order of frames accessing the same data records.
2. Discussion of the Related Art
In networking applications, frames of data are sent through a network. The frames may contain data and reference additional data. Networking applications often utilize Transmission Control Protocol (TCP) to transmit and receive the frames. Frames are packets of information that may be transferred on a network, such as a computer network.
A single device in a TCP protocol implementation can have many “conversations” (TCP connections) with other devices occurring simultaneously. When a device on the network receives a frame, a conversation-identifier is extracted from IP (Internet Protocol) and TCP headers in the frame. The conversation-identifier may be a “key.” A key is piece or data, or code, that references a section of data. For example, a frame may be sent with the key “1010”. The key “1010” may reference a “status record” for one of the TCP conversations, for example, in a memory. The status record is used by the TCP protocol to process the frame.
There are several methods in the art for locating a key in a memory. For example, a hash-based method has been used. In a hash-based method, there are a set number of look-up engines. Each lookup engine may be a separate program, or a subroutine in a program, for example, that searches for keys in a memory. Many systems in the art utilize more than one lookup engine to search for keys in the memory. The systems typically allocate keys to one of the plurality of lookup engines based upon certain calculations. For example, the hashing method creates a hash value for each key and, based upon the hash value, assigns the key to one of the lookup engines. An exemplary hash-based embodiment may include two lookup engines, A and B, and use keys comprised of four digits. The hash function may be set to sum the digits of the key and send all keys with even-number hash values to lookup engine A and all keys with odd-number hash values to lookup engine B. For example, the sum of the digits in the key “1010” yields an even number, and would therefore be assigned to lookup engine A. The sum of the digits of key “1011” yields an odd number, and would therefore be assigned to lookup engine B. However, a hash-based method is inefficient in a situation where two keys yield the same even (or odd) hash value. In such a situation, one of the lookup engines remains idle while the second key waits until the lookup engine for even hash values locates the first key. Then, the second key may be allocated to the even hash value lookup engine.
Another method for finding keys utilizes a distribution calculation in link aggregation. The distribution calculation in link aggregation is similar to the hash-based method, except that keys for frames are distributed to a number of network links, rather than to a number of lookup engines. The distribution calculation suffers from shortcomings similar to those of the hash-based method, because the system once again searches for the keys based upon the results of a calculation.
The order of processing of frames may matter, for example, in situations where two frames have the same key, and therefore access the same set of data in the memory. If the data is subject to change by virtue of it being accessed, then the first frame must be processed before the second frame is processed.
The order of processing of frames may also matter if a routing protocol is being used that requires frames to be processed in the order in which they are received. An additional reason why the order of processing of the frames may matter is because TCP processing of frames is faster/better when frames for a given conversation are processed by a device in the same order in which that they were generated by the other device. Usually the network does not reorder frames, so by processing frames in the order they are received, they are thereby usually processed in the order they were generated.
In many embodiments in the art, lookups typically take a constant amount of time. The lookups ordinarily complete in the order in which they were initiated, so no specific action has to be taken to ensure the order. However, a problem with this type of lookup is that the usable lookup engines are limited because they always have to use the same low number of memory access to perform the lookup. In another method where the order matters, lookups may take a variable amount of time. However, in the current state of the art, such lookups are performed one-at-a-time.
Accordingly, the systems in the prior art are inefficient in looking up frames where the order of the lookups matters. Prior systems either utilize multiple lookups engines that each search for a set length of time, or search for a variable length of time using one lookup engine at a time. Therefore, systems in the prior art cannot perform multiple lookups for variable lengths of time simultaneously.
REFERENCES:
patent: 6499028 (2002-12-01), Brock et al.
patent: 6557091 (2003-04-01), Houldsworth
patent: 6564217 (2003-05-01), Bunney et al.
Chaddha et al., A frame-work for live multicast of video streams over the Internet, Image Processing, 1996, Proceedings, International Conference on, vol. 1, Sep. 16-19, 1996, pp. 1-4.*
Dudgeon et al., Real time processing of multiple input multiple output systems using crosscut memory, Southeastcon '89, Proceedings, Energy and Information Technologies in the Southeast, IEEE, Apr. 9-12, 1989, pp. 1352-1355, vol. 3.*
Chang et al., Efficient IP routing table VLSI design for multigigabit routers, Circuits and Systems, 2002, ISCAS 2002, IEE International Symposium on, vol. 2, May 26-29, 2002, pp. II-776 to II-779.
Jung David
Pillsbury & Winthrop LLP
LandOfFree
Parallel lookups that keep order does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Parallel lookups that keep order, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parallel lookups that keep order will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3334129