Cache Dependent Rules With Size-Limited Flow Table in Software-Defined Networking

To address the contradiction between insufficient flow table space and increasing data communication, we focus on improving the caching efficiency with size-limited flow table. As the matching fields of rules with different priorities may overlap, caching entries with lower priorities may result in processing packets with an incorrect action. Thus, entries cached in flow table need to be carefully selected complying with dependencies among rules. Existing approaches usually use heuristic algorithms by considering the local dependencies to select rules to be stored in flow tables. In this paper, we propose a global-local combined optimizing algorithm to determine the caching entries which further rises the cache hit ratio. The algorithm computes a local bundle of rules with maximum cache hit probability, and then combines the bundles with an adapted knapsack algorithm to obtain the global optimized set of rules. The evaluation results show that our algorithm always achieves better cache utilization and improves 5% cache hit ratio than existing approaches.