OSPF协议之"计算路由"

13719654321

　　OSPF协议的路由器，采用的路由计算的算法是Dijkstra算法。
算法描述如下：
第一步：把Root加入最小树，并设Root可直达的顶点为候选人。
第二步：若候选人列表为空，则最小树生成，否则候选人列表中选取花费最小的，加入到最小树中。
第三步：把新加入的顶点所能直达的顶点列为候选人。
第四步：在候选人名单中除去最小树中已经出现的，返回到第二步。

工作过程：
通过LSDB可得到个顶点的连接状态，利用Dijkstra算法有"内"向外，从区域内到区域间，从AS内到AS外，诼步生成最小树，进而生成路由表。
路由计算过程：
首先判断区域是否为NULL，是的话结束。否则计算区域内路由，区域间路由，用转换区域改进路由，计算AS外部路由，取下一区域，返回开始部分（判断该区域是否为NULL.....）。

路由比较法则：
有两条或者两条以上的路由到同一节点，应用以下规则：
1 同一级别的路由比较总是选小花费的路由。
2 不同级别的路由，分为含AS外部路由：
  a 区域内路由/区域间路由，在AS外路由之前考虑，也就是不含外部路由的路由优先。
  b  type1在type2前考虑，小type2比大type2优先
  AS外部路由分两种：
  1类外部路由是AS边节点引入的同等级路由协议的路由其花费视为与AS内部路由同一级别
  2类外部路由是AS 边节点引入的不同等级的路由，花费视为比任何AS内部路由的花费大。
  c 如果新的AS外部路由扔不可从当前的路由表入口的路由区分大小，选择基于intra_AS的到ASBR的路由。
  d 仍然不可分，选少花费的。
  e 视为等价ASE花费路由。
3 不含外部路由的路由：
  优先级别依次是： 区域内路由 > 骨干区域内路由 >区域间路由(指经过了2个区域的路由，但又不
  是虚连接构成的骨干区域内路由)