论文部分内容阅读
Internet主机的数目正以每两年增加3倍的速度增长，同样Internet流量正以每3个月增加1倍的速度增长，同时由于光纤技术和密集波分复用(DWDM)技术的发展使得链路传输速率已经基本解决。提高Internet性能的关键问题是需要更快的路由器。传统的路由器仅根据目的IP地址转发数据包，提供未加区分(undifferentiated)的尽力服务。而近年来兴起的一些网络应用希望路由器提供相应的功能支持。这些功能包括防火墙、基于策略的路由、区分服务、QoS、流量计费、VPN等。这时就需要路由器区分不同功能的数据包进行不同的对待。
IP数据包分类是路由器根据IP数据包的多个域，从分类器数据库中匹配每个输入数据包，确定数据包转发规则的技术。包含IP源地址和IP目的地址的是二维数据包分类。包含IP源地址、IP目的地址、协议域、源端口号和目的端口号的五维数据包分类是Internet环境下多维数据包分类的主要形式。分类器为实现Internet新业务提供了统一的方式，IP数据包分类是Internet提供一切有差别服务和其他新业务的基础。
本文首先对现有的各种IP数据包分类算法进行了系统、详细的研究，并对各种算法的查找性能和存储空间需求进行了分析比较，分析总结出当前数据包分类领域所面临的问题。
针对多维IP数据包分类算法，提出了CPHTIT算法，该算法是一种基于Cross-Product与HashTree的IP分类算法，结合了交叉积查找和哈希树查找的特点，是在CPHT算法的基础上进行两次改进得出的。仿真实验表明CPHTIT在时间和空间上都达到了高速IP分类的要求，并与现有经典算法GridofTries和Modular比较，综合性能有所改进。