Apparatus and Method for Uniquely Enumerating Paths in a Parse Tree
A method includes constructing a graph characterizing a set of packet headers associated with network traffic. The graph has a unique identifier for each possible combination of packet headers forming a path in the graph. A received packet is associated with a unique identifier in the graph. Characteristics of the received packet are reconstructed based upon the unique identifier.
1 . A method, comprising:
constructing a graph characterizing a set of packet headers associated with network traffic, wherein the graph has a unique identifier for each possible combination of packet headers forming a path in the graph;
associating a received packet with a unique identifier in the graph; and
reconstructing characteristics of the received packet based upon the unique identifier.
2 . The method of claim 1 wherein the unique identifier is based upon a non-commutative function.
3 . The method of claim 2 wherein the non-commutative function is a Cyclic Redundancy Check function.
4 . The method of claim 1 wherein the characteristics specify the headers present in a traversed path.
5 . The method of claim 1 wherein the characteristics have an associated set of flags.
6 . The method of claim 1 wherein the characteristics have an associated set of actions.
7 . The method of claim 1 further comprising loading the graph into an associative memory as a path table.
8 . The method of claim 1 further comprising operating the associative memory as a multiple simultaneous match parser capable of matching multiple paths in a single lookup.
9 . A processor, comprising:
an associative memory storing a graph characterizing a set of packet headers associated with network traffic, wherein the graph has a unique identifier for each possible combination of packet headers forming a path in the graph, wherein the associative memory matches attributes of a received packet with a unique identifier; and
an index memory to reconstruct characteristics of the received packet based upon the unique identifier.
10 . The processor of claim 9 wherein the associative memory is a Ternary Content Addressable Memory.
11 . The processor of claim 9 wherein the associative memory operates as a multiple simultaneous match parser capable of matching multiple paths in a single lookup.
12 . The processor of claim 9 wherein the unique identifier is based upon a non-commutative function.
13 . The processor of claim 12 wherein the non-commutative function is a Cyclic Redundancy Check function.
14 . The processor of claim 9 wherein the characteristics specify the headers present in a traversed path.
15 . The processor of claim 9 wherein the characteristics have an associated set of flags.
16 . The processor of claim 9 wherein the characteristics have an associated set of actions.
17 . A method, comprising;
forming unique assigned values to arcs in a graph;
constraining paths in the graph;
forming calculated paths through the graph based upon the assigned values;
constructing a path table with the calculated paths; and
determining whether any of the calculated paths have an identical value, and if so, repeating the forming and constructing operations.
18 . The method of claim 17 wherein constraining paths includes limiting the number of transitions through cyclic paths in the graph.
19 . The method of claim 17 wherein constraining paths includes selectively eliminating paths in the graph.
20 . The method of claim 17 wherein the unique assigned values are based upon a non-commutative function.