300 would terminate after processing R6, and the packet would proceed down the pipeline for further processing.

Example 3—Hit on Rule R2 (Chained Branch Rules)

Policy rule R2 matches IPv4 packets that have a destination IP address in the range 3.3.3.0/24 and a source port of 80. Accordingly, R2 will match a packet having:

- DIP=3.3.3.32 and source port=80.
  
  Because R2 is a branch rule, the increment action on the EDGE-CACHE counter will be delayed, and packet classification continues. The packet will be compared to the continuation rule specified in the GOTO action, namely policy rule R4. There are two outcomes from comparing the packet to R4 to consider:
- Outcome 1, where R4 matches the packet. Because R4 is another branch rule, non-branching actions associated with R4, namely increment EDGE-CACHE-HTTPS, will be delayed. At this point, the list of delayed actions would include:
  - increment EDGE-CACHE
  - increment EDGE-CACHE-HTTPS.
- Packet classification continues, and the packet would be compared to the continuation rule specified in the GOTO action of R4, namely policy rule R6 (described below).
- Outcome 2, where R4 does not match the packet. The action in R4 is not performed. Moreover, the branch in R4 is not taken. Processing continues with the next rule, namely, R5. If R5 matches the packet, both the actions of R5 and the list of delayed actions, namely increment EDGE-CACHE, would be performed; packet classification with traffic policy 300 would terminate and the packet would proceed down the pipeline for further processing. Otherwise, processing continues with the next rule, namely, R6.
  
  There are two outcomes from comparing the packet to R6 to consider:
- Outcome 1, where R6 matches the packet. Because R6 is a terminal rule, all previously delayed action(s) would be performed. In addition, the action associated with R6 would be performed. Because R6 is a terminal rule, packet classification with traffic policy 300 would terminate and the packet would proceed down the pipeline for further processing.
- Outcome 2, where R6 does not match the packet. Because R6 is a terminal rule, all previously delayed action(s) would be performed. However, because R6 does not match the packet, the action(s) associated with R6 would not be performed. Further, because R6 is a terminal rule, packet classification with traffic policy 300 would terminate and the packet would proceed down the pipeline for further processing.

The foregoing examples describe the execution flow (execution order) in connection with terminal policy rules and branch policy rules. As explained above, the policy rules in a traffic policy can be compiled to produce a list of packet filters (e.g., compiled rules 126) that can then be downloaded and programmed into a packet processor. A TCAM performs a single lookup for a packet to output a single packet filter and as such does not support being able to branch from one filter to another filter. When a traffic policy is compiled in accordance with the present disclosure, the resulting list of packet filters nonetheless preserve the branch semantics (behavior) of any branch rules in the traffic policy.

FIGS. 4A to 4C illustrate examples of traffic policies and corresponding packet filters. Traffic policy 402 in FIG. 4A, for example, comprises two terminal policy rules R1, R2. Compiled rules 404 is a representation of the list of packet filters (<key, value> pairs) 406 generated from traffic policy 402 that can be stored in a given TCAM. Each packet filter in compiled rules 404 can be a <key, value> pair comprising a set of one or more match criteria (key) and a set of one or more actions (value). For example, policy rule R1 matches IPv4 packets having a destination IP address in the block of addresses specified by 1.1.1.0/24. The key component in the corresponding packet filter F1 comprises a set of match criteria M1, M2, where M1 represents the IPv4 match criterion and M2 represents the 1.1.1.0/24 match criterion in a data format suitable for the given TCAM. The value component (action set) of packet filter F1 is a set containing one action A1 which represents the action specified in policy rule R1, namely “count edge.”

Likewise, policy rule R2 matches packets according to the following match criteria:

- packet is IPv4 (M3) AND
- destination IP is in the range 3.3.3.0/24 (M4) AND
- source port is 80 (M5).
  
  The corresponding <key, value> pair of packet filter F2 comprises:
- key={M3, M4, M5}
- value={A2}

FIG. 4B shows an example of a traffic policy that includes a branch policy rule. Policy rule R1 in traffic policy 412, for example, includes the branch action “GOTO R3.” Compiled rules 414 comprise corresponding packet filters 416 generated in accordance with the present disclosure. For example, policy rules R1, R2, R3 correspond to packet filters F1, F2, F3. The GOTO action in rule R1 does not represent an action that is performed in connection with a packet, but rather specifies another rule to match against a packet. Recall from above, however, that in some embodiments TCAMs are configured to perform a lookup operation in a single pass through their memory (e.g., for high throughput), and as such are not configured for an additional pass to process the GOTO action. Accordingly, while the set of actions in packet filter F1, represent the actions of rule R1 (action A, “count edge”), filter F1 excludes the branch action that corresponds to “GOTO R3” in rule R1.

