Method and apparatus for finding variable length data patterns within a data stream
View Patent ↗A method and apparatus for searching for a character pattern within a data stream. A checksum is computed for one or more patterns for which the data stream will be searched. The patterns may be of the same length or they may be of different lengths. A shift register is used to sequentially parse through the data stream and compute the checksum of a series of bytes in the data stream. If the checksum of the bytes in the data stream that have been shifted into the register matches the checksum from one of the character patterns, then the character pattern corresponding to the checksum has been found. The system may search multiple character patterns simultaneously by using multiple checksum generators in parallel.
1. A method of searching through packets of data traffic within a data stream to identify the nature of the traffic in support a switching decision based on traffic content, comprising the steps of:
computing a plurality of character patterns associated with the traffic content, where a first character pattern has a first length and a second character pattern has a second length and the first length is not equal to the second length;
computing a first checksum for each said character pattern;
computing a second checksum for a predetermined portion of said data stream;
comparing said second checksum to said first checksums to determine if there is a match, a match being indicative of a probability that the data stream includes traffic content associated with the matching character pattern; and
if there is a match, computing a switching decision based at least in-part on the traffic content.
2. The method according to claim 1 further comprising shifting said portion of said data stream into a shift register.
3. The method according to claim 2 further comprising: shifting more data from said data stream into said shift register if said comparison does not result in a match; and recomputing said second checksum by removing an oldest unit of data and adding said more data to said recomputation.
4. The method according to claim 3 further comprising: continuing said shifting and said recomputing until said comparison results in a match.
5. The method according to claim 1 further comprising: shifting multiple portions of said data stream into a shift register.
6. The method according to claim 5 further comprising computing a plurality of second checksums based upon different parts of said multiple portions of said data stream.
7. The method according to claim 6 wherein said character pattern includes a plurality of character sub-patterns and said checksum comprises a plurality of sub-checksums; said method further comprising simultaneously comparing said plurality of second checksums to at least two of said plurality of sub-checksums to determine if there are any matches.
8. The method according to claim 7 wherein at least two of said plurality of sub-checksums have different lengths.
9. The method according to claim 1 wherein said character pattern includes a plurality of character sub-patterns and said checksum comprises a plurality of sub-checksums; said method further comprising simultaneously comparing said second checksum to at least two of said plurality of sub-checksums to determine if there are any matches.
10. The method according to claim 1 wherein said character pattern includes a plurality of character sub-patterns and said checksum comprises a plurality of sub-checksums; said method further comprising comparing said second checksum to one of said plurality of sub-checksums to determine if there is a match; recomputing said second checksum based upon a longer portion of said data stream; and comparing said recomputed second checksum to at least another of said plurality of sub-checksums.
11. The method according to claim 1 wherein said potion of said data stream includes a byte of data.
12. The method according to claim 1 wherein said potion of said data stream includes a plurality of bytes of data.
13. Apparatus that searches through packets of data traffic to identify the nature of the traffic in support of a switching decision based on traffic content within a data stream comprising:
logic operable to compute a plurality of character patterns associated with the traffic content, where a first character pattern has a first length and a second character pattern has a second length, and the first length is not equal to the second length;
a register;
a processor for copying a predetermined portion of said data stream into said register;
at least checksum generator configured to compute a first checksum for each said character pattern and a second checksum for said predetermined portion;
at least one comparator configured to compare said second checksum to said first checksum, a match being indicative of a probability that the data stream includes traffic content associated with the character pattern; and
logic operable in response to a match to computing a switching decision based at least in-part on the traffic content.
14. The apparatus according to claim 13 wherein said register further includes a plurality of sub-registers.
15. The apparatus according to claim 13 wherein said predetermined portion of said data stream is a byte of data.
16. The apparatus according to claim 13 wherein said predetermined portion of said data stream is a plurality of bytes of data.
17. The apparatus according to claim 13 wherein said checksum generator is configured to respectively compute a plurality of first checksums for a plurality of character patterns and to compute the second checksum for said predetermined portion; and, wherein said at least one comparator includes a plurality of sub-comparators each configured to respectively compare said second checksum to different ones of said plurality of first checksums.
18. The apparatus according to claim 17 wherein at least two of said plurality of first checksums have different lengths.
19. The apparatus according to claim 17 wherein said checksum generator comprises a plurality of checksum sub-generators.
20. The apparatus according to claim 13 wherein said processor is configured to shift more data from said data stream into said register if said comparator does not detect a match; and, said checksum generator is configured to recompute said second checksum by removing an oldest unit of data from said second checksum recomputation and adding said more data to said recomputation.
21. A method of searching through packets of data traffic within a data stream to identify the nature of the traffic in support of a switching decision based on traffic content, comprising the steps of:
computing a plurality of character patterns associated with the traffic content, where a first character pattern has a first length and second character pattern has a second length, and the first length is not equal to the second length;
computing a first checksum for each said character pattern, wherein each said character pattern has a length;
shifting a byte of data from said data stream into a register;
computing a second checksum for said byte of said data stream;
continuing said shifting and computing of the second checksum until a length of said shifted bytes of data is equal to said length of at least one of said character patterns;
comparing said second checksum to each said first checksum having a pattern of equal length to determine if a match exists;
shifting another byte of data from said data stream into said register if said comparison does not result in a match; and
recomputing said second checksum by removing an oldest byte of data from said second checksum recomputation and adding said another byte of data to said recomputation;
comparing said recomputed checksum to each said checksum to determine if a match exist;
continuing said shifting another byte, said recomputing, and said comparing until a match exists, a match being indicative of a probability that the data stream includes traffic content associated with the character pattern, and
if there is a match, computing a switching decision based at least in-part on the traffic content.
22. Apparatus that searches through packets of data traffic of a data stream to identify the nature of the traffic in support of a switching decision based on traffic content, comprising:
logic operable to compute a plurality of character patterns associated with the traffic content, where a first character pattern has a first length and a second character pattern has a second length, and the first length is not equal to the second length;
register means for temporarily storing a portion of said data stream;
processor means, electrically coupled to said register means, for copying said portion of said data stream into said register means;
checksum generator means for computing a first checksum for each said character pattern and for computing a second checksum for said portion of said data stream;
comparison means coupled to said checksum generator means for comparing said second checksum to each said first checksum to determine if a match exists, a match being indicative of a probability that the data stream includes traffic content associated with the character pattern; and
logic operable in response to a match to computing a switching decision based at least in-part on the traffic content.