Cost minimization for rule caching in software defined networking

Huawei Huang, Song Guo, Peng Li, Weifa Liang, Albert Y. Zomaya

Research output: Journal article publicationJournal articleAcademic researchpeer-review

52 Citations (Scopus)


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.
Original languageEnglish
Article number7105417
Pages (from-to)1007-1016
Number of pages10
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number4
Publication statusPublished - 1 Apr 2016
Externally publishedYes


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

ASJC Scopus subject areas

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'Cost minimization for rule caching in software defined networking'. Together they form a unique fingerprint.

Cite this