In accordance with the present disclosure, compiled rules 414 includes an additional packet filter F1a that represents execution of the GOTO action without having to refer to another packet filter. The <key, value> pair comprising filter F1a and the position of filter F1a in the list of packet filters are determined in accordance with the present disclosure so as to preserve the branch semantics of the GOTO action without requiring an additional pass in the TCAM. The following description will bear this out.

Consider first classification of the following packets using traffic policy 412:

- Packet 1—IPv4, source IP=5.5.5.12; destination IP=1.1.1.10
- Packet 2—IPv4, source IP=4.4.4.32; destination IP=1.1.1.128
- Packet 3—IPv4, source IP=4.4.4.64; destination IP=2.2.2.138
- Packet 1—R1 will match Packet 1 and so processing will continue with R3 by way of the “GOTO R3” action. R3 will not match Packet 1; action A1 will be applied in connection with Packet 1, and processing of traffic policy 412 terminates.
- Packet 2—R1 will match Packet 2 and so processing will continue with R3 by way of the “GOTO R3” action. R3 will match Packet 2; action A1 will be applied in connection with Packet 2 followed by action A3, and processing of traffic policy 412 terminates.
- Packet 3—R1 will not match Packet 3, nor will R2. R3 will match Packet 3; action A3 will be applied in connection with Packet 3, and processing of traffic policy 412 terminates.

Consider now the operation of packet filters 414 with respect to Packets 1, 2, and 3, keeping in mind that a single pass is made through the TCAM and the TCAM will output a single filter:

- Packet 1—F1a, F1, and F3 will match Packet 1. However, F1a will hit because it has the highest priority among F1a, F1, and F3. Accordingly, the TCAM will output packet filter F1a and actions A1 and A3 will be applied.
- Packet 2—Only F1 will match, and so the TCAM will output packet filter F1 and action A1 will be applied.
- Packet 3—Only F3 will match, and so the TCAM will output packet filter F3 and action A3 will be applied.
  
  It can be seen from the above discussion that although packet filters 414 do not contain branch actions nor specify other packet filters, nonetheless can represent the branch behavior in traffic policy 412. In particular, the branch action semantics of policy rule R1 is represented by the packet filters by virtue of the addition of packet filter F1a and its placement in the list of packet filters.

FIG. 4C shows an example of chained branch rules in a traffic policy. Policy rules R1 and R3 in traffic policy 422, for example, are “chained” in that one branch rule (R3) follows another branch rule (R1). Compiled rules 424 comprise the packet filters 426 that represent the policy rules in traffic policy 422, including the semantics of the chained branch rules in the traffic policy. Consider, for example, processing the following packets in accordance with traffic policy 422:

- Packet 1—IPv4, src IP=2.2.2.32, dst IP=1.1.1.10, next protocol=TCP, source port=80
- Packet 2—IPv4, src IP=4.4.4.28, dst IP=1.1.1.25, next protocol=TCP, source port=80
- Packet 3—IPv4, src IP=2.2.2.28, dst IP=6.6.6.25, next protocol=TCP, source port=80
- Packet 4—IPv4, src IP=4.4.4.28, dst IP=6.6.6.25, next protocol=TCP, source port=80
- Packet 5—IPv4, src IP=*, dst IP=1.1.1.30, next protocol=TCP, source port=8000
- Packet 1 will match policy rule R1, then continue to and match R3, and then continue to and match R6. Accordingly, actions A1, A3, and A6 will be applied.
- Packet 2 will match policy rule R1, then continue to and match R3, and then continue to but NOT match R6. Accordingly, actions A1 and A3 will be applied.
- Packet 3 will match policy rule R3 and then continue to, and match, R6. Accordingly, actions A3 and A6 will be applied.
- Packet 4 will match policy rule R3 and then continue to, but NOT match, R6. Accordingly, action A3 will be applied.
- Packet 5 will match policy rules R1 and then continue to R3, but will not match R3 and processing to continue with the next lower priority rule, namely R4. The ‘*’ in the source IP indicates a wildcard.

