Alcatel-lucent USA Inc.

Muthuprasanna Muthusrinivasan

Mansoor Ali Khan Alicherry

Vijay Pochampalli Kumar

Govindarasu Manimaran

Disclosed is a method and system for multi-character multi-pattern pattern matching. In the multi-character multi-pattern pattern matching method, patterns in an input stream are detected by transitioning between states of a 'compressed deterministic finite state automaton (DFA)', with each transition based on multiple characters of the input stream. The compressed DFA is created by compressing an original DFA, such as an Aho-Corasick DFA, such that each state of the compressed DFA represents multiple consecutive states of the original DFA and each transition between the states of the compressed DFA is a combination of all of the transitions between the multiple consecutive states of the original DFA. This method can be implemented using a Ternary Content-Addressable Memory (TCAM) to store the transitions of the compressed DFA and compares the transitions with multiple characters of an input stream at a time to detect patterns in the input stream.

Method and system for multi-character multi-pattern pattern matching

Disclosed is a two tier packet labeling technique for use in connection with network traceback in a network having multiple autonomous systems, with routers and other network resources within each autonomous system. Tier 1 labels are assigned at the autonomous system level, and tier 2 labels are assigned at the router level. In order to reduce the number of labels that are required, a technique called logical partitioned coloring may be used, in which certain autonomous systems and border routers may be logically partitioned into a plurality of mesh connected nodes, and the labels are assigned to these mesh-connected nodes. During network operation the network routers store either tier 1 or tier 2 labels in data packets. The determination of whether to store a label in any particular packet, and the determination of which label to store, may be determined probabilistically by the network router.

Growing community of inventors

Ames, IA, United States of America

Muthuprasanna Muthusrinivasan