Hierarchical self-organizing classification processing in a network switch

Abstract

Described embodiments process data packets received by a switch coupled to a network processor. The switch determines whether one or more rules for classifying and processing the received packet are stored in an internal classification database of the switch. If one or more rules are stored in the internal database, the switch updates statistics corresponding to each of the rules and classifies and processes the received packet in accordance with the rules. If no associated rules are stored in the internal database, the switch tags the received packet with metadata and forwards the packet to the network processor. The network processor determines one or more rules for classifying and processing the forwarded packet in a classification database of the network processor and updates statistics corresponding to each rule. The network processor classifies and processes the packet in accordance with the rules and updates the internal database of the switch.

I claim: 
     
       1. A method of processing data packets received by a network switch coupled to a network processor, the method comprising:
 determining, by the network switch, whether one or more associated rules for classifying and processing the received packet are stored in an internal classification database of the network switch; 
 if one or more associated rules are stored in the internal classification database:
 updating statistics data of the network switch corresponding to each of the one or more associated rules; and 
 classifying and processing, by the network switch, the received packet in accordance with the one or more associated rules; 
 
 otherwise, if no associated rules are stored in the internal classification database:
 tagging, by the network switch, the received packet with metadata; 
 forwarding, by the network switch, the packet to the network processor; 
 determining, by the network processor, one or more associated rules for classifying and processing the forwarded packet in a classification database of the network processor; 
 updating statistics data of the network processor corresponding to each of the one or more associated rules in the classification database of the network processor; 
 classifying and processing, by the network processor, the forwarded packet in accordance with the one or more associated rules in the classification database of the network processor; and 
 updating, by the network processor, the internal classification database of the network switch. 
 
 
     
     
       2. The method of  claim 1 , wherein the step of updating, by the network processor, the internal classification database of the network switch comprises:
 providing the statistics data of the network switch to the network processor; 
 determining, by a control processor of the network processor, based on the statistics data of the network switch and the statistics data of the network processor, whether the internal classification database of the network switch should be updated and, if so:
 generating, by the network processor, an updated database for the network switch; 
 transferring, by the network processor to the network switch, the updated database; 
 storing, by the network switch, the updated database in the internal classification database; and 
 maintaining, by the network processor, packet ordering based on the corresponding tagged metadata. 
 
 
     
     
       3. The method of  claim 2 , wherein the metadata comprises at least one of a timestamp and a packet sequence number corresponding to a flow of the packet. 
     
     
       4. The method of  claim 2 , wherein the step of maintaining, by the network switch, packet ordering based on the corresponding tagged metadata comprises:
 determining, by the network processor, whether the tagged metadata of a packet most recently processed by the network processor matches metadata of a last packet of the corresponding flow forwarded by the network switch to the network processor and, if so:
 determining whether the step of storing the updated database in the internal classification database is complete and, if so:
 processing packets for the flow by the network switch; 
 
 otherwise, if the step of storing the updated database in the internal classification database is incomplete:
 continuing to process packets for the flow by the network processor; 
 
 
 if the tagged metadata of a packet most recently processed by the network processor does not match metadata of a last packet of the corresponding flow forwarded by the network switch to the network processor:
 continuing to process packets for the flow by the network processor. 
 
 
     
     
       5. The method of  claim 2 , wherein the statistics data of the network switch and the statistics data of the network processor each comprise a counter corresponding to each rule in the corresponding classification database, the method further comprising:
 incrementing each counter corresponding with a rule associated with the received packet. 
 
     
     
       6. The method of  claim 2 , further comprising:
 performing, periodically in time, the step of updating the internal classification database of the network switch; and 
 resetting, periodically in time, the statistics data of the network switch and the statistics data of the network processor. 
 
     
     
       7. The method of  claim 2  wherein the step of updating the internal classification database of the network switch is performed after a predetermined number of packets are classified and processed by at least one of the network switch and the network processor. 
     
     
       8. The method of  claim 2  wherein the step of determining, by a control processor of the network processor, based on the statistics data of the network switch and the statistics data of the network processor, whether the internal classification database of the network switch should be updated further comprises:
 determining, based on the statistics data, whether one or more classification rules should be updated at certain times of operation of the network switch. 
 
     
     
       9. The method of  claim 8 , wherein the certain times of operation of the network switch comprise at least one of: time of day and day of week. 
     
     
       10. The method of  claim 1 , wherein:
 the network switch comprises an Ethernet switch; and 
 the network processor comprises a plurality of processing modules and at least one shared memory, the processing modules configured to:
 generate one or more tasks corresponding to each packet received by the network processor; 
 send the tasks between processing modules over one or more unidirectional ring buses, each ring bus coupled between two adjacent processing modules. 
 
 
     
     
       11. A non-transitory machine-readable medium, having encoded thereon program code, wherein, when the program code is executed by a machine, the machine implements a method of processing data packets received by a network switch coupled to a network processor, the method comprising:
 determining, by the network switch, whether one or more associated rules for classifying and processing the received packet are stored in an internal classification database of the network switch; 
 if one or more associated rules are stored in the internal classification database:
 updating statistics data of the network switch corresponding to each of the one or more associated rules; and 
 classifying and processing, by the network switch, the received packet in accordance with the one or more associated rules; 
 
 otherwise, if no associated rules are stored in the internal classification database:
 tagging, by the network switch, the received packet with metadata; 
 forwarding, by the network switch, the packet to the network processor; 
 determining, by the network processor, one or more associated rules for classifying and processing the forwarded packet in a classification database of the network processor; 
 updating statistics data of the network processor corresponding to each of the one or more associated rules in the classification database of the network processor; 
 classifying and processing, by the network processor, the forwarded packet in accordance with the one or more associated rules in the classification database of the network processor; and 
 updating, by the network processor, the internal classification database of the network switch. 
 
 
     
     
       12. The non-transitory machine-readable medium of  claim 11 , wherein the step of updating, by the network processor, the internal classification database of the network switch comprises:
 providing the statistics data of the network switch to the network processor; 
 determining, by a control processor of the network processor, based on the statistics data of the network switch and the statistics data of the network processor, whether the internal classification database of the network switch should be updated and, if so:
 generating, by the network processor, an updated database for the network switch; 
 transferring, by the network processor to the network switch, the updated database; 
 storing, by the network switch, the updated database in the internal classification database; and 
 maintaining, by the network processor, packet ordering based on the corresponding tagged metadata. 
 
 
     
     
       13. The non-transitory machine-readable medium of  claim 12 , wherein the step of maintaining, by the network switch, packet ordering based on the corresponding tagged metadata comprises:
 determining, by the network processor, whether the tagged metadata of a packet most recently processed by the network processor matches metadata of a last packet of the corresponding flow forwarded by the network switch to the network processor and, if so:
 determining whether the step of storing the updated database in the internal classification database is complete and, if so:
 processing packets for the flow by the network switch; 
 
 otherwise, if the step of storing the updated database in the internal classification database is incomplete:
 continuing to process packets for the flow by the network processor; 
 
 
 if the tagged metadata of a packet most recently processed by the network processor does not match metadata of a last packet of the corresponding flow forwarded by the network switch to the network processor:
 continuing to process packets for the flow by the network processor, 
 
 wherein the metadata comprises at least one of a timestamp and a packet sequence number corresponding to a flow of the packet. 
 
     
     
       14. The non-transitory machine-readable medium of  claim 12 , wherein the statistics data of the network switch and the statistics data of the network processor each comprise a counter corresponding to each rule in the corresponding classification database, the method further comprising:
 incrementing each counter corresponding with a rule associated with the received packet. 
 
     
     
       15. The non-transitory machine-readable medium of  claim 12 , further comprising:
 performing, periodically in time, the step of updating the internal classification database of the network switch; and 
 resetting, periodically in time, the statistics data of the network switch and the statistics data of the network processor. 
 
     
     
       16. The non-transitory machine-readable medium of  claim 12  wherein the step of updating the internal classification database of the network switch is performed after a predetermined number of packets are classified and processed by at least one of the network switch and the network processor. 
     
     
       17. The non-transitory machine-readable medium of  claim 12  wherein the step of determining, by a control processor of the network processor, based on the statistics data of the network switch and the statistics data of the network processor, whether the internal classification database of the network switch should be updated further comprises:
 determining, based on the statistics data, whether one or more classification rules should be updated at certain times of operation of the network switch, wherein the certain times of operation of the network switch comprise at least one of: time of day and day of week. 
 
     
     
       18. The non-transitory machine-readable medium of  claim 11 , wherein:
 the network switch comprises an Ethernet switch; and 
 the network processor comprises a plurality of processing modules and at least one shared memory, the processing modules configured to:
 generate one or more tasks corresponding to each packet received by the network processor; 
 send the tasks between processing modules over one or more unidirectional ring buses, each ring bus coupled between two adjacent processing modules. 
 
 
     
     
       19. A system comprising:
 a network switch coupled to a network and a network processor; 
 the network switch configured to:
 receive a packet from the network; 
 determine whether one or more associated rules for classifying and processing the received packet are stored in an internal classification database of the network switch; 
 if one or more associated rules are stored in the internal classification database:
 update statistics data of the network switch corresponding to each of the one or more associated rules; and 
 classify and process the received packet in accordance with the one or more associated rules; 
 
 otherwise, if no associated rules are stored in the internal classification database:
 tag the received packet with metadata; and 
 forward the packet to the network processor; 
 
 
 the network processor configured to:
 determine one or more associated rules for classifying and processing the forwarded packet in a classification database of the network processor; 
 update statistics data of the network processor corresponding to each of the one or more associated rules in the classification database of the network processor; 
 classify and process the forwarded packet in accordance with the one or more associated rules in the classification database of the network processor; 
 wherein the network processor is configured to update the internal classification database of the network switch by:
 retrieving the statistics data of the network switch; 
 determining, based on the statistics data of the network switch and the statistics data of the network processor, whether the internal classification database of the network switch should be updated and, if so:
 generating an updated database for the network switch; 
 transferring the updated database to the network switch; and 
 maintaining packet ordering based on the corresponding tagged metadata. 
 
 
 
 
     
     
       20. The system of  claim 19 , wherein:
 the network processor is further configured to determine whether the tagged metadata of a packet most recently processed by the network processor matches metadata of a last packet of the corresponding flow forwarded by the network switch to the network processor and, if so:
 determine whether the updated database is stored in the internal classification database and, if so:
 the network switch is configured to process packets for the flow; 
 
 otherwise, if the updated database is not stored in the internal classification database:
 the network processor continues processing packets for the flow; 
 
 
 if the tagged metadata of a packet most recently processed by the network processor does not match metadata of a last packet of the corresponding flow forwarded by the network switch to the network processor:
 the network processor continues processing packets for the flow.