多域网分组分类算法研究

doi:10.3969/j.issn.1000-0801.2014.12.015

摘要/Abstract

摘要：

随着网络业务的不断增长，网分组分类技术成为下一代互联网的研究热点。多域网分组分类算法作为网分组分类的核心技术，具有重要的研究价值。介绍了网分组分类算法的理论基础；对典型的网分组分类算法进行了介绍和比较分析，指出了各自存在的优缺点，并针对性地提出了改进措施；最后对多域网分组分类算法加以总结，探讨了新的研究方向。

关键词: 多域网分组, 五元组, 载荷

Abstract:

With the increase of network services, multi-dimensional packet classification technology has become a core technology for network devices in the next generation internet. Firstly, the theoretical foundation of packet classification algorithm was introduced. Secondly, the typical packet classification algorithms were introduced and analyzed, and the improvement measures were proposed. Finally, the multi-dimensional packet classification algorithm was proposed and the future work was discussed.

Key words: multi-dimensional packet, 5-tuple, payload

刘寒冰,杨亚丽,胡爱娜. 多域网分组分类算法研究[J]. 电信科学, 2014, 30(12): 103-110.

Hanbing Liu,Yali Yang,Aina Hu. Research on Multi-Dimensional Packet Classification Algorithm[J]. Telecommunications Science, 2014, 30(12): 103-110.

图/表 14

图1

图2

图3

图4

表1

图5

图6

图7

图8

图9

图10

图11

图12

表2

参考文献 17

1	Varghese G . Network Algorithmics: an Interdisciplinary Approach to Designing Fast Network Devices. San Francisco: Morgan Kaufmann Publishers, 2005
2	Chao J , Liu B . High Performance Switches and Routers. New Jersey: Wiley, 2007
3	徐恪，吴建平，徐明伟 . 高等计算机网络——体系结构、协议机制、算法设计与路由技术第二版. 北京：机械工业出版社， 2009
4	Joseph D , Tavakoli A , Stoica I . A policy aware switching layer for data centers. Proceedings of the ACM SIGCOMM, Seattle, USA, 2008: 51～62
5	Koponen T , Casado M , Gude N , et al. Onix: a distributed control platform for large-scale production networks. Proceedings of the 9th USENIX Symposium on Operating Systems Design and Implementation, Vancouver, Canada, 2010: 351～364
6	Opa L , Egi N , Ratnasamy S , et al. Building extensible networks with rule-based forwarding. Proceedings of the 9th USENIX Symposium on Operating Systems Design and Implementation, Vancouver, Canada, 2010: 379～392
7	Overmars M , Stappen A . Range searching and point location among fat objects. Journal of Algorithms, 1996, 21 (3): 629～656
8	Gupta P , McKeown N . Packet classification on multiple fields. Proceedings of ACM SIGCOMM, Cambridge, Massachusetts, USA, 1999: 147～160
9	Vamanan B , Voskuilen G , Vijaykumar T . EffiCuts: optimizing packet classification for memory and throughput. Proceedings of ACM SIGCOMM, New Delhi, India, 2010: 207～218
10	Srinivasan V , Varghese G , Suri S , et al. Fast and scalable layer four switching. Proceedings of ACM SIGCOMM, Vancouver, Canada, 1998: 191～202
11	亓亚煊，李军 . 多域网分组分类算法研究. 清华大学博士学位论文， 2011
12	Xu B , Jiang D Y , Li J . HSM: a fast packet classification algorithm. Proceedings of the International Conference on Advanced Information Networking and Application, Taipei, China, 2005: 987～992
13	Hua N , Song H Y , Lakshman T V . Variable-stride multi-pattern matching for scalable deep packet inspection. Proceedings of the 28th IEEE International Conference on Computer Communications, Riode Janeiro, Brazil, 2009: 415～423
14	Thompson K . Regular expression search algorithm. Communication of ACM, 1968, 11 (6): 419～422
15	Kumar S , Dharmapurikar S , Yu F , et al. Algorithms to accelerate multiple regular expressions matching for deep packet inspection. Proceedings of ACM SIGCOMM, Pisa, Italy, 2006: 339～350
16	Qi Y X , Wang K , Fong J , et al. Feacan: front-end acceleration for content-aware network process. Proceedings of the 30th IEEE International Conference on Computer Communications, Shanghai, China, 2011: 2114～2122
17	Schleimer S , Wilkerson D S , Aiken A . Winnowing: local algorithms for document fingerprinting. Proceedings of the ACM SIGMOD International Conference on Management of Data, San Diego, California, USA, 2003: 204～212

算法	内存使用	预处理时间	吞吐率
HSM	＞4 GB	＞24 h	3 Gbit/s
HyperSplit	753 MB	10 min	6.4 Gbit/s

算法	内存使用	预处理时间	吞吐率
D²FA	6 MB	20 min
FEACAN	＜2 MB	10 s	9.6 Gbit/s
VS-DFA	＜2 MB	＜1s