Consider now the operation of packet filters 424 on Packets 1, 2, 3, and 4, keeping in mind that a single pass is made through the TCAM and the TCAM will output a single filter:

- Packet 1—F1a, F1b, F1, F3a, F3, and F6 will match Packet 1. However, F1a will hit because it has the highest priority among F1a, F1b, F1, F3a, F3, and F6. Accordingly, the TCAM will output packet filter F1a and actions A1, A3, and A6 will be applied.
- Packet 2—F1b, F1, F3a and F3 will match Packet 2. However, F1b will hit because it has the highest priority among F1b, F1, F3a and F3. Accordingly, the TCAM will output packet filter F1b and actions A1 and A3 will be applied.
- Packet 3—F3a, F3, and F6 will match Packet 3. However, F3a will hit because it has the highest priority among F3a, F3, and F6. Accordingly, the TCAM will output packet filter F3a and actions A3 and A6 will be applied.
- Packet 4—Only F3 will match, and so the TCAM will output packet filter F3 and action A3 will be applied.

Referring to FIGS. 5, 6, and 7, the discussion will now turn to a high-level description of processing in a network device (e.g., 100, FIG. 1) for generating packet filters from a traffic policy in accordance with some embodiments of the present disclosure. FIGS. 6 and 7 illustrate the operations using a simple traffic policy. Traffic policy 600 in FIG. 6 includes branch rules where the semantics of a branch rule allows for multiple rules that match a packet to be applied in connection with the packet. In some embodiments, the network device can include one or more digital processing units, which when operated, can cause the network device to perform processing in accordance with FIG. 5. Digital processing units can include general CPUs in the control plane that operate by way of executing computer program code stored on a non-volatile computer readable storage medium (e.g., read-only memory); for example, CPU 102 (FIG. 1) in the control plane can be a general CPU. The flow of operations performed by the network device is not necessarily limited to the order of operations shown.

Operation 502 The network device can receive a traffic policy. In some embodiments, for example, the network device can be configured with a user interface to allow a user to create a new traffic policy or manage an existing traffic policy. In other embodiments, the network device can communicate with a central controller to receive a traffic policy from the central controller. The received traffic policy can be stored locally in the network device (e.g., solid state drive, SSD) and processed by the network device. In accordance with the present disclosure, the traffic policy may include one or more branch rules.

Operation 504 The network device can scan the policy rules in the traffic policy to generate a flow graph. Referring to FIGS. 6 and 7 for an illustrative example, traffic policy 600 shown in FIG. 6 consists of a list of four policy rules A, B, C, D. Rules A and B are branch rules. In accordance with some embodiments, flow graph 700 in FIG. 7 can be generated from traffic policy 600 as follows:

- Each policy rule in the traffic policy has a corresponding node in the flow graph. A ‘Y’ branch and a ‘N’ branch connect the node to another node. The Y branch indicates the policy rule matches an input packet to be processed according to the traffic policy. As noted above, the input packet can be an ingress packet received by the network device or an egress packet to be transmitted by the network device. The N branch indicates a non-match with the input packet, so processing continues with the node that corresponds to the next policy rule in the traffic policy.
- All rule nodes lead to a DONE node, which represents termination of the traffic policy.
- Terminal policy rule. The Y branch of a node that corresponds to a terminal rule leads directly to the DONE node to indicate that the traffic policy terminates with respect to the input packet when a terminal policy matches a packet; no further rules in that traffic policy are matched. The N branch of the node connects to a node that corresponds to the next policy rule. See, for example, policy rule C in traffic policy 600 and corresponding node C in flow graph 700; if an input packet does not match rule C, then the next policy (rule D) is compared. Action(s) associated with a terminal policy rule are not represented in the flow graph, but can be inferred; if the rule is matched then the action(s) are applied in connection with the packet and if the rule is not matched then the action(s) are not applied.
- Branch policy rule. The Y branch of a node that corresponds to a branch rule connects that node to a node that corresponds to the continuation rule (FIG. 3) specified in the GOTO action. See, for example, policy rule A in traffic policy 600 and corresponding node A in flow graph 700. The N branch (branch rule is not matched) connects to a node in the flow graph that corresponds to the next policy rule. Action(s) associated with a branch policy rule are not represented in the flow graph, but can be inferred. In accordance with some embodiments, for example, if the rule is matched then the action(s) are accumulated and applied when a terminal rule is reached; if the rule is not matched then the action(s) are not accumulated.

