Jumping window based fast pattern matching method with sequential partial matches using TCAM
| Title: | Jumping window based fast pattern matching method with sequential partial matches using TCAM |
|---|---|
| Document Number: | 20080050469 |
| Publication Date: | February 28, 2008 |
| Appl. No: | 11/508474 |
| Application Filed: | August 23, 2006 |
| Abstract: | A jumping window based fast pattern matching method using TCAM includes TCAM entries containing all possible sub-patterns independent of position. Due to these sub-patterns, the method can search for all patterns appearing within the window at once. If a match is not found, the method jumps to the next window (shift size of M bytes), opposed to the sliding window method that shifts to the next byte (shift size of 1 byte). This incurs a pattern match that is M times faster, despite requiring a larger TCAM size to be able to represent all possible redundant sub-patterns in the TCAM; here, M is the size of a jumping window. In addition, the present invention employs a two-phase pattern matching sequence for a large number of long patterns such as virus and worm signatures. In the first phase, the fixed prefix will be searched with TCAM; then, only the CRC value for the remaining pattern is examined to confirm the existence of the entire pattern. Since the TCAM only stores the prefixes of the patterns instead of storing entire long patterns, a smaller TCAM size is sufficient to match the large number of long patterns at link-speed of the high-speed Internet. |
| Inventors: | Kwon, Taeck-Geun (Youseong-Gu, KR); Kang, Seok-Min (Youseong-Gu, KR); Song, Il-Seop (Youseong-Gu, KR) |
| Assignees: | The Industry & Academic Cooperation in Chungnam National University (Youseong-gu, KR) |
| Claim: | 1. A fast method of pattern matching using TCAM, comprising of: a method to represent all possible sub-patterns to match the pattern independent of the position that the pattern appears in; a method to jump to the next window for matching the next sub-patterns using TCAM; a method to represent state information with a unique identifier in order to manage the series of sub-pattern matches in the sequence; and a method to make search keys for TCAM entries by concatenating both state information and sub-pattern. |
| Claim: | 2. A method of pattern matching for a large number of long patterns, comprising of: a method to split long patterns into the prefix and the suffix of the pattern, and to match the prefix using TCAM and to match the suffix using the CRC value; and a method to fix the starting suffix using ‘shift’ values in the associated data, as shown in FIG. 14. |
| Current U.S. Class: | 426/23 |
| Current International Class: | 21 |
| Accession Number: | edspap.20080050469 |
| Database: | USPTO Patent Applications |
| FullText | Text: Availability: 0 CustomLinks: – Url: https://ppubs.uspto.gov/pubwebapp/external.html?q=(%2220080050469%22).pn.&db=US-PGPUB&type=ids Name: EDS - USPTO Patent Applications Category: fullText Text: View record from USPTO MouseOverText: View record from USPTO – Url: https://resolver.ebsco.com/c/xy5jbn/result?sid=EBSCO:edspap&genre=article&issn=&ISBN=&volume=&issue=&date=20080228&spage=&pages=&title=Jumping window based fast pattern matching method with sequential partial matches using TCAM&atitle=Jumping%20window%20based%20fast%20pattern%20matching%20method%20with%20sequential%20partial%20matches%20using%20TCAM&aulast=Kwon%2C%20Taeck-Geun&id=DOI: Name: Full Text Finder (for New FTF UI) (s8985755) Category: fullText Text: Find It @ SCU Libraries MouseOverText: Find It @ SCU Libraries |
|---|---|
| Header | DbId: edspap DbLabel: USPTO Patent Applications An: edspap.20080050469 RelevancyScore: 718 AccessLevel: 3 PubType: Patent PubTypeId: patent PreciseRelevancyScore: 717.869506835938 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Jumping window based fast pattern matching method with sequential partial matches using TCAM – Name: DocumentID Label: Document Number Group: Patent Data: 20080050469 – Name: DateEntry Label: Publication Date Group: Patent Data: February 28, 2008 – Name: DocumentID Label: Appl. No Group: Patent Data: 11/508474 – Name: DateFiled Label: Application Filed Group: Patent Data: August 23, 2006 – Name: Abstract Label: Abstract Group: Ab Data: A jumping window based fast pattern matching method using TCAM includes TCAM entries containing all possible sub-patterns independent of position. Due to these sub-patterns, the method can search for all patterns appearing within the window at once. If a match is not found, the method jumps to the next window (shift size of M bytes), opposed to the sliding window method that shifts to the next byte (shift size of 1 byte). This incurs a pattern match that is M times faster, despite requiring a larger TCAM size to be able to represent all possible redundant sub-patterns in the TCAM; here, M is the size of a jumping window. In addition, the present invention employs a two-phase pattern matching sequence for a large number of long patterns such as virus and worm signatures. In the first phase, the fixed prefix will be searched with TCAM; then, only the CRC value for the remaining pattern is examined to confirm the existence of the entire pattern. Since the TCAM only stores the prefixes of the patterns instead of storing entire long patterns, a smaller TCAM size is sufficient to match the large number of long patterns at link-speed of the high-speed Internet. – Name: Author Label: Inventors Group: Patent Data: <searchLink fieldCode="ZA" term="%22Kwon%2C+Taeck-Geun%22">Kwon, Taeck-Geun</searchLink> (Youseong-Gu, KR); <searchLink fieldCode="ZA" term="%22Kang%2C+Seok-Min%22">Kang, Seok-Min</searchLink> (Youseong-Gu, KR); <searchLink fieldCode="ZA" term="%22Song%2C+Il-Seop%22">Song, Il-Seop</searchLink> (Youseong-Gu, KR) – Name: OtherAuthors Label: Assignees Group: Patent Data: <searchLink fieldCode="ZS" term="%22The+Industry+%26+Academic+Cooperation+in+Chungnam+National+University%22">The Industry & Academic Cooperation in Chungnam National University</searchLink> (Youseong-gu, KR) – Name: Comment Label: Claim Group: Patent Data: 1. A fast method of pattern matching using TCAM, comprising of: a method to represent all possible sub-patterns to match the pattern independent of the position that the pattern appears in; a method to jump to the next window for matching the next sub-patterns using TCAM; a method to represent state information with a unique identifier in order to manage the series of sub-pattern matches in the sequence; and a method to make search keys for TCAM entries by concatenating both state information and sub-pattern. – Name: Comment Label: Claim Group: Patent Data: 2. A method of pattern matching for a large number of long patterns, comprising of: a method to split long patterns into the prefix and the suffix of the pattern, and to match the prefix using TCAM and to match the suffix using the CRC value; and a method to fix the starting suffix using ‘shift’ values in the associated data, as shown in FIG. 14. – Name: CodeClass Label: Current U.S. Class Group: Patent Data: 426/23 – Name: CodeClass Label: Current International Class Group: Patent Data: 21 – Name: AN Label: Accession Number Group: ID Data: edspap.20080050469 |
| PLink | https://login.libproxy.scu.edu/login?url=https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&scope=site&db=edspap&AN=edspap.20080050469 |
| RecordInfo | BibRecord: BibEntity: Languages: – Text: English Titles: – TitleFull: Jumping window based fast pattern matching method with sequential partial matches using TCAM Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Kwon, Taeck-Geun – PersonEntity: Name: NameFull: Kang, Seok-Min – PersonEntity: Name: NameFull: Song, Il-Seop IsPartOfRelationships: – BibEntity: Dates: – D: 28 M: 02 Text: February 28, 2008 Type: published Y: 2008 |
| ResultId | 1 |