# US 7,613,775 B2 · Network message filtering using hashing and pattern matching

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

- Number: US 7,613,775 B2
- Document ID: US7613775B2
- Status: Granted
- Kind: B2
- Application number: 10/721,201
- Filed: 2003-11-25
- Published: 2005-05-26
- Granted: 2009-11-03
- Earliest claimed: 2003-11-25
- Assignees: Freescale Semiconductor, Inc.
- Inventors: Carlos A. Greaves; Harold M. Martin; Thang Q. Nguyen; Jose M. Nunez
- Web page: https://patentgrep.com/patent/US7613775B2

## CPC

- H04L 49/351: for local area network [LAN], e.g. Ethernet switches
- H04L 49/201: Multicast operation; Broadcast operation
- H04L 49/3018: {Input queuing}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

Hashing and pattern matching are used in an information processing system to process incoming messages from a network such as an Ethernet-based network. Using hashing and pattern matching increases the efficiency of message acceptance and rejection without increasing software-based processor tasks. A hash function and a pattern matching function are performed on a message received by an information processing system, and the message is selectively accepted based on at least one of a hash result and a pattern matching result. The incoming message can be searched for the existence of patterns and the absence of the patterns. The incoming message can be searched for the existence of multiple patterns. The results of pattern matching can be used not only for acceptance and rejection of messages, but also for other post-receipt tasks such as selective storage of incoming messages according to identified relative priorities or absolute criticality of messages having particular pattern matches.

## Claims

### Claim 1

In a packet controller having an input, hash logic, pattern matching logic coupled to the hash logic, and control logic coupled to the hash logic and the pattern matching logic, a method comprising:
receiving a message at an input of the packet controller;
providing the message to the hash logic which performs a hash function on the message to provide a hash result;
providing the message to the pattern matching logic which performs pattern matching on the message to provide a pattern match result, wherein performing pattern matching to provide the pattern match result comprises:
determining whether a pattern match exists within the received message based on pattern match data which indicates at least one pattern and pattern match control corresponding to the pattern match data, wherein the pattern match result indicates whether the pattern match exists, and wherein when the pattern match result indicates that the pattern match exists, the pattern match result further indicates whether the received message is one of accepted, rejected, and neither accepted nor rejected; and
the control logic selectively accepting the message based at least on the pattern match result.

### Claim 2 (depends on 1)

The method of claim 1, wherein receiving the message comprises receiving at least a portion of a packet.

### Claim 3 (depends on 2)

The method of claim 2, wherein the packet is further characterized as an Ethernet packet.

### Claim 4 (depends on 1)

The method of claim 1, wherein the message comprises a destination address and wherein performing the hash function on the message comprises performing the hash function on the destination address.

### Claim 5 (depends on 1)

The method of claim 1, wherein selectively accepting the message is based on the pattern match result and the hash result.

### Claim 6 (depends on 1)

The method of claim 1, wherein the hash result indicates whether the hash function resulted in a hash hit.

### Claim 7 (depends on 1)

The method of claim 1, wherein determining whether the pattern match exists is further based on a pattern match mask corresponding to the pattern match data.

### Claim 8 (depends on 1)

The method of claim 1, wherein the at least one pattern comprises a first predetermined pattern, and wherein the pattern match result indicates that the pattern match exists when the received message includes the first predetermined pattern.

### Claim 9 (depends on 8)

The method of claim 8, wherein the at least one pattern comprises a second predetermined pattern, and wherein the pattern match result indicates that the pattern match exists when the received message includes at least one of the first predetermined pattern and the second predetermined pattern.

### Claim 10 (depends on 9)

The method of claim 9, wherein when the received message includes at least one of the first predetermined pattern and the second predetermined pattern, the pattern match result further indicates whether the message having the at least one of the first predetermined pattern and the second predetermined pattern is one of accepted, rejected, and neither accepted nor rejected.

### Claim 11 (depends on 8)

The method of claim 8, wherein the at least one pattern comprises a second predetermined pattern, and wherein the pattern match result indicates that the pattern match exists when the received message includes the first predetermined pattern and the second predetermined pattern.

### Claim 12 (depends on 11)

The method of claim 11, wherein when the received message includes the first predetermined pattern and the second predetermined pattern, the pattern match result further indicates whether the message having the first predetermined pattern and the second predetermined pattern is one of accepted, rejected, and neither accepted nor rejected.

### Claim 13 (depends on 1)

The method of claim 1, wherein the pattern match control comprises a pattern match acceptance indicator which indicates whether to perform one of accepting, rejecting, or neither accepting nor rejecting the received message when the pattern match exists.

### Claim 14 (depends on 1)

The method of claim 1, wherein the pattern match control comprises a match index which indicates an offset into the received message at which to perform pattern matching.

### Claim 15 (depends on 1)

The method of claim 1, wherein the pattern match control comprises a continuous search enable which indicates a conditional acceptance of the received message when a pattern match exists.

