基于OpenFlow的报文分类算法研究与实现

计算机工程与科学 ›› 2014, Vol. 36 ›› Issue (05): 860-865.

基于OpenFlow的报文分类算法研究与实现

吕昭，李韬

（国防科学技术大学计算机学院，湖南长沙 410073）

收稿日期:2013-08-30 修回日期:2013-11-25 出版日期:2014-05-25 发布日期:2014-05-25
基金资助:
国家自然科学基金资助项目（61202483）

Study and implementation of packet classification algorithms for OpenFlow

Lv Zhao，LI Tao

（College of Computer,National University of Defense Technology,Changsha 410073,China）

Received:2013-08-30 Revised:2013-11-25 Online:2014-05-25 Published:2014-05-25

摘要/Abstract

摘要：

随着软件定义网络、OpenFlow等技术的兴起，传统的基于5元组的报文分类技术已不能满足OpenFlow基于多元组的细粒度流量控制需求。因此，以分析已有的报文分类算法为基础，采用分而治之的思想，针对OpenFlow报文分类的精确匹配需求，设计实现了一种基于Hash的计数型链表Bloom Filter算法——OF_CBF算法。针对OpenFlow报文分类的通配匹配需求，借鉴正则表达式匹配算法思想，设计实现了基于有限自动机的报文匹配算法——OF_FSMP算法。对两种算法进行分析验证，并初步对两种算法进行了性能分析。

关键词: 网络处理器, 报文分类, OpenFlow, Bloom Filter, 有限自动机

Abstract:

With the emergence of software defined network and OpenFlow in recent years, fine grained flow control based on the multi tuple packet classification makes a huge challenge to the traditional 5 tuple packet classification. The basic concept of packet classification, some typical packet classification algorithms and the packet classification for OpenFlow are introduced. For the demand of exact match in the OpenFlow packet classification, a counting and linked list Bloom Filter base on Hash, named OF_CBF, is designed and implemented. And it is tested and analyzed. For the demand of wildcard match in the OpenFlow packet classification, an algorithm based on finite state machine, named OF_FSMP is designed, implemented, tested and analyzed.

Key words: network processor, packet classification, OpenFlow, Bloom Filter, finite state machine

吕昭, 李韬. 基于OpenFlow的报文分类算法研究与实现[J]. 计算机工程与科学, 2014, 36(05): 860-865.

Lv Zhao, LI Tao. Study and implementation of packet classification algorithms for OpenFlow [J]. Computer Engineering & Science, 2014, 36(05): 860-865.

参考文献

［1］OpenFlowSwitch specification 1.1.0 ［EB/OL］. ［2013-07-21］.
［2］Jiang W, Prasanna V K. Scalable packet classification on FPGA［J］. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2012, 20(9):1668-1680.
［3］Song H, Lockwood J W. Efficient packet classification for network intrusion detection using FPGA［C］∥Proc of the ACM/SIGDA 13th International Symposium on Field programmable Gate Arrays, 2005:238245.
［4］Sun Yi, Liu Tong, Cai Yibing, et al. Research on packet classification algorithm［J］. Application Research of Computers, 2007, 24(4):5-7.(in Chinese)
［5］Gao Lei, Tan Ming feng, Gong Zheng hu. Survey and evaluation of IP packet classification algorithms［J］. Computer Engineering & Science, 2006,28（3）:70-73.(in Chinese)
［6］Ganegedara T, Jiang W, Prasanna V. FRUG:A benchmark for packet forwarding in future networks［C］∥Porc of 2010 Performance Computing and Communications Conference(IPCCC), 2010:231-238.
［7］Dharmapurikar S,Krishnamurthy P,Sproull T S, et al. Deep packet inspection using parallel bloom filters［J］. Micro, IEEE, 2004,24(1):52-61.
［8］Bin Xiao, Yu Hua. Using parallel bloom filters for multiattribute representation on network services［J］. IEEE Transactions on Parallel and Distributed Systems, 2010,21(1):20-32.
［9］Bloom B H. Space/time trade offs in Hash coding with allowable errors［J］. Communications of the ACM, 1970,13(7):422-426.
［10］Chisvin L, Duckworth R J. Contentaddressable and associative memory:Alternatives to the ubiquitous RAM［J］. IEEE Computer,1989,22(7):51-64.
［11］Liang Zhong bin, Lan Ju long, Xia Bin. Range encoding scheme based on TCAM packet classification［J］. Network and Communication, 2010,36(8):117-119.(in Chinese)
［12］Guo D, Wu J, Chen H, et al. Theory and network applications of dynamic bloom filters［C］∥Proc of the 25th IEEE INFOCOM’06, 2006:1-12.
［13］Chen Qian. A fast string matching algorithm based on finite automation［J］.Computer Technology and Development, 2009(1):131-133.(in Chinese)
［14］Aho A V, Corasick M J. Efficient string matching:An aid to bibliographic search［J］. Communications of the ACM, 1975, 18(6):333-340.
［15］Li Gang, Wu Liao yuan, Zhang Ren bing, et al. Research on algorithm of finite automaton based pattern matching and its applications［J］.Journal of System Simulation, 2007,19(12):2772-2775.(in Chinese)
［16］Chen Shu hui,Sun Zhi gang,Su Jin shu.Research on range matching for wire speed hardwares NIDS［J］.Journal of Communications, 2006, 27(10):7-12. (in Chinese)
附中文参考文献:
［4］孙毅,刘彤,蔡一兵,等.报文分类算法研究［J］.计算机应用研究, 2007, 24(4):5-7.
［5］高蕾,谭明峰,龚正虎.IP报文分类算法综述与评价［J］. 计算机工程与科学,2006,28（3）：70-73.
［11］梁仲斌,兰巨龙,夏斌.基于TCAM报文分类的范围编码方案［J］.网络与通信, 2010,36(8):117-119.
［13］陈倩.一种基于有限自动机的快速串匹配算法［J］. 计算机技术与发展,2009(1):131-133.
［15］李钢,吴燎原,张仁斌,等.基于有限自动机的模式匹配算法及其应用研究［J］ .系统仿真学报, 2007,19(12):2772-2775.
［16］陈曙晖,孙志刚,苏金树.线速硬件网络入侵检测系统的范围匹配研究［J］.通信学报, 2006, 27(10):7-12.

