Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2001-04-16
2004-03-16
Amsbury, Wayne (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
Reexamination Certificate
active
06708168
ABSTRACT:
FIELD OF THE INVENTION
The invention relates generally to the field of content switching, and, more specifically, to the use of hardware to implement a parallel search through a data stream.
BACKGROUND
Conventional content switches search through packets of data to identify the nature of the traffic so that they make an intelligent switching decision based on the traffic content. These switches employ software that performs a serial search through the packets to determine data patterns. The fact that the search is serial in nature means that it starts with the first portion of the data, determines if the desired pattern is present then moves on to the next portion of the data. While this may provide acceptable performance when searching through short data packets, it is generally a relatively slow method that does not scale well when the search space becomes larger.
It would thus be beneficial to have a method of searching for data patterns in a quick and efficient manner which scales well for larger search spaces.
SUMMARY OF THE INVENTION
The present invention provides methods and apparatus for finding data patterns in a data stream.
An aspect of the invention provides a method that includes copying a portion of a data stream into a register bank to form a search space. Then the method includes comparing a data pattern to the data stream, using a multiple comparators. The comparisons are simultaneously performed by comparing the data pattern to different portions of the search space.
Another aspect of the invention provides an apparatus. The apparatus includes a register bank configured to temporarily store a portion of a data stream. The apparatus also includes multiple comparators, each linked to a register in the register bank. At least one of the comparators is configured to compare a data pattern to a portion of the data stream stored in the register bank. At least one other comparator is configured to compare the data pattern to another portion of the data stream stored in said register bank. Both comparitors are configured to operate simultaneously.
Yet another aspect of the invention provides an apparatus that includes a register module for storing portions of a data stream. The apparatus also includes a comparing module for simultaneously comparing a character pattern to different portions of the stored data stream.
An aspect of the invention provides an apparatus that includes a register bank, having different portions, that is configured to store a portion of a data stream. The apparatus also includes multiple comparators, each having an output and each linked to a different portion of the register bank. One of the comparators is configured to compare a data pattern to a portion of the stored data stream. Another comparator is configured to simultaneously compare the data pattern to another portion of the stored data stream. The apparatus includes an encoder circuit that receives the output from the comparators. The encoder circuit is configured to determine if a comparison made by one or more of the comparators results in a match.
The invention will next be described in connection with certain illustrated embodiments and practices. However, it will be clear to those skilled in the art that various modifications, additions and subtractions can be made without departing from the spirit or scope of the claims.
REFERENCES:
patent: 4760523 (1988-07-01), Yu et al.
patent: 5051947 (1991-09-01), Messenger et al.
patent: 5276868 (1994-01-01), Poole
patent: 5379420 (1995-01-01), Ullner
patent: 5497488 (1996-03-01), Akizawa et al.
patent: 5777608 (1998-07-01), Lipovski et al.
patent: 5781772 (1998-07-01), Wilkinson et al.
Amsbury Wayne
Nortel Networks Limited
Steubing McGuinness & Manaras LLP
LandOfFree
Method and apparatus for searching a data stream for... 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 searching a data stream for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for searching a data stream for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3232734