Hierarchical pattern matching for deep packet analysis
First Claim
1. An apparatus, comprising:
- a first content addressable memory (CAM) storing a substring of a string of a regular expression as a plurality of bits that are individually searchable;
a memory comprising executable instructions; and
one or more processors coupled to the memory wherein the one or more processors execute the instructions to;
receive a data packet comprising a plurality of bits;
search the received data packet at a first hierarchical level using, at least in part, the first CAM and compare in parallel the plurality of bits of the received data packet to the plurality of bits of the substring to determine whether the substring of the string of the regular expression exists in the received data packet;
search the received data packet at a second hierarchical level when the search of the received data packet at the first hierarchical level finds a match, to determine whether the string of the regular expression exists in the received data packet; and
transmit the received data packet to a next network element along an original path of the received data packet without searching the received data packet at a third hierarchical level when the search of the received data packet at the first or second hierarchical level does not find a match.
1 Assignment
0 Petitions
Accused Products
Abstract
A method comprising receiving, by a network element, a data packet, searching, by the network element, the received data packet at a first hierarchical level to determine whether a substring of a string of a regular expression exists in the received data packet, searching, by the network element when the search of the received data packet at the first hierarchical level finds a match, the received data packet at a second hierarchical level to determine whether the string of the regular expression exists in the received data packet, and transmitting, by the network element, the received data packet to a next network element along an original path of the received data packet without searching the received data packet at a third hierarchical level when the search of the received data packet at the first or second hierarchical level does not find a match.
-
Citations
16 Claims
-
1. An apparatus, comprising:
-
a first content addressable memory (CAM) storing a substring of a string of a regular expression as a plurality of bits that are individually searchable; a memory comprising executable instructions; and one or more processors coupled to the memory wherein the one or more processors execute the instructions to; receive a data packet comprising a plurality of bits; search the received data packet at a first hierarchical level using, at least in part, the first CAM and compare in parallel the plurality of bits of the received data packet to the plurality of bits of the substring to determine whether the substring of the string of the regular expression exists in the received data packet; search the received data packet at a second hierarchical level when the search of the received data packet at the first hierarchical level finds a match, to determine whether the string of the regular expression exists in the received data packet; and transmit the received data packet to a next network element along an original path of the received data packet without searching the received data packet at a third hierarchical level when the search of the received data packet at the first or second hierarchical level does not find a match. - View Dependent Claims (2, 3, 4)
-
-
5. An apparatus, comprising:
-
a first binary content addressable memory (BCAM) configured to search for a substring of a string of a regular expression in a received data packet; a second BCAM configured to search for the string in the received data packet when the substring is found in the received data packet; a first processor programmed to search for the regular expression in the received data packet when the string is found in the received data packet; and a second processor programmed to; schedule the received data packet for analysis by the second BCAM when the first BCAM determines that the substring is found in the received data packet, and transmit the received data packet according to a bypass path that bypasses the second BCAM and the first processor when the first BCAM determines that the substring is not found in the received data packet. - View Dependent Claims (6, 7, 8, 9, 10)
-
-
11. A method, comprising:
-
receiving, by a network element, a data packet comprising a plurality of bits; searching, by the network element, the received data packet at a first hierarchical level using, at least in part, a first content addressable memory (CAM) storing a substring of a string of a regular expression as a plurality of bits that are individually searchable and comparing in parallel the plurality of bits of the received data packet to the plurality of bits of the substring to determine whether the substring of the string of the regular expression exists in the received data packet; searching, by the network element the received data packet at a second hierarchical level when the search of the received data packet at the first hierarchical level finds a match, to determine whether the string of the regular expression exists in the received data packet; and transmitting, by the network element, the received data packet to a next network element along an original path of the received data packet without searching the received data packet at a third hierarchical level when the search of the received data packet at the first or second hierarchical level does not find a match. - View Dependent Claims (12, 13, 14, 15, 16)
-
Specification