论文网
关于嵌入式论文范文文献,与基于中间点划分无冲突哈希的高速包处理相关论文开题报告
本论文是一篇关于嵌入式论文开题报告,关于基于中间点划分无冲突哈希的高速包处理相关毕业论文的格式范文。免费优秀的关于嵌入式及函数及关键字方面论文范文资料,适合嵌入式论文写作的大学硕士及本科毕业论文开题报告范文和学术职称论文参考文献下载。
小型状态机来改进存储需求以适应Snort的特征库,使用了0.4MB的存储空间,采用ASIC实现,可以运行在10Gbps网络下.潘志浩等人提出了结合专用网络处理器(NP)的嵌入式深度包检测解决方案［10］.Jung［11］给出了文献［9］的FPGA的实现,获取了更低的吞吐率,但是存储空间更大.Hua等［12］用一次扫描可变步长的多个字符,提高字符串匹配的吞吐量,并减少其存储空间需求；Papadopoulos［13］使用了稀疏哈希表来存储特征串,尽管改进了存储空间,但存储利用率还是比较低.一些研究者尝试使用外部存储结构TCAM及SRAM,但是T
关于嵌入式论文范文文献
本文研究目标是提供一种低成本和节省空间的最小无冲突哈希函数,称之为中间点划分哈希,即易于构建,又适合在高速硬件平台下实现.该算法基于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等于｛sg1,sg2,等,sgn｝,首先定义一个二分函数BF.该函数定义如下：
BFn(e,S)等于
0,e∈Sl,Sl等于{sg1,等,sgn/2}
1,e∈Sr,Sr等于{sgn/2+1,等,sgn}
(1)
其中e表示待查询的关键字.如果元素e属于左分组Sl,令BFn(e,S)等于0；如果e属于右分组Sr,则令BFn(e,S)等于1.这样查询问题就变为查询元素隶属于左分组还是右分组,而不是具体的位置查询.Sl与Sr是S集合中两个互不相交的子集.当确定被查询关键字隶属于组Sl还是Sr后,可以在一个更小的具有n/4个关键字的组中进行查找,集合中包括被查询的关键字,通过应用BFn/2于被查询的关键字上.例如,如果BFn(e,S)等于0,即e∈Sl,可以应用BFn/2(e,Sl)在包含e有n/4个关键字的组中寻找.上述操作重复执行,直到结果组大小为1为止,即直到应用BF2为止,它指出一个关键字集合可以匹配被查询关键字.定义一个trie树,节点Nl,i是层l中第i个子集,大小n/2l(【i等于1,等,2l,l等于0,等,lb(n)-1).l层每个节点使用二分函数BFln/2,有两个孩子节点,每个孩子节点具有n/2l+1个关键字.式(2)定义一个函数Hn(e)为lbn个二分函数{BFn,BFn/2,BFn/4,等,BF2}的连接.
| 有关论文范文主题研究: | 嵌入式类论文范文 | 大学生适用: | 学士学位论文、学士学位论文 |
|---|---|---|---|
| 相关参考文献下载数量: | 81 | 写作解决问题: | 怎么撰写 |
| 毕业论文开题报告: | 论文提纲、论文结论 | 职称论文适用: | 技师论文、职称评初级 |
| 所属大学生专业类别: | 怎么撰写 | 论文题目推荐度: | 经典题目 |
Hn(e,S)等于BFn&BFn/2&BFn/4等&BF2
(2)
其中&符号是位连接符.令Hn［i］表示Hn的第i个位.
定理1
函数Hn(e,S)定义了有n个关键字集合S的最小无冲突哈希函数.
证明
BFln/2将层l的节点的关键字划分为两个不相交的子集,Sl和Sr.sgl∈Sl,Hn(l)等于0,sgr∈Sr,Hn(l)等于1.Hn(sgl,S)与Hn(sgr,S)至少有一个位是不同的(即在Hn［l］处).这样不会有sgl(sgl∈Sl)与任何sgr(sgr∈Sr)冲突.这一原理可以迭代地应用到从根节点开始的所有节点中,直到到达最后一层ll(即lbn-1).对于两个在层ll的两个不同节点中的特征串sgi和sgj,Hn(sgi,S)和Hn(sgj,S)至少有一位是不同的,这样不会有两个不同节点的两个不同的特征串发生冲突.在层ll中,BF2划分一个节点到两个不相交的集合中,每个只有一个特征串,因为Hn［ll］对于这两个特征串是不同的.在层ll中相同节点中的特征串是没有冲突的.这样Hn是一个无冲突哈希函数.Hn的输出有lbn个位.因为有lbn个函数.这样,Hn的范围是［0..n-1］,所以Hn是集合S的最小无冲突哈希函数.
推理1
在具有n个特征串的集合S上构建一个最小无冲突哈希函数等同于对集合S迭代地构建二分函数｛BFn,BFn/2,等,BF2｝.
2构建最小无冲突哈希函数
假设一个无冲突哈希函数H,取值范围在［0..m-1］,用来存储和查询n个特征串,具有m个桶(m≥n),并且没有冲突.每个特征串根据哈希函数值被插入到对应的存储桶中.在所有特征串被存储后,按照存储单元从左到右递增地次序给每个特征串赋一个序号.例如第一个关键是sg1,最后一个是sgn.图1示意有8个关键字,使用无冲突哈希函数H,插入到11个桶中.在查询关键字时计算H的值,读取对应的存储桶编号.
5结语
包检测是网络入侵检测系统的核心操作.本文提出基于中间点划分,实现一种节省存储适合硬件实现的最小无冲突哈希函数的构建.中间点哈希提供了一种新的具有较少空间的节点结构,适合于在将入侵特征信息以哈希表的方式存储于片上存储器中,提高了查找匹配速度.理论与实验证明,利用中间点构建最小无冲突哈希函数,存储中间点的空间复杂度在O(n),整个中间点哈希表的构建时间随关键字呈线性增长.该方法可广泛应用于IP查找、数据包分类、深度包检测和流量监控、分析等高速数据包处理中.
参考文献:
[1]
PAXSONV,ASANOVICK,DHARMAPURIKARS,etal.Rethinkinghardwaresupportforworkanalysisandintrusionprevention［C］//ProceedingsofUSENIXWorkshoponHotTopicsinSecurity.Boston:USENIXAssociationBerkeley,2006:63-68.
关于嵌入式论文范文文献,与基于中间点划分无冲突哈希的高速包处理相关论文开题报告参考文献资料：