基于有限前缀扩展和多Hash函数的动态IP路由查找算法

该算法根据IP路由表的分布特征将前缀有限扩展为三种长度,并用算法所提出的最大熵判定法选取多个Hash函数,将扩展后的前缀映射到三个Hash表的不同级别.在查找过程中算法根据三个Hash表的命中率动态计算查找代价,并据此调整对三个Hash表的搜索顺序.算法支持增量更新,适于软件实现和硬件流水实现.实验表明,对128K前缀的真实转发表算法仅约需3.7M字节,平均每次查找仅需约1.1次访存,而且路由更新时间较小.

基于前缀扩展的三级索引路由查找算法

根据路由表前缀扩展特性,采用特殊的结构构造索引表,提出了一种基于3级索引的储存表查找方法,进行流水线方式的并行查找。引入了缓冲池的思想,提出了一种改进的路由表更新方法,同时该算法支持动态更新。与基于压缩算法相比,该算法数据结构简单;与传统TCAM路由查找相比,可以节省约40%的功耗。此外,该算法在查找性能、路由更新和存储空间方面也有很大优势,能够达到最少访问一次存储器,最多需要访问3次实现处理一个IP数据包。

应用扩展前缀编码的测试数据压缩方案

提出一种扩展前缀编码的测试数据压缩方案,采用变长到变长的编码方式对任意长度的0游程和1游程编码,代码字由前缀和尾部组成,用扩展的前缀表明编码的游程类型;不引入额外的标记位,并能有效地压缩芯片测试数据量.理论分析和实验结果表明:扩展前缀编码能取得比FDR编码更高的压缩率,能够更好地适应于多样的编码对象.解压时使用一种特殊的计数器简化控制电路,解码电路硬件开销小且较易实现.

基于扩展前缀树的协议格式推断方法

对未知网络协议进行协议格式推断在网络安全领域具有重要意义。现有的协议格式推断方法存在时间复杂度高、精确度较低等问题。提出了一种基于扩展前缀树协议格式推断方法。该方法首先通过N-gram分词获取候选协议关键词,使用互信息进行合并得到不同长度的协议关键词。在此基础上,依据与报文相对应的关键词序列构建扩展前缀树,实现对报文样本的初步聚类。而后,在扩展前缀树的基础上采用分段的多序列比对方法获取精确的协议格式。实验结果表明,该协议格式推断方法对于文本协议和二进制协议都能够取得理想的推断效果。

LTE-A系统中基于扩展CP的Rank 3-4解调参考信号设计

为了支持先进的长期演进（LTE-A）中更高阶多输入多输出（MIMO）技术，为物理下行链路共享信道（PDSCH）定义了新的解调参考信号（DMRS）。先提出了基于扩展循环前缀（CP）的参考信号设计原则，根据已确定的基于常规CP的参考信号设计方案，提出了4种基于扩展CP的Rank 3，4参考信号设计方案。为了验证设计方案的优劣，通过仿真比较了不同参考信号设计方案估计的信道和理想信道的均方误差（MSE）和相应的误块率（BLER），最终确定最佳的扩展CP的Rank 3，4参考信号设计方案。

IP路由缓存技术研究

针对目前用于IP路由查找的地址缓存技术和前缀缓存技术的局限性,分析了骨干网路由表前缀重叠特征,提出了一种基于阈值的IP路由缓存方法,该方法结合了地址缓存和前缀缓存技术,无需进行前缀扩展,克服了地址缓存技术缓存空间要求过大、前缀缓存技术无法缓存内部前缀节点的问题,在缓存空间、缓存命中率、缓存公平性以及路由增量更新方面具有优势;仿真实验表明对于路由条目超过260000的路由表,缓存空间大小为30000,选择阈值K=4时97%以上的节点可实现1:1缓存,其余节点采用地址缓存,缓存失效率小于0.02,可以用小的缓存空间实现高速线速转发.

路由查找算法的性能分析与研究

本文介绍了当前几种路由查找算法,并对这几种路由查找算法的复杂度和实际运行性能进行了分析研究。研究表明,虽然二分查找算法在查找性能上没有很大提高,但是在IPv6环境中由于多分支Tire树的查找性能将会有很大的降低,因而二分查找算法的优越性将会得到充分体现。

动态快速路由查找算法

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

一种基于分段压缩的IPv6路由查找算法

提出了一种基于分段压缩的快速 IPv6 路由查找算法。与文献中的 LLCAT 算法相比,该算法节省了存储空间,当某扩展节点的表项所对应的前缀数量小于预先设定的值时,前缀不再扩展而使用压缩算法。同时,最坏情况下算法的查找时间和更新复杂度基本没有改变。仿真试验结果表明:算法的平均查找时间和消耗的存储器容量都优于 LLCAT 算法。

基于多分支Trie的路由查找算法设计与实现

基于多分支Trie数据结构的查找算法在路由查找中有着广泛的应用。文章对基于多分支Trie的路由查找算法进行了介绍,并对其特点进行了分析。在此基础上,设计实现了便于高速动态路由查找的多分支Trie数据结构,公开了一个使用多分支Trie数据结构的基于前缀值的动态最长前缀匹配算法,提高了路由查找速度。

大规模IPv6网络拓扑发现探测目标点的构建和选取

探测目标点的数量及分布位置对网络拓扑发现的覆盖率和探测效率有直接的影响,因此成为网络拓扑发现研究领域一直关注的焦点。本文针对目前大规模网络拓扑发现目标点相关研究现状,提出了两种目标点集合构建方法,在对目标点冗余分析的基础上提出了相应的探测目标点选取方法。最后通过对CERNET-2骨干网络的实际测试,说明了本文提出的这些方法可以推广至国家级规模的IPv6网络拓扑发现应用中。

路由查找算法的性能分析与研究

该文介绍了当前几种路由查找算法,并对这几种路由查找算法的复杂度和实际运行性能进行了分析研究。研究表明,虽然二分查找算法在查找性能上没有很大提高,但是在IPv6环境中由于多分支Tire树的查找性能将会有很大的降低 ,因而二分查找算法的优越性将会得到体现。