基于混沌查找表的单向Hash函数构造算法

提出一种基于混沌查找表的单向Hash函数构造算法。该算法通过控制符更新的混沌查找表将明文信息映射为查找表中的数据,置换出相应的信息后按照一定的规则提取长度为128 bit的Hash值。理论分析和仿真结果证明,该算法具有较好的单向性、混乱与扩散性以及抗碰撞性,满足单向Hash函数的各项性能要求。     

一种面向深度数据包检测的索引拆分Bloom过滤器

高速数据包处理迫切需要时空高效的深度数据包检测(DPI),满足其线速处理和低存储空间需求.Trie位图内容分析器(TriBiCa)采用片上位图Trie树来实现元素的最小完美Hash;但是,TriBiCa存在更新开销高和假阳性访问次数多等问题.共享节点快速Hash表(SFHT)采用片上计数Bloom过滤器(CBF)来实现硬件Hash表的快速查找;但是,SFHT存在更新开销高和存储空间需求大等问题.文中提出了一种索引拆分Bloom过滤器(ISBF).ISBF是由片上多组并行CBF和片外元素集构成,其核心思想是:元素的片外索引值被拆分成多组比特,每组比特采用多个片上并行CBF表示元素集;当查询元素时,每组并行CBF产生多个比特值,并合成候选元素的片外索引值.为了降低ISBF的更新开销,文中又提出了懒惰删除(lazyd eletion)算法和空缺插入(vacant insertion)算法,即采用一个片上删除位图,仅在片上并行CBF中删除或插入元素,而不需要调整其他元素的片外索引值.ISBF是一种时空高效的数据结构,其插入、删除和查询操作的平均片外存储器访问次数均为O(1);与TriBiCa和SFHT相比,ISBF在...     

命名数据网络中基于Hash映射的命名检索

命名数据网络(NDN)是一种以内容为中心的新型网络架构,可有效提高网络资源的共享利用率。但与传统的IPv4、IPv6相比,NDN命名的长度更长且具有可变性,因此实现NDN中命名的快速检索对提高网络性能具有重要作用。为此,提出一种基于Hash映射的分治命名检索方法,将命名分解为组件并进行CRC32映射后分别存储在相应的Hash表中,对Hash表中的数据进行快速排序后使用二分查找定位Hash值,并利用排序后Hash表的递增数据结构进行Hash冲突的快速检测,通过对Hash值添加标志位的方法解决冲突问题。实验结果表明,相比建立命名前缀树的检索方法,该分治命名检索方法可将NDN命名的存储空间压缩近65%,并且大幅提升了检索速度。     

基于Hash表的关联规则挖掘算法的改进

经典的Apriori算法在大项目集的挖掘过程中因为重复搜索导致效率低下。提出一种改进的Hash表结构应用于DHP算法中的项目集存放,定义新的Hash函数确定项目集的存放地址,并基于新的Hash表结构,以并行挖掘的方式优化关联规则算法的剪枝过程。实验结果表明,与Apriori算法相比,文中的方法可以更好地节省存储空间,提高挖掘效率。     

Hash算法在网络处理器中的实现

提出一种应用于网络处理器的Hash算法,通过建立新型查找表的结构和构造两级Hash函数,能够有效地解决Hash冲突的问题。描述Hash表的软件建立流程和硬件查找过程,在Hash查找的基础上,给出硬件表项的学习过程和老化方法,简化表项的更新操作。针对不同的应用,建立不同类型的Hash表,合理地利用内外部存储资源,兼顾了存储资源和处理速度的平衡。实验结果表明,该算法对各种查找表中不同的表项数目和关键词长度均具有较好的兼容性,成功查找的平均长度为2,减少了存储器的访存次数,其单个微引擎的查找速度高达25Mb/s,能够满足网络处理器接口处理带宽20Gb/s的要求。     

基于Hash表的关联规则挖掘算法的改进

经典的Apriori算法在大项目集的挖掘过程中因为重复搜索导致效率低下。提出一种改进的Hash表结构应用于DHP算法中的项目集存放,定义新的Hash函数确定项目集的存放地址,并基于新的Hash表结构,以并行挖掘的方式优化关联规则算法的剪枝过程。实验结果表明,与Apriori算法相比,文中的方法可以更好地节省存储空间,提高挖掘效率。     

适用于范围查询的列存储数据桶划分算法

