基于改进型MBF的命名数据网PIT存储结构研究

命名数据网(named data networking,NDN)是一种新型的未来网络架构,以解决当今TCP/IP(transmissioncontrol protocol/internet protocol)网络面临的问题.NDN路由器的转发平面采用了一个新的数据结构待定Interest表(pending interest table,PIT),用于记录所有待定兴趣包的转发信息,并根据此信息正确地转发返回的数据包.因此,设计一个高效的PIT存储结构对提高转发性能具有重要的作用.结合Bitmap提出一种改进的数据结构B-MBF(bitmap-mapping bloom filter),该结构采用一个哈希函数实现多次哈希映射以提高检索速度,并利用Bitmap实现元素内存单元的地址偏移量的动态分配.同时,在此基础上提出PIT存储结构B-MaPIT,通过管理多个动态存储空间实现片外存储消耗随元素数量改变而改变.通过仿真实验与现有PIT结构进行了性能对比,结果表明B-MaPIT在存储消耗、数据表构建速度、吞吐量方面具有更优秀的性能表现.     

分组IP路由最长前缀匹配查找算法研究

介绍了几种常见的IP路由查找算法,并简单分析其优点与不足。二进制Trie树结构虽占用空间较小,但因其查找时间太长而很少运用于实际生活中,目前常见的算法都是在查找时间与存储空间上寻找折衷点．本文在此基础之上提出了一种基于分组IP路由最长前缀匹配查找算法,通过将IP前缀按其长度进行分组,并在各组内采用Trie树结构进行存储,最长只需4次存储器访问,且因利用了公共前缀,固能节约存储空间,实验结果表明,本算法在查找时间上取得了非常理想的效果。     

一种基于CHT的可扩展非对称二分查找平衡算法

从讨论非对称二分查找树的平衡问题出发,给出了一种通用的平衡权函数构造方法,解决了Waldvogel等在算法优化过程中提出的启发式平衡权函数构造问题,优化了非对称二分查找树平衡算法,使得CHT(collection of hash tables)算法很容易扩展到128 bit的IPv6地址.实验表明,该算法与Waldvogel等在特殊情况下给出的推测结果基本符合,能很好地适应IP前缀分布的变化,具有很好的适应性和可扩展性.     

使用T-CAM的路由查找表的优化

目前用于实现快速IP地址查找处理的硬件设备主要是T—CAM。本文描述了一种方法，将前缀进行预计算，使前缀表项之间成为前缀无关关系，这样无需保持T—CAM中前缀列表的排序关系，使得其在最差情况下递增式更新时间保持较小，从而解决T—CAM中更新操作复杂的问题。     

用几何参数表实现快速三维重建CT图像

重建时间过长一直是影响三维直接重建在 CT(com puted tom ography)中广泛使用的主要原因之一 ,对于很少采用专用硬件的工业 CT,影响更为严重。用几何参数表方法替代 FDK(Feldkamp- Davis- Kress)算法可以避免由于周期函数的存在而产生的大量重复计算。预先计算出反投影的地址和权重 ,使得反投影的过程中只需从存储的几何参数表中查找。这使得计算量减少到微机可以接受的程度。预插值和最近邻插值的办法能避免大量的插值运算 ,分离变量能避免存储庞大的三维查找表。实验结果说明这些简化在实际系统中是令人满意的     

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

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

用PIC单片机设计数字频率计

介绍了用ＰＣＩ１６Ｃ５４单片机设计数字频率计的原理和技巧，给出了主体硬件结构及关键软件的设计方法。     

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,     

三维图像重构的点云精简算法

为解决光学三维测量系统测量数据的精简问题,提出一种基于图像重构三维的点云精简算法.利用数字图像处理技术,建立数字图像像素点与三维数据点的对应关系表,采用分级方式建立查找表,根据建立的查找表对三维数据进行精简.实验结果表明：精简算法将数据从712 068个点有效地精简至132 064个点,文件大小也从21.6 M减小到4M.该方法能有效对数据进行精简,兼具基于距离和曲率精简的优点.     

分布式路由器中的路由管理模型

高性能分布式路由器中 ,路由管理必须面对两个技术难点 :1)实现高性能的路由查找算法 ;2 )实现主从路由表同步。该文提出一种分布式的路由管理模型 ,给出了这两个技术难点的解决方案。模型实现了路径压缩 Trie树和TCAM硬件相配合的路由查找算法 ,采用了自主设计的过滤算法对路由信息进行过滤 ,并应用 Zebra协议兼容 IPv4和 IPv6路由协议。模型可支持 2 .5 Gb/s接口的分组转发以及 2 0 0 0条 /s的路由更新速度。目前该模型已在国家“八六三”重大攻关项目——“核心路由器”中得到实现