Apparatus and method for two-stage packet classification using most specific filter matching and transport level sharing

Claim 3

The method of claim 1 , wherein the rule matching the source and destination ports of the received packet comprises a highest priority matching rule.

Claim 4

The method of claim 1 , wherein: the source port range of each rule is specified by a source port lower bound and a source port upper bound; and the destination port range of each rule is specified by a destination port lower bound and a destination port upper bound.

Claim 5

The method of claim 3 , wherein: the source port of the received packet is within the source port range of a rule if the packet's source port is greater than or equal to the source port lower bound of the rule and less than or equal to the source port upper bound of the rule; and the destination port of the received packet is within the destination port range of the rule if the packet's destination port is greater than or equal to the destination port lower bound of the rule and less than or equal to the destination port upper bound of the rule.

Claim 6

The method of claim 1 , wherein identifying a bin corresponding to a network path and a protocol of a received packet comprises: identifying, from a number of entries in a data structure, an entry having a source address prefix matching a source address of the received 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 a destination address of the received packet, the matching entry including a second identifier; and identifying, from the number of bins, a bin corresponding to the first and second identifiers and the protocol.

Claim 7

The method of claim 1 , further comprising: searching a first of two secondary tables for an entry matching a key formed from the third index and the protocol, the first secondary table including a number of entries, each entry corresponding to a partially specified filter; and searching a second of the two secondary tables for an entry matching a key formed from the fourth index and the protocol, the second secondary table including a number of entries, each entry corresponding to a partially specified filter; wherein, if no match is found in the primary table, a matching entry in one of the two secondary tables will identify the corresponding bin.

Claim 8

The method of claim 6 , wherein, if no match is found in the primary table or either of the secondary tables, the corresponding bin comprises a default bin associated with an entire two-dimensional address space.

Claim 9

The method of claim 1 , further comprising: searching the source address data structure to find a fifth index associated with a wide filter having a source prefix matching the source address of the packet; searching the destination address data structure to find a sixth index associated with a wide filter having a destination prefix matching the destination address of the packet; forming a second key from the fifth index, the sixth index, and the protocol; and searching a wide filter table for an entry matching the second key, the wide filter table including a number of entries, each entry corresponding to a wide filter; wherein, if no match is found in the primary table, a matching entry the wide filter table will identify the corresponding bin.

Claim 10

The method of claim 8 , wherein each wide filter contained in the wide filter table comprises a fully specified filter having a number of indicator filters exceeding a specified threshold.

Claim 13

The method of claim 10 , wherein the matching rule comprises a highest priority matching rule.

Claim 14

The method of claim 10 , wherein the at least one transport level field of the received packet comprises a source port and a destination port.

Claim 15

The method of claim 12 , wherein each rule of a bin includes a source port lower bound, a source port upper bound, a destination port lower bound, and a destination port upper bound.

Claim 16

The method of claim 13 , wherein a rule matches the at least one transport level field of the packet if: the source port of the received packet is greater than or equal to the source port lower bound of the rule and less than or equal to the source port upper bound of the rule; and the destination port of the received packet is greater than or equal to the destination port lower bound of the rule and less than or equal to the destination port upper bound of the rule.

Claim 17

The method of claim 10 , wherein identifying a bin corresponding to a network path of a received packet comprises: identifying, from a number of entries in a data structure, an entry having a source address prefix matching the source address of the received 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 received packet, the matching entry including a second identifier; and identifying, from the number of bins, a bin corresponding to the first and second identifiers and the protocol.

Claim 18

The method of claim 10 , further comprising: searching a first of two secondary tables for an entry matching a key formed from the third index and the protocol, the first secondary table including a number of entries, each entry corresponding to a partially specified filter; and searching a second of the two secondary tables for an entry matching a key formed from the fourth index and the protocol, the second secondary table including a number of entries, each entry corresponding to a partially specified filter; wherein, if no match is found in the primary table, a matching entry in one of the two secondary tables will identify the corresponding bin.

