Journal of Frontiers of Computer Science and Technology ›› 2012, Vol. 6 ›› Issue (7): 612-620.DOI: 10.3778/j.issn.1673-9418.2012.07.005

Previous Articles     Next Articles

Research on Multi-Dimension Packet Matching Utilizing Differential Evolutionary Algorithm

WANG Zelin1,2+, WU Zhijian1   

  1. 1. State Key Laboratory of Software Engineering, Wuhan University, Wuhan 430072, China
    2. School of Computer Science and Technology, Nantong University, Nantong, Jiangsu 226000, China
  • Online:2012-07-01 Published:2012-07-02

运用差分演化算法实现多维包匹配的研究

王则林1,2+ ,吴志健1   

  1. 1. 武汉大学 软件工程国家重点实验室,武汉 430072
    2. 南通大学 计算机科学与技术学院,江苏 南通 226000

Abstract: The development of Internet has transferred the bottleneck of network speed from link speed to packet processing speed of the core network equipment, the critical work of packet processing is packet matching. The speed of packet matching is difficult to adapt for packets linear forwarding of the core network equipment by traditional algorithms. This paper proposes a novel algorithm of packet matching by combining improved differential evolutionary algorithm and classic packet matching algorithm. To increase objectivity, the method of statistics is used in computing the fitting value. Experimental results show that this new algorithm effectively improves the performance at the speed, storage space and update time, compared with the traditional one, and also show that the time performance of the proposed algorithm in packet matching is very weakly correlated with the number of rules, thus the algorithm is very suitable for solving multi-field and large-scale problems. The paper uses evolutionary algorithm to solve the network data packet forwarding in the condition of multi-field and large-scale rules warehouse, and packets can forward in the linear speed. This new algorithm is universal and adapts for many equipments such as firewall and QoS router etc.

Key words: packet matching, differential evolutionary algorithm, coefficient of variation

摘要: 互联网的发展已经使网速的瓶颈由链路速度转移到核心网络设备的包处理速度上,而包处理的核心工作是包匹配。传统方法难以做到包匹配速度适应核心网络设备数据包线速转发。提出了一种新的包匹配算法,该算法对差分演化算法进行了改进,并结合了改进算法和传统的包匹配算法。在适应值处理上运用统计学方法,从而增加了分析问题的客观性。数值实验表明,新算法与传统算法相比,在速度、存储空间以及更新时间等性能上得到了有效改善,另外新算法的包匹配的时间性能与规则数目只有很弱的相关性,从而适合处理多维和大规模问题。新算法把演化算法运用于多域大规模规则库的网络数据包的转发,并且数据包还能做到线速转发。新算法具有普适性,适用于防火墙、差别服务路由器等网络设备。

关键词: 包匹配, 差分演化算法, 变异系数