Method and apparatus for matching flow table, and switch

Abstract

A method and an apparatus for matching a flow table, and a switch are provided. An exact match entry and a wildcard entry that are in each flow entry are stored separately, the exact match entry is stored in a memory, the wildcard entry is stored in a TCAM, and an index value index is used to represent the exact match entry, so that the wildcard entry uses less TCAM resources, thereby increasing utilization of the TCAM; and a proper searching algorithm is used to separately perform matching on the exact match entry and the wildcard entry, which increases a searching speed.

What is claimed is: 
     
         1 . A method for storing a flow entry in a flow table, wherein the flow entry comprises at least one exact match field and at least one wildcard match field, and the flow table comprises an exact match flow table and a wildcard match flow table, the method comprising:
 extracting, by a switch, the at least one exact match field in the flow entry, and matching the at least one exact match field with exact match entries in the exact match flow table;   creating, by the switch, an exact match entry in the exact match flow table, and storing the at least one exact match field in the exact match entry of the exact match flow table, and allocating an index value to the exact match entry when the matching fails;   acquiring, by the switch, an index value corresponding to the exact match entry of the exact match flow table when the matching succeeds;   extracting, by the switch, the at least one wildcard match field in the flow entry;   creating, by the switch, a wildcard entry in the wildcard match flow table, and storing the at least one wildcard match field in the wildcard entry; and   storing, by the switch, the index value in the index field of the wildcard entry.   
     
     
         2 . The method according to  claim 1 , further comprising:
 setting a valid time for a first wildcard entry in the wildcard match flow table; and   when the valid time elapses, deleting both the first wildcard entry and at least one exact match entry that is corresponding to a first index value in the index field of the first wildcard entry, if the first index value stored in the first wildcard entry is different from a second index value stored in another wildcard entry.   
     
     
         3 . The method according to  claim 2 , further comprising:
 when the valid time elapses, deleting the first wildcard entry if the first index value stored in the first wildcard entry is the same as an index value stored in another wildcard entry.   
     
     
         4 . A method for matching a flow table, wherein the flow table comprises an exact match flow table and a wildcard match flow table, the exact match flow table comprises one or more exact match entries, each exact match entry comprises at least one exact match field, each exact match entry corresponds to one index value, the wildcard match flow table comprises one or more wildcard entries, each wildcard entry comprises at least one wildcard field and one index field that is used for storing the index value, and an exact match entry and a wildcard entry that are associated by using the index value form a flow entry, the method comprising:
 acquiring at least two match data field in a received packet, wherein the at least two match data field comprises at least one exact match data field and at least one wildcard data field;   matching the at least one exact match data field in the packet with the at least one exact match field of each exact match entry in the exact match flow table, and if the matching succeeds, acquiring an index value corresponding to the exact match entry;   matching the at least one wildcard data field in the packet with the at least one wildcard field of each wildcard entry in the wildcard match flow table according to the index value; and   obtaining a matching result.   
     
     
         5 . The method according to  claim 4 , wherein matching the at least one exact match data field in the packet with the at least one exact match field of each exact match entry in the exact match flow table comprises:
 matching the at least one exact match data field in the packet with the at least one exact match field of each exact match entry in the exact match flow table by using a HASH algorithm.   
     
     
         6 . The method according to  claim 4 , further comprising:
 setting a valid time for a first wildcard entry in the wildcard match flow table; and   when the valid time elapses, deleting both the first wildcard entry and at least one exact match entry that is corresponding to a first index value in the index field of the first wildcard entry, if the first index value stored in the first wildcard entry is different from a second index value stored in another wildcard entry.   
     
     
         7 . The method according to  claim 6 , further comprising:
 when the valid time elapses, deleting the first wildcard entry if the first index value stored in the first wildcard entry is the same as an index value stored in another wildcard entry.   
     
     
         8 . A switch, comprising:
 a memory and a ternary content-addressable memory;   a flow table comprising an exact match flow table and a wildcard match flow table, wherein:
 the exact match flow table is stored in the memory and the wildcard match flow table is stored in the ternary content-addressable memory, 
 the exact match flow table comprises one or more exact match entries, wherein each exact match entry comprises at least one exact match field and corresponds to one index value, 
 the wildcard match flow table comprises one or more wildcard entries, and each wildcard entry comprises at least one wildcard field and one index field that is used for storing the index value, and 
 an exact match entry and a wildcard entry that are associated by using the index value form a flow entry; and 
   a processor, configured to:
 acquire at least two match data field in a received packet, wherein the at least two match data field comprises at least one exact match data field and at least one wildcard data field, 
 match the at least one exact match data field in the packet with the at least one exact match field of each exact match entry in the exact match flow table, and if the matching succeeds, acquiring an index value corresponding to the exact match entry, 
 match the at least one wildcard data field in the packet with the at least one wildcard field of each wildcard entry in the wildcard match flow table according to the index value, and 
 obtain a matching result. 
   
     
     
         9 . The switch according to  claim 8 , wherein the processor is further configured to:
 match the at least one exact data match field in the packet with the at least one exact match field of each exact match entry in the exact match flow table by using a HASH algorithm.   
     
     
         10 . The switch according to  claim 8 , wherein the processor is further configured to:
 set a valid time for a first wildcard entry in the wildcard match flow table; and   when the valid time elapses, delete both the first wildcard entry and at least one exact match entry that is corresponding to a first index value in the index field of the first wildcard entry, if the first index value stored in the first wildcard entry is different from a second index value stored in another wildcard entry.   
     
     
         11 . The switch according to  claim 10 , wherein the processor is further configured to:
 when the valid time elapses, delete the first wildcard entry if the first index value stored in the first wildcard entry is the same as an index value stored in another wildcard entry.