State processor for pattern matching in a network monitor device
DC
First Claim
Patent Images
1. A packet monitor for examining all packets passing through a connection point on a computer network, the monitor comprising:
- (a) a packet acquisition device coupled to the connection point and configured to receive packets passing through the connection point; and
(b) a memory for storing a database comprising none or more flow-entries for previously encountered conversational flows to which a received packet may belong;
(c) a lookup engine coupled to the packet acquisition device configured to lookup whether a received packet belongs to a flow in the flow-entry database, and to determine the state of the flow for the received packet in the case that the packet belongs to a flow-entry;
(d) a state determining mechanism coupled to the lookup engine to determine the state of a flow in the case that the received packet does not belong to a flow in the flow-entry database, and (e) a state processor coupled to the lookup engine and to the state determining mechanism configured to perform any state operations specified for the state of the flow starting from the last encountered state of the flow in the case that the packet is from an existing flow, and to perform any state operations required for the initial state of the new flow in the case that the packet is from an existing flow.
5 Assignments
Litigations
0 Petitions
Accused Products
Abstract
A processor for processing contents of packets passing through a connection point on a computer network. The processor includes a searching apparatus having one or more comparators for searching for a reference string in the contents of a packet, and processes contents of all packets passing through the connection point in real time. In one implementation, the processor is programmable and has an instruction set that includes an instruction for invoking the searching apparatus to search for a specified reference string in the packet starting at an unknown location within a range of the packet.
235 Citations
22 Claims
-
1. A packet monitor for examining all packets passing through a connection point on a computer network, the monitor comprising:
-
(a) a packet acquisition device coupled to the connection point and configured to receive packets passing through the connection point; and
(b) a memory for storing a database comprising none or more flow-entries for previously encountered conversational flows to which a received packet may belong;
(c) a lookup engine coupled to the packet acquisition device configured to lookup whether a received packet belongs to a flow in the flow-entry database, and to determine the state of the flow for the received packet in the case that the packet belongs to a flow-entry;
(d) a state determining mechanism coupled to the lookup engine to determine the state of a flow in the case that the received packet does not belong to a flow in the flow-entry database, and (e) a state processor coupled to the lookup engine and to the state determining mechanism configured to perform any state operations specified for the state of the flow starting from the last encountered state of the flow in the case that the packet is from an existing flow, and to perform any state operations required for the initial state of the new flow in the case that the packet is from an existing flow. - View Dependent Claims (2, 3, 4, 5, 6)
(i) a first reference register configured to receive the NR units of a first reference string;
(ii) one or more target data registers coupled in series and coupled to the buffer, the target data registers configured to receive contents from the buffer; and
(iii) a first plurality of comparator sets, one comparator set corresponding to each of a set of starting positions in the target data registers, the comparator set of a particular starting position coupled to each unit of the first reference register and to NR units of the target data registers starting from the particular starting position and comparing the first reference register contents to corresponding contents of NR contiguous units of the target data registers starting from the particular starting position, such that each comparator set indicates if there is a match of the first reference string in the target data starting from its corresponding different starting position, whereby the first plurality of comparator sets indicates in parallel if the first reference string is contained in the target data registers starting at any of the starting positions.
-
-
7. A searching apparatus configured to search for a reference string of NR units in target data starting from any of a set of starting positions within the target data, the searching apparatus comprising:
-
(a) a first reference register configured to receive the NR units of a first reference string;
(b) one or more target data registers coupled in series to receive the target data; and
(c) a first plurality of comparator sets, one comparator set corresponding to each of the starting positions, the comparator set of a particular starting position coupled to each unit of the first reference register and to NR units of the target data registers starting from the particular starting position and comparing the first reference register contents to corresponding contents of NR contiguous units of the target data registers starting from the particular starting position, such that each comparator set indicates if there is a match of the first reference string in the target data starting from its corresponding different starting position, whereby the first plurality of comparator sets indicates in parallel if the first reference string is contained in the target data registers starting at any of the starting positions. - View Dependent Claims (8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19)
whereby in one or more clock cycles, the searching apparatus indicates if the first reference string is in the target data starting anywhere other than the first Noffset units.
-
-
12. A searching apparatus according to claim 8, wherein NR is 16 bytes and wherein each of the data registers has Nstart bytes, such that the searching apparatus indicates a match starting anywhere within the first data register.
-
13. A searching apparatus according to claim 7, wherein each comparator set includes NR consecutive comparators, each comparator having a reference unit input, a target unit input, and an output indicating a match, each comparator coupled to the previous comparator'"'"'s output such that the output of a comparator is asserted when the reference and target data inputs match and the previous comparator'"'"'s output indicates a match.
-
14. A searching apparatus according to claim 7, further comprising:
-
(d) one or more further reference register for receiving NR units of one or more further reference strings; and
(e) one or more further pluralities of comparator sets, one comparator set for each of a corresponding plurality of starting positions, each particular comparator set of each further plurality coupled to each unit of the corresponding further reference register and to NR units of the data registers starting from the particular comparator set'"'"'s starting position and comparing the corresponding further reference register contents to NR units of the target data registers starting from the particular comparator set'"'"'s starting position, such that the searching apparatus searches for any one of the first or further reference strings of NR units in contents of the target registers starting from any of the starting positions.
-
-
15. A searching apparatus according to claim 14, wherein each comparator set includes NR consecutive comparators, each comparator having a reference unit input, a target data unit input, and an output indicating a match, each comparator coupled to the previous comparator'"'"'s output such that the output of a comparator is asserted when the reference and target data inputs match and the previous comparator'"'"'s output indicates a match.
-
16. A searching apparatus according to claim 7, wherein each comparator set includes NR consecutive comparators, each comparator having a reference unit input, a target data unit input, an enable input, and an output indicating a match, such that the match output of a comparator is asserted when the reference and target inputs match and the enable input is asserted,
wherein for a particular set of comparators for a particular starting position, the reference inputs of consecutive comparators are coupled to consecutive units of the reference register, the target data inputs of consecutive comparators are coupled to consecutive units of the target data registers starting at the particular starting location, the first comparator of the set is enabled, and the enable input of each comparator is coupled to the output of the previous comparator, such that the output of the final comparator is asserted when the NR units of the reference string and the NR units of the target data agree. -
17. A searching apparatus according to claim 16, wherein the final comparator outputs of the sets are coupled to a priority selector having an output indicating if and where a match of the reference string occurred in the target data.
-
18. A searching apparatus according to claim 7, wherein the unit is a byte.
-
19. A searching apparatus according to claim 18, wherein NR is 16 bytes.
-
20. A searching apparatus configured to search for a reference string of NR units in a target data stream, the apparatus comprising:
-
(a) a first NR unit comparator having NR pairs of inputs and an output indicating a match of each pair of the NR-pairs of inputs; and
(b) NR connections indicating values of the reference string and defining a first axis of a matrix, and NR connections indicating values of the target data defining a second axis of the matrix perpendicular to the first axis, the target data connections starting from a first starting location of the target data and ending at an ending location, wherein the first comparator is oriented along the diagonal of the matrix such that NR connections of the target data are compared to the NR reference string connections. - View Dependent Claims (21, 22)
additional one or more contiguous connections parallel and contiguous to the target data connections in the matrix and starting from the ending location; and
an additional NR-unit comparator for and corresponding to each of the additional target data connections, each additional comparators parallel to the first comparator and shifted towards the additional target connections in the matrix, such that each additional comparator compares the reference string to a different set of NR units continuous values of the target data starting from a different staring point.
-
-
22. A searching apparatus according to claim 21, further comprising:
-
one or more further sets of NR-unit comparators; and
further sets connections corresponding for the further sets of NR-unit comparators, the further connections defining one or more additional matrices, each further set of connections along the first axis indicating values of one or more corresponding further reference strings along the first axis, and NR connections indicating values of the target data along the second axis, such that each additional comparator set compares the corresponding one of the reference strings to a different set of NR contiguous values of the target data starting from a different staring point.
-
Specification
-
- Resources
Litigation Campaign Assessment
Thank you for your request. You will receive a custom alert email when the Litigation Campaign Assessment is available.
×
Litigation Data
-
Current AssigneePacket Intelligence LLC (Packet Intelligence Holdings LLC)
-
Original AssigneeHifn, Inc. (Maxlinear Incorporated)
-
InventorsSarkissian, Haig A., Dietz, Russell S., Koppenhaver, Andrew A.
-
Primary Examiner(s)Meky, Moustafa M.
-
Application NumberUS09/608,267Time in Patent Office1,530 DaysField of Search709/200, 709/201, 709/220, 709/223, 709/224, 709/231, 709/232, 709/236, 709/238, 709/239, 709/240, 709/246, 370/235, 370/392US Class Current709/224CPC Class CodesH04L 41/142 using statistical or mathem...H04L 41/5009 Determining service level p...H04L 43/00 Arrangements for monitoring...H04L 43/106 using time related informat...H04L 43/12 Network monitoring probesH04L 45/7453 using hashingH04L 49/101 using crossbar or matrixH04L 49/20 Support for servicesH04L 49/205 Quality of Service basedH04L 49/25 Routing or path finding in ...H04L 49/3009 Header conversion, routing ...H04L 69/16 Implementation or adaptatio...H04L 69/161 Implementation details of T...H04L 69/18 Multiprotocol handlers, e.g...H04L 69/22 Parsing or analysis of headersH04L 9/40 Network security protocols
