×

Rule set partitioning based packet classification method for internet

  • US 7,747,553 B2
  • Filed: 01/31/2006
  • Issued: 06/29/2010
  • Est. Priority Date: 01/31/2005
  • Status: Active Grant
First Claim
Patent Images

1. A method for generating a partitioned rule set for use in classifying a packet for a communications network, the method comprising executing the following steps:

  • obtaining a rule set comprising a plurality of rules, the plurality of rules being used to classify a packet for the communications network;

    partitioning the rule set into a plurality of horizontal subsets in accordance with a classification operation and a field associated with the rule set, a given horizontal subset comprising one or more rule layers, each of the one or more rule layers comprising one or more of the plurality of rules;

    partitioning at least a first and a second of the plurality of horizontal subsets into a plurality of vertical subsets, wherein, within a given one of the plurality of horizontal subsets, a first vertical subset range interval of a given one of the plurality of vertical subsets is non-overlapping with a second vertical subset range interval of another given one of the plurality of vertical subsets;

    creating a plurality of non-overlapping partitions across a range interval of the rule set, a given one of the non-overlapping partitions corresponding to values which are within each of a set of vertical subset range intervals comprising one vertical subset within at least the first and the second of the horizontal subsets; and

    generating a hash table that indexes the plurality of vertical subsets in accordance with the plurality of non-overlapping partitions, wherein a given vertical subset is grouped together with a given partition in accordance with a corresponding range interval of the given vertical subset.

View all claims
  • 5 Assignments
Timeline View
Assignment View
    ×
    ×