|
二、Dijkstra算法 Dijkstra算法是路由表计算的依据，通过Dijkstra算法可以得到有关网络节点的最短路径树，然后由最短路径优先树得到路由表。 1.Dijkstra算法的描述如下： （1）初始化集合E，使之只包含源节点S，并初始化集合R，使之包含所有其它节点。初始化 路径列O，使其包含一段从S起始的路径。这些路径的长度值等于相应链路的量度值，并以递增顺序排列列表O. （2）若列表O为空，或 者O中第1个路径长度为无穷大，则将R中所有剩余节点标注为不可达，并终止算法。 （3）首先寻找列表O中的最短路径P，从O中删除 P.设V为P的最终节点。若V已在集合E中，继续执行步骤2.否则，P为通往V的最短路径。将V从R移至E. （4）建立一个与P相 连并从V开始的所有链路构成的侯选路径集合。这些路径的长度是P的长度加上与P相连的长度。将这些新的链路插入有序表O中，并放置在其长度所对应的等级 上。继续执行步骤2. 2.Dijkstra算法举例： 下面我们以路由器A为例，来说明最短路径树的建立过 程： （1）路由器A找到了路由器B、C，将它们列入候选列表{B：1；C：2}. （2）从候选列表中找出最 小代价项B，将B加入最短路径树并从候选列表中删除。接着从B开始寻找，找到了D，将其放入候选列表{C：2；D：2}. （3）从 列表中找出C，再由C又找到了D.但此时D的代价为4，所以不再加入候选列表。最后将D加入到最短路径树。此时候选列表为空，完成了最短路径树的计算。 三、OSPF路由表的计算与实现 有关路由表的计算是OSPF的核心内容，它是动态生成路由器 内核路由表的基础。在路由表条目中，应包括有目标地址、目标地址类型、链路的代价、链路的存活时间、链路的类型以及下一跳等内容。关于整个计算的过程，主 要由以下五个步骤来完成： （1）保存当前路由表，当前存在的路由表为无效的，必须从头开始重新建立路由表； （2）域内路由的计算，通过Dijkstra算法建立最短路径树，从而计算域内路由； （3）域间路由的计算，通过检查 Summary-LSA来计算域间路由，若该路由器连到多个域，则只检查主干域的Summary-LSA； （4）查看 Summary-LSA：在连到一个或多个传输域的域边界路由器中，通过检查该域内的Summary-LSA来检查是否有比第（2）（3）步更好的路径； （5）AS外部路由的计算，通过查看AS-External-LSA来计算目的地在AS外的路由。 通过以上步骤，OSPF生成了 路由表。但这里的路由表还不同于路由器中实现路由转发功能时用到的内核路由表，它只是OSPF本身的内部路由表。因此，完成上述工作后，往往还要通过路由 增强功能与内核路由表交互，从而实现多种路由协议的学习。 OPSF作为一种重要的内部网关协协议的普遍应用，极大地增强了网络的可 扩展性和稳定性，同时也反映出了动态路由协议的强大功能。但是，在有关OSPF协议的研究、实现中尚存在一些问题，如数据库的溢出、度量的刻画、以及 MTU协商等等。同时，在IPv6中，OSPFv3基于链路的处理机制、IP地址的变化、泛洪范围的增加、包格式、LSA的变化以及邻居的识别等技术都将 是我们共同探讨的课题。 (责任编辑：编程世界) |