High.speed packet processing by non.collision hash functions based on
middle.point partition
ZHANG Mo.hua1*, LI Ge2
1.School of Computer and Information Engineering, Henan University of Economics and Laws, Zhengzhou Henan 450000, China
;
2.Department of Information Engineer, Conservancy Vocational Institute of North China Institute of Water Conservancy and Hydroelectric Power, Zhengzhou Henan 450000, China
Abstract:
High.speed packet inspection can be achieved through storing attack signatures on the high.speed on.chip memory. Concerning the limited on.chip memory, this paper proposes a new trie structure with non.collision hash functions based on middle.point partition. The algorithm evenly partitiones attack signatures into mutiple groups at each layer in trie tree to achieve the effective control of memory. The trie.tree structure can be implemented on a single chip and perform query operations by pipelining and parallelism,thus achieves higher throughput. The space complex of storing middle.point is O(n) and the construction time of hash table is linearly growing with the number of attack signatures The experimental results show that the new structure decreases the demand of on.chip memory and can facilitate access to the attack signature on the on.chip memory while allowing to perform the signatures matching operations only once.
High.speed packet inspection can be achieved through storing attack signatures on the high.speed on.chip memory. Concerning the limited on.chip memory, this paper proposed a new trie structure with non.collision hash functions based on middle.point partition. The algorithm evenly partitioned attack signatures into multiple groups at each layer in trie tree to achieve the effective control of memory. The trie.tree structure can be implemented on a single chip and perform query operations by pipelining and parallelism, thus achieving higher throughput. The space complex of storing middle.point is O(n) and the construction time of hash table is linearly growing with the number of attack signatures. The experimental results show that the new structure decreases the demand of on.chip memory and can facilitate access to the attack signature on the on.chip memory while allowing to perform the signatures matching operations only once.
Key words:
high.speed packet processing;non.collision hash;middle.point partition;trie tree ;on.chip memory
0 引言
网络入侵检测技术是网络攻击防范的主要手段，数据包检测是其核心。数据包检测不仅检查数据包头部信息，而且要检查数据包有效载荷［1］。采用数据包预处理方法，依据数据包头部字段对其进行分类和查找，采用特征匹配算法，将每个数据包内容与一组预定义的特征串进行匹配。本质上来说，包检测是一种数据包内容过滤技术，不仅应用于网络入侵检测系统中，而且应用于网络取证系统、P2P流量识别以及基于上下文的流量计费等［2］。随着网络带宽和业务流量的迅猛增长，包处理正面临如何满足高速数据包处理的时间和空间需求的挑战。包处理通常部署在高速路由器的关键数据路径上，检查海量高速数据包，与大量预定义的规则进行匹配。由于基于软件的包处理难以适应高速数据包处理，当前研究者采用现代嵌入式存储器技术，例如 【确认全称是否正确】
专用集成电路(Application Specific Integrated Circuit, ASIC)、现场可编程门阵列(Field.Programmable Gate Array, FPGA)、网络处理器(Network Processor, NP) 和三重内容可寻址存储器(Ternary Content Addressable Memory, TCAM)等，
设计和实现了多种基于硬件的包处理技术，支持10Gbps以上的线速数据包处理［3］。这些嵌入式存储器技术通常采用分层存储器体系结构，即由快速片上存储器和大容量片外存储器组成。基于硬件的方法通常被分为片外储器和片上存储器两种架构。考虑速度第一，片外存储架构并没有片上方法那么吸引人。片外架构的主要缺点在于需要与芯片上的匹配引擎进行物理连接。即使外部存储速度显著增加，但是仍然会妨碍引擎的并行性。这样，片外方法对于高速线速操作并不是很合适。例如片上SRAM存储的访问时间为1～2ns，但是其存储空间受限，难以存储大量元素；而片外存储器提供更大容量存储空间，适合于存储大量元素，但是其查找速度较慢，例如片外DRAM的访问时间在60ns左右［4］。因此，研究设计一种快速和存储高效的数据包预处理方法，不仅减少片外存储器访问次数，而且降低其存储空间需求，是高速数据包处理的关键所在。
在包检测研究方面，当前主要着眼于两个方面提高检测性能:1)设计基于硬件的特征匹配算法,减少单个特征匹配的处理时间和存储空间需求；2)设计基于硬件的Hash表等数据包预处理方法，减少片外存储器访问次数和特征匹配次数［4］。王志佳等［5］提出了一种改进的基于确定有限自动机的深度包检测算法，该算法在牺牲少量运算时间的情况下，减少算法所需的运算空间。徐乾等［6］提出一种基于确定的有穷状态自动机的正则表达式压缩算法，采用选择性分群算法大幅度减少了状态机的个数，降低了包检测匹配算法的复杂性。Smith等［7］提出了XFA(eXtended FiniteAutomaton)模型，在状态上增加辅助变量及其操作指令,消除确定性有限自动机状态空间爆炸问题。Lu等［8］提出了多字符并行处理的Aho.Corasick算法，通过并行操作提高Aho.Corasick算法的吞吐量，并最小化其存储空间需求。总的来说，由于软件包检测系统运行在通用处理器上，不适合高速网络，很难在当今线速环境下完成检测。为了满足高速网络的需要，本文重点关注基于硬件的方法。Tan等［9］使用一种小型状态机来改进存储需求以适应Snort的特征库，使用了0.4MB的存储空间，采用ASIC实现，可以运行在10Gbps网络下。潘志浩等人提出了结合专用网络处理器(NP)的嵌入式深度包检测解决方案［10］。Jung［11］给出了文献［9］的FPGA的实现，获取了更低的吞吐率，但是存储空间更大。Hua等［12］用一次扫描可变步长的多个字符,提高字符串匹配的吞吐量,并减少其存储空间需求；Papadopoulos［13］使用了稀疏哈希表来存储特征串，尽管改进了存储空间，但存储利用率还是比较低。一些研究者尝试使用外部存储结构TCAM及SRAM，但是TCAM比较昂贵，而SRAM则受限于速度。Sourdis等采用一种混合的方法［14］，使用可配置的电路和片上存储器，采用无冲突哈希的方法，该方法与本文的方法类似，但与本文方法不同的是，该方法需要进行重配置，并且存储利用率低，因为其使用了无冲突哈希，而不是最小无冲突哈希。Lu等［15］提供了一种空间复杂度为O(n)的最小无冲突哈希方法，具有较快的构建时间，但这一方法需要复杂的地址方案，而且要求有附加的逻辑来计算哈希表的地址。 (责任编辑：南粤论文中心)转贴于南粤论文中心: http://www.nylw.net(南粤论文中心__代写代发论文_毕业论文带写_广州职称论文代发_广州论文网）
- 毕业论文定制
南粤论文中心提供本科/研究生/博士毕业论文，从提纲，开题到后期免费修改,免费指导答辩等 ，联系人：魏老师，电话：13450375436。 - 代写代发职称论文
南粤论文中心提供职称论文代写，报告总结，演讲致辞,心得体会,党团辅导等代写服务并推荐发表省级,国家级,核心杂志包发。联系QQ:631069747。
基于中间点划分无冲突哈希的高速包处理
来源：网络(转载) 作者：张墨华 李戈 发表于：2012-04-14 13:32 点击：次
【关健词】高速包处理;无冲突哈希;中间点划分;trie树;片上存储
通过在高速片上存储器上存储所有的攻击特征，实现对数据包的高速检测。针对有限的片上存储器空间，提出一种新的基于中间点划分无冲突哈希函数的trie树结构，将攻击特征串平均分配到trie树每层的多个组中，实现对片上存储器有效的控制。通过在同一个芯片中采用流水并行方
顶一下
(0)
0%
踩一下
(0)
0%
版权声明：因本文均来自于网络，如果有版权方面侵犯,请及时联系本站删除.
