多单元散列表与TCAM结合的OpenFlow流表查找方法

doi:10.11959/j.issn.1000-436x.2016204

摘要/Abstract

摘要：

在OpenFlow网络中，交换机通过标准化的接口接受基于流的规则，执行基于流的报文处理。流表的查找是OpenFlow交换机的核心功能，TCAM以其优异的性能广泛用于OpenFlow流表的查找，然而基于TCAM的OpenFlow流表查找具有较高的成本与能耗。为了降低流表查找的成本与能耗，提出了多单元散列表与TCAM结合的OpenFlow流表存储与查找的方法。通过理论分析与仿真测试，给出了查找结构成本优化后的散列表、TCAM的容量配置；在该配置下，Hash-TCAM流表查找结构比单纯使用TCAM的方案节约90%以上的成本，有效降低了能耗，同时保持了相近的查找性能。

关键词: OpenFlow, 三态内容寻址存储器, 散列表, 流表

Abstract:

In OpenFlow networks,switches accept flow rules through standardized interfaces,and perform flow-based packet processing.To facilitate the lookup of flow tables,TCAM has been widely used in OpenFlow switches.However,TCAM is expensive and consumes a large amount of power.A hybrid lookup scheme integrating multiple-cell Hash table with TCAM was proposed for flow table matching to simultaneously reduce the cost and power consumption of lookup structure without sacrificing the lookup performance.By theoretical analysis and extensive experiments,optimal capacity configuration of Hash table and TCAM was achieved with the optimized cost of flow table lookup.The experiment results also show that the proposed lookup scheme can save over 90% cost and the power consumption of flow table matching can be reduced significantly compared with the pure TCAM scheme while keeping the similar lookup performance.

Key words: OpenFlow, ternary content addressable memory, Hash table, flow table

李春强,董永强,吴国新. 多单元散列表与TCAM结合的OpenFlow流表查找方法[J]. 通信学报, 2016, 37(10): 128-140.

Chun-qiang LI,Yong-qiang DONG,Guo-xin WU. OpenFlow table lookup scheme integrating multiple-cell Hash table with TCAM[J]. Journal on Communications, 2016, 37(10): 128-140.

图/表 16

图1

图2

图3

图4

图5

表1

图6

图7

图8

图9

图10

图11

图12

图13

表2

Hash-TCAM表的配置与成本及能耗"

数据	2单元	3单元	4单元	5单元	6单元	7单元	8单元
主表	$\frac{N}{2}$	$\frac{N}{3}$	$\frac{N}{4}$	$\frac{N}{5}$	$\frac{N}{6}$	$\frac{N}{7}$	$\frac{N}{8}$
辅表	0.271N	0.224N	0.098N	0.088N	0.054N	0.037N	0.0349N
TCAM理论值	0.028N	0.005 2N	0.007 3N	0.002N	0.002N	0.003 2N	0.001 2N
Univ1-TCAM	0.027 7N₁	0.005 18N₁	0.007 42N₁	0.002N₁	0.002 58N₁	0.002 98N₁	0.001 22N₁
Univ2-TCAM	0.027 5N₂	0.005 35N₂	0.007 82N₂	0.001 44N₂	0.002 7N₂	0.003 33N₂	0.001 26N₂
成本理论值	2.242	1.802	1.575	1.49	1.392	1.339	1.309
Univ1-成本	2.235	1.802	1.578	1.49	1.389	1.334	1.309 7
Univ2-成本	2.225	1.816	1.579	1.48	1.392	1.342	1.310 7
能耗理论值	1.962	1.75	1.502	1.47	1.365	1.307	1.297
Univ1-能耗	1.958	1.75	1.503	1.47	1.363	1.304	1.297
Univ1-能耗	1.955	1.752	1.509	1.462	1.365	1.309	1.298

表2

图14

参考文献 34

