Importance

Loading Importance Indicators...

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.

Loading the Abstract Image...

First Claim