Compiling method for command based router classifiers

• US 8,260,886 B2
• Filed: 12/30/2005
• Issued: 09/04/2012
• Est. Priority Date: 12/30/2005
• Status: Active Grant

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Kling, Lars-Örjan, Penny, Robert E, Jin, Yonghui
• Primary Examiner(s): Won, Michael Y
• Assistant Examiner(s): Chang, Tom Y
• Application Number:
  US12/158,791
• Publication Number:
  US 20090199266A1
• Time in Patent Office: 2,440 Days
• Field of Search: 709/238
• US Class Current: 709/220
• CPC Class Codes: H04L 63/0263 Rule management
• CPC Class Codes: H04L 63/101 Access control lists [ACL]

Abstract

A method and compiler for compiling hierarchical command based policy rules to a flat filter list structure adapted for storage in a Content Addressable Memory (CAM), wherein the policy rules are organized in a tree-structure of classifiers. First, all of the possible search paths in the tree structure are found, and then only the valid search paths according to defined criteria are added to the flat filter list. The CAM may be a Ternary Content Addressed Memory.

Claims

1. A method of compiling command-based policy rules to a flat filter list structure for storage in a Content Addressable Memory (CAM), said policy rules being organized in a tree-structure of classifiers, wherein a processor is configured to perform the steps of:

(a) finding all the possible search paths in the tree structure;

(b) adding to the flat filter list only the valid search paths according to defined criteria;

(c) transforming a policy map (PMAP) into a flat policy map (F PMAP), wherein the PMAP is a sequence of pairs (CMAP_i, Z_i), where Z_i is the action to be taken for a data packet (P) if it matches the Class map CMAP_i with permit (deny), and each CMAP_i is an ordered pair of a Class list (CL) and a corresponding match operator Y_i that either is set to MATCH ALL (Y_all) or set to MATCH ANY (Y_any), and the F PMAP is a list of ordered pairs (F_i, Z_i), wherein the list of ordered pairs (F_i, Z_i) is the result of steps (a) and (b);

wherein step (c) includes;

transforming a Class map (CMAP) into a flat Class map (F_CMAP), wherein the CMAP comprises the Class list (CL), which comprises a sequence of Access Control Lists (ACL_i), wherein each ACL_i is a sequence of ordered pairs (F_i, X_i), where F_i is a filter and X_i, is a corresponding matching outcome, wherein X_i is either PERMIT or DENY, and the F_CMAP is a second sequence of ordered pairs (F_j, X_j), wherein the second sequence of ordered pairs (F_j, X_j) is the result of the steps;

(d) listing all search paths by a using a filter intersection between two ACLs in accordance with the individual order of the ACLs;

(e) adding only the valid search paths according to the match operator, Y, in the CMAP with the same order as in step (d); and

(f) repeating steps (d) and (e) until all the ACLs in the CL of the CMAP are joined in to a single ACL.

2. The method according to claim 1, wherein step (c) includes repeating steps (d)-(f) for each CMAP until all CMAPS are F-CMAPs.

3. The method according to claim 1, wherein step (e) includes determining valid search paths, said determining step including:

for the search path involving only the first ACL, determining the path is valid only when any of the following criteria are fulfilled;

Y=Y_All and X_1,i=X₋

; and

Y=Y_Any and X_1,i=X₊;

for the search path involving both ACLs, determining the path is valid only when any of the following criteria are fulfilled;

Y=Y_All and X_1,i=X₊; and

Y=Y_Any and X_1,i=X₋

.

4. The method according to claim 1, wherein step (c) includes the step of first transforming F_PMAPs into a flat PMAP format according to rules for transforming a single CMAP into a PMAP.

5. The method according to claim 4, wherein step (c) includes the steps of:

(g) determining all possible combinations by using a filter intersection when joining two neighboring F_PMAPs;

(h) adding only the valid elements (F, Z), to the flat PMAP (F_PMAP), if the element fulfills one of the following criteria;

for filters involving only the first F_CMAP;

Z_1,i≠

Z_Def, i ε

{1, 2, . . . , N₁}; and

for filters involving both F_CMAPs;

F_1,i∩

F_2,J≠

F_Ø

, i ε

{1, 2, N₁); and

jε

{1, 2, . . . , N₂}; and

(i) repeating steps (g) and (h) until the last CMAP is compiled.

6. The method according to claim 1, wherein the transformation of step (c) involves a combination of a firewall ACL and a PMAP to flat filter structure, and step (c) includes the steps of:

inverting the firewall ACL by inverting the match outcome in the firewall ACL, resulting in ˜

ACL_FW =((F₁, ˜

X₁), (F₂, ˜

X₂), ... , (F_N1, ˜

X_N), (F_*1, ˜

X_));

setting the equivalent firewall CMAP to CMAP_FW =(˜

ACL_FW, Y*); and

setting the combined firewall ACL and PMAP to PMAP_+FW =((CMAP_FW, Z_FW), (CMAP₂, Z₂), (CMAP₃, Z₃), ... , (CMAP_N, Z_N), (CMAP, Z_Def)).

7. The method according to claim 1, wherein the Content Addressed Memory (CAM) is a Ternary Content Addressed Memory (TCAM).