Operation 506 Continuing with FIG. 5, the network device can identify paths in the flow graph. In some embodiments, flow paths can be identified using a traversal strategy that is loosely based on depth first traversal as follows:

- Find all paths from the root node (A) to the leaf node (DONE).
- Paths are traversed, where traversal priority is given to Y edges over N edges. Referring again to flow graph 700 (FIG. 7), the first path that is traversed is A to C to DONE because we traverse from A (root node) to DONE (leaf node) along the Y edges first. The next path is A to C to D to DONE: traverse A to C on the Y edge, then C to D on the N edge, then D to DONE on the Y edge. Continuing with this sequence leads to the following list of prioritized paths:
  - 1. A-y→C-y→DONE
  - 2. A-y→C-n→D-y→DONE
  - 3. A-y→C-n→D-n→DONE
  - 4. A-n→B-y→DONE
  - 5. A-n→B-y→D-n→DONE
  - 6. A-n→B-n→C-y→DONE
  - 7. A-n→B-n→C-n→D-y→DONE
  - 8. A-n→B-n→C-n→D-n→DONE
- In each path, remove (skip) from the path nodes that have an outgoing N edge. Referring to path #2 in the list above, for example, the C node is removed because the C node has an outgoing N edge. Likewise, in path #3, the C and D nodes are removed because each has an outgoing N edge. Continuing with this strategy of removing outgoing N edges leads to the final list of paths below. Path #8 (above) is removed from the list because it become empty after removing all nodes in the path that have outgoing N edges, namely nodes A, B, C, D:
  - 1. A→C→DONE
  - 2. A→D→DONE
  - 3. A→DONE
  - 4. B→D→DONE
  - 5. B→DONE
  - 6. C→DONE
  - 7. D→DONE

Operation 508 The network device can generate a packet filter based on each path in the flow graph. Summarizing up to this point, in accordance with some embodiments, a traffic policy (e.g., 600) can be scanned and analyzed to produce a corresponding flow graph (e.g., 700). Each node in the flow graph corresponds to a policy rule in the traffic policy. The flow graph represents the execution order through the traffic policy when packets are processed, from the first (highest priority) rule to the last (lowest priority) rule. The nodes in the flow graph are connected by Y and N edges, which represent when a match occurs (Y) or does not occur (N) with a given input packet. The above final list of paths represents a layout of packet filters that preserves the execution order of the traffic rules. In some embodiments, a packet filter can be generated from these paths according to the following formation guidelines:

- Single-node Path (excluding the DONE node)—The key component of the packet filter (FIG. 4A) comprises the match criteria of the policy rule that corresponds to the one node. The value component of the packet filter comprises the action(s) of that policy rule. Consider path #3, for example, which has a single node A. The packet filter generated from path #3 can be represented by the following <key, value> pair:
  - <{SRC==“1.1.1.1”}, {COUNT ACC-A}>
- As another example, single-node path #5 would produce;
  - <{PROT==6 &&SRC_PORT==1}, {COUNT ACC-B}>
- Multi-node Path (not counting the DONE node)—The key component of the packet filter comprises an intersection of the respective match conditions of the corresponding nodes, and the value component comprises a union of the respective actions of the corresponding nodes. Consider multi-node path #1, for example, comprising nodes A and C:
  - node A: <{SRC==“1.1.1.1” }, {COUNT ACC-A}>
  - node C: <{PROT==6 && DST_PORT==2}, {COUNT ACC-C}>
- To facilitate an explanation for computing the intersection of the key components, we expand nodes A and C as follows so that there is a one-to-one correspondence between the match criteria:
  - node A: <{SRC==“1.1.1.1” && PROT==ANY && DST_PORT==ANY}, {COUNT ACC-A}>
    - node C: <{src==ANY && PROT==6 && DST_PORT==2}, {COUNT ACC-C}>
- The ‘ANY’ terms represent match-all wildcards. For example, node A does not specify a next protocol (PROT) or a destination port (DST_PORT), so this is equivalent to expressing node A as matching on a packet having source IP==1.1.1.1 and “any” next protocol (PROT==ANY) and “any” destination port (DST_PORT==ANY). Accordingly, The intersection of the match criteria of A and C can be computed by taking the intersection of the corresponding match criteria:
  - SRC==“1.1.1.1”∩SRC==ANY→SRC==“1.1.1.1”
    - PROT==ANY∩PROT==6→PROT==6
  - DST_PORT==2 ∩DST_PORT==2→DST_PORT==2
