基于随机分布的多比特Trie树IP数据包分类算法研究

在无冲突散列算法和多比特Trie树算法的基础上,提出了一种基于随机分布的IP分类算法,该算法的核心有3点:一是基于目的,源端口和协议域构造无冲突散列,由于该三域的组合数目非常少,避免了空间爆炸;二是将目的/源IP连成比特串后分为4块,每块16bit,并将其中一块映射到一随机空间,将随机数和其余3块进行异或,获得分类索引值,并用此值生成多比特Trie树,一般情况下减小了空间和时间复杂度;三是在Trie树终点存放最终分类规则的索引值,为了保证查找到的规则的正确性,对每一个索引值的源,目的IP地址均匹配一次.通过以上3点改进一般要降低算法的时间复杂度和空间复杂度,通过仿真,当对10 000条分类规则进行包分类时,该算法的包分类速度可以达到2Mpaekut/s,所消耗的最大内存为1MB.     

IP分类技术研究

网络应用的发展要求路由器必须有能力支持防火墙、QoS、流量计费等一系列功能.这就要求路由器对IP包进行分类,根据分类结果完成对数据包的不同处理.本文全面地介绍了IP分类技术研究的最新成果,以及IP分类的典型算法.最后本文对其中三种典型算法在虚拟环境下做了评测,比较了它们的优缺点.     

流分类算法研究综述

流分类问题是未来宽带通信网络中的关键技术之一。对流分类算法的现状进行分析讨论，并对其今后的研究思路进行探讨。     

一种基于Trie的快速IP路由查找算法

Internet的飞速发展要求核心路由器能够实现快速的分组转发和路由更新功能,实现这一功能的关键是路由表的组织结构和快速的路由查找算法.提出了带有转发域信息树的多分支Trie结构路由查找算法,它由固定步长的多分支Tile结构的路由表和转发域信息树两部分组成.对于一个长度为w的路由前缀,其查找、插入、删除路由的时间复杂度均为O((w-m)/n+1),其中m、n为Trie树的步长.它解决路由查找过程中快速更新的问题,具有算法简单、查找速度快、易于更新、空间利用率高、便于向IPv6过渡等优点.     

一种基于索引指针的可扩展IP包分类算法

设计并实现了一种基于索引指针的可扩展IP包分类算法.该算法通过分析源/目的端口号和协议类型字段在实际应用中的分布特性,将这3个字段映射到一个8比特元组上,压缩了分类维数;算法依据压缩后的8比特元组将分类规则集划分为256个子集,并为每个子集建立一个索引指针,指向该子集的存贮起始地址;算法通过计算IP包中"源/目的IP地址联合字段"中各个比特的信息熵值,找出最优的比特序列作为根和子节点,为每个规则子集建立一棵Tries查找树,既保证了存贮空间和查找时间最小,而且不存在回溯问题.实验结果证明,该算法分类效率高.     

基于分割多分枝Trie树的并行路由查找算法

为解决在多核处理器平台下路由器报文转发时路由查找速度慢的“瓶颈”问题,提出了一种基于分割的多分枝 Trie树的并行路由查找算法。该算法将一棵多分枝 Trie 树根据处理器的核数分割成若干子树,每棵子树又构成一棵单独的多分枝Trie树,子树中取消了前缀查找,采取组成一个大中间节点的方式,在中间节点之间采用固定步长查询,中间节点内部采用二进制Trie树来表示。实验结果表明,该算法具有访存次数少、查询速度快、占用存储空间少和更新开销小等特点,同时适用于IPv4和 IPv6地址。     

基于Grid Of Tries的无冲突多维IP分类算法

快速IP分类算法是提高网络设备性能的关键，无冲突规则集则是正确进行IP报文分类的前提和保证、本文首先形式化描述了IP分类算法和规则冲突问题，介绍了常用的IP分类算法及冲突解决策略，并提出了一种基于Grid Of Tries的无冲突多维IP分类算法，解决了规则集中存在冲突的问题，最后对该算法进行了性能分析和展望。     

一种多维IP包分类算法

IP分类算法是应用在高性能路由器中的一种重要算法，研究IP分类算法对于提高路由器综合性能具有重要意义。基于无冲突哈希函数和AQT算法提出了一种新的IP分类算法NCHAQT（Non—Collision Hash AQT）。NCHAQT解决了AQT算法只能应用于二维的情况，使AQT可以应用于五维分类，增强了它的可扩展性。理论分析与仿真实验表明，NCHAQT在时间性能上算法优于经典算法Modular，是一个综合性能较高的包分类算法．     

