Methods for performing packet classification
First Claim
1. A method, comprising:
- partitioning rules in an access control list (ACL) into a plurality of partitions, each partition defined by a meta-rule comprising a set of filter dimension ranges and/or values covering the rules in that partition;
building a plurality of filter data structures, each including a plurality of filter entries defining packet header filter criteria corresponding to one or more filter dimensions; and
storing partition data identifying, for each filter entry, any partition having a meta-rule defining a filter dimension range or value that covers that entry'"'"'s packet header filter criteria.
1 Assignment
0 Petitions
Accused Products
Abstract
Methods for performing packet classification via partitioned bit vectors. Rules in an access control list (ACL) are partitioned into a plurality of partitions, wherein each partition is defined by a meta-rule comprising a set of filter dimension ranges and/or values covering the rules in that partition. Filter data structures comprising rule bit vectors are then built, each including multiple filter entries defining packet header filter criteria corresponding to one or more filter dimensions. Partition bit vectors identifying, for each filter entry, any partition having a meta-rule defining a filter dimension range or value that covers that entry'"'"'s packet header filter criteria are also generated and stored in a corresponding data structure.
-
Citations
23 Claims
-
1. A method, comprising:
-
partitioning rules in an access control list (ACL) into a plurality of partitions, each partition defined by a meta-rule comprising a set of filter dimension ranges and/or values covering the rules in that partition;
building a plurality of filter data structures, each including a plurality of filter entries defining packet header filter criteria corresponding to one or more filter dimensions; and
storing partition data identifying, for each filter entry, any partition having a meta-rule defining a filter dimension range or value that covers that entry'"'"'s packet header filter criteria. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. A method comprising:
-
extracting header data from a packet based on filter dimension criteria defined by an access control list (ACL) employed for packet classification;
for each filter dimension in the filter dimension criteria, employing header data that is extracted corresponding to that filter dimension to identify an applicable entry in a corresponding filter data structure including a set of ranges and/or values corresponding to the filter dimension; and
retrieving a partition bit vector corresponding to the entry, the partition bit vector including a string of bits, each bit position in the string associated with a corresponding partition for the ACL;
logically ANDing the partition bit vectors together to identify one or more partitions to be searched;
for each entry that is identified, retrieving portions of a rule bit vector associated with that entry, the portions corresponding to the one or more partitions to be searched;
for each of the one or more partitions, logically ANDing the bit vector portions corresponding to that partition to identify a highest-priority rule for that partition; and
comparing the highest-priority rules to identify a rule with the highest priority. - View Dependent Claims (13, 14, 15, 16)
-
-
17. A machine-readable medium, to store instructions that if executed perform operations comprising:
-
extracting header data including a source address, a destination address, a source port, and destination port, and a protocol field value from a packet;
for each dimension defined for a packet classification scheme employing a partitioned access control list (ACL) including a plurality of partitions, each partition including a corresponding set of rules for forwarding packets;
employing header data corresponding to the dimension as an input to a lookup process that locates a matching entry in a filter data structure corresponding to the dimension; and
retrieving a partition bit vector corresponding to the entry from memory, the partition bit vector including a string of bits, each bit position in the string associated with a corresponding partition for the ACL;
logically ANDing the partition bit vectors together to identify one or more partitions to be searched;
for each entry that is identified, retrieving portions of a rule bit vector associated with that entry from memory, the portions corresponding to the one or more partitions to be searched;
for each of the one or more partitions, logically ANDing the bit vector portions corresponding to that partition to identify a highest-priority rule for that partition; and
comparing the highest-priority rules to identify a rule with the highest priority. - View Dependent Claims (18, 19, 20)
-
-
21. A network line card, comprising:
-
a network processor, a plurality of input/output (I/O) ports, communicatively-coupled to the network processor;
memory, communicatively-coupled to the network processor; and
a storage device, communicatively-coupled to the network processor, having instructions stored therein that if executed perform operations comprising;
extracting header data including a source address, a destination address, a source port, and destination port, and a protocol field value from a packet;
for each dimension defined for a packet classification scheme employing a partitioned access control list (ACL) including a plurality of partitions, each partition including a corresponding set of rules for forwarding packets;
employing header data corresponding to the dimension as an input to a lookup process that locates a matching entry in a filter data structure corresponding to the dimension; and
retrieving a partition bit vector corresponding to the entry from memory, the partition bit vector including a string of bits, each bit position in the string associated with a corresponding partition for the ACL;
logically ANDing the partition bit vectors together to identify one or more partitions to be searched;
for each entry that is identified, retrieving portions of a rule bit vector associated with that entry from memory, the portions corresponding to the one or more partitions to be searched;
for each of the one or more partitions, logically ANDing the bit vector portions corresponding to that partition to identify a highest-priority rule for that partition; and
comparing the highest-priority rules to identify a rule with the highest priority. - View Dependent Claims (22, 23)
-
Specification