Efficient packet classification for dynamic containers

Abstract

A novel algorithm for packet classification that is based on a novel search structure for packet classification rules is provided. Addresses from all the containers are merged and maintained in a single Trie. Each entry in the Trie has additional information that can be traced back to the container from where the address originated. This information is used to keep the Trie in sync with the containers when the container definition dynamically changes.

1 - 20 . (canceled) 
     
     
         21 . A method for performing a network operation on a packet, the method comprising:
 using at least two different attributes associated with the packet to identify at least two different set of potentially-match rules for the network operation;   selecting, from the identified sets of rules, one rule as a rule that matches the packet;   performing a network operation on the packet based on the selected rule.   
     
     
         22 . The method of  claim 21 , wherein the two different attributes comprise two header values of the packet. 
     
     
         23 . The method of  claim 22 , wherein the two header values comprise source and destination IP (Internet Protocol) addresses of the packet. 
     
     
         24 . The method of  claim 22 , wherein the two header values comprise an IP (Internet Protocol) address and a port address of the packet. 
     
     
         25 . The method of  claim 22 , wherein the two header values comprise a protocol value and an address value from a header of the packet. 
     
     
         26 . The method of  claim 21 , wherein selecting the matching rule comprises
 combining the two sets of rules in a sorted list of rules that is ordered according to a rule priority value;   iteratively examining, according to the sorted order, each rule in the list until the matching rule is identified.   
     
     
         27 . The method of  claim 21 , wherein using the attributes comprises using a particular attribute to identify an identifier of a container that stores a plurality of packet attributes. 
     
     
         28 . The method of  claim 27 , wherein selecting one rule comprises using the container identifier to perform match operations that try to match the container identifier with one or more container identifiers specified as match criterion by one or more potentially-matching rules. 
     
     
         29 . The method of  claim 21 , wherein using the attributes comprises using the attributes to search a data structure that identifies one set of rules for each attribute that comprises one or more rules with each rule using the attribute as a match criterion in the rule. 
     
     
         30 . The method of  claim 21 , wherein using the attributes comprises using the attributes to search a tree or trie data structure that identifies one set of rules for each attribute. 
     
     
         31 . A non-transitory machine readable medium storing a program for performing a network operation on a packet, the program for execution by at least one processing unit, the program comprising sets of instructions for:
 using at least two different attributes associated with the packet to identify at least two different set of potentially-match rules for the network operation;   selecting, from the identified sets of rules, one rule as a rule that matches the packet;   performing a network operation on the packet based on the selected rule.   
     
     
         32 . The non-transitory machine readable medium of  claim 21 , wherein the two different attributes comprise two header values of the packet. 
     
     
         33 . The non-transitory machine readable medium of  claim 22 , wherein the two header values comprise source and destination IP (Internet Protocol) addresses of the packet. 
     
     
         34 . The non-transitory machine readable medium of  claim 22 , wherein the two header values comprise an IP (Internet Protocol) address and a port address of the packet. 
     
     
         35 . The non-transitory machine readable medium of  claim 22 , wherein the two header values comprise a protocol value and an address value from a header of the packet. 
     
     
         36 . The non-transitory machine readable medium of  claim 21 , wherein the set of instructions for selecting the matching rule comprises sets of instructions for
 combining the two sets of rules in a sorted list of rules that is ordered according to a rule priority value;   iteratively examining, according to the sorted order, each rule in the list until the matching rule is identified.   
     
     
         37 . The non-transitory machine readable medium of  claim 21 , wherein the set of instructions for using the attributes comprises a set of instructions for using a particular attribute to identify an identifier of a container that stores a plurality of packet attributes. 
     
     
         38 . The non-transitory machine readable medium of  claim 26 , wherein the set of instructions for selecting one rule comprises a set of instructions for using the container identifier to perform match operations that try to match the container identifier with one or more container identifiers specified as match criterion by one or more potentially-matching rules. 
     
     
         39 . The non-transitory machine readable medium of  claim 21 , wherein the set of instructions for using the attributes comprises a set of instructions for using the attributes to search a data structure that identifies one set of rules for each attribute that comprises one or more rules with each rule using the attribute as a match criterion in the rule. 
     
     
         40 . The non-transitory machine readable medium of  claim 21 , wherein the set of instructions for using the attributes comprises a set of instructions for using the attributes to search a tree or trie data structure that identifies one set of rules for each attribute.