Partial Order Theory for Fast TCAM Updates

doi:10.1109/TNET.2017.2776565

	Partial Order Theory for Fast TCAM Updates
	He, Peng 1; Zhang, Wenyuan 2; Guan, Hongtao 1; Salamatian, Kave 3; Xie, Gaogang 1,2
	2018-02-01
发表期刊	IEEE-ACM TRANSACTIONS ON NETWORKING
ISSN	1063-6692
卷号	26 期号:1 页码:217-230
摘要	Ternary content addressable memories (TCAMs) are frequently used for fast matching of packets against a given ruleset. While TCAMs can achieve fast matching, they are plagued by high update costs that can make them unusable in a high churn rate environment. We present, in this paper, a systematic and in-depth analysis of the TCAM update problem. We apply partial order theory to derive fundamental constraints on any rule ordering on TCAMs, which ensures correct checking against a given ruleset. This theoretical insight enables us to fully explore the TCAM update algorithms design space, to derive the optimal TCAM update algorithm (though it might not be suitable to be used in practice), and to obtain upper and lower bounds on the performance of practical update algorithms. Having lower bounds, we checked if the smallest update costs are compatible with the churn rate observed in practice, and we observed that this is not always the case. We therefore developed a heuristic based on ruleset splitting, with more than a single TCAM chip, that achieves significant update cost reductions (1.05 similar to 11.3x) compared with state-of-the-art techniques.
关键词	Ternary content addressable memory (TCAM) update software-defined networking partial order theory
DOI	10.1109/TNET.2017.2776565
收录类别	SCI
语种	英语
资助项目	National Nature Science Foundation of China[61502458] ; National Nature Science Foundation of China[61725206] ; Natural Science Foundation of Beijing[4162057]
WOS研究方向	Computer Science ; Engineering ; Telecommunications
WOS类目	Computer Science, Hardware & Architecture ; Computer Science, Theory & Methods ; Engineering, Electrical & Electronic ; Telecommunications
WOS记录号	WOS:000425324000016
出版者	IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
引用统计	被引频次：34[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/6134
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Xie, Gaogang
作者单位	1.Chinese Acad Sci, Inst Comp Technol, State Key Lab Comp Architecture, Beijing 100190, Peoples R China 2.Univ Chinese Acad Sci, Dept Comp Sci, Beijing 100049, Peoples R China 3.Univ Savoie, F-74016 Annecy Le Vieux, France
推荐引用方式 GB/T 7714	He, Peng,Zhang, Wenyuan,Guan, Hongtao,et al. Partial Order Theory for Fast TCAM Updates[J]. IEEE-ACM TRANSACTIONS ON NETWORKING,2018,26(1):217-230.
APA	He, Peng,Zhang, Wenyuan,Guan, Hongtao,Salamatian, Kave,&Xie, Gaogang.(2018).Partial Order Theory for Fast TCAM Updates.IEEE-ACM TRANSACTIONS ON NETWORKING,26(1),217-230.
MLA	He, Peng,et al."Partial Order Theory for Fast TCAM Updates".IEEE-ACM TRANSACTIONS ON NETWORKING 26.1(2018):217-230.