基于频繁子串的报文分类算法
摘要
针对现有报文分类算法难以胜任高速网络中大规模规则的报文分类应用需求的不足，在元组空间算法的基础上提出了以频繁子串替代元组的新算法，通过压缩散列方法构建的散列表数目来减少匹配过程的表空间查找数目，达到提高匹配性能的目的。介绍了规则存放和匹配的算法细节，以及对前缀描述、任意区间描述的扩展。从存储开销、匹配时间复杂度和动态更新时间复杂度等方面，对新算法和元组空间算法进行了对比，并实验测试了两种算法的匹配用时和更新用时。最后，总结了新算法的性能以及优缺点。
出处
《电信技术研究》
2015年第4期11-18,共8页
Research on telecommunication technology
参考文献34
-
1逢丹.骨干网召唤400G三大运营商开启400G路由器集采测试[EB/OL].[2014-12-20].http://www.ccidcom.com/html/chanpinjishu/chengzai/40G100G/201405/12,227415.html.
-
2Braden R, Clark D, Shenker S. RFC1663 Integrated Services in the Internet Architecture: an Over- view[S/OL]. (1994-06) [2014-05-15]. http://www. hj p.at/(en,st_a)/doc/r fc/r fc 1633.html.
-
3Braden R, Zhang L, Berson S, et al. RFC2205 Re- source ReSerVation Protocol (RSVP)——Version 1 Function Specification[S/0L]. (1997-09) [2014-05-15]. http://tools.ietf.org/html/rfc2205.html.
-
4Blake S, Black D, Carlson M, et al. RFC2475 An Architecture for Differentiated Servic- es[S/OL].(1998-12)[2014-05-15].http://www.hjp.at /doc/rfc/rfc2475.html.
-
5Taylor D E. Survey and Taxonomy of Packet Clas- sification Techniques[J]. ACM Computing Surveys, 2005, 37(3): 238-275.
-
6Baidu.com, Inc.TCAM[EB/OL]. [2014-12-20] http://baike.baidu.com/link?url=DumYzTwbi5 CoV toqec2pu54BLt_Bd-5hBSIyO_fl Fs0U9_YT-TkJQ9 JlrjnugzwNlzWWqrvslSulAkKmlh6mea.
-
7Spitznagel E, Taylor D, Turner J. Packet Classifi- cation Using Extended TCAMs[C]. In ICNP'03.Atlanta: IEEE,2003 : 120-131.
-
8Lakshminarayanan K, Rangarajan A, Venkatachary S. Algorithms for Advanced Packet Classification withTernary CAMs[C]. In: SIGCOMM'05. Phila- delDhia:ACM. 2005:193-204.
-
9Yu Fang, Katz R. Efficient Multi-Match Packet Classification with TCAM[C]. Proceedings of the 12th Annual IEEE Symposium on High Perfor- mance Interconnects. Stanford: IEEE, 2004:28-34.
-
10Srinivasan V, Varghese G, Suri S, et al. Fast and Scalable Layer Four Switching[C] InSIGCOMM'98. Vancouver: ACM, 1998:191-202.
二级参考文献43
-
1Taylor D E. Survey and taxonomy of packet classification techniques[J].ACM Computing Surveys,2005,(03):238-275.
-
2De Berg M,Cheong O,Van Kreveld M. Computational Geometry:Algorithms and Applications[M].Germany:Springer,2008.153-180.
-
3Gupta P,Mckeown N. Packet classification using hierarchical intelligent cuttings[J].IEEE Micro,2000,(01):34-41.doi:10.1109/40.820051.
-
4Singh S,Baboescu F,Varghese G. Packet classification using multidimensional cutting[A].Karlsruhe,Germany,2003.213-224.
-
5Qi Ya-xuan,Xu Liang-hong,Yang Bao-hua. Packet classification algorithms:from theory to practice[A].Rio de Janeiro,Brazil,2009.648-656.
-
6Qi Ya-xuan;Jeffery Fong;Jiang Wei-rong.Multi-dimensional packet classification on FPGA:100 Gbps and beyond[A]北京,2010241-248.
-
7Vamanan B,Voskuilen G,Vijaykumar T N. Efficuts:optimizing packet classification for memory and throughput[A].New Delhi,India,2010.207-218.
-
8Jiang Wei-rong,Prasanna V K. Scalable packet classification on FPGA[J].IEEE Transactions on Very Large Scale Integration Systems,2012,(09):1668-1680.
-
9Jiang Wei-rong,Prasanna V K. Large-scale wire-speed packet classification on FPGAs[A].Monterey,USA,2009.219-228.
-
10Jeffery Fong,Wang Xiang,Qi Ya-xuan. ParaSplit:a scalable architecture on FPGA for terabit packet classification[A].Stanford,California:Stanford University,2012.1-8.
-
1吴英杰,陈鸿,王一蕾,孙岚.面向任意区间树结构的差分隐私直方图发布算法[J].模式识别与人工智能,2015,28(12):1084-1092. 被引量：4
-
2付利华,毛明毅,何华灿.任意区间上的泛组合运算模型研究[J].计算机工程与应用,2009,45(36):35-37.
-
3康健,吴英杰,黄泗勇,陈鸿,孙岚.异方差加噪下的差分隐私直方图发布算法[J].计算机科学与探索,2016,10(6):786-798. 被引量：5
-
4巨政权,郑见灵,满梦华.三模冗余演化自修复系统设计及可靠性分析[J].微电子学与计算机,2012,29(5):29-33. 被引量：1
-
5李莹.用随机函数编制小学低年级算术运算命题程序[J].科技信息,2012(1):511-512.
-
6e学通——英语学习的好帮手[J].电脑采购,2002,0(15):17-17.
-
7陈志成,何华灿,毛明毅.任意区间上的广义N范数与生成元[J].西北工业大学学报,2005,23(3):347-351. 被引量：1
-
8成媛媛,全惠云.解非线性方程自适应变搜索区间的遗传算法[J].计算机工程与应用,2005,41(21):58-60. 被引量：5
-
9张军,段亚辉.混凝土冷却水管的有限元沿程水温改进算法[J].华中科技大学学报（自然科学版）,2014,42(2):56-58. 被引量：4
