BGP路由查表算法的分析与改进

Default-Free Zone内的路由器拥有巨大的路由表项,为了方便实现,大多数开发者在实现过程中均采用路径压缩树的数据结构对边界网关协议路由进行存储。计算机仿真分析发现,采用路径压缩树算法会引起路由搜索时间抖动严重、存储空间利用率低,路径压缩树性能受BGP路由前缀的分布特性影响。引入AVL算法解决存在的问题,可以较好地提高路由查表的性能。

基于在线有向无环图的船舶轨迹压缩算法

为了解决船舶轨迹数据的压缩问题,提出了一种船舶轨迹在线压缩算法;使用多次滑动推算船位判断方法清洗船舶轨迹,使用在线有向无环图在干净轨迹上建立压缩路径树并输出采样点;为了提高轨迹队列和路径树在内存中的查询速度,使用哈希表对其进行管理;为了验证提出算法的效果,比较了真实船舶自动识别系统数据与方向保留算法、道格拉斯-普克算法的压缩时间和误差,采用可视化方法分析了原始轨迹、清洗轨迹和压缩轨迹。试验结果表明:在压缩时间方面,方向保留算法和道格拉斯-普克算法的压缩时间分别约为提出算法的1.1、1.3倍,说明提出的算法比其他2种算法的处理时间更短;提出的算法在压缩过程中保留了时间信息,平均同步欧氏距离误差在任何压缩率下都能保持在10 m以下,最大同步欧氏距离误差在压缩率为1%时仅有127 m,而其他2种算法的平均同步欧氏距离误差和最大同步欧氏距离误差不受控制,会随机变化;在垂直距离误差方面,提出的算法与道格拉斯-普克算法在压缩率不小于5%的条件下,都能保证垂直距离误差小于20 m,而方向保留算法的垂直距离误差会随机变化;在显示效果方面,提出的算法能有效清除轨迹噪声点,压缩轨迹能够较好地代表原始轨迹的宏观交通流情况。可见,提出的算法能更高效地保留原始轨迹的形状和时间信息。

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

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