采用改进哈希算法提高IP分类查找速度的研究

分析几种常用的数据包分类算法和IP地址查找方法，介绍一种基于异或哈希的IP分类算法和一种采用特定哈希算法技术缩短IP转发表的大小的方法，以满足网络发展的需要。     

快速的IP路由查找算法

下一代路由器的一个主要设计问题是IP查找机制。对于每一个接受的信息包,路由器在地址查找过程中需执行一次最长前缀匹配操作,以此决定下一个转发站点。目前,这一过程由软件完成并且已成为路由器性能的一个主要瓶颈。因此,我建议使用一种快速的IP查找机制,其中的转发表足够小可存储在SRAM（静态随机存储器）中,并且费用非常低。通过管道技术它也能用硬件来实现。通过使用我们建议的方法,一个大的、拥有45000路由前缀的路由表可以被压缩成大小大约为430千字节的转发表。在最坏的情况下,一次查询的存储器访问的次数是三次。当通过管道技术实现时,所建议的机制能达到每次存储器访问完成一次路由查询。对于目前10纳秒的静态随机存储器,这个机制提供大约每秒1亿次的路由查询。此外,查询速度可以通过存储器访问速度的加速线性提升。     

基于单链表与哈希表的商品信息查找算法的比较研究

信息检索及其相关运算广泛应用于计算机信息管理实践中.基于单链表和哈希表两种结构实现动态查找算法为例,探讨商品信息查找的相关算法,说明这些算法的特点,比较分析了它们的时间性能,并从实验角度验证了这些算法时间性能的差异.     

采用图像感知哈希的TLD改进算法

为了提高长时间视觉目标跟踪的鲁棒性,提出了一种基于图像感知哈希的TLD改进算法。在改进算法中,跟踪模块使用尺度自适应的KCF跟踪器,检测模块对每个检测窗口提取感知哈希特征,并引入量子遗传算法作为搜索策略加快检测速度。对文中算法在OTB2013的50组视频序列上进行了测试,实验结果表明:其跟踪精度与成功率分别达到了0.784和0.568,较TLD算法分别提高了18.7%和14.2%。并且在处理光照变化、遮挡及目标分辨率低等问题时,文中算法在多数情况下取得了优于参考算法的跟踪性能,表现出良好的跟踪鲁棒性。     

域名式IP地址的探讨

本文主要简介了IP协议,分析了IP协议的现状及改进措施。探讨将IP地址的格式变成不固定长度字母加数字格式,类似于域名格式,使得IP地址更加直观,去除了DNS服务器,而且路由器寻址更加快捷准确,路由收敛的性能也大大提高。     

设账查找：路由新算法

针对路由查找时间越来越长，影响到网络运营速度和可靠性以及网络未来的发展的这一问题，提出了路由查找新算法——设账查找法。该算法是在重新构建路由表的基础上，将每一个IP地址在路由表中采用分层设账的形式进行管理；查找时逐级查找账户，避免许多不必要的查找，缩短了查找时间，可将目前的查找速度提高10000倍以上。     

基于二分查找和Trie的IPv6路由查找算法

分析基于前缀长度的二分路由查找算法和基于Trie的路由查找算法的优缺点,在此基础上提出一个改进的路由查找算法,并给出其在IPv6下的实现方案.由于基于前缀长度的二分路由查找算法扩展性好、查找速度快,而基于Trie的路由查找算法实现灵活、转发表动态更新快,这使得所提算法具备路由转发表动态更新快、查找速度快、对前缀长度扩展性好等优点.模拟实验表明该算法能够较好地满足IPv6的要求.     

动态快速路由查找算法

给出了动态快速路由查找算法（DFR）的原理和实现。该算法采用特殊的数据结构来构建索引表，能支持动态插入、删除和更新路由；DFR算法最多4次访存，最少2次访存，就能找到完整的路由信息。该算法不仅适用于软件实现，而且由于查找简单，也适合于硬件实现。     

异或哈希算法查找中文词组性能评价

本文根据汉字内码的特点，利用异或哈希算法建立中文词库和查找中文词组。根据不同规模的中文词库，给出了相应的改进算法，对实际的中文词库测试表明，此哈希算法分布均匀，冲突较少，且速度快，因此具有较好的实用性。     

一种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.     

Study on an absolute non-collision hash and jumping table IP classification algorithms

In order to classify packet, we propose a novel IP classification based the non-collision hash and jumping table frie-tree (NHJTTT) algorithm, which is based on noncollision hash Trie-tree and I.akshman and Stiliadis proposing a 2-dimensional classification algorithn! (LS algorithm). The core of algorithm consists of two parts: structure the non-collision hash function, which is constructed mainly based on destination source port and protocol type field so that the hash {unction can avoid space explosion problem; introduce jumping table frie tree based LS algorithm in order to reducetime complexity. The test results show that the classification rate of NHJTTT algorithm is up to 1 million packets per second and the maximum memory consumed is 9MB for 10000 rules,     

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

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

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

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

引入流量因素的路由表查找算法

分析了流量因素对路由表查找算法性能的影响,在CPU缓存技术的基础上提出引入流量分布因素的路由表查找算法,并对算法性能及适用性进行了讨论。     

网格环境中分层次哈希表资源发现机制

网格环境中,资源是异质的、动态的,广泛分布于整个网络。基于树型网络结构提出了一种分层次哈希表资源发现机制。资源在此机制中被哈希成为键值,每个哈希表节点存储一系列键值,对应注册在该节点或索引在该节点上的资源。因此,此机制的资源发现过程是有目的的寻找过程。对此机制进行了模拟,系统最大节点数达到700。所得结论:资源发现过程可以保证在O(logqp)步内完成;适当调整树型结构的子节点个数有助于提高性能;该机制性能优于传统洪泛机制。     

基于Cisco3600路由器的IP电话实现

利用VoIP技术开发了基于Cisco3600路由器的IP电话系统，完成了相应的程序配置，并在Cisco3600 Router系统进行了无链路传输内部验证，效果良好。实践证明，该系统稳定可靠，并有很好的可扩充性，可直接扩展成为实用的网络电话系统，具有直接的市场化应用前景。     

防火墙规则的动态分配和散列表匹配算法

防火墙应用在大型传输网络中存在管理和吞吐量问题 :手工方式配置多个防火墙 ,无法适应开放的、动态网络环境 ;大量过滤规则导致防火墙吞吐量下降。针对管理问题 ,提出了一种访问控制政策的自动分配与动态配置方法 ,将全局过滤规则自动地分发到相应的防火墙 ;利用入侵监测系统和搜索引擎的结果 ,自动定位防火墙、动态配置过滤规则。针对吞吐量问题 ,提出了一种基于散列表的规则匹配算法 ,该算法在所讨论的安全政策下可以将时间复杂度从 O(N )降低到 O(1) ,从而提高了防火墙的吞吐量     

保持前缀地址随机化的混合算法

针对以前的保持前缀地址随机化算法或是性能不高,或是不能进行一致的随机化的问题,该文提出了一种基于随机字符串的保持前缀地址随机化算法。该算法使用预先得到的随机字符串,避免了计算的开销,加快了地址随机化的速度。使用基于随机字符串算法和C rypto-pan的混合算法,可以进一步避免大的内存开销。实验结果表明,对相同的需要随机化的地址数,基于随机字符串的算法使用的时间只相当于C rypto-pan的1/10。采用二者的混合算法,一般使用的时间相当于C rypto-pan的1/4,而所使用的内存要比基于随机字符串所使用内存少得多,因此能够实现更好的时间、空间折衷。