论文部分内容阅读
由于Internet网络用户数目的增长以及多媒体网络应用的广泛使用,未来网络流量将呈爆炸式的增长趋势.随着网络流量持续的增长,Internet若要想继续提供较好的服务,必须同时保持三个关键因素的增长:①链路速率,②路由交换吞吐量,③数据包分类转发速率.目前,对于前两个因素已经研究出基本可行的解决方案,而对于第三个因素,由于数据包转发这一操作需要进行比较复杂的处理工作,仍未能达到较高的处理速率.该文主要针对这一问题进行了深入的探索性研究工作.该文所做的主要工作在于以下几个方面:一、该文针对网络流量的发展需求,对路由查找和数据包分类问题进行了深入的分析.研究了路由查找和数据包分类原理,给出了问题的形式化描述,并为IP分类问题从数学上建模,概括分析了评测算法性能的度量标准以及总结了IP分类算法研究的现状.二、提出了一种基于T-CAM的路由表的优化处理方法.目前用于实现快速IP地址查找处理的硬件设备主要是T-CAM,该文提出了一种将前缀表项进行预计算的方法,使前缀表项之间成为前缀无关的关系,这样就无需保持T-CAM中前缀列表的排序关系,使得其在最坏情况下的渐增式更新时间保持较小值,从而解决了T-CAM中更新操作复杂的问题.三、在基于T-CAM的路由查寻算法的设计思想上,使用精简划分方案同时结合Trie数据结构来解决对非前缀规则的分类算法.设计了聚合位串的并行解决方案,并将其并行处理的思路应用到了一般的针对非前缀规则的多维数据包分类算法中.四、提出了一个解决二维包分类的CSD算法.该算法基于对计算几何的洞察,用多维空间来表示多维过滤器,多维空间中的点来表示到达的数据包,将数据包和过滤器的匹配用多维空间中点的定位来实现.并通过对传统Trie结构的适当变动和对多维查找空间的递归划分,较好地设计了空间定位问题的数据结构,另外还有效地实现了向多维数据包分类的扩展.五、从二维IP分类出发提出了一种适用于多维的高效IP分类查找算法--TSBP算法.它以位并行算法为出发点,通过引入位图映射与元组空间的概念,大大降低了位并行算法的空间占用量.六、在前文的理论研究分析之后,又对部分算法进行了实施,并对算法进行了相应的仿真模拟测试和实验性能比较分析,还与其它算法进行了比较.实验结果基本上与理论分析吻合,达到了预期的效果.