Partial Order Theory for Fast TCAM Updates

doi:10.1109/TNET.2017.2776565

CORC > 计算技术研究所 > 中国科学院计算技术研究所 > 中国科学院计算技术研究所期刊论文 > 英文

	Partial Order Theory for Fast TCAM Updates
	He, Peng 2; Zhang, Wenyuan 1; Guan, Hongtao 2; Salamatian, Kave 3; Xie, Gaogang 1,2
刊名	IEEE-ACM TRANSACTIONS ON NETWORKING
	2018-02-01
卷号	26 期号:1 页码:217-230
关键词	Ternary content addressable memory (TCAM) update software-defined networking partial order theory
ISSN号	1063-6692
DOI	10.1109/TNET.2017.2776565
英文摘要	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.
资助项目	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
语种	英语
出版者	IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
WOS记录号	WOS:000425324000016
内容类型	期刊论文
源URL	[http://119.78.100.204/handle/2XEOYT63/6133]
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Xie, Gaogang
作者单位	1.Univ Chinese Acad Sci, Dept Comp Sci, Beijing 100049, Peoples R China 2.Chinese Acad Sci, Inst Comp Technol, State Key Lab Comp Architecture, Beijing 100190, 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.