Method and apparatus for two-stage packet classification using most specific filter matching and transport level sharing
First Claim
Patent Images
1. A method comprising:
- receiving a packet, the packet having a header including a source address, a destination address, and a number of other fields;
identifying, from a number of entries in a data structure, an entry having a source address prefix matching the source address of the packet, the matching entry including a first identifier;
identifying, from a number of entries in another data structure, an entry having a destination address prefix matching the destination address of the packet, the matching entry including a second identifier;
identifying, from a number of bins, a bin corresponding to the first and second identifiers, the corresponding bin including a number of sets of transport level fields; and
comparing at least one of the other fields of the packet header with each set of transport level fields in the corresponding bin to find a matching set of transport level fields.
1 Assignment
0 Petitions
Accused Products
Abstract
A method and apparatus for two-stage packet classification, the two-stage packet classification scheme including a first stage and a second stage. In the first classification stage, a packet is classified on the basis of the packet'"'"'s network path. In the second stage of classification, the packet is classified on the basis of one or more transport (or other) fields of the packet. Also disclosed are embodiments of most specific filter matching and transport level sharing, and either one or both of these techniques may be implemented in the two-stage classification method.
120 Citations
27 Claims
-
1. A method comprising:
-
receiving a packet, the packet having a header including a source address, a destination address, and a number of other fields; identifying, from a number of entries in a data structure, an entry having a source address prefix matching the source address of the packet, the matching entry including a first identifier; identifying, from a number of entries in another data structure, an entry having a destination address prefix matching the destination address of the packet, the matching entry including a second identifier; identifying, from a number of bins, a bin corresponding to the first and second identifiers, the corresponding bin including a number of sets of transport level fields; and comparing at least one of the other fields of the packet header with each set of transport level fields in the corresponding bin to find a matching set of transport level fields. - View Dependent Claims (2, 3, 4)
-
-
5. A method comprising:
-
receiving a packet, the packet having a header including a source address, a destination address, and a number of transport level fields; searching a source address data structure to find a first index and a third index, the first index associated with a fully specified filter having a source prefix matching the source address of the packet, the third index associated with a partially specified filter having a source prefix matching the source address of the packet; searching a destination address data structure to find a second index and a fourth index, the second index associated with a fully specified filter having a destination prefix matching the destination address of the packet, the fourth index associated with a partially specified filter having a destination prefix matching the destination address of the packet; forming a key from the first and second indexes; searching a primary table for an entry matching the key, the primary table including a number of entries, each entry corresponding to one of a fully specified filter, a fully specified filter intersection, and an indicator filter; and if a matching entry is found in the primary table, accessing a list of bin pointers associated with the matching entry, each bin pointer of the list identifying a bin containing a number of sets of transport level fields. - View Dependent Claims (6, 7, 8, 9, 10, 11, 12, 13, 14)
-
-
15. An apparatus comprising:
-
a processing device; a memory coupled with the processing device, the memory having a first data structure stored therein, the first data structure including a source address look-up data structure, the source address look-up data structure including a number of entries, each of the entries having a source prefix, a filter type, and an index, a destination address look-up data structure, the destination address look-up data structure including a number of entries, each of the entries having a destination prefix, a filter type, and an index, a primary table, the primary table including a number of entries, each of the entries having a key and at least one bin pointer, wherein each of the entries is associated with one of a fully specified filter, a fully specified filter intersection, and an indicator filter, and two secondary tables, each of the secondary tables including a number of entries, each of the entries having a key and at least one bin pointer, wherein each entry of each of the two secondary tables is associated with a partially specified filter. - View Dependent Claims (16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27)
-
Specification