US7619983B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Parse state encoding for a packet parsing processor
Assignee: Cisco Technology Inc
•
Filing: 2004-08-25
•
Granted: 2009-11-17
•
Expires: 2024-08-25
Abstract
Abstract The present invention provides a packet processing device and method. A parsing processor provides instruction-driven content inspection of network packets at 10-Gbps and above with a parsing engine that executes parsing instructions. A flow state unit maintains statefulness of packet flows to allow content inspection across several related network packets. A state-graph unit traces state-graph nodes to keyword indications and/or parsing instructions. The parsing instructions can be derived from a high-level application to emulate user-friendly parsing logic. The parsing processor sends parsed packets to a network processor unit for further processing.
Inventors
- 👤 Rina Panigrahy
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 13:29
CPC Classifications
H; H04; H04L; H04L63/00; H04L63/02; H04L63/0227; H04L63/0254; H04L63/14; H04L63/1408; H04L69/00; H04L69/22
Claims Analysis
Total Claims: 51
Claim 1
Independent Claim
117 words
A method of encoding packet parsing states into bitmaps for determining next packet parsing states from current packet parsing states in a packet parsing processor, the method comprising: grouping a set of potential characters into subsets; representing each subset that contains one or more potential characters capable of causing a transition from a current packet parsing state to one or more next packet parsing states responsive to data related to a network packet with a bit in a current state bitmap indicative of the transition; storing the current state bitmap at a memory location representative of the current packet parsing state; and representing the one or more next packet parsing states with a plurality of memory locations.
Claim 2
Independent Claim
117 words
A method of encoding packet parsing states into bitmaps for determining next packet parsing states from current packet parsing states in a packet parsing processor, the method comprising: grouping a set of potential characters into subsets; representing each subset that contains one or more potential characters capable of causing a transition from a current packet parsing state to one or more next packet parsing states responsive to data related to a network packet with a bit in a current state bitmap indicative of the transition; storing the current state bitmap at a memory location representative of the current packet parsing state; and representing the one or more next packet parsing states with a plurality of memory locations.
Claim 3
Dependent Claim
33 words
The method of claim 1 , further comprising: representing each subset that does not contain the one or more potential characters with a bit in the current state bitmap indicative of no transition.
Claim 4
Dependent Claim
29 words
The method of claim 1 , further comprising: determining that more than a threshold amount of the one or more potential characters exist for the current packet parsing state.
Claim 5
Dependent Claim
52 words
The method of claim 3 , further comprising: determining that less than a threshold amount of the one or more potential characters exist for the current packet parsing state; and encoding the current state bitmap with the one or more next packet parsing states corresponding to the one or more potential characters.
Claim 6
Dependent Claim
14 words
The method of claim 1 , wherein the set of characters comprises ASCII characters.
Claim 7
Dependent Claim
26 words
The method of claim 5 , further comprising: setting a bit to indicate that the current state bitmap corresponds to a first subset of ASCII characters.
Claim 8
Dependent Claim
19 words
The method of claim 6 , wherein the first subset of ASCII characters comprises a first 128 ASCII characters.
Claim 9
Dependent Claim
29 words
The method of claim 5 , further comprising: setting a bit to indicate that the current state bitmap corresponds to a second subset comprising a second 128 ASCII characters.
Claim 10
Dependent Claim
55 words
The method of claim 1 , further comprising: receiving character data from a byte stream capable of spanning a plurality of related network packets; receiving the current state bitmap; and determining a next packet parsing state based on the current packet parsing state, the character data, and a corresponding bit in the current state bitmap.
Claim 11
Dependent Claim
24 words
The method of claim 1 , further comprising: storing a next state bitmap at a memory location representative of a next packet parsing state.
Claim 12
Dependent Claim
31 words
The method of claim 1 , further comprising: storing a parsing instruction for instruction-driven packet parsing of the network packet at the memory location representative of the next packet parsing state.
Claim 13
Dependent Claim
28 words
The method of claim 1 , wherein the bit indicative of the transition comprises a logical “1” and the bit indicative of no transition comprises a logical “0”.
Claim 14
Dependent Claim
45 words
The method of claim 1 , wherein the packet parsing processor is contained within a network device, coupled to a network operating at 10-Gbps or above, the network device performing one from the group containing: data packet routing, data packet forwarding, and data packet bridging.
Claim 15
Dependent Claim
29 words
The method of claim 1 , wherein the packet parsing supports one from the group containing: intrusion detection, quality of service, application recognition, virus detection, and an application-level firewall.
Claim 16
Dependent Claim
121 words
A packet parsing processor having a memory comprising bitmaps for determining next packet parsing states from current packet parsing states in a packet parsing processor, the memory comprising: a current state bitmap comprising bit fields capable of indicating a transition for each subset of a set of potential characters that contains one or more potential characters capable of causing the transition from the current packet parsing state to one or more next packet parsing states responsive to data related to a network packet; and a state-graph having a node at a memory location representative of the current packet parsing state and a plurality of nodes at a plurality of memory locations representative of the one or more next packet parsing states.
Claim 17
Dependent Claim
121 words
A packet parsing processor having a memory comprising bitmaps for determining next packet parsing states from current packet parsing states in a packet parsing processor, the memory comprising: a current state bitmap comprising bit fields capable of indicating a transition for each subset of a set of potential characters that contains one or more potential characters capable of causing the transition from the current packet parsing state to one or more next packet parsing states responsive to data related to a network packet; and a state-graph having a node at a memory location representative of the current packet parsing state and a plurality of nodes at a plurality of memory locations representative of the one or more next packet parsing states.
Claim 18
Dependent Claim
31 words
The packet parsing processor of claim 15 , wherein the bit fields are capable of indicating no transition for each subset that does not contain the one or more potential characters.
Claim 19
Dependent Claim
72 words
The packet parsing processor of claim 15 , wherein if more than a threshold amount of the one or more potential characters, the bit fields being capable of indicating each subset of the set of potential characters that contains the one or more potential characters capable for causing the transition from the current packet parsing state to one or more next packet parsing states responsive to data related to the network packet.
Claim 20
Dependent Claim
36 words
The packet parsing processor of claim 16 , wherein if less than a threshold amount of the one or more potential characters, the bit fields storing bits representing the one or more next packet parsing states.
Claim 21
Dependent Claim
16 words
The packet parsing processor of claim 15 , wherein the set of characters comprises ASCII characters.
Claim 22
Dependent Claim
29 words
The packet parsing processor of claim 19 , further comprising: a subset field capable of indicating that the current state bitmap corresponds to a first subset of ASCII characters.
Claim 23
Dependent Claim
21 words
The packet parsing processor of claim 20 , wherein the first subset of ASCII characters comprises a first 128 ASCII characters.
Claim 24
Dependent Claim
32 words
The packet parsing processor of claim 19 , further comprising a subset field capable of indicating that the current state bitmap corresponds to a second subset comprising a second 128 ASCII characters.
Claim 25
Dependent Claim
64 words
The packet parsing processor of claim 15 , further comprising: a parsing engine, having an input/output coupled to an input/output of the memory, the parsing engine determining the next packet parsing state based on the current packet parsing state, character data from a byte stream capable of spanning a plurality of related network packets, and a corresponding bit field in the current state bitmap.
Claim 26
Dependent Claim
27 words
The packet parsing processor of claim 15 , wherein the state-graph stores a next state bitmaps at a memory location representative of a next packet parsing state.
Claim 27
Dependent Claim
34 words
The packet parsing processor of claim 15 , wherein the state-graph stores a parsing instruction for instruction-driven packet parsing of the network packet at a memory location representative of a next packet parsing state.
Claim 28
Dependent Claim
47 words
The packet parsing processor of claim 15 , wherein the packet parsing processor is contained within a network device, coupled to a network operating at 10-Gbps or above, the network device performing one from the group containing: data packet routing, data packet forwarding, and data packet bridging.
Claim 29
Dependent Claim
31 words
The packet parsing processor of claim 15 , wherein the packet parsing supports one from the group containing: intrusion detection, quality of service, application recognition, virus detection, and an application-level firewall.
Claim 30
Dependent Claim
134 words
A packet parsing processor having a memory comprising bitmaps for determining next packet parsing states from current packet parsing states in a packet parsing processor, the memory comprising: means for mapping a current state comprising means for individually mapping each subset, of a set of potential characters, that contains one or more potential characters capable of causing a transition from a current packet parsing state to one or more next packet parsing states responsive to data related to a network packet with a bit in the means for mapping the current state indicative of the transition; means for state-graphing having a node at a memory location representative of the current packet parsing state and a plurality of nodes at a plurality of memory locations representative of the one or more next packet parsing states.
Claim 31
Dependent Claim
134 words
A packet parsing processor having a memory comprising bitmaps for determining next packet parsing states from current packet parsing states in a packet parsing processor, the memory comprising: means for mapping a current state comprising means for individually mapping each subset, of a set of potential characters, that contains one or more potential characters capable of causing a transition from a current packet parsing state to one or more next packet parsing states responsive to data related to a network packet with a bit in the means for mapping the current state indicative of the transition; means for state-graphing having a node at a memory location representative of the current packet parsing state and a plurality of nodes at a plurality of memory locations representative of the one or more next packet parsing states.
Claim 32
Dependent Claim
39 words
The packet parsing processor of claim 28 , wherein the means for individually mapping represents each subset that does not contain the one or more potential characters with a bit in the means for mapping indicative of no transition.
Claim 33
Dependent Claim
71 words
The packet parsing processor of claim 28 , wherein if more than a threshold amount of the one or more potential characters, the means for individually mapping indicating each subset of the set of potential characters that contains one or more potential characters capable of causing the transition from the current packet parsing state to the one or more next packet parsing states responsive to data related to the network packet.
Claim 34
Dependent Claim
43 words
The packet parsing processor of claim 30 , wherein the means for individually mapping comprises, if less that a threshold amount of the one or more potential characters, the means for individually mapping storing bits representing the one or more next packet states.
Claim 35
Dependent Claim
17 words
The packet parsing processor of claim 28 , wherein the set of characters camp rises ASCII characters.
Claim 36
Dependent Claim
65 words
The packet parsing processor of claim 28 , further comprising a means for executing, coupled to the memory, the means for executing determining a next packet parsing state based on the current packet parsing state, character data from a byte stream capable of spanning a plurality of elated network packets, and a corresponding means for individually mapping in the means for mapping the current state.
Claim 37
Dependent Claim
33 words
The packet parsing processor of claim 28 , wherein the means for storing comprises storing a means for mapping a next state at a memory location representative of a next packet parsing state.
Claim 38
Dependent Claim
37 words
The packet parsing processor of claim 28 , wherein the means for storing comprises storing a parsing instruction for instruction-driven packet parsing of the network packet at the memory location representative of the next packet parsing state.
Claim 39
Dependent Claim
30 words
The packet parsing processor of claim 28 , wherein the bit indicative of the transition comprises a logical “1” and the bit indicative of no transition comprises a logical “0.”
Claim 40
Dependent Claim
134 words
A computer program product, comprising a computer-readable medium having computer program instructions and data embodied thereon for a method of encoding packet parsing states into bitmaps for determining next packet parsing states from current packet parsing states in a packet parsing processor, the method comprising: grouping a set of potential characters into subsets; representing each subset that contains one or more potential characters capable of causing a transition from a current packet parsing state to one or more next packet parsing states responsive to data related to a network packet with a bit in a current state bitmap indicative of the transition; storing the current state bitmap at a memory location representative of the current packet parsing state; and representing the one or more next packet parsing states with a plurality of memory locations.
Claim 41
Dependent Claim
134 words
A computer program product, comprising a computer-readable medium having computer program instructions and data embodied thereon for a method of encoding packet parsing states into bitmaps for determining next packet parsing states from current packet parsing states in a packet parsing processor, the method comprising: grouping a set of potential characters into subsets; representing each subset that contains one or more potential characters capable of causing a transition from a current packet parsing state to one or more next packet parsing states responsive to data related to a network packet with a bit in a current state bitmap indicative of the transition; storing the current state bitmap at a memory location representative of the current packet parsing state; and representing the one or more next packet parsing states with a plurality of memory locations.
Claim 42
Dependent Claim
35 words
The computer program product of claim 37 , further comprising: representing each subset that does not contain the one or more potential characters with a bit in the current state bitmap indicative of no transition.
Claim 43
Dependent Claim
31 words
The computer program product of claim 37 , further comprising: determining that more than a threshold amount of the one or more potential characters exist for the current packet parsing state.
Claim 44
Dependent Claim
54 words
The computer program product of claim 39 , further comprising: determining that less than a threshold amount of the one or more potential characters exist for the current packet parsing state; and encoding the current state bitmap with the one or more next packet parsing states corresponding to the one or more potential characters.
Claim 45
Dependent Claim
16 words
The computer program product of claim 37 , wherein the set of characters comprises ASCII characters.
Claim 46
Dependent Claim
57 words
The computer program product of claim 37 , further comprising: receiving character data from a byte stream capable of spanning a plurality of related network packets; receiving the current state bitmap; and determining a next packet parsing state based on the current packet parsing state, the character data, and a corresponding bit in the current state bitmap.
Claim 47
Dependent Claim
26 words
The computer program product of claim 37 , further comprising: storing a next state bitmap at a memory location representative of a next packet parsing state.
Claim 48
Dependent Claim
33 words
The computer program product of claim 37 , further comprising: storing a parsing instruction for instruction-driven packet parsing of the network packet at the memory location representative of the next packet parsing state.
Claim 49
Dependent Claim
30 words
The computer program product of claim 37 , wherein the bit indicative of the transition comprises a logical “1” and the bit indicative of no transition comprises a logical “0.”
Claim 50
Dependent Claim
122 words
A network device comprising a processor, a memory and bitmaps for determining next packet parsing states from current packet parsing states in a packet parsing processor, the memory comprising: a current state bitmap comprising bit fields capable of indicating a transition for each subset of a set of potential characters that contains one or more potential characters capable of causing the transition from the current packet parsing state to one or more next packet parsing states responsive to data related to a network packet; and a state-graph having a node at a memory location representative of the current packet parsing state and a plurality of nodes at a plurality of memory locations representative of the one or more next packet parsing states.
Claim 51
Dependent Claim
122 words
A network device comprising a processor, a memory and bitmaps for determining next packet parsing states from current packet parsing states in a packet parsing processor, the memory comprising: a current state bitmap comprising bit fields capable of indicating a transition for each subset of a set of potential characters that contains one or more potential characters capable of causing the transition from the current packet parsing state to one or more next packet parsing states responsive to data related to a network packet; and a state-graph having a node at a memory location representative of the current packet parsing state and a plurality of nodes at a plurality of memory locations representative of the one or more next packet parsing states.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2012-11-16 | 2013-05-18 | 2013-11-17 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2016-11-16 | 2017-05-18 | 2017-11-17 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2020-11-16 | 2021-05-18 | 2021-11-17 | $7700.00 | Window Closed / Lapsed |