### Claim 16 (depends on 1)

The method of claim 1, wherein the pattern match control comprises a concatenation indicator and wherein determining whether the pattern match exists within the received message is based on at least two patterns indicated by the pattern match data.

### Claim 17 (depends on 1)

The method of claim 1, wherein the pattern match control comprises an inverse pattern indicator, wherein the pattern match result indicates whether the received message includes a pattern indicated by the pattern match data when the inverse pattern indicator has a first value and indicates whether the received message does not include a pattern indicated by the pattern match data when the inverse pattern indicator has a second value.

### Claim 18 (depends on 1)

The method of claim 1, wherein selectively accepting the message based at least on the pattern match result is performed without processor interruption.

### Claim 19 (depends on 1)

The method of claim 1, wherein when the message is accepted, the method further comprises:
selecting a buffer descriptor queue (BDQ) based on the pattern match result, wherein the pattern match result indicates whether the received message includes a first pattern and provides pattern match attributes;
storing the message to memory according to the selected BDQ; and
selectively storing at least a portion of the accepted message to cache, wherein the portion of the accepted message is indicated by the pattern match attributes.

### Claim 20 (depends on 19)

The method of claim 19, wherein the pattern match attributes indicate one of a plurality of BDQs corresponding to the first pattern, wherein the one of the plurality of BDQs corresponds to the selected BDQ.

### Claim 21 (depends on 19)

The method of claim 19, wherein when the at least a portion of the accepted message is stored to cache, the pattern match attributes provide an extract index and an extract length to indicate the portion of the accepted message stored to cache.

### Claim 22

In a packet controller having an input, hash logic, pattern matching logic coupled to the hash logic, and control logic coupled to the hash logic and the pattern matching logic, a method, comprising:
receiving a message at an input of the packet controller;
providing the message to the hash logic which performs a hash function to determine whether a hash hit occurs;
providing the message to the pattern matching logic which determines whether a first pattern match corresponding to a first pattern is detected within the received message, wherein the first pattern is indicated by pattern match data and has a corresponding pattern match acceptance indicator;
when the first pattern match is detected, the control logic selectively accepting the received message when the pattern match acceptance indicator corresponding to the first pattern indicates acceptance of the received message and a hash hit occurs; and
when the first pattern match is detected, the pattern match acceptance indicator corresponding to the first pattern indicates rejection of the received message and a hash hit occurs, the control logic rejecting the received message.

### Claim 23 (depends on 22)

The method of claim 22, wherein when the first pattern match is detected, selectively accepting the received message when the pattern match acceptance indicator corresponding to the first pattern indicates neither acceptance nor rejection of the received message and a hash hit occurs.

### Claim 24 (depends on 23)

The method of claim 23, wherein when the pattern match acceptance indicator corresponding to the first pattern indicates neither acceptance nor rejection of the received message and a hash hit occurs, accepting the received message when the hash hit is a perfect hash hit.

### Claim 25 (depends on 23)

The method of claim 23, wherein when the pattern match acceptance indicator corresponding to the first pattern indicates neither acceptance nor rejection of the received message and a hash hit occurs, accepting the received message when a promiscuous mode is indicated.

### Claim 26 (depends on 23)

The method of claim 23, wherein when the pattern match acceptance indicator corresponding to the first pattern indicates neither acceptance nor rejection of the received message and a hash hit occurs, selectively accepting the received message based on a full address comparison.

### Claim 27 (depends on 22)

The method of claim 22 further comprising:
rejecting the received message when the first pattern match is not detected and a hash hit occurs.

### Claim 28 (depends on 22)

The method of claim 22, wherein determining whether the first pattern match is detected is further based on a concatenate indicator.

### Claim 29 (depends on 28)

The method of claim 28, wherein when the concatenate indicator has a first value, the first pattern match corresponds to the first pattern and a second pattern, the second pattern indicated by second pattern match data.

### Claim 30 (depends on 29)

The method of claim 29, wherein when the concatenate indicator has a second value, the first pattern match corresponds to the first pattern and not the second pattern.

### Claim 31 (depends on 22)

The method of claim 22, wherein when the first pattern match is detected, the received message is selectively accepted based on a continuous search indicator when the pattern match acceptance indicator corresponding to the first pattern indicates acceptance of the received message and the hash hit occurs.

### Claim 32 (depends on 31)

The method of claim 31, wherein when the first pattern match is detected, the received message is accepted when:
the continuous search indicator indicates no continuous searching,
the pattern match acceptance indicator corresponding to the first pattern indicates acceptance of the received message, and
the hash hit occurs.

### Claim 33 (depends on 31)

The method of claim 31, wherein when the first pattern match is detected, the received message is accepted when:
the continuous search indicator indicates continuous searching,
the pattern match acceptance indicator corresponding to the first pattern indicates acceptance of the received message,
the hash hit occurs, and
a second pattern match corresponding to a second pattern is detected, the second pattern having a corresponding pattern match acceptance indicator which does not indicate rejection of the received message.