Claim 19

The method of claim 16 , wherein, if no match is found in the primary table or either of the secondary tables, the corresponding bin comprises a default bin associated with an entire two-dimensional address space.

Claim 20

The method of claim 10 , further comprising: searching the source address data structure to find a fifth index associated with a wide filter having a source prefix matching the source address of the packet; searching the destination address data structure to find a sixth index associated with a wide filter having a destination prefix matching the destination address of the packet; forming a second key from the fifth index, the sixth index, and the protocol; and searching a wide filter table for an entry matching the second key, the wide filter table including a number of entries, each entry corresponding to a wide filter; wherein, if no match is found in the primary table, a matching entry the wide filter table will identify the corresponding bin.

Claim 21

The method of claim 18 , wherein each wide filter contained in the wide filter table comprises a fully specified filter having a number of indicator filters exceeding a specified threshold.

Claim 24

The apparatus of claim 20 , wherein the rule matching the at least one transport level field comprises a highest priority matching rule.

Claim 25

The apparatus of claim 20 , wherein the at least one transport level field of the packet includes a source port and a destination port, and wherein each rule of a bin includes a source port lower bound, a source port upper bound, a destination port lower bound, and a destination port upper bound.

Claim 26

The apparatus of claim 22 , wherein the classification circuit comprises: a first comparison circuit to compare the source port of the received packet with the source port lower and upper bounds of one of the rules; a second comparison circuit to compare the destination port of the received packet with the destination port lower and upper bounds of the rule; and an output circuit to output a match signal if a rule of the corresponding bin matches the source and destination ports of the received packet.

Claim 27

The apparatus of claim 23 , wherein the rule matches the source and destination ports of the received packet if: the source port of the received packet is greater than or equal to the source port lower bound of the rule and less than or equal to the source port upper bound of the rule; and the destination port of the received packet is greater than or equal to the destination port lower bound of the rule and less than or equal to the destination port upper bound of the rule.

Claim 28

The apparatus of claim 20 , wherein to identify a bin corresponding to a network path of a received packet, the processing system is programmed to perform operations including: identifying, from a number of entries in a data structure, an entry having a source address prefix matching the source address of the received 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 received packet, the matching entry including a second identifier; and identifying, from the number of bins, a bin corresponding to the first and second identifiers and the protocol.

Claim 29

The apparatus of claim 20 , wherein to identify a bin corresponding to a network path of a received packet, the processing system is programmed to perform operations further including: searching a first of two secondary tables for an entry matching a key formed from the third index and the protocol, the first secondary table including a number of entries, each entry corresponding to a partially specified filter; and searching a second of the two secondary tables for an entry matching a key formed from the fourth index and the protocol, the second secondary table including a number of entries, each entry corresponding to a partially specified filter; wherein, if no match is found in the primary table, a matching entry in one of the two secondary tables will identify the corresponding bin.

Claim 30

The apparatus of claim 26 , wherein, if no match is found in the primary table or either of the secondary tables, the corresponding bin comprises a default bin associated with an entire two-dimensional address space.

Claim 31

The apparatus of claim 20 , wherein to identify a bin corresponding to a network path of a received packet, the processing system is programmed to perform operations further including: searching the source address data structure to find a fifth index associated with a wide filter having a source prefix matching the source address of the packet; searching the destination address data structure to find a sixth index associated with a wide filter having a destination prefix matching the destination address of the packet; forming a second key from the fifth index, the sixth index, and the protocol; and searching a wide filter table for an entry matching the second key, the wide filter table including a number of entries, each entry corresponding to a wide filter; wherein, if no match is found in the primary table, a matching entry the wide filter table will identify the corresponding bin.

Claim 32

The apparatus of claim 28 , wherein each wide filter contained in the wide filter table comprises a fully specified filter having a number of indicator filters exceeding a specified threshold.

