FastUp: Fast TCAM update for SDN switches in datacenter networks

Wan，Ying1; Song，Haoyu2; Che，Hao3; Xu，Yang4; Wang，Yi5; Zhang，Chuwen1; Wang，Zhijun3; Pan，Tian8; Li，Hao7; Jiang，Hong3; Hu，Chengchen6,7; Liu，Bin1

10.1109/ICDCS51616.2021.00089

2021-07-01

41st IEEE International Conference on Distributed Computing Systems (ICDCS)

1063-6927

978-1-6654-4514-6

Proceedings - International Conference on Distributed Computing Systems

2021-July

887-897

JUL 07-10, 2021

null,null,ELECTR NETWORK

10662 LOS VAQUEROS CIRCLE, PO BOX 3014, LOS ALAMITOS, CA 90720-1264 USA

IEEE COMPUTER SOC

TCAM is widely used for flow table lookup in Software-Defined Networking (SDN) switches for datacenter and enterprise networks. While its lookup throughput is unparalleled, TCAM updating, particularly for new rule insertions, can impair the overall system performance. A rule insertion entails two steps: 1) Computing the rule moving operations; and 2) Interrupting the TCAM lookups to apply the operations. In previous work, the performance gain on one step is always at the expense of the performance loss on the other. However, update throughput and latency depend on both. In this paper, we present a faster and more balanced TCAM update scheme, which not only achieves the shortest interrupt time so far but also significantly reduces the computation time. By using a novel sequential stack, FastUp reduces the time and space complexity of the state-of-the-art schemes from $O(m^{2})$ and $O(m)$ to $O(m\log h)$ and $O(h)$, respectively, where $h << m$. Evaluations show that FastUp shortens the computation time and the interrupt time by $100\times$ and $1.6\times$, respectively, which is equivalent to update delay ${15\times}$ reduction and $\mathbf{10\times}$ update throughput gain against the state-of-the-art schemes. Moreover, we debunk a common mistake and show the dynamic programming based algorithm cannot be used to solve the reorder problem, and instead we use a bidirectional rule moving method to address the problem. In addition, we propose a practical method to find the theoretical lower bound of interrupt time in relatively large TCAM, which can be used to evaluate the optimality degree of TCAM update schemes. Evaluations show that FastUp achieves 90 % optimality.

Degree of optimization Hardware implementation SDN switch in cloud datacenters TCAM update algorithm

其他

英语

CPCI-S ; EI

Guangdong Basic and Applied Basic Research Foundation[2019B1515120031] ; National Natural Science Foundation of China[62032013,61872213,61432009,"LZC0019"]

Computer Science

Computer Science, Hardware & Architecture ; Computer Science, Information Systems ; Computer Science, Software Engineering ; Computer Science, Theory & Methods

WOS:000728379200080

20214211032608

Dynamic programming ; Ternary content adressable memory

Data Storage, Equipment and Techniques:722.1 ; Computer Programming:723.1 ; Optimization Techniques:921.5

2-s2.0-85117122597

Scopus

1.Tsinghua University,China
2.Futurewei Technologies,United States
3.University of Texas at Arlington,United States
4.Fudan University,China
5.Southern University of Science and Technology,China
6.Xilinx,Singapore,Singapore
7.Xi'An Jiaotong University,China
8.Beijing University of Posts and Telecommunications,China

Wan，Ying,Song，Haoyu,Che，Hao,et al. FastUp: Fast TCAM update for SDN switches in datacenter networks[C]. 10662 LOS VAQUEROS CIRCLE, PO BOX 3014, LOS ALAMITOS, CA 90720-1264 USA:IEEE COMPUTER SOC,2021:887-897.