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

Chun-qiang LI; Yong-qiang DONG; Guo-xin WU

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

您当前的位置：

首页 >

文章列表页 >

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

Papers | 更新时间：2024-06-05

- OpenFlow table lookup scheme integrating multiple-cell Hash table with TCAM
- Journal on Communications Vol. 37, Issue 10, Pages: 128-140(2016)
- 作者机构：
  
  1. 东南大学计算机科学与工程学院，江苏南京 211189
  2. 东南大学计算机网络和信息集成教育部重点实验室，江苏南京 211189
- 作者简介：
- 基金信息：
  
  The National High Technology Research and Development of China (863 Program)(2013AA013503);The National Natural Science Foundation of China(61272532);The National Natural Science Foundation of China(61370209);The Future Networks Prospective Research Program of Jiangsu Province(BY2013095-2-06)
- DOI：10.11959/j.issn.1000-436x.2016204
  CLC： TP393
- Online First：2016-10，
  
  Published：25 October 2016
- 稿件说明：
移动端阅览
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：

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

Views

2169

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

New delay measurement method based on accurate timestamp in OpenFlow

Research on software-defined network and the security defense technology

Moving target defense solution on network layer based on OpenFlow

Mechanism of eliminating UDP redundancy control packets in OpenFlow network

Information entropy based match field cutting algorithm

Related Author

Jing-jing LI

Jian-er ZHOU

Jun LI

Xin-yi QIU

Guo-zhen CHENG

Hong-chang CHEN

Tao WANG

Xin-xin NIU

Related Institution

University of Chinese Academy of Sciences

Computer Network information Center, Chinese Academy of Sciences

National Digital Switching System Engineering and Technological Research Center

College of Cyberspace Security,Beijing University of Posts and Telecommunications

State Key Laboratory of Public Big Data, Guizhou University

AI问答

⁰