Lossless, stateful, real-time pattern matching with deterministic memory resources

1. A method comprising: a processor and a memory for performing the steps of

broadcasting data units of packets to a plurality of finite state machine (FSM) comparison units, each of the FSM comparison units implementing a portion of a signature;

comparing the data units of the packets to a plurality of signatures, including each FSM comparison unit of the plurality of FSM comparison units independently and concurrently comparing one of the data units to the corresponding portion of a signature implemented by said each of the FSM comparison units; and

combining results of the plurality of FSM comparison units independently processing the data units using a logic combinatorial circuit wherein combining results comprises logically ANDing results from a subset of the plurality of FSM comparison units, each FSM in the plurality matching a portion of a first signature from the plurality of signatures, and translating information on the match of the first signature into one or more values.

2. The method defined in claim 1 wherein one FSM comparison unit of the plurality of FSM comparison units implement a single portion of a signature that forms a portion of two signatures of the plurality of signatures.

3. The method defined in claim 2 wherein a set of the plurality of FSM comparison units implement one signature, and comparing the data units of the packets to the plurality of signatures comprises performing unanchored string matching by comparing the data units of the packets to the one signature.

4. The method defined in claim 2 wherein a set of the plurality FSM comparison units implement one signature, and comparing the data units of the packets to the plurality of signatures comprises performing anchored string matching by comparing the data units of the packets to the one signature.

5. The method defined in claim 1 wherein the logic combinatorial circuit forms at least a portion of a reduction network.

6. The method defined in claim 1 wherein the one or more values comprises a block value and a pass value.

7. The method defined in claim 1 further comprising blocking a packet if no pass values are generated for a signature and one or more block values are generated for the signature.

8. The method defined in claim 1 further comprising forwarding a packet without blocking the packet if at least one pass value is generated for the signature.

9. The method defined in claim 1 wherein comparing the data units of the packets to a plurality of signatures comprises a processor managing comparisons by at least a group of FSM comparison units of the plurality of FSM comparison units and managing transitions of the at least one group of FSM comparison units.

10. The method defined in claim 1 wherein a group of the plurality of FSM comparison units is programmed to perform arbitrary signature matching.

11. The method defined in claim 10 wherein a set of the plurality of FSM comparison units comprise a plurality of programmable registers programmed to match a signature, and further wherein a first of the plurality of programmable registers is coupled to the output of a second of the plurality of programmable registers, and at least one of the plurality of programmable registers comprises a last register of a match of the signature.

12. An apparatus having a processor and a memory, comprising:

a bus system to broadcast data units of a packet;

a plurality of finite state machine (FSM) comparison units coupled to the bus system to compare the data units of the packet to a plurality of signatures, each of the FSM comparison units implementing a portion of a signature, wherein each FSM comparison unit of the plurality of FSM comparison units independently and concurrently compares one of the data units to its associated portion of one signature; and

a logic combinatorial circuit to combine results of the plurality of FSM comparison units independently processing the data units the logical combinatorial circuit comprising a logic circuit to logically AND results from each FSM implementing a portion of a first signature from the plurality of signatures to determine if a match for the signature exists, and to translate information on the match into one or more values.

13. The apparatus defined in claim 11 wherein one FSM comparison unit of the plurality of FSM comparison units implement a portion of two signatures of the plurality of signatures.

14. The apparatus defined in claim 13 wherein a set of the plurality FSM comparison units implement one signature, and the set of FSM comparison units compares the data units of the packet to the plurality of signatures by performing unanchored string matching by comparing the data units of the packets to the one signature.

15. The apparatus defined in claim 13 wherein a set of the plurality FSM comparison units implement one signature, and the FSM comparison units compare the data units of the packet to the plurality of signatures by performing anchored string matching by comparing the data units of the packets to the one signature.

16. The apparatus defined in claim 12 wherein the logic combinatorial circuit forms at least a portion of a reduction network.

17. The apparatus defined in claim 13 wherein the one or more values comprises a block value and a pass value.

18. The apparatus defined in claim 13 wherein the network interface is operable to block the packet if no pass values are generated for a signature and one or more block values are generated for the signature.

19. The apparatus defined in claim 13 wherein the network interface is operable to forward the packet without blocking the packet if at least one pass value is generated for the signature.

20. The apparatus defined in claim 12 wherein a processor manages comparisons by at least a group of FSM comparison units of the plurality of FSM comparison units and manages transitions of the at least one group of FSM comparison units.

21. The apparatus defined in claim 12 wherein a group of the plurality of FSM comparison units is programmed to perform arbitrary signature matching.

22. The apparatus defined in claim 21 wherein a set of the plurality of FSM comparison units comprise a plurality of programmable registers programmed to match a signature, and further wherein a first of the plurality of programmable registers is coupled to the output of a second of the plurality of programmable registers, and at least one of the plurality of programmable registers comprises a last register of a match of the signature.

23. An apparatus having a processor and a memory, comprising:

means for broadcasting data units of packets to a plurality of finite state machine (FSM) comparison units, each of the FSM comparison units implementing a portion of a signature;

means for comparing the data units of the packets to a plurality of signatures, including each FSM comparison unit of the plurality of FSM comparison units independently and concurrently comparing one of the data units to the corresponding portion of a signature implemented by said each of the FSM comparison units; and

means for combining results of the plurality of FSM comparison units independently processing the data units using a logic combinatorial circuit, wherein combining results comprises logically ANDing results from a subset of the plurality of FSM comparison units, each FSM in the plurality matching a portion of a first signature from the plurality of signatures, and translating information on the match of the first signature into one or more values.