×

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
First Claim
Patent Images

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 (CMAPi, Zi), where Zi is the action to be taken for a data packet (P) if it matches the Class map CMAPi with permit (deny), and each CMAPi is an ordered pair of a Class list (CL) and a corresponding match operator Yi that either is set to MATCH ALL (Yall) or set to MATCH ANY (Yany), and the F PMAP is a list of ordered pairs (Fi, Zi), wherein the list of ordered pairs (Fi, Zi) 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 (ACLi), wherein each ACLi is a sequence of ordered pairs (Fi, Xi), where Fi is a filter and Xi, is a corresponding matching outcome, wherein Xi is either PERMIT or DENY, and the F_CMAP is a second sequence of ordered pairs (Fj, Xj), wherein the second sequence of ordered pairs (Fj, Xj) 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.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×