范围查询是数据库中一项重要的操作.列存储数据库中,能否有效查找一个范围内的属性值,获取对应的行号集合,将极大影响元组重构的效率.与树型结构相比,Hash表对数据的精确查找具有更高的效率,但是范围查找的效率比较低.针对这种情况,提出了一种改进的可用于范围查询的数据桶划分算法.为了能够更好地对算法进行描述,首先提出了可用于范围查询的Hash存储模型(ranged Hash,RH),并给出了桶的值域和序列化的定义.其次针对列存储等“读优先”特性,在RH模型的基础上,提出一种改进的桶划分算法.该算法生成可序列化的哈希函数把属性值划分到桶中,能够同时提高属性值的范围查询效率和存储效率.最后,通过实验结果验证算法的有效性.     

使用Hash表和树位图的两级IPv6地址查找算法

为了提高IPv6地址查找效率,在分析IPv6路由前缀长度分布规律的基础上,提出了基于哈希表及树位图(Tree-bitmap)的两级IPv6地址查找算法.算法将长度为16,32,48和64比特的前缀分别存储在4个Hash表中,其余前缀的前16,32和48比特利用已有的Hash表存储,剩余的不足16比特的部分前缀利用树位图存储,并将树位图的入口地址保存在Hash表中.IP地址查找时在Hash表和树位图中进行两级查找.实验表明,该查找算法的平均内存访问次数为1～2,最坏情况下为7,适用于高速IPv6地址查找.     

一种新的快速IPv6路由查找算法

在分析原有查找算法的基础上,结合IPv6地址结构和骨干路由表特点,提出一种新的快速IPv6路由查找算法。基于Hash表和多分支Trie树结构,将最常用到的路由前缀按前缀长度放置在Hash表中,并按前缀值有序存放在表结点中,不仅可以进行最常用前缀的二分查找,同时又是其他前缀匹配的索引。对于其他的前缀匹配问题,根据Hash表中的索引到相应的多分支Trie树完成最长前缀匹配。分析及测试证明该算法具有很好的时间效率,更新速度很快。     

一种新的快速报文分类算法——RC-FST*

RC-FST 算法利用IP 地址高8 比特前缀建立Hash 压缩索引表, 将分类规则集分成多个子集, 并针对每个子集建立快速搜索树, 而这些规模相对小的本地搜索树更利于实现快速建立、查找和优化。为提高搜索树性能, 在规则分割等问题上也提出了独到的解决方法。该算法查找速度快( 50Mbps) , 支持分类规则数据库大(105) , 可扩展性好, 适于硬件流水线方式实现, 具有很高的实用价值。     

用双链哈希表提高基于网络处理器的防火墙性能

基于网络处理器的防火墙中大量的内存访问会影响对高速网络流的处理速度。哈希表是防火墙中重要的数据结构,用拉链法解决冲突时一次查表的平均内存访问次数与相应拉链的长度成正比。把一条拉链划分成两条可以缩短链的长度,减少总的内存访问次数,从而提高系统性能。介绍了用两条链处理哈希表冲突问题的方法,分析了它对性能的影响,并以网络处理器IXP2400为例给出了具体设计和实现。     

一种基于硬件的大规模哈希流表设计与实现

基于流的报文处理是防火墙、入侵检测等网络安全应用的重要组成功能,其中流表是流处理技术的关键数据结构,流表的规模及访问性能直接影响到流处理的能力和速度。着眼于高速网络下大规模流表的硬件实现,设计了一种基于硬件的千万级哈希流表查找架构,并在FPGA平台上进行了实现和测试。该方案在保证访存效率的同时很好地解决了冲突的难题,利用有限的存储资源,满足了高达4 900万项的流表查找需求,测试能够实现92Mdesc/s的表查找速度,支持约220Gbps高速以太网的处理能力。     

基于软件的网络处理器的路由高速缓存算法研究

路由器需要以较低的代价灵活、高速地实现路由查找这一基本功能.为网络处理器设计了一种基于软件的路由查找高速缓存算法.网络处理器片上高速存储器中的一部分空间被划分出来,由指令代码来维护一个路由查找结果缓存表.通过选择合适的哈希函数,平衡表项之间的冲突并刷新复杂度,该算法可以缩短路由查找的延迟,减少多处理单元对存储器总线的竞争,为其他网络应用提供更多的处理时间.基于真实网络流量的实验表明,即便每个处理单元中仅有少量表项,网络处理器的吞吐量仍然可以得到有效的提升.     

NGN业务平台内存数据库的设计与实现

