基于源转发树路由结构的多播路由表查找方案的比较

随着多播通信在Internet上的应用越来越广泛，对多播路由表查找算法的性能要求越来越高。该文提出了几种基于源转发树路由结构的多播路由表查找方案，并给出实验结果比较。     

快速路由查找算法研究

随着互联网络光链路速率不断提高，路由查找已成为路由器报文转发的瓶颈。主要介绍近年来提出的各种路由查找方法，并对各种方法的性能及对IPv6适应性进行了分析比较。     

基于代数决策图的路由查找算法

为解决路由查找过程中路由表项数不断增加导致存储冗余大和查找效率低的问题,在代数决策图(ADD)的基础上,提出一种改进的路由查找算法。根据符号算法的特性对路由表项进行伪布尔函数表示,综合考虑路由表结构特征和符号算法的优势,基于ADD结构构建基于前缀的路由表,并给出路由表更新、删除、查找算法。通过国际项目管理协会提供的开源路由表进行实验仿真,结果表明该算法能够有效减少路由表操作时的内存访问次数,节省路由表存储空间。     

UCLA网络加速器路由表快速查找改进模型

论文针对网络服务的应用,研究了UCLA设计的网络加速器模型,发现UCLA网络加速器设计在某些情况下得到较多不合理的下一跳出口地址,减低了加速器的性能。通过增加运算符改进加速器的运算,减少了所查找的路由表的出口数目,能更准确地定位下一跳的位置,提高了加速器的效率。     

一种改进的二分法IPv6路由查找算法

随着IPv6协议的广泛应用，传统的IPv4路由表查找算法不再适应IPv6网络环境中路由转发的需要。该文在基于hash表的二分查找算法基础之上，提出了一种改进算法，该算法应用于超大规模路由表时能表现出较好、稳定的运行效率。为了减小内存消耗，还针对该算法提出了优化方案，并通过实验数据进行了对比分析。     

基于RAM和TCAM存储结构的高速路由查找算法

由于因特网速度的不断提高,网络流量的不断增加和路由表规模的不断扩大,IP路由查找已经成为制约核心路由器性能的主要瓶颈。文章分析了两种常用的基于硬件存储器的路由查找算法,并结合它们各自优点,提出了一种基于RAM和TCAM存储结构的路由查找算法,该算法克服了上述两种算法的不足,具有查找速率高、更新时间快、存储代价低、易于实现等特点,是一种理想的适合于高速核心路由器环境的查找机制。     

高速路由器中基于树型结构路由查找算法的研究与实现

本文在比较各种基于树型结构查找算法的基础上提出了一种改进的路由查找算法,该算法具有查找速度快、所需存储空间小、更新速度快、硬件实现简单等特点,能够满足10Gbps核心路由器环境的要求。     

混合查找算法

本文对数据的比较查找提出混合查找算法，充分利用有序数据局部均匀性的特点，效率优于二分查找。     

B-树和Bloom filter相结合的IPv6路由查找算法

为了提高IPv6的路由查找效率,针对IPv6路由前缀分布不均匀的问题,提出了一种基于B-树和Bloom filter相结合的IPv6路由查找算法（BTBF）。BTBF分为B-树和Bloom filter查找两部分,利用B-树查找路由前缀的前16 bit值,然后通过B-树节点中位向量的映射,将下一步链接到Bloom filter,再利用Bloom filter位数组的值映射提取下一跳。实验结果表明,BTBF算法与其他树型和Bloom filter类算法相比有效减少了空间和时间占用,在路由表项数变化较大的情况下也能维持稳定的查找性能。     

路由查找算法研究综述

随着Internet的迅猛发展,用于主干网络互联的核心路由器的接口速率已经达到了2.5Gbps～10Gbps.这一速率要求核心路由器每秒能够转发几百万乃至上千万个以上的分组.分组转发的重要一步就是查找路由表,因此快速的路由查找算法是实现高速分组转发的关键.路由查找需要实现最长前缀匹配.近年来,研究人员提出了多种路由查找算法,以提高查找性能.分析了路由查找问题及其难点,全面综述了各种查找算法,并对它们进行了详细的分析和比较,最后指出了进一步的研究方向.     

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

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

基于多层混合结构的IPv6路由表查找算法

针对现有的大多IPv6路由表查找算法采用各种优化手段提高查找性能,却使得路由更新需要重构整个路由表的问题,提出基于多层混合结构的IPv6路由表查找算法。该算法在第一层借鉴最优查找树的优点,把前缀1~16位的不同取值按其在路由表中出现的概率降序存储在线性表中,在第二、三层把前缀的17~32位和33~48位分别用二叉平衡树组织,在第四层把49~64位使用线性表组织。实验结果表明,该算法查找速度快,占用内存少,动态增量更新速度快。     