Claim 33

The apparatus of claim 20 , wherein the memory, the processing system, and the classification circuit comprise a single processing device.

Claim 36

The system of claim 31 , wherein the rule matching the at least one transport level field comprises a highest priority matching rule.

Claim 37

The system of claim 31 , wherein the at least one transport level field of the packet includes a source port and a destination port, and wherein each rule of a bin includes a source port lower bound, a source port upper bound, a destination port lower bound, and a destination port upper bound.

Claim 38

The system of claim 33 , wherein the classification circuit comprises: a first comparison circuit to compare the source port of the received packet with the source port lower and upper bounds of one of the rules; a second comparison circuit to compare the destination port of the received packet with the destination port lower and upper bounds of the rule; and an output circuit to output a match signal if a rule of the corresponding bin matches the source and destination ports of the received packet.

Claim 39

The system of claim 34 , wherein the rule matches the source and destination ports of the received packet if: the source port of the received packet is greater than or equal to the source port lower bound of the rule and less than or equal to the source port upper bound of the rule; and the destination port of the received packet is greater than or equal to the destination port lower bound of the rule and less than or equal to the destination port upper bound of the rule.

Claim 40

The system of claim 31 , wherein to identify a bin corresponding to a network path of a received packet, the processing engine is programmed to perform operations including: identifying, from a number of entries in a data structure, an entry having a source address prefix matching the source address of the received 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 received packet, the matching entry including a second identifier; and identifying, from the number of bins, a bin corresponding to the first and second identifiers and the protocol.

Claim 41

The system of claim 31 , wherein to identify a bin corresponding to a network path of a received packet, the processing engine is programmed to perform operations further including: searching a first of two secondary tables for an entry matching a key formed from the third index and the protocol, the first secondary table including a number of entries, each entry corresponding to a partially specified filter; and searching a second of the two secondary tables for an entry matching a key formed from the fourth index and the protocol, the second secondary table including a number of entries, each entry corresponding to a partially specified filter; wherein, if no match is found in the primary table, a matching entry in one of the two secondary tables will identify the corresponding bin.

Claim 42

The system of claim 37 , wherein, if no match is found in the primary table or either of the secondary tables, the corresponding bin comprises a default bin associated with an entire two-dimensional address space.

Claim 43

The system of claim 31 , wherein to identify a bin corresponding to a network path of a received packet, the processing engine is programmed to perform operations farther including: searching the source address data structure to find a fifth index associated with a wide filter having a source prefix matching the source address of the packet; searching the destination address data structure to find a sixth index associated with a wide filter having a destination prefix matching the destination address of the packet; forming a second key from the fifth index, the sixth index, and the protocol; and searching a wide filter table for an entry matching the second key, the wide filter table including a number of entries, each entry corresponding to a wide filter; wherein, if no match is found in the primary table, a matching entry the wide filter table will identify the corresponding bin.

Claim 44

The system of claim 39 , wherein each wide filter contained in the wide filter table comprises a fully specified filter having a number of indicator filters exceeding a specified threshold.

Claim 45

The system of claim 31 , wherein the memory comprises a static random access memory (SRAM).

Claim 46

An article of manufacture comprising: a computer-readable medium encoded with computer-executable instructions that, when accessed by a machine, causes the machine, to: identify, from a plurality of bins stored in a memory, a bin corresponding to a network path of a received packet, and farther corresponding to a protocol associated with the received packet, each of the bins including a number of rules; issue a command to a classification circuit, the command identifying the corresponding bin; copy the rules of the corresponding bin from the memory to the classification circuit, wherein the classification circuit compares at least one transport level field of the received packet with each of the rules and provides a match signal if a rule matches the at least one transport level field of the packet; in response to the match signal, apply an action associated with the matching rule to the received packet; and when identifying a bin corresponding to a network path of a received packet, to: search a source address data structure to find a first index and a third index, the first index associated with a filly 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; search a destination address data structure to find a second index and a fourth index, the second index associated with a filly 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; form a key from the first index, the second index, and the protocol; and search 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; wherein an entry of the primary table matching the key will identify the corresponding bin.

