浏览全部资源
扫码关注微信
多单元散列表与TCAM结合的OpenFlow流表查找方法
OpenFlow table lookup scheme integrating multiple-cell Hash table with TCAM
- 通信学报 2016年37卷第10期 页码：128-140
- 作者机构：
1. 东南大学计算机科学与工程学院，江苏 南京 211189
2. 东南大学计算机网络和信息集成教育部重点实验室，江苏 南京 211189
- 作者简介：
[ "李春强（1975-），男，山东沾化人，东南大学博士生，主要研究方向为数据中心网络体系结构及传输控制、报文转发及查找算法等。" ]
[ "董永强（1973-），男，河南渑池人，博士，东南大学副研究员，主要研究方向为网络体系结构、移动网络计算、高效内容分发等。" ]
[ "吴国新（1956-），男，安徽芜湖人，东南大学教授、博士生导师，主要研究方向为网络协议、网络安全和自组网等。" ]
- 基金信息：国家高技术研究发展计划(863“”计划)基金资助项目(2013AA013503);国家自然科学基金资助项目(61272532);国家自然科学基金资助项目(61370209);江苏省未来网络前瞻性研究基金资助项目(BY2013095-2-06)
DOI：10.11959/j.issn.1000-436x.2016204
中图分类号： TP393-
网络出版日期：2016-10，
纸质出版日期：2016-10-25
- 稿件说明：
移动端阅览
李春强, 董永强, 吴国新. 多单元散列表与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.
李春强, 董永强, 吴国新. 多单元散列表与TCAM结合的OpenFlow流表查找方法[J]. 通信学报, 2016,37(10):128-140. DOI： 10.11959/j.issn.1000-436x.2016204.
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. DOI： 10.11959/j.issn.1000-436x.2016204.
摘要
在OpenFlow网络中，交换机通过标准化的接口接受基于流的规则，执行基于流的报文处理。流表的查找是OpenFlow交换机的核心功能，TCAM以其优异的性能广泛用于OpenFlow流表的查找，然而基于TCAM的OpenFlow流表查找具有较高的成本与能耗。为了降低流表查找的成本与能耗，提出了多单元散列表与TCAM结合的OpenFlow流表存储与查找的方法。通过理论分析与仿真测试，给出了查找结构成本优化后的散列表、TCAM的容量配置；在该配置下，Hash-TCAM流表查找结构比单纯使用TCAM的方案节约90%以上的成本，有效降低了能耗，同时保持了相近的查找性能。
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.
关键词
Keywords
references
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 .
Open Networking Foundation . OpenFlow switch specification Version 1.1.0 (Wire Protocol 0x02) [S/OL ] . https://www.opennetworking.org/images/stories/downloads/sdn-resources/onf-specifications/ openflow/openflow-spec-v1.1.0.pdf https://www.opennetworking.org/images/stories/downloads/sdn-resources/onf-specifications/ openflow/openflow-spec-v1.1.0.pdf , 2011 .
Open Networking Foundation . OpenFlow switch specification Version 1.3.0 (Wire Protocol 0x04) [S/OL ] . https://www.opennetworking.org/images/stories/downloads/sdn-resources/onf-specifications/ openflow/openflow-spec-v1.3.0.pdf https://www.opennetworking.org/images/stories/downloads/sdn-resources/onf-specifications/ openflow/openflow-spec-v1.3.0.pdf , 2012 .
Open Networking Foundation . OpenFlow switch specification Version 1.5.0 (Protocol version 0x06) [S/OL ] . https://www.opennetwork ing.org/images/stories/downloads/sdn-resources/onf-specifications/ openflow/openflow-switch-v1.5.0.pdf https://www.opennetwork ing.org/images/stories/downloads/sdn-resources/onf-specifications/ openflow/openflow-switch-v1.5.0.pdf , 2014 .
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 .
TAYLOR D E . Survey and taxonomy of packet classification techniques [J ] . ACM Computing Surveys , 2005 , 37 ( 3 ): 238 - 275 .
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 .
刘中金 , 李勇 , 苏厉 , 等 . 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 .
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 .
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 .
鄂跃鹏 , 陈智 , 葛敬国 , 等 . 一种高效的 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 .
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 .
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 .
MCGEER R , YALAGANDULA P . Minimizing rule sets for TCAM implementation [C ] // IEEE INFOCOM . Rio de Janeiro,IEEE , 2009 : 1314 - 1322 .
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 .
LIM H , LEE S , SWARTZLANDER E E J . A new hierarchical packet classification algorithm [J ] . Computer Networks , 2012 , 56 ( 13 ): 3010 - 3022 .
CORMODE G , THOTTAN M . Algorithms for next generation networks [M ] . London : SpringerPress , 2010 : 181 - 218 .
PAGH R , RODLER F . Cuckoo hashing [J ] . Journal of Algorithms , 2004 , 51 ( 2 ): 122 - 144 .
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 .
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 .
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 .
LI D , SHANG Y , CHEN C . Software defined green data center network with exclusive routing [C ] // IEEE INFOCOM . Toronto,IEEE , 2014 : 1743 - 1751 .
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 .
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 .
RECEP O . RECEP O.Intel® Ethernet Switch FM6000:SDN with OpenFlow [EB/OL ] . http://www.intel.com/content/www/us/en/switch-silicon/ethernet-switch-fm6000-sdn-paper.html,2014 http://www.intel.com/content/www/us/en/switch-silicon/ethernet-switch-fm6000-sdn-paper.html,2014 .
MICHAEL O R . Fingerprinting by random polynomials [R ] . Center for Research in Computing Technology Harvard University Report TR-15-81 , 1981 .
BRODER A Z , KARLIN A R . Multilevel adaptive hashing [C ] // ACM-SIAM Symposium on Discrete Algorithm . San Francisco,ASSOC COMP MACHINERY , 1990 : 43 - 53 .
KUMAR S , TURNER J , CROWLEY P . Peacock hashing:deterministic and updatable hashing for high performance networking [C ] // IEEE INFOCOM . Phoenix,IEEE , 2008 : 101 - 105 .
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 .
THEOPHILUS B . THEOPHILUS B.Data set for IMC 2010 data center measurement [EB/OL ] . http://pages.cs.wisc.edu/~tbenson/IMC10_Data.html,2010 http://pages.cs.wisc.edu/~tbenson/IMC10_Data.html,2010 .
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 .
https://en.wikipedia.org/wiki/Jenkins_hash_function https://en.wikipedia.org/wiki/Jenkins_hash_function [EB/OL ] .
GIRISH K . QDR®-II,QDR-II+,DDR-II,and DDR-II+ Design Guide [EB/OL ] . http://www.cypress.com/file/38596/download,2015 http://www.cypress.com/file/38596/download,2015 .
http://accellera.org/downloads/standards/systemc http://accellera.org/downloads/standards/systemc [EB/OL ] .
0
浏览量
970
下载量
5
CSCD
- 网络PDF下载
- XML下载
- Meta-XML下载
- BibTeX下载
- Endnote下载
- RefMan 下载
- NoteExpress下载
- NoteFirst下载
关联资源
相关文章
相关作者
相关机构
AI问答
鸿云智能
中文
- 技术支持由北京北大方正电子有限公司提供 京ICP备09064830号-19
京公网安备11010802024621 - 本系统建议在Chrome、 IE9+ 以上版本浏览器阅读本站内容，360浏览器请切换至极速模式
- Cookies帮助我们提供服务并提供个性化体验。使用本网站，即表示您同意我们使用Cookies
- 总访问量：151733 今日访问量：2