星上路由查找的设计与分析

星上路由器是构建下一代全球信息网络的重要节点设备,路由查找是影响数据转发性能的关键技术之一。考虑到空间环境对设备在可靠性、重量和功耗等因素的限制,该文通过分析比较多种路由查找算法,根据软硬件协同设计的思想,给出了适合星上硬件路由查找的设计与分析。     

IP交换中流分类的神经网络方法

本文对IP交换机中流的分类问题进行了探讨。首先对现有的X／Y分类器进行了分析,指出其不足之处,然后总结了进行流判断时应考虑的各种因素。之后提出了一种利用Hopfield神经网络进行流分类的方法,并对其参数的选取进行了讨论。仿真结果表明,神经网络分类器可根据网络中流的具体情况,自动调节分类阈值,保证IP交换机利用的VC数基本稳定。与常规X／Y分类器相比,神经网络分类器可利用更少的VC交换更多的数据包。     

分类算法的分析与比较

在全面综述通用机器学习归纳分类算法的基础上,采用算法分类机制分析的方法,从预测精度、学习效率、健壮性等方面对决策树和规则归纳分类算法进行深入的分析和比较研究,为在不同的应用领域选择最优分类算法奠定了基础。由于RIPPER分类算法采用了重复增量裁减机制,所以在计算复杂性、分类精度、噪音数据适应性等方面都优于其它分类算法,更适用于入侵检测建模使用。     

基于哈希的IP会话分时段统计方法

研究了基于哈希的IP会话分时段统计方法。它增加了对时间维度的考量,从而能够满足单地址、地址对和时间粒度多维度的业务量统计,并成功应用于商用网络分析产品中。     

基于压缩NH表的高速IP路由查找算法的研究

由于因特网速度不断提高、网络流量不断增加和路由表规模不断扩大,IP路由查找已经成为制约核心路由器性能的主要原因,因而受到了广泛重视.目前人们已经提出几种高速IP路由查找算法,但没有一种是理想的.本文提出一种使用压缩NH表进行IP路由查找的方法,它具有查找速率高、更新时间快、存储代价低、易于实现等特点,能满足10Gbps速率核心路由器环境的要求.     

PTN芯片中IP组播查找电路的设计与实现

网络数据量的急剧增加,带来了带宽的急剧消耗和网络拥挤问题,这些问题对分组传输网络芯片的转发容量、速率、拥塞避免和流量管理等方面提出了更高的要求。为了提高分组传输网络芯片中 IP组播查找电路的工作速率和降低电路设计复杂度,采用流水线结构,并利用 RAM(随机访问存储器)记录查找中间状态信息等技术完成了对 IP 组播查找电路的设计。在Altera系列FPGA(现场可编程门阵列)开发板EP4SGX230KF40C2ES上进行了硬件验证,结果表明,该电路能够完成IP组播查找功能,并稳定工作在200 MHz频率下。     

IP router architectures: an overview

In the emerging environment of high performance IP networks, it is expected that local and campus area backbones, enterprise networks, and internet service providers (ISPs) will use multigigabit and terabit networking technologies where IP routers will be used not only to interconnect backbone segments but also to act as points of attachments to high performance wide area links. Special attention must be given to new powerful architectures for routers in order to play that demanding role. In this paper, we identify important trends in router design and outline some design issues facing the next generation of routers. It is also observed that the achievement of high throughput IP routers is possible if the critical tasks are identified and special purpose modules are properly tailored to perform them. Copyright © 2001 John Wiley & Sons, Ltd.     

高速路由器中快速地址查找方案及其实现方法研究

本文提出一种用于高速路由器的IP地址快速查找方案，探讨其实现方法，并对其性能进行了分析和比较。     

一种节省存储量的SOVA子译码器IP核的设计

在简单分析SOVA译码算法的基础上,对SOVA子译码器IP核的设计进行了整体分析;从硬件实现的角度,对译码算法的特征进行了理论分析,得到了对称状态节点的软信息具有确定关联的结论;并据此优化了硬件设计,极大地减少了存储资源的占用。同时,采用其他两种减少存储空间的优化设计方案和流水线策略,进一步减少了SOVA子译码器的功耗。对以上优化设计方案进行了设计实现。仿真结果及FPGA硬件测试验证表明,文章提出的优化方案可行、有效,极大地降低了硬件资源占用和功耗。