一种IP数据包快速分类算法

为了提高查找效率,在无冲突哈希查找算法和Grid of Tries算法的基础上提出了一种基于无冲突哈希和多比特Trie树(NHMT)的IP分类算法.该算法的核心有3部分:哈希函数的构造,主要是采用基于目的端口和协议两域构造哈希函数,使得在最坏情况下完全避免了空间爆炸问题;在Grid of Tries算法的基础上,对Grid of Tries算法改造成修剪的Trie树和多比特Trie树,以减少空间复杂度;在无冲突哈希查找算法的基础上扩展一层用于存放源端口号(或范围),扩展后一般要提高算法的时间复杂度,要通过引入多比特Trie树的方法进行解决.对于空间复杂度方面与无冲突哈希查找算法比较,一般情况下不增加空间复杂度.通过仿真,当对10 000条规则进行包分类时,该算法的分类速度可以达到1 Mbit/s,所消耗的最大内存为8.2 MB.     

一种适用于军事MANET的服务查找算法

因为高效、负载均衡及可扩展性强等特点,Chord服务查找算法在Internet中得到了成功的应用。然而研究表明,在带宽受限、信道质量差的移动Ad-hoc网络(MANET)中,Chord算法的性能会明显下降。长期以来,人们主要在民用MANET中对Chord算法进行了改进,而对军事MANET的关注很少。为改善Chord算法在军事MANET中的性能,从优化建环过程,改善Finger表和适当增加冗余查找信息三方面对Chord算法进行了改进,提出了一种新的适用于军事MANET环境的MM-Chord(MILITARYMANET Chord)算法。仿真结果与分析表明,MM-Chord算法不仅在查找成功率和查找时延两个关键性能方面明显优于Chord算法,而且比Chord算法具有更好的可扩展性。     

一种高效的多维数据包分类算法

介绍了数据包分类算法的基本思想及一种包分类算法解决方案的评价原则，在现有的ABV算法的基础上，对该算法进行了分析，提出了一种新的改进方案，并对该改进方案进行了性能分析。     

CRC校验算法分析及C语言实现

详细分析了循环冗余校验(CRC)码的表驱动实现方法，并用C语言编写程序予以验证，所提供的程序代码可作为函数直接嵌入软件系统中。     

一种求解GF(2m)上2,3次多项式根的快速查表算法

对BCH码和RS码解码时,常用Chien搜索法或直接查表法求取GF(2m)上错误位置多项式σ(x)的根.随着m增大,搜索次数或查找表容量以2的m次幂迅速增长,使求根过程的时间或空间开销大大增加.当m较大而σ(x)的次数较低时(如2或3),采用这些方法尤其不理想.为此研究了GF(2m)上2次错误位置多项式x2 ax b和3次错误位置多项式x3 ax2 bx c根的快速查表算法,该算法简化了前述多项式的原始求根表,理论分析表明它比直接查表法明显节省存储容量;比Chien搜索法明显加快求根速度.     

融合构型查找表与邻接查找子表的改进MC方法

针对医学图像三维可视化中移动立方体面绘制算法（marching cubes,MC）执行速度慢、效率不高的问题,提出了融合构型查找表与邻接查找子表的改进MC方法。该方法通过显性构建邻接查找子表约束体元搜索路径,使面绘制时只处理有效体元,根据邻接查找子表特点设计堆栈结构实现搜索算法,不仅提高了算法访问效率,而且减少了临时存储空间。在可视化工具包(VTK）下用改进MC方法对人体脚、胸腔、头部的CT数据集进行三维重建实验,结果表明在不损失重建质量的前提下,重建过程中遍历立方体数目缩短95%左右,重建时间缩短20%左右,提高了MC方法的执行速度和重建效率。     

一种硬件哈希表压缩方法及其性能研究

在高速1大容量的基于流的报文分类应用中,采用硬件哈希表具有成本低、扩展性好等优点。但由 于需要在硬件哈希表中保存流标识,而流标识的长度依不同应用可能长达几十字节,一方面需要较大的存 储空间,另一方面也严重影响了哈希查表的性能。提出了一种硬件哈希表压缩方法,可以有效压缩保存在 哈希表中流标识的长度,减小所需存储器容量,提高查表性能,同时实现复杂度低,具有较高的实用价值。     

可编程虚拟化路由器的转发表查找技术综述

可编程虚拟化路由器是未来互联网的核心网络设备,即在一个物理路由器平台上并行实现多个相互独立的虚拟路由器.综述了可编程虚拟化路由器的转发表(forwarding table,FIB)查找技术.分析了FIB查找技术的性能与可伸缩性挑战,即查找吞吐量、存储空间和增量更新问题.讨论了多FIB融合的IP查找算法和基于NDN(named data networking)命名的非IP查找算法的研究进展.指出了OpenFlow的多域FIB查找和基于硬件的NDN线速转发是未来研究亟需解决的重点问题.     

Trie树和单字倒排相结合的汉英词典查找机制

在对词典的查找算法作了回顾基础上,根据跨语言信息检索系统的要求,提出了一种词典查找的新机制,与其他查找算法的不同之处在于本方法支持模糊查找.查找机制结合Trie树和单字倒排的方法,既实现了查找的高效率又实现了模糊查找的算法,实验证明这种方法能够满足实际系统的需要.     

ARIA访问驱动Cache计时模板攻击

为评估ARIA密码抗Cache计时攻击安全性,提出了一种访问驱动Cache计时模板分析模型,给出了直接分析和排除分析2种模板匹配方法.以ARIA分组密码为例,给出了前4轮模板攻击方法,并通过本地攻击实验验证理论正确性.结果表明:ARIA易遭受访问驱动Cache计时模板攻击,应用直接模板分析和排除模板分析方法,200个样本均可在1s内恢复ARIA 128bit密钥.模板分析模型还可为其他使用S盒的分组密码访问驱动Cache计时模板分析提供一定参考.