Cost minimization for rule caching in software defined networking

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

48 Scopus Citations
View graph of relations



Original languageEnglish
Article number7105417
Pages (from-to)1007-1016
Journal / PublicationIEEE Transactions on Parallel and Distributed Systems
Issue number4
Publication statusPublished - 1 Apr 2016
Externally publishedYes


Software-defined networking (SDN) is an emerging network paradigm that simplifies network management by decoupling the control plane and data plane, such that switches become simple data forwarding devices and network management is controlled by logically centralized servers. In SDN-enabled networks, network flow is managed by a set of associated rules that are maintained by switches in their local Ternary Content Addressable Memories (TCAMs) which support high-speed parallel lookup on wildcard patterns. Since TCAM is an expensive hardware and extremely power-hungry, each switch has only limited TCAM space and it is inefficient and even infeasible to maintain all rules at local switches. On the other hand, if we eliminate TCAM occupation by forwarding all packets to the centralized controller for processing, it results in a long delay and heavy processing burden on the controller. In this paper, we strive for the fine balance between rule caching and remote packet processing by formulating a minimum weighted flow provisioning ( MWFP) problem with an objective of minimizing the total cost of TCAM occupation and remote packet processing. We propose an efficient offline algorithm if the network traffic is given, otherwise, we propose two online algorithms with guaranteed competitive ratios. Finally, we conduct extensive experiments by simulations using real network traffic traces. The simulation results demonstrate that our proposed algorithms can significantly reduce the total cost of remote controller processing and TCAM occupation, and the solutions obtained are nearly optimal.

Research Area(s)

  • Approximation Algorithm, Software-Defined Networking, Ternary Content Addressable Memories

Bibliographic Note

Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to

Citation Format(s)

Cost minimization for rule caching in software defined networking. / Huang, Huawei; Guo, Song; Li, Peng; Liang, Weifa; Zomaya, Albert Y.

In: IEEE Transactions on Parallel and Distributed Systems, Vol. 27, No. 4, 7105417, 01.04.2016, p. 1007-1016.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review