基于LFT和DAG方式的IPv6路由查找算法

随着网络的不断发展,路由表的信息量也在不断增加,这势必会影响路由转发的效率,影响网络速度.在分析了衡量路由算法优劣的标准后,又通过对现有IPv4和IPv6各种路由算法的分析,尤其是LFT和DAG结构的说明,综合了二者以及LC Trie的优点,提出了算法改进的思想,给出了算法的主要数据结构以及算法执行的流程图,此算法提高了路由查找效率.     

一种基于哈希编码的内容路由查询匹配机制

基于名字的路由查找是命名数据网络(NDN)的一个关键技术,但由于NDN名字层次化的结构以及无限制的长度,使得查询匹配的实现具有很大的挑战性.提出一种有效的元素哈希编码机制,首先利用哈希函数压缩数据名字,然后采用改进的状态转换阵列实现名称最长前缀的快速匹配,最后设计一种快速的增量更新机制,满足NDN转发过程中频繁地插入、修改与删除等操作.仿真结果表明,提出的方法使路由条目压缩率达到40％以上,匹配速率提高约10％.     

A complete lookup table for marching cubes

The well-known marching cubes method is used to generate isosurfaces from volume data or data on a 3D rectilinear grid.To do so,it refers to a lookup table to decide on the possible configurations of the isosurface within a given cube,assuming we know whether each vertex lies inside or outside the surface.However,the vertex values alone do not uniquely determine how the isosurface may pass through the cube,and in particular how it cuts each face of the cube.Earlier lookup tables are deficient in various respects.The possible combinations of the different configurations of such ambiguous faces are used in this paper to find a complete and correct lookup table.Isosurfaces generated using the new lookup table here are guaranteed to be watertight.     

基于亚像素边缘定位点查找表的检测算法

提出了一种新型的测量图像快速亚像素边缘检测方法。首先通过计算机模拟仿真,找出图像边缘处灰度落差与边缘点偏移之间的规律性,建立了一个由灰度落差得到边缘亚像素定位点的查找表;然后结合改进的Sobel检测算子和十字窗检测法将图像边缘检测精度达到像素级,并应用查找表实现了亚像素级的检测精度。实验表明:该方法不仅得到了较高的检测精度,定位精度为0.3pixels,而且可以大大地提高检测速度。     

基于无冲突哈希表和多比特树的两级IPv6路由查找算法

为了提高IPv6的路由查找效率,根据IPv6路由前缀分布规律和前缀层次关系,提出了基于无冲突哈希表和多比特树的两级IPv6路由查找算法。该算法将地址前缀划分区间并按长度为32,40,48比特分别存储于3个哈希表中,剩下不足的前缀比特由多比特树存储,IPv6路由查找时在无冲突哈希表和多比特树中两级查找。实验表明,该查找算法的平均查找路径数为1.0~1.7,适用于高速的IPv6路由查找。     

Efficient lookup table based camera pose estimation for augmented reality

Until now, exising camera pose estimation methods for the widely used square marker‐based augmented reality (AR) are either highly sensitive to noise or much time consuming, and developers have to work hard to find the proper trade‐off between computational speed and quality in mobile AR applications where computational resources are limited. The major difficulty is that only the four corner points of the square AR marker are available, and no redundant point correspondences can be used for a stable estimation. To solve this problem, an efficient lookup table (LUT)‐based non‐iterative solution is presented in this paper that achieves high stability in the presence of noise better than the most robust and accurate iterative solutions in the field, with the same level of accuracy and a much lower computational complexity. Our central idea consists of extracting a key parameter β from the camera pose and creating a LUT for β by taking the symmetrical structure of the square marker into account, thereby exploiting additional information. Copyright © 2011 John Wiley & Sons, Ltd.     

防火墙寄存器技术的FPGA低功耗布线算法研究*

针对减少毛刺能够有效地降低电路功耗,提出了一种基于防火墙寄存器技术的FPGA低功耗布线算法。在布线过程中,一方面运用算法增加防火墙寄存器滤掉毛刺;另一方面通过修改代价函数,动态地调节输入信号的路径,使信号到达查找表输入端的时间基本趋于一致,从而有效地减少毛刺,降低电路的动态功耗。实验结果表明,在运算时间相同的情况下,与其他算法相比,该算法平均能消除约72%～81%的毛刺,降低约4%～8%的功耗,减少约23%～26%的关键路径延时,而只增加4%的触发器。