IP地址查找中的数据结构及其性能分析

许多计算机应用涉及字符串处理。为了提高处理效率,设计一个好的数据结构十分重要。本文以IP地址查找为应用背景,分析了数据结构trie及其变种的结构特性、查找性能和应用方法,表明了trie作为一种通用的数据结构的重要性。

基于SD-Torus网络的分布式IP地址查找

针对IP路由器的FIB(Forwarding Information Base)极限问题和分布式IP地址查找中的通信延迟问题,提出了SD-Torus(Semi-Diagonal Torus)直连网络。按照"临近存储"的原则,将路由表划分后存储在每个节点及其邻居节点上,以减少分布式IP地址查找中的通信延迟,提高整体的查找性能。在分析SD-Torus网络拓扑性质的基础上,提出了一种负载均衡的路由算法。基于SystemC的仿真结果表明,使用该结构可以大大降低分布式IP地址查找的通信延迟,提高系统的扩展性。该研究结果可以应用于高性能的分布式IP地址查找。

IP地址查找算法的分析

由于Internet中通信量的迅速增加，千兆网已被越来越多地采用。为了处理千兆/s的通信速度，中心路由器必须能够每秒转发几百万个包。因而快速的IP地址查找，就成为获得所需的数据包转发率的关键。文章分析了几种高效的IP地址查找算法，并从查找速度、可量测性、更新速度方面，对它们的性能进行了比较。

基于集合理论的IP地址并行搜索技术

针对现有的IP地址查询技术存在查找速度慢、性能低、可扩展性差、算法空间复杂度大以及成本高等问题,提出了一种结合使用软硬件的方法执行IP地址查询,将路由集合分割成奇偶位两个子集,然后对每个子集进行搜索.此方案能以较低的硬件代价在较短的时间内搜索到IP地址的网络ID号,减少了查找的比较次数和存储空间.

一种基于Trie的流水式IP查找结构

为了减小基于Trie的流水式IP查找引擎的内存占用和延时,基于优化线性流水线(OLP),利用其引入空操作(Nop)能够更灵活布局的特点,提出了EOLP(Enhanced Optimized Linear Pipeline)方案,包括前缀扩展长度确立算法,流水线长度确立方案,布局算法和编码算法.实验结果表明,相对于OLP方案,EOLP方案的内存占用和流水线延时至少减少了1/6,能够完全布局Trie节点,并达到了72Gb/s的吞吐率,满足高速网络的需求.

基于路由的网络流向特征分析

通过BGP路由表中地址段和自治域信息来聚合IP流可以对数据流向特征有较好的描述。以流经一个较大规模校园网接入链路的IP流数据为分析对象，有流量发生的地址段和自治域在概率分布上呈现出相当的聚合度，即约20％的地址段和自治域承载了绝大多数的数据通信量，所取得的特征分布对于网络路由优化、路由策略的设置和容量规划具有指导作用。此外，根据统计结果可得出一些网络安全方面的启示。

垃圾邮件源的地理分布

为了测量垃圾邮件的地理分布情况，FOPE会根据在网络边界拦截的垃圾邮件的源IP地址查找其地理位置，将IP地址同它们所代表的国家／地区对应起来。当前大多数的垃圾邮件都是通过僵尸网络或其他自动化工具发送的，因此，即便知道垃圾邮件是从哪个地理位置发送的，