IS-IS协议路由计算方法的研究和实现

作     者：范炜玮 

作者单位：国防科学技术大学 

学位级别：硕士

导师姓名：苏金树

授予年度：2004年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：高性能路由器 IS-IS 链路状态路由协议 路由表 并行 路由计算 

摘      要：随着网络技术的飞速发展和网络规模的迅速扩大,路由设备的作用日益重要,对它的性能要求也随之提高。路由协议在路由器之间实现信息交换,其本质就是收集网络中的路由选择信息并选择到所有己知目的网段的最佳路径,因此路由计算过程和路由表的组织与管理对于路由器的功能增强和性能提高起到关键的作用。 本文在深入理解IS-IS(Intermediate System-to-Intermediate System)路由协议运行机制的基础上,依据RFC和ISO的标准给出了IS-IS路由计算算法的设计与实现;根据当今网络前缀的分布特点,提出了一种基于Hash的路由表组织方法,并对这种方法进行了改进;最后针对核心网络上具有多个路由节点的路由器提出了一种并行路由计算方法,使得路由计算能够在多个节点中同时进行。 本文的主要工作包括: ***-IS路由协议是一种链路状态路由协议,在利用路由信息进行路由计算的时候采用的是最短路径优先(Shortest Path First,SPF)算法。因此,首先对SPF算法有比较深入的了解,并在此基础之上设计及实现了IS-IS路由协议的路由计算过程;2.研究了路由表的高效组织与管理。分析了当前常用的路由表组织方法,提出了一种基于Hash的路由表的组织方式,结合网络前缀的分布特点,对这种基于Hash的路由表组织方法进行了改进和实验,在理论上分析了该算法的性能,并在实验中比较了该算法和其它算法的性能差异;3.针对目前大型网络中核心层采用的高性能核心路由器有多个路由节点的特点,将现有的IS-IS路由域划分为路由子域(Routing Sub-Area,RSA),提出了一种由各个路由节点并行计算路由表的方法,给出了算法的正确性以及可行性分析,在路由节点数目为n的情况下,能将域内更新路由计算的加速比提高到n至n,域外更新路由计算的加速比提高到n。