Tongxin xuebao (May 2017)
Information entropy based match field cutting algorithm
Abstract
With the increasing diversity of network functions,packet classification had a higher demand on the number of match fields and depth of match table,which placed a severe burden on the storage capacity of hardware.To ensure the efficiency of matching process while at the same time improve the usage of storage devices,an information entropy based cutting algorithm on match fields was proposed.By the analysis on the redundancy of match fields and distribution pattern in a rule set,a match field cutting model was proposed.With the mapping of matching process to the process of entropy reduction,the complexity of optimal match field cutting was reduced from NP-hard to linear complexity.Experiment results show that compared to existing schemes,this scheme can need 40% less TCAM storage space,and on the other side,with the growing of table size,the time complexity of this algorithm is also far less than other algorithms.
