随着光纤通信技术的飞速发展,链路的传输能力迅速提升,而路由器转发数据的能力相对落后,其主要原因之一是路由查找的困难。路由查找是为到达路由器的数据包找到转发端口,其依据是路由表。一方面,随着因特网规模扩大,路由表急剧膨胀,需要更大的存储空间,导致路由查找速度降低。另一方面,由于路由表结构的复杂,必须采用最长地址前缀匹配算法,既要比较目的IP 地址和地址前缀的值,又要比较地址前缀的长度—二维查找。这些特点说明了路由查找技术研究的意义和难度。面对不断膨胀的路由表和高速数据转发的需要,路由查找技术的研究受到广泛的重视。传统的二维查找算法不能满足高速数据转发的要求,许多研究者提出了新的解决方法,路由器的数据转发能力有明显提高。仍然,有许多问题需要研究,如:(1)在提高路由查找效率的同时,如何保证高效的路由更新操作?(2)基于硬件的算法能够提高路由查找的速率,但需要克服高能耗、路由更新的困难; (3)设计适应IPv6 地址结构的算法等。针对这些问题,本文选择了“高速数据转发引擎的关键技术研究”这一课题,对数据转发引擎的主要技术,如交换结构、调度算法、路由查找等进行了系统的分析。然后,基于路由表结构的分析,提出了一种研究路由查找技术的新思路。本文从分析路由表中地址前缀之间的关系出发,提出了一种分类方法,将地址前缀分为:独立前缀、根前缀、子前缀。然后,采用数据结构Trie 描述地址前缀,定义了地址前缀的级别,提出了路由表结构的概念。通过分析实际路由表,发现:各级别地址前缀数的比例相对固定; 级别的最大值远小于理论值; 与同一IP 地址匹配的地址前缀数较小,即只需要在较少的地址前缀中搜索最长匹配前缀等。通过研究路由发布行为对路由表的增长、结构变化的影响,发现:地址分配策略对路由表中独立前缀、根前缀的长度分布会产生显著的影响,但对子前缀的长度分布没有明显的影响; 用户发布分段的地址前缀是导致独立前缀增长的主要原因之一; 发布子前缀是导致路由查找困难的根本原因等。利用地址前缀级别的定义,提出了一种基于层次划分技术的路由查找算法。路由表中每项地址前缀有唯一的级别,由此,提出了一种按层次划分路由表的方法,将路由表按级别划分为几个部分。各部分路由表中地址前缀互不相交,对于任何IP地址最多有一个匹配的地址前缀,因而在各部分路由表中可采用精确匹配算法查找