Claim 47

An article of manufacture comprising: a computer-readable medium encoded with computer-executable instructions that, when accessed by a machine, causes the machine, to: identify, from a plurality of bins stored in a memory, a bin corresponding to a network path of a received packet, and farther corresponding to a protocol associated with the received packet, each of the bins including a number of rules; issue a command to a classification circuit, the command identifying the corresponding bin; copy the rules of the corresponding bin from the memory to the classification circuit, wherein the classification circuit compares at least one transport level field of the received packet with each of the rules and provides a match signal if a rule matches the at least one transport level field of the packet; in response to the match signal, apply an action associated with the matching rule to the received packet; and when identifying a bin corresponding to a network path of a received packet, to: search a source address data structure to find a first index and a third index, the first index associated with a filly 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; search a destination address data structure to find a second index and a fourth index, the second index associated with a filly 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; form a key from the first index, the second index, and the protocol; and search 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; wherein an entry of the primary table matching the key will identify the corresponding bin.

Claim 48

The article of manufacture of claim 42 , wherein the matching rule comprises a highest priority matching rule.

Claim 49

The article of manufacture of claim 42 , wherein the at least one transport level field of the received packet comprises a source port and a destination port, and wherein each rule of a bin includes a source port lower bound, a source port upper bound, a destination port lower bound, and a destination port upper bound.

Claim 50

The article of manufacture of claim 44 , wherein a rule matches the at least one transport level field of the packet if: the source port of the received packet is greater than or equal to the source port lower bound of the rule and less than or equal to the source port upper bound of the rule; and the destination port of the received packet is greater than or equal to the destination port lower bound of the rule and less than or equal to the destination port upper bound of the rule.

Claim 51

The article of manufacture of claim 42 , wherein the computer-executable instructions, when accessed, further causes the machine, when identifying a bin corresponding to a network path of a received packet, to: identify, from a number of entries in a data structure, an entry having a source address prefix matching the source address of the received packet, the matching entry including a first identifier; identify, from a number of entries in another data structure, an entry having a destination address prefix matching the destination address of the received packet, the matching entry including a second identifier; and identify, from the number of bins, a bin corresponding to the first and second identifiers and the protocol.

Claim 52

The article of manufacture of claim 42 , wherein the computer-executable instructions, when accessed, further causes the machine to: search a first of two secondary tables for an entry matching a key formed from the third index and the protocol, the first secondary table including a number of entries, each entry corresponding to a partially specified filter; and search a second of the two secondary tables for an entry matching a key formed from the fourth index and the protocol, the second secondary table including a number of entries, each entry corresponding to a partially specified filter; wherein, if no match is found in the primary table, a matching entry in one of the two secondary tables will identify the corresponding bin.

Claim 53

The article of manufacture of claim 47 , wherein, if no match is found in the primary table or either of the secondary tables, the corresponding bin comprises a default bin associated with an entire two-dimensional address space.

Claim 54

The article of manufacture of claim 42 , wherein the computer-executable instructions, when accessed, further causes the machine to: search the source address data structure to find a fifth index associated with a wide filter having a source prefix matching the source address of the packet; search the destination address data structure to find a sixth index associated with a wide filter having a destination prefix matching the destination address of the packet; form a second key from the fifth index, the sixth index, and the protocol; and search a wide filter table for an entry matching the second key, the wide filter table including a number of entries, each entry corresponding to a wide filter; wherein, if no match is found in the primary table, a matching entry the wide filter table will identify the corresponding bin.

Claim 55

The article of manufacture of claim 49 , wherein each wide filter contained in the wide filter table comprises a fully specified filter having a number of indicator filters exceeding a specified threshold.