[1]	谢莹，邱为好，孙志刚，全巍. FAE:一种OpenFlow协议FlowMod消息的action扩展机制[J]. 计算机工程与科学, 2019, 41(07): 1176-1183.
[2]	杨惠，冯振乾，厉俊男. 基于FPGA的并行多发可编程解析器[J]. 计算机工程与科学, 2019, 41(01): 24-30.
[3]	李元平1,3,李华1,2,赵俊岚3,阮宏玮1. OpenFlow协议IPv6属性测试研究[J]. 计算机工程与科学, 2018, 40(10): 1757-1765.
[4]	范林军1，史湘宁2，凌云翔1,3. 时钟有限自动机模型及其演化算法[J]. 计算机工程与科学, 2017, 39(02): 378-384.
[5]	孟祥辉1,2，曾学文2，陈晓2，叶晓舟2. iSCSI网络存储系统中加密方法研究与设计[J]. 计算机工程与科学, 2016, 38(12): 2456-2462.
[6]	王拥兵1,2,李永明1. 确定型模糊多重集有限自动机的极小化[J]. 计算机工程与科学, 2016, 38(12): 2574-2578.
[7]	朱书宏，兰少华. 基于OpenFlow的主动式节点失效保护机制[J]. 计算机工程与科学, 2016, 38(10): 2018-2024.
[8]	丁亦喆，魏刃佳，刘博，吴振强. 移动互联网中一种移动学习方案的设计与原型实现[J]. J4, 2015, 37(02): 288-293.
[9]	李韬, 孙志刚. 面向粗粒度数据流网络处理器的混合定制硬件加速[J]. J4, 2011, 33(11): 40-47.
[10]	时向泉曹季军苏金树. 一种基于多阶段资源感知的拥塞控制算法[J]. J4, 2008, 30(9): 4-7.
[11]	时向泉苏金树. 一种面向汇聚网络处理器模型的负载均衡算法[J]. J4, 2008, 30(12): 1-4.
[12]	张晓明王勇军张民选. 网络处理器中协处理器设计方法研究及实现[J]. J4, 2007, 29(3): 80-83.
[13]	王勇军黄清元. 基于网络处理器的MPLS VPN协议的研究与实现[J]. J4, 2006, 28(6): 9-12.
[14]	卢炎生郭红涛谢晓东毛澄映. 基于UML规格说明的增量式测试用例生成[J]. J4, 2006, 28(4): 53-55.
[15]	高蕾谭明峰龚正虎. IP报文分类算法综述与评价[J]. J4, 2006, 28(3): 70-73.