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

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

Abstract

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

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.

Figures/Tables 16

数据	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

References 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].

Metrics

Recommended 0

No Suggested Reading articles found!

λ	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%

OpenFlow table lookup scheme integrating multiple-cell Hash table with TCAM

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 16

References 34

Related Articles 15

Metrics

Recommended 0

[1]	Dongbin WANG, Dongzhe WU, Hui ZHI, Kun GUO, Xu ZHANG, Jinqiao SHI, Yu ZHANG, Yueming LU. Preventing flow table overflow against denial of service attack in software defined network [J]. Journal on Communications, 2023, 44(2): 1-11.
[2]	Xi QIN,Guodong TANG,Chaowen CHANG. SDN security control and forwarding method based on cipher identification [J]. Journal on Communications, 2018, 39(2): 31-42.
[3]	Songjie WEI,Xin SUN,Rudong ZHAO,Chao WU. Tracing IP-spoofed packets in software defined network [J]. Journal on Communications, 2018, 39(11): 181-189.
[4]	Hui HU,Ming CHEN,Bo LIU,Bo XU,Chang-you XING,Chao HU. Mechanism of eliminating UDP redundancy control packets in OpenFlow network [J]. Journal on Communications, 2017, 38(9): 167-175.
[5]	Peng-hao SUN,Ju-long LAN,Shao-jun ZHANG,Jun-fei LI. Information entropy based match field cutting algorithm [J]. Journal on Communications, 2017, 38(5): 182-189.
[6]	Tao WANG,Hong-chang CHEN,Guo-zhen CHENG. Research on software-defined network and the security defense technology [J]. Journal on Communications, 2017, 38(11): 133-160.
[7]	Xin-yi QIU,Jun LI,Jian-er ZHOU,Jing-jing LI. New delay measurement method based on accurate timestamp in OpenFlow [J]. Journal on Communications, 2017, 38(11): 178-187.
[8]	Yi-xun HU,Kang-feng ZHENG,Yi-xian YANG,Xin-xin NIU. Moving target defense solution on network layer based on OpenFlow [J]. Journal on Communications, 2017, 38(10): 102-112.
[9]	Yue-ping CAI,Chang-ping WANG. Software defined data center network with hybrid routing [J]. Journal on Communications, 2016, 37(4): 44-52.
[10]	Jiang LIU,Tao HUANG,Chen ZHANG,Ge ZHANG. Research on network virtualization slicing mechanism in SDN-based testbeds [J]. Journal on Communications, 2016, 37(4): 159-171.
[11]	Xiu-lei WANG,Guo-min ZHANG,Chao HU,Ming CHEN,Xiang-lin WEI. SDFAC:software defined flow access control mechanism [J]. Journal on Communications, 2015, 36(Z1): 188-196.
[12]	Zhe WANG,Man-gui LIANG,Xiao-meng JI,MateusAbisai Fillipus. Source-controlled OpenFlow data plane [J]. Journal on Communications, 2015, 36(3): 195-201.
[13]	Xi WENG,Ming CHEN,Guo-min ZHANG,Bo XU,Chang-you XING. Design and implementation of a network measurement and analysis system in OpenFlow networks [J]. Journal on Communications, 2015, 36(3): 81-88.
[14]	Yan-wei SHI,Zheng CAO. IMISA：interconnection mechanism for IP subnet and SDN subnet in autonomous system [J]. Journal on Communications, 2014, 35(Z1): 76-81.
[15]	. IMISA：interconnection mechanism for IP subnet and SDN subnet in autonomous system [J]. Journal on Communications, 2014, 35(Z1): 15-81.