[1]	MCKEOWN N , ANDERSON T , BALAKRISHNAN H ,et al. OpenFlow:enabling innovation in campus networks[J]. ACM SIGCOMM Computer Communication Review, 2008,38(2): 69-74.
[2]	Open Networking Foundation. OpenFlow switch specification Version 1.1.0 (Wire Protocol 0x02)[S/OL]. , 2011.
[3]	Open Networking Foundation. OpenFlow switch specification Version 1.3.0 (Wire Protocol 0x04)[S/OL]. , 2012.
[4]	Open Networking Foundation. OpenFlow switch specification Version 1.5.0 (Protocol version 0x06)[S/OL]. , 2014.
[5]	CONGDON P T , MOHAPATRA P , FARRENS M ,et al. Simultaneously reducing latency and power consumption in OpenFlow switches[J]. IEEE/ACM Transactions on Networking, 2014,22(3): 1007-1020.
[6]	TAYLOR D E . Survey and taxonomy of packet classification techniques[J]. ACM Computing Surveys, 2005,37(3): 238-275.
[7]	AGRAWAL B , SHERWOOD T . Modeling ternary CAM power and delay model:extensions and uses[J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2008,16(5): 554-564.
[8]	刘中金, 李勇, 苏厉 ,等. TCAM 存储高效的 OpenFlow 多级流表映射机制[J]. 清华大学学报(自然科学版), 2014,54: 437-442. LIU Z J , LI Y , SU L ,et al. TCAM-efficient flow table mapping scheme for OpenFlow multiple-table pipelines[J]. Journal of Tsinghua Univ Sci＆Technol, 2014,54: 437-442.
[9]	GE J , CHEN Z , WU Y ,et al. H-SOFT:a heuristic storage space optimization algorithm for flow table of OpenFlow[J]. Concurrency and Computation:Practice and Experience, 2015,27(13): 3497-3509.
[10]	CHEN Z , WU Y , GE J ,et al. A new lookup model for multiple flow tables of OpenFlow with implementation and optimization considerations[C]// IEEE International Conference on Computer and Information Technology (CIT). Xi’an,IEEE, 2014: 528-532.
[11]	鄂跃鹏, 陈智, 葛敬国 ,等. 一种高效的 OpenFlow 流表存储与查找实现方法[J]. 中国科学:信息科学, 2015,45(10): 1280-1288. E Y P , CHEN Z , GE J ,et al. An efficient implementation of storage and lookup for flow tables in OpenFlow[J]. Scientia Sinica Informationis, 2015,45(10): 1280-1288.
[12]	SUN H , SUN Y , VALGENTI V C ,et al. OpenFlow accelerator:a decomposition-based hashing approach for flow processing[C]// 24th International Conference on Computer Communication and Networks (ICCCN). Las Vegas:IEEE, 2015: 1-10.
[13]	ZHU H , XU M , LI Q ,et al. MDTC:An efficient approach to TCAM-based multidimensional table compression[C]// IFIP Networking Conference. Toulouse,IFIP, 2015: 1-9.
[14]	MCGEER R , YALAGANDULA P . Minimizing rule sets for TCAM implementation[C]// IEEE INFOCOM. Rio de Janeiro,IEEE, 2009: 1314-1322.
[15]	VEERAMANI S , KUMAR M M , NOOR S K . Hybrid trie based partitioning of TCAM based openflow switches[C]// IEEE International Conference on Advanced Networks and Telecommunications Systems (ANTS). Chennai,IEEE, 2013: 1-5.
[16]	LIM H , LEE S , SWARTZLANDER E E J . A new hierarchical packet classification algorithm[J]. Computer Networks, 2012,56(13): 3010-3022.
[17]	CORMODE G , THOTTAN M . Algorithms for next generation networks[M]. London: SpringerPress, 2010: 181-218.
[18]	PAGH R , RODLER F . Cuckoo hashing[J]. Journal of Algorithms, 2004,51(2): 122-144.
[19]	KIRSCH A , MITZENMACHER M , WIEDER U . More robust hashing:cuckoo hashing with a stash[C]// 16th Annual European Symposium on Algorithms,Karlsruhe (L). Springer Verlag,Heidelberg, 2008: 611-622.
[20]	CURTIS A R , KIM W , YALAGANDULA P . Mahout:low overhead datacenter traffic management using end-host-based elephant detection[C]// IEEE INFOCOM. Shanghai, 2011: 1629-1637.
[21]	MOHAMMAD A F , RADHAKRISHNAN S , RAGHAVAN B ,et al. Hedera:dynamic flow scheduling for datacenter networks[C]// USENIX Association NSDI. San Jose:USENIX, 2010: 281-296.
[22]	LI D , SHANG Y , CHEN C . Software defined green data center network with exclusive routing[C]// IEEE INFOCOM. Toronto,IEEE, 2014: 1743-1751.
[23]	FERKOUSS O E , SNAIKI I , MOUNAOUARO ,et al. A 100Gig network processor platform for OpenFlow[C]// Conf Network and Service Management (CNSM),Paris:IEEE, 2011.
[24]	LUO Y , CASCON P , MURRAY E ,et al. Accelerating OpenFlow switching with network processors[C]// ACM/IEEE Symposium on Architecture for Networking and Communications Systems(ANCS). Princeton,ACM, 2009: 70-71.
[25]	RECEP O . RECEP O.Intel? Ethernet Switch FM6000:SDN with OpenFlow[EB/OL]. .
[26]	MICHAEL O R . Fingerprinting by random polynomials[R]. Center for Research in Computing Technology Harvard University Report TR-15-81, 1981.
[27]	BRODER A Z , KARLIN A R . Multilevel adaptive hashing[C]// ACM-SIAM Symposium on Discrete Algorithm. San Francisco,ASSOC COMP MACHINERY, 1990: 43-53.
[28]	KUMAR S , TURNER J , CROWLEY P . Peacock hashing:deterministic and updatable hashing for high performance networking[C]// IEEE INFOCOM. Phoenix,IEEE, 2008: 101-105.
[29]	KIRSCH A , MICHAEL M . On the Performance of multiple choice hash tables with moves on deletes and inserts[C]// 46th Annual Allerton Conference on Communication,Control,and Computing, 2008: 1285-1290.
[30]	THEOPHILUS B . THEOPHILUS B.Data set for IMC 2010 data center measurement[EB/OL]. .
[31]	BRAYER K , HAMMOND J L . Evaluation of error detection polynomial performance on the AUTOVON channel[C]// National Telecommunications Conference. New Orleans,IEEE, 1975: 21-25.
[32]	[EB/OL].
[33]	GIRISH K . QDR?-II,QDR-II+,DDR-II,and DDR-II+ Design Guide[EB/OL]. .
[34]	[EB/OL].

λ	2单元	3单元	4单元	5单元	6单元	7单元	8单元
λ=1	10.364%	2.334%	0.435%	0.069%	0.009 5%	0.001 1%
λ=2	27.067%	10.901%	3.757%	1.124%	0.296%	0.069 5%	0.014 7%
λ=3		22.404%	10.645%	4.487%	1.690%	0.573%	0.176%
λ=4			19.537%	10.258%	4.886%	2.119%	0.841%
λ=5				17.547%	9.866%	5.109%	2.442%
λ=6					16.062%	9.501%	5.234%
λ=7						14.900%	9.168%
λ=8							13.959%