基于中间点划分无冲突哈希的高速包处理(2)_代写代发论文(医学论文)_sci论文代发_广州论文发表_

本文研究目标是提供一种低成本和节省空间的最小无冲突哈希函数，称之为中间点划分哈希，即易于构建，又适合在高速硬件平台下实现。该算法基于trie树，算法渐近地决定关键字集合中哪个关键字与数据包进行比较。算法

　　
　　本文研究目标是提供一种低成本和节省空间的最小无冲突哈希函数，称之为中间点划分哈希，即易于构建，又适合在高速硬件平台下实现。该算法基于trie树，算法渐近地决定关键字集合中哪个关键字与数据包进行比较。算法开始从trie树的根节点开始将所有关键字集合划分为两个相等大小的组，每个组中有n/2个关键字。新划分的组被置于根节点的左右孩子节点中，每个新组继续被划分成两个相同大小的组(每个组有n/4个关键字)。这种划分迭代重复执行，直至n个节点为止，分别对应于n个关键字。为了查询关键字，算法遍历整个trie树，直到在某个叶子节点中找到候选关键字为止。当找到单个关键字，只需要进行一次匹配(即只比较查询关键字与候选关键字)，就可以决定被查询的关键字是否实际与候选关键字相同。
　　1 最小无冲突哈希函数
　　定义1
　　最小无冲突哈希函数。对于具有n个元素的关键字集合S，一个无冲突的哈希函数f将S中每个关键字映射到值域［0，m-1］中的各不相同的唯一的数值(m≥n)。最小无冲突哈希函数指的是满足m=n的无冲突哈希函数。
　　根据上述定义，函数f是最小无冲突哈希函数，当j，k∈S时，如果f(j)=f(k)，则必然是j=k，不存在j≠k而f(j)=f(k)的情况。最小无冲突哈希函数保证仅有一个关键字被保存在某一个哈希位置，这样只需要执行一次匹配操作就可以完成查询，换句话说是没有哈希冲突的。通过将哈希表的大小设置为与关键字的数量一致，可以达到最小的哈希表大小。值得注意的是，除了保存关键字外，哈希函数需要附加的空间来存储其自身。
　　定义2
　　二分函数。对于具有n个关键字的集合S，S=｛sg1，sg2，…，sgn｝，首先定义一个二分函数BF。该函数定义如下：
　　BFn(e,S)=
　　0,e∈Sl,Sl={sg1,…,sgn/2}
　　1,e∈Sr,Sr={sgn/2+1,…,sgn}
　　
　　(1)
　　其中e表示待查询的关键字。如果元素e属于左分组Sl，令BFn(e,S)=0；如果e属于右分组Sr，则令BFn(e,S)=1。这样查询问题就变为查询元素隶属于左分组还是右分组，而不是具体的位置查询。Sl与Sr是S集合中两个互不相交的子集。当确定被查询关键字隶属于组Sl还是Sr后，可以在一个更小的具有n/4个关键字的组中进行查找，集合中包括被查询的关键字，通过应用BFn/2于被查询的关键字上。例如，如果BFn(e,S)=0，即e∈Sl，可以应用BFn/2(e,Sl)在包含e有n/4个关键字的组中寻找。上述操作重复执行，直到结果组大小为1为止，即直到应用BF2为止，它指出一个关键字集合可以匹配被查询关键字。定义一个trie树，节点Nl,i是层l中第i个子集，大小n/2l(【i=1,…,2l，l=0,…,lb(n)-1)。l层每个节点使用二分函数BFln/2，有两个孩子节点，每个孩子节点具有n/2l+1个关键字。式(2)定义一个函数Hn(e)为lbn个二分函数{BFn,BFn/2,BFn/4,…,BF2}的连接。
　　
　　Hn(e,S)=BFn & BFn/2 & BFn/4… & BF2
　　(2)
　　其中&符号是位连接符。令Hn［i］表示Hn的第i个位。定理1
　　函数Hn(e,S)定义了有n个关键字集合S的最小无冲突哈希函数。
　　证明
　　BFln/2将层l的节点的关键字划分为两个不相交的子集，Sl和Sr。sgl∈Sl，Hn(l)=0，sgr∈Sr，Hn(l)=1。Hn(sgl,S)与Hn(sgr,S)至少有一个位是不同的(即在Hn［l］处)。这样不会有sgl(sgl∈Sl)与任何sgr(sgr∈Sr)冲突。这一原理可以迭代地应用到从根节点开始的所有节点中，直到到达最后一层ll(即lbn-1)。对于两个在层ll的两个不同节点中的特征串sgi和sgj，Hn(sgi,S)和Hn(sgj,S)至少有一位是不同的，这样不会有两个不同节点的两个不同的特征串发生冲突。在层ll中，BF2划分一个节点到两个不相交的集合中，每个只有一个特征串，因为Hn［ll］对于这两个特征串是不同的。在层ll中相同节点中的特征串是没有冲突的。这样Hn是一个无冲突哈希函数。Hn的输出有lbn个位。因为有lbn个函数。这样，Hn的范围是［0..n-1］，所以Hn是集合S的最小无冲突哈希函数。
　　推理1
　　在具有n个特征串的集合S上构建一个最小无冲突哈希函数等同于对集合S迭代地构建二分函数｛BFn，BFn/2，…,BF2｝。
　　2 构建最小无冲突哈希函数
　　
　　假设一个无冲突哈希函数H，取值范围在［0..m-1］，用来存储和查询n个特征串，具有m个桶(m≥n)，并且没有冲突。每个特征串根据哈希函数值被插入到对应的存储桶中。在所有特征串被存储后，按照存储单元从左到右递增地次序给每个特征串赋一个序号。例如第一个关键是sg1，最后一个是sgn。图1示意有8个关键字，使用无冲突哈希函数H，插入到11个桶中。在查询关键字时计算H的值，读取对应的存储桶编号。
　　
　　5 结语
　　包检测是网络入侵检测系统的核心操作。本文提出基于中间点划分，实现一种节省存储适合硬件实现的最小无冲突哈希函数的构建。中间点哈希提供了一种新的具有较少空间的节点结构，适合于在将入侵特征信息以哈希表的方式存储于片上存储器中，提高了查找匹配速度。理论与实验证明，利用中间点构建最小无冲突哈希函数，存储中间点的空间复杂度在O(n)，整个中间点哈希表的构建时间随关键字呈线性增长。该方法可广泛应用于IP查找、数据包分类、深度包检测和流量监控、分析等高速数据包处理中。
　　
　　参考文献:
　　[1]
　　PAXSON V, ASANOVIC K, DHARMAPURIKAR S, et al. Rethinking hardware support for network analysis and intrusion prevention ［C］// Proceedings of USENIX Workshop on Hot Topics in Security. Boston: USENIX Association Berkeley, 2006: 63-68.

(责任编辑：南粤论文中心)转贴于南粤论文中心: http://www.nylw.net(南粤论文中心__代写代发论文_毕业论文带写_广州职称论文代发_广州论文网）

顶一下

(0)

踩一下

(0)

上一篇：Wspruce:一种改进的可用带宽测量方法

下一篇：基于改进BP神经网络的围岩自稳能力评估模型

论文发表,代写代发论文

本站业务范围

推荐论文内容

最新发表杂志目录

基于中间点划分无冲突哈希的高速包处理(2)

南粤论文网友情链接