Network message processing using inverse pattern matching

• US 7,240,041 B2
• Filed: 11/25/2003
• Issued: 07/03/2007
• Est. Priority Date: 11/25/2003
• Status: Expired due to Fees

• Current Assignee: North Star Innovations Inc. (Wi-LAN Inc.)
• Original Assignee: Freescale Semiconductor, Inc. (NXP Semiconductors NV)
• Inventors: Martin, Harold M., Greaves, Carlos A., Nguyen, Thang Q., Nunez, Jose M.
• Primary Examiner(s): Knight, Anthony
• Assistant Examiner(s): Holmes, Michael B.
• Application Number:
  US10/721,196
• Publication Number:
  US 20050108943A1
• Time in Patent Office: 1,316 Days
• Field of Search: 706/48, 706/206, 707/6, 709201-245, 370351-545
• US Class Current: 706/48
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]

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

1. In a packet controller, a method comprising:

receiving a message;

determining 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 inverse pattern indicator and a corresponding pattern match acceptance indicator;

when the first pattern match is detected, selectively accepting the message based on the corresponding pattern match acceptance indicator, wherein;

when the corresponding inverse pattern indicator has a first value, the first pattern match is detected when the first pattern is detected within the received message, and

when the corresponding inverse pattern indicator has a second value, the first pattern match is detected when the first pattern is not detected within the received message; and

when the message is accepted, storing the accepted message.

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

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

4. The method of claim 1, wherein the corresponding pattern match acceptance indicator indicates one of acceptance, rejection, and neither acceptance nor rejection of the received message.

5. The method of claim 1, wherein the first pattern has a corresponding continuous search enable indicator and wherein selectively accepting the message based on the corresponding pattern acceptance indicator comprises selectively accepting the message based on the corresponding pattern acceptance indicator and the corresponding search enable indicator.

6. The method of claim 5, wherein when the first pattern match is detected and the pattern match acceptance indicator corresponding to the first pattern indicates acceptance of the received message, accepting the received message when the continuous search indicator corresponding to the first pattern indicates no continuous searching.

7. The method of claim 5, wherein when the first pattern match is detected and the pattern match acceptance indicator corresponding to the first pattern indicates acceptance of the received message, accepting the received message when:

the continuous search indicator corresponding to the first pattern indicates continuous searching, 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.

8. The method of claim 7, wherein the second pattern is indicated by the pattern match data and 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.

9. The method of claim 7, 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.

10. The method of claim 7, wherein the second pattern has a corresponding inverse pattern indicator, wherein:

when the inverse pattern indicator corresponding to the second pattern has the first value, the second pattern match is detected when the second pattern is detected within the received message, and

when the inverse pattern indicator corresponding to the second pattern has the second value, the second pattern match is detected when the second pattern is not detected within the received message.

11. The method of claim 5, wherein when the first pattern match is detected and the pattern match acceptance indicator corresponding to the first pattern indicates acceptance of the received message, not accepting the received message when:

the continuous search indicator corresponding to the first pattern indicates continuous searching, 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.

12. The method of claim 11, wherein the second pattern has a corresponding inverse pattern indicator, wherein:

when the inverse pattern indicator corresponding to the second pattern has the first value, the second pattern match is detected when the second pattern is detected within the received message, and

when the inverse pattern indicator corresponding to the second pattern has the second value, the second pattern match is detected when the second pattern is not detected within the received message.

13. The method of claim 1, further comprising:

when the first pattern match is not detected, rejecting the message.

14. The method of claim 1, wherein the first pattern has a corresponding match index which indicates a location within the received message at which to determine whether the first pattern match is detected.

15. The method of claim 1, wherein when the first pattern match is detected, the method further comprises:

determining whether a second pattern match is detected within the received message, each of the first pattern and the second pattern having a corresponding concatenate indicator, wherein selectively accepting the message is based on the pattern match acceptance indicator corresponding to the first pattern and at least one of the concatenate indicator corresponding to the first pattern and the concatenate indicator corresponding to the second pattern;

when the second pattern match is detected and the at least one of the concatenate indicator corresponding to the first pattern and the concatenate indicator corresponding to the second pattern indicates concatenation of the first and second patterns, selectively accepting the message when the pattern match acceptance indicator corresponding to the first pattern indicates acceptance of the received message; and

when the second pattern match is not detected and the at least one of the concatenate indicator corresponding to the first pattern and the second pattern indicates concatenation of the first and second patterns, the first pattern match is deemed not detected.

16. The method of claim 15, wherein the second pattern has a corresponding inverse pattern indicator, wherein:

when the inverse pattern indicator corresponding to the second pattern has a first value, the second pattern match is detected when the second pattern is detected within the received message, and

when the inverse pattern indicator corresponding to the second pattern has a second value, the second pattern match is detected when the second pattern is not detected within the received message.

17. The method of claim 1, further comprising:

performing a hash function to determine whether a hash hit occurs, wherein when a hash hit occurs, the first pattern match is detected, and the pattern match acceptance indicator corresponding to the first pattern indicates acceptance of the received message, selectively accepting the message.

18. The method of claim 1, 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.

19. The method of claim 18, 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.

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

21. The method of claim 18, wherein when the message is accepted, the message further comprises:

determining whether a second pattern match exists corresponding to a second pattern, wherein the pattern match attributes correspond to the second pattern.

22. The method of claim 18, 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.

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

24. The method of claim 18, wherein when the message is accepted, the method further comprises:

storing at least a portion of the selected BDQ to cache.

25. A packet controller, comprising:

an input which receives a message;

pattern matching 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 an inverse pattern indicator corresponding to the first pattern; and

control logic, coupled to the pattern matching logic, which selectively accepts the received message when the first pattern match is detected and the pattern match acceptance indicator corresponding to the first pattern indicates acceptance of the received message, wherein;

when the corresponding inverse pattern indicator has a first value, the first pattern match is detected when the first pattern is detected within the received message, and

when the corresponding inverse pattern indicator has a second value, the first pattern match is detected when the first pattern is not detected within the received message.

26. The packet controller of claim 25, 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.

27. The packet controller of claim 26, 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.

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

29. The packet controller of claim 27, wherein the pattern match control includes an inverse pattern indicator corresponding to the second pattern.

30. The packet controller of claim 25, 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 and the pattern match acceptance indicator corresponding to the first pattern indicates acceptance of the received message.