Reducing Update Cost of TCAM-Based Flow Table

In Software-Defined Networking(SDN), traffic forwarding delay depends on the latency of flow table updating. With increasing fined-grained flow control requirements, more and more frequent operations occur in flow tables inserting or removing forwarding rules. Meanwhile, the matching fields of the rules may overlap, which implies dependency relationships among rules. The dependencies impose restrictions on forwarding rules during updating, e.g., updating order, storage locations of rules, especially in the TCAM-based flow table. Otherwise, mismatching or packet dropping will occur. It usually takes a while to resolve and maintain dependencies during updating, which hinder forwarding efficiency. In this paper, we propose an updating algorithm for TCAM-based flow table to reduce update delay of dependent rules. We first propose and prove an optimal moving chain for a single rule update with the minimum moving steps, and then design a heuristic approach to update concurrent rules dynamically. We evaluate our flow table updating algorithm with different dependency complexities, and the results show that our updating approach achieves about 6% less moving steps than existing approaches.