# US 2012/0084245 A1 · Positionally dependent pattern checking in character strings using deterministic finite automata

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2012/0084245 A1
- Document ID: US20120084245A1
- Status: Published application
- Kind: A1
- Application number: 13/252,776
- Filed: 2011-10-04
- Published: 2012-04-05
- Earliest claimed: 2006-09-01
- Assignees: Hewlett-Packard Development Company, L.P.
- Inventors: David Law; Peter Furlong; Eugene O'Neill; Kevin Loughran
- Web page: https://patentgrep.com/patent/US20120084245A1

## CPC

- H04L 45/742: {Route cache; Operation thereof}
- H04L 69/22: Parsing or analysis of headers
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

An apparatus including logic to receive a data packet comprising a string of characters, said apparatus having a plurality of states and at least one state for every character position in the string of characters; logic to examine the string of characters for matches with a plurality of predefined values, beginning with an initial character; and logic to execute forward exit transitions from any of the plurality of states based upon the examination of the characters, wherein a current state of the apparatus represents a count of a number of characters from the initial character of the string of characters.

## Claims

### Claim at position 1

1-11. (canceled)

### Claim 12

A method comprising:
receiving, into an apparatus, a data packet comprising a string of characters, said apparatus comprising a plurality of states and at least one state for every character position in the string of characters;
examining the characters in the string of characters for matches with a plurality of predefined values, beginning with an initial character; and
executing forward exit transitions from any of the plurality of states based upon the examination of the characters, wherein a current state of the apparatus represents a count of a number of characters from the initial character of the string of characters.

### Claim 13 (depends on 12)

The method according to claim 12, wherein the apparatus further comprises an exit transition from a current state to another state for each character in the string of characters and wherein executing the forward exit transitions further comprises executing only forward exit transitions.

### Claim 14 (depends on 12)

The method according to claim 12, further comprising:
transitioning the apparatus into at least one match state that indicates that all of the characters in the string of characters match the plurality of predefined values, wherein the plurality of predefined values are defined by at least one rule.

### Claim 15 (depends on 12)

The method according to claim 12, wherein at least one of the states in the plurality of states has a single exit transition for a value of a respective character in the string of characters.

### Claim 16 (depends on 12)

The method according to claim 12, wherein at least some of the states in the plurality of states define an exit transition to a state indicating a “no match” state.

### Claim 17 (depends on 16)

The method according to claim 16, further comprising:
ceasing examination of the string of characters in response to an exit transition to the “no match” state being reached.

### Claim 18 (depends on 12)

The method according to claim 12, wherein at least one of the states in the plurality of states has a first exit transition to a first different state prescribed for a particular value of a respective character in the string of characters and a second exit transition, to a second different state, prescribed for any value of the character other than the particular value.

### Claim 19 (depends on 12)

The method according to claim 12, wherein the characters in the string of characters are in a header of an addressed data packet, the header comprising a succession of fields, each comprising at least one character.

### Claim 20 (depends on 12)

The method according to claim 12, wherein each character of the string of characters consists of one byte.

### Claim 21 (depends on 12)

The method according to claim 12, wherein the apparatus comprises a dual table finite state machine comprising further states that indicate whether a complete match for the string of characters has been detected and wherein the plurality of states and the further states are represented in a random access memory that is partitioned such that the states in the plurality of states and the further states are respectively grouped within respective ranges of the memory.

### Claim 22 (depends on 21)

The method according to claim 21, wherein the plurality of states comprise at least one “no match” state indicating the absence of a match for the string of characters and wherein the “no match” state is represented within a respective range of the memory.

### Claim 23

An apparatus comprising:
logic to receive a data packet comprising a string of characters, said apparatus having a plurality of states and at least one state for every character position in the string of characters;
logic to examine the string of characters for matches with a plurality of predefined values, beginning with an initial character; and
logic to execute forward exit transitions from any of the plurality of states based upon the examination of the characters, wherein a current state of the apparatus represents a count of a number of characters from the initial character of the string of characters.

### Claim 24 (depends on 23)

The apparatus of claim 23, further comprising:
logic to transition the apparatus into at least one match state that indicates that all of the characters in the string of characters match the plurality of predefined values, wherein the plurality of predefined values are defined by at least one rule.

### Claim 25 (depends on 23)

The apparatus of claim 23, wherein at least one of the states in the plurality of states has a single exit transition for a value of a respective character in the string of characters.

### Claim 26 (depends on 23)

The apparatus of claim 23, wherein at least some of the states in the plurality of states each define an exit transition to a state indicating a “no match” state.

### Claim 27 (depends on 26)

The apparatus of claim 26, further comprising:
logic to cease examination of the string of characters in response to an exit transition to the “no match” state being reached.

### Claim 28 (depends on 23)

The apparatus of claim 23, wherein at least one of the states in the plurality of states has a first exit transition to a first different state prescribed for a particular value of a respective character in the string of characters and a second exit transition, to a second different state, prescribed for any value of the character other than the particular value.

### Claim 29 (depends on 23)

The apparatus of claim 23, wherein the characters in the string of characters are in a header of an addressed data packet, the header comprising a succession of fields each comprising at least one character.

### Claim 30 (depends on 23)

The apparatus of claim 23, wherein the apparatus comprises a dual table finite state machine comprising further states that indicate whether a complete match for the string of characters has been detected and wherein the plurality of states and the further states are represented in a random access memory that is partitioned such that the states in the plurality of states and the further states are respectively grouped within respective ranges of the memory.

### Claim 31 (depends on 30)

The apparatus according to claim 30, wherein the plurality of states comprise at least one “no match” state indicating the absence of a match for the string of characters and wherein the “no match” state is represented within a respective range of the memory.