在下一代网络(NGN)业务的运行过程中,由于大量的呼叫同时存在,因此对数据的访问实时性要求高。针对该情况,提出一种内存数据库的设计开发思路,把业务需要访问的表和数据,通过一个二级散列表的方式,在内存中进行统一存储,并对内存中数据的加载、同步、访问接口等进行了实现。该内存数据库已在上线的NGN业务中成功使用,其可靠性、安全性得到了实际检验。     

An analytical study on optimizing the lookup performance of distributed hash table systems under churn

The phenomenon of system churn degrades the lookup performance of distributed hash table (DHT) systems greatly. To handle the churn, a number of approaches have been proposed to date. However, there is a lack of theoretical analysis to direct how to make design choices under different churn rates and how to configure their parameters optimally. In this paper, we analytically study three important aspects on optimizing DHT lookup performance under churn, i.e. lookup strategy, lookup parallelism and lookup key replication. Our objective is to build a theoretical basis for designers to make better design choices in the future. We first compare the performance of two representative lookup strategies—recursive routing and iterative routing—and explore the existence of better alternatives. Then we study the effectiveness of lookup parallelism in systems with different churn rates and show how to select the optimal degree of parallelism. Owing to the importance of key replication on lookup performance, we also analyze the reliability of the replicated key under two different replication policies, and show how to perform proper configuration. Besides the analytical study, our results are also validated by simulation, and Kad is taken as a case to show the meaningfulness of our analysis. Copyright © 2007 John Wiley & Sons, Ltd.     

基于改进哈希编码的路由查询匹配算法

路由查找算法是网络路由器关键技术之一,为了提高数据查询性能,提出一种基于改进哈希编码的路由查询匹配算法。利用哈希函数压缩数据名字,采用状态转换阵列实现名称最长前缀的快速匹配,将路由节点缓存因素引入路由决策,采用仿真对比实验对算法的性能进行测试。结果表明,与其它路由查询匹配算法相比,本文算法不仅降低了数据内存开销,大幅度减少平均查询时间,而且提高了数据路由查询的效率。     

基于压缩Trie树的以太网地址查找结构

介绍了一种基于hash表和压缩trie树的查找与更新方法,每个hash桶中的4个地址节点按照trie树的方式组织,并压缩成一个25位字。基于FPGA实现时查找速度为133MSPS,IXP1200的一个微引擎每秒可完成1M次转发表更新。与采用片上嵌入式存储器的以太网交换芯片相比,查找过程可以减少一半的存储器访问带宽,转发表可放置到大容量片外存储器中,从而减少交换芯片面积和成本,显著降低hash表的冲突率。     

基于完美彩虹表的检查点算法改进研究

本文对完美彩虹表下的检查点算法进行了研究和改进.时间存储折中攻击是由Hellman于1980年提出的一种适用于分组密码和哈希函数的算法.该算法具有可以用空间复杂度来换取时间复杂度的特点,然而由于链之间的碰撞,算法具有较高的误报率.其一个变种,Oechslin于2003年提出的彩虹表算法可以大幅减少碰撞的数量,从而提升效率.2005年,Avoine等人提出了另一种名为"检查点"的改进,该算法从另一个角度,即降低误报的影响来提升效率.然而,检查点的设置问题(数量和位置)仍未得到完全的解答.在本文中,我们对检查点算法在基于完美彩虹表的条件下进行研究,对检查点的设置进行理论分析,推导出最佳位置的计算式,并构造实验来检验最优选择的结果.在空间复杂度相当的条件下,相较于没有设置检查点的彩虹表,攻击时间可以减少10%到30%.     

Evolutionary design of hash function pairs for network filters

Network filtering is a challenging area in high-speed computer networks, mostly because lots of filtering rules are required and there is only a limited time available for matching these rules. Therefore, network filters accelerated by field-programmable gate arrays (FPGAs) are becoming common where the fast lookup of filtering rules is achieved by the use of hash tables. It is desirable to be able to fill-up these tables efficiently, i.e. to achieve a high table-load factor in order to reduce the offline time of the network filter due to rehashing and/or table replacement. A parallel reconfigurable hash function tuned by an evolutionary algorithm (EA) is proposed in this paper for Internet Protocol (IP) address filtering in FPGAs. The EA fine-tunes the reconfigurable hash function for a given set of IP addresses. The experiments demonstrate that the proposed hash function provides high-speed lookup and achieves a higher table-load factor in comparison with conventional solutions.