### Claim 34 (depends on 33)

The method of claim 33, wherein the pattern match acceptance indicator corresponding to the second pattern indicates one of accepting the received message and neither accepting nor rejecting the received message.

### Claim 35 (depends on 33)

The method of claim 33, wherein the pattern match acceptance indicator corresponding to the second pattern indicates one of accepting the received message, neither accepting nor rejecting the received message, and pattern matching is disabled for the second pattern.

### Claim 36 (depends on 31)

The method of claim 31, wherein when the first pattern match is detected, the received message is not accepted when:
the continuous search indicator indicates continuous searching,
the pattern match acceptance indicator corresponding to the first pattern indicates acceptance of the received message,
the hash hit occurs, and
a second pattern match corresponding to a second pattern is detected, the second pattern having a corresponding pattern match acceptance indicator which indicates rejection of the received message.

### Claim 37 (depends on 22)

The method of claim 22, wherein the first pattern has a corresponding inverse pattern indicator, and wherein when the inverse pattern indicator has a first value, the first pattern match is detected when the received message includes the first pattern.

### Claim 38 (depends on 37)

The method of claim 37, wherein when the inverse pattern indicator has a second value, the first pattern match is detected when the received message does not include the first pattern.

### Claim 39 (depends on 22)

The method of claim 22, wherein when the message is accepted, the method further comprises:
selecting a buffer descriptor queue (BDQ) based on pattern match attributes;
storing the message to memory according to the selected BDQ; and
selectively storing at least a portion of the accepted message to cache, wherein the portion of the accepted message is indicated by the pattern match attributes.

### Claim 40 (depends on 39)

The method of claim 39, wherein the pattern match attributes indicate one of a plurality of BDQs corresponding to the first pattern, wherein the one of the plurality of BDQs corresponds to the selected BDQ.

### Claim 41 (depends on 39)

The method of claim 39, wherein the pattern match attributes correspond to the first pattern.

### Claim 42 (depends on 39)

The method of claim 39, wherein when the message is accepted, the method further comprises:
determining whether a second pattern match exists corresponding to a second pattern, wherein the pattern match attributes correspond to the second pattern.

### Claim 43 (depends on 39)

The method of claim 39, wherein the pattern match attributes provide a pattern match extract indicator, and wherein the portion of the accepted message is stored to cache when the pattern match extract indicator indicates that extraction is enabled and the portion of the accepted message is not stored to cache when the pattern match extract indicator indicates that extraction is disabled.

### Claim 44 (depends on 43)

The method of claim 43, wherein the pattern match attributes provide an extract index and an extract length to indicate the portion of the accepted message stored to cache.

### Claim 45 (depends on 39)

The method of claim 39, wherein when the message is accepted, the method further comprises:
storing at least a portion of the selected BDQ to cache.

### Claim 46

A packet controller, comprising:
an input which receives a message;
hash logic which performs a hash function to determine whether a hash hit occurs within the received message;
pattern matching logic, coupled to the hash logic, which determines whether a first pattern match corresponding to a first pattern is detected within the received message, wherein the pattern match logic comprises at least one pattern match register which stores pattern match data which indicates the first pattern and stores pattern match control which includes a pattern match acceptance indicator corresponding to the first pattern; and
control logic, coupled to the hash logic and the pattern matching logic, which selectively accepts the received message when the first pattern match is detected, the pattern match acceptance indicator corresponding to the first pattern indicates acceptance of the received message, and a hash hit occurs, and which rejects the received message when the first pattern match is not detected and a hash hit occurs.

### Claim 47 (depends on 46)

The packet controller of claim 46, wherein the pattern match control further includes a concatenate indicator, and wherein the pattern matching logic uses the concatenate indicator to determine whether the first pattern match is detected.

### Claim 48 (depends on 47)

The packet controller of claim 47, wherein when the concatenate indicator has a first value, the first pattern match corresponds to the first pattern and a second pattern, the second pattern indicated by second pattern match data stored within the at least one pattern match register.

### Claim 49 (depends on 48)

The packet controller of claim 48, wherein when the concatenate indicator has a second value, the first pattern match corresponds to the first pattern and not the second pattern.

### Claim 50 (depends on 46)

The packet controller of claim 46, wherein the pattern match control further includes a continuous search indicator, and wherein the control logic selectively accepts the received message based on the continuous search indicator when the first pattern match is detected, the pattern match acceptance indicator corresponding to the first pattern indicates acceptance of the received message, and the hash hit occurs.

### Claim 51 (depends on 46)

The packet controller of claim 46, wherein the pattern match control further includes an inverse pattern indicator, and wherein when the inverse pattern indicator has a first value, the first pattern match is detected when the received message includes the first pattern.

### Claim 52 (depends on 51)

The packet controller of claim 51, wherein when the inverse pattern indicator has a second value, the first pattern match is detected when the received message does not include the first pattern.