RuleTris: Minimizing Rule Update Latency for TCAM-Based SDN Switches

Xitao Wen, Bo Yang, Yan Chen, Li Erran Li, Kai Bu, Peng Zheng, Yang Yang, Chengchen Hu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

58 Scopus citations


Software-defined network (SDN) is deemed to enable more dynamic management of data center networks that promptly respond to network events with changes in network policies. Although the SDN controller architecture is increasingly optimized for swift policy updates, the data plane, especially the prevailing TCAM-based flow tables on physical SDN switches, remains unoptimized for fast rule updates, and is gradually becoming the primary bottleneck along the policy update pipeline. In this paper, we present RuleTris, the first SDN update optimization framework that minimizes rule update latency for TCAM-based switches. RuleTris employs the dependency graph (DAG) as the key abstraction to minimize the update latency. RuleTris efficiently obtains the DAGs with novel dependency preserving algorithms that incrementally build rule dependency along with the compilation process. Then, in the guidance of the DAG, RuleTris optimizes the rule updates in TCAM to avoid unnecessary entry moves, which are the main cause of TCAM update inefficiency. We prove that RuleTris generates TCAM updates with the minimum number of TCAM entry moves. In evaluation, RuleTris achieves a median of <12ms and 90-percentile of <15ms the end-to-end per-rule update latency on our hardware prototype, outperforming the state-of-the-art composition compiler CoVisor by 20 times.

Original languageEnglish (US)
Title of host publicationProceedings - 2016 IEEE 36th International Conference on Distributed Computing Systems, ICDCS 2016
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages10
ISBN (Electronic)9781509014828
StatePublished - Aug 8 2016
Event36th IEEE International Conference on Distributed Computing Systems, ICDCS 2016 - Nara, Japan
Duration: Jun 27 2016Jun 30 2016

Publication series

NameProceedings - International Conference on Distributed Computing Systems


Other36th IEEE International Conference on Distributed Computing Systems, ICDCS 2016


  • Software-defined networks
  • TCAM update
  • policy update

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Hardware and Architecture
  • Software


Dive into the research topics of 'RuleTris: Minimizing Rule Update Latency for TCAM-Based SDN Switches'. Together they form a unique fingerprint.

Cite this