- to yield:
  - {(SRC==“1.1.1.1” && PROT==ANY) && (PROT==6 && DST_PORT==2)},
- The union of the actions of A and C can be expressed as:
  - {COUNT ACC-A, COUNT ACC-C}.
- The packet filter for path #1 can be represented by the following <key, value> pair:
  - <{SRC==“1.1.1.1” && PROT==6 && DST_PORT==2}, {COUNT ACC-A, COUNT ACC-C}>
    
    Based on the foregoing guidelines, the following packet filters can be generated from paths 1-7 above:
- 1. <{SRC==“1.1.1.1” && PROT==6 && DST_PORT==2}, {COUNT ACC-A, COUNT ACC-C}>
- 2. <{SRC==“1.1.1.1” && DST==“2.2.2.2”}, {COUNT ACC-A, COUNT ACC-D}>
- 3. <{SRC==“1.1.1.1” }, {COUNT ACC-A}>
- 4. <{PROT==6 && SRC_PORT==1 && DST==“2.2.2.2”}, {COUNT ACC-B, COUNT ACC-D}>
- 5. <{PROT==6 && SRC_PORT==1}, {COUNT ACC-B}>
- 6. <{PROT==6 && DST_PORT==2}, {COUNT ACC-C}>
- 7. <{DST==“2.2.2.2”}, {COUNT ACC-D}>
  
  The above packet filters represent the semantics (execution order) of the terminal and branch rules in traffic policy 600.

Operation 510 The network device can install the packet filters in each of its packet processors (e.g., 112, FIG. 1). In some embodiments, the packet filters can be programmed in the TCAMs 114 of respective packet processors 112. Processing of a traffic policy in accordance with the present disclosure can be deemed complete.

FIG. 8 is a procedure expressed in pseudo code that sets forth an algorithm for compiling a traffic policy that contains branch policy rules, in accordance with another embodiment of the present disclosure. The procedure “GotoActionResolver” takes as input a “rulelist” which is the traffic policy (containing branch policy rules) to be compiled. Whereas the processing shown in FIG. 5 scans the list of policy rules starting from the top, the GotoActionResolver procedure in FIG. 8 processes a traffic policy starting from the lowest priority branch policy rule in the list and working up. Basically, for each branch rule, we define:

- R_c—the current lowest priority branch policy rule being resolved
- C={R_i, . . . , R_n}—set of rules (terminal and branch) to be matched on after the GOTO action, where i is the priority of the branch rule containing the GOTO action. Because R_cis the current lowest priority branch policy rule being resolved, it is guaranteed that the set C does not contain any branch rule, as they would have been resolved by a previous iteration of the decomposition algorithm.
- N={R_skipped-1, . . . , R_skipped-N}—set of rules between R_cand R_iwhich are skipped if a packet hits the branch rule.
  
  For each rule in C, we DECOMPOSE the rule into two sets of rules (intersection rules and difference rules) as follows:
- C_int={IR(R_k, R_c) fork in range([i, n])}—set of intersection rules, sorted by priority i to n,
- C_diff={R_kIR(R_k, R_c) for k in range([i, n])}—set of difference rules, sorted by priority i to n.

An intersection rule IR(R_a, R_b) for rules R_a, R_bis a rule defined according to the following formal definition:

- Rules can be viewed as being composed of d fields. Rules can be geometrically represented as a prioritized collection of hyper-rectangles in a d-dimensional Euclidean space. A packet is a point in this space. Let R[i] represent the i^thfield in R (i ranges from 1 to d).
- IR(R_a, R_b) is defined as R_a∩R_b={Ra[i]∩Rb[i], ∀i},
- where, if Ra[i]∩Rb[i] is a null set for some i, then IR(R_a, R_b) is deemed empty.
  
  Stated less formally, the intersection rule IR(R_a, R_b) for rules R_a, R_b, is a rule comprising the minimum set of match criteria from R_aand R_bthat matches a packet that would also be matched by R_aand by R_b. For example, suppose we have:
- policy rule R_a: source IP 10.0.0.0/8 && source port 100
- policy rule R_b: source IP 10.0.0.0/24 && source port 100-110,
  
  then IR(R_a, R