快速路由器的路由查找和流分类算法研究.pdfVIP

第33 卷 第6 期 电 子 科 技 大 学 学 报 Vol.33 No.6 2004 年12 月 Journal of UEST of China Dec. 2004 快速路由器的路由查找和流分类算法研究 姚兴苗， 李乐民，胡光岷 ( 电子科技大学 宽带光纤传输与通信网技术教育部重点实验室 成都 610054) 【摘要】分析了路由器的体系结构发展，研究了路由查找算法和流分类算法在快速路由器中的应用。研究表 明，基于分段压缩的路由查找算法支持IPv6路由查找，具有合理的存储容量和快速的查找时间；采用按值分支树 的多维综合流分类算法支持前缀和范围匹配，可扩展性强，适合大容量规则数据库。两种算法适合在快速路由器 中应用。 关 键 词 体系结构; 路由查找; 流分类; 快速路由器 中图分类号 TP393 文献标识码 A Research on IP Route Lookup and Packet Classification Algorithms for High Speed Router Yao Xingmiao ，Li Lemin ，Hu Guangming (Key Laboratory of Brodband Optical Fiber Transmission and Communication Networks UEST of China, Ministry of Education Chengdu 610054) Abstract The development of router architecture is analyzed, and the fast route lookup and packet classification algorithms for high speed router are researched. The research shows the lookup algorithm for IPv6 route lookup with compression trie has reasonable memory space and fast lookup time. The compositive multi-dimensional packet classification algorithm based on tree divided by value is scalable. It can deal with prefixes match and range match for large rule sets. Two algorithms are suitable for high speed router. Key words router architecture; route lookup; packet classification; high speed router 随着Internet 的快速发展和各种宽带技术的不断出现，以及多种Internet业务的增长，路由器的体系结构 不断发展，第一代路由器主要采用单处理器共享总线式结构，中央处理器通过通用的总线与多个接口卡互 连。中央处理器负责包括路由收集，报文转发处理等所有的事务处理。这种体系结构的性能主要取决于中 央处理器的速度和共享总线的带宽，路由器扩展性比较差。第二代路由器在网络接口卡上采用了一些智能 处理，如业务接口卡的cache技术来增加转发速率。第三代路由器采用路由与转发相分离的技术，从而有效 地解决了路由计算能力的问题，并且总线技术也得到了较大的发展。第四代路由器采用硬件ASIC转发模式 和交换结构，解决了带宽容量和性能不足的问题。第五代路由器继承了第四代路由器的优点，增加了更为 灵活的网络处理器。对于一些复杂的标准操作，如路由查找算法等，采用硬件协处理器方式提高处理性能，