Efficient TCAM Rules Distribution Algorithms in Software-Defined Networking

Jang Ping Sheu, Woan Tyng Lin, Guey Yun Chang

Research output: Contribution to journalArticlepeer-review

23 Scopus citations


In software-defined networking (SDN), network rules are installed in ternary content-addressable memory (TCAM). TCAM is a scarce and expensive resource which is a bottleneck for scaling SDN. Rule distribution is a strategy to solve the TCAM shortage problem, which decomposes a large table stored at network ingress into a number of smaller sub-tables and distributes them across network switches. Rule distribution includes two sub-problems, sub-table allocation, and table decomposition. Sub-table allocation is to guarantee that each flow path passes all the partitioned sub-tables and maximize the number of partitioned sub-tables (for reducing the size of sub-tables). Table decomposition problem is to partition a large rule table into a number of balanced sub-tables and reduce the rules overhead. In this paper, we propose a sub-table allocation algorithm and size-balancing sub-table partition algorithm. Simulation results show that the performance of both algorithms is better than previous works in terms of reducing the TCAM entries used in each switch.

Original languageEnglish
Pages (from-to)854-865
Number of pages12
JournalIEEE Transactions on Network and Service Management
Issue number2
StatePublished - Jun 2018


  • Rule distribution
  • software-defined networking
  • ternary content-addressable memory


Dive into the research topics of 'Efficient TCAM Rules Distribution Algorithms in Software-Defined Networking'. Together they form a unique fingerprint.

Cite this