Abstract
In Software-Defined Networking (SDN), Ternary Content Access Memory (TCAM) is a scarce and expensive resource, providing only a few thousands of rule entries on a network switch. In this paper, we propose an algorithm under rule distribution scheme which allows switches in the network to share their TCAM resources in order to achieve better TCAM space utilization. Rule distribution scheme collects rules from network switches and redistributes the rule sets to network switches after partition the overall rules to rule sets. Our proposed algorithm mainly deals with the balanced rule partition problem, which is an NP-hard problem. We design a heuristic algorithm utilizing cover-set graph dependency and Fiduccia-Matheyses graph partition concept. We evaluate our algorithm by real world synthetic routing policy provided by ClassBench packet classification simulator. The result shows that our algorithm efficiently reduces the overall rule space overhead and balances the decomposed rule sets.