ospf 中的SPF（small path frist）算法

SPF主要的依据为： 1、根据router-LSA和network-LSA中的拓扑信息，构建SPF树干 2、基于SPF树干和router-LSA、network-LSA中的路由信息，计算最优路由 注意：ospf路由器将分别以自身为根节点计算最短生成树 第一步：以R1为根节点 [r1]display ospf lsdb router self-originate    OSPF Process 1 with Router ID 1.1.1.1           Area: 0.0.0.0   Link State Database    Type      : Router  Ls id     : 1.1.1.1  Adv rtr   : 1.1.1.1    Ls age    : 976    Len       : 60    Options   :  E    seq#      : 8000000f    chksum    : 0xb5eb  Link count: 3   * Link ID: 2.2.2.2           Data   : 10.1.1.1           Link Type: P-2-P             Metric : 1562   * Link ID: 10.1.1.0           Data   : 255.255.255.0       Link Type: StubNet           Metric : 1562       Priority : Low   * Link ID: 10.1.2.1           Data   : 10.1.2.1           Link Type: TransNet           Metric : 1 通过以上信息可以看出：R1的router ID为1.1.1.1，与其直接相连的包括P-2-P  、MA 两种网络类型 进入后选列表的包括 DR:10.1.2.1 开销：1，父节点为1.1.1.1 2.2.2.2 开销：1562 父节点为1.1.1.1 第二步： [r1]display ospf lsdb network 10.1.2.1  OSPF Process 1 with Router ID 1.1.1.1           Area: 0.0.0.0   Link State Database    Type      : Network  Ls id     : 10.1.2.1  Adv rtr   : 1.1.1.1    Ls age    : 1635    Len       : 36    Options   :  E    seq#      : 8000000a    chksum    : 0xe032  Net mask  : 255.255.255.0  Priority  : Low     Attached Router    1.1.1.1     Attached Router    4.4.4.4     Attached Router    5.5.5.5 与本DR直接相连的路由器为 1.1.1.1（前面已经选择，不用考虑）、4.4.4.4、5.5.5.5 计入候选列表的包括： 2.2.2.2 ，开销为1562，父节点为1.1.1.1 4.4.4.4，开销为1+0，父节点为10.1.2.1 5.5.5.5 ，开销为1+0，父节点为10.1.2.1 ​ 第三步： [r1]display ospf lsdb router 5.5.5.5  OSPF Process 1 with Router ID 1.1.1.1           Area: 0.0.0.0   Link State Database    Type      : Router  Ls id     : 5.5.5.5  Adv rtr   : 5.5.5.5    Ls age    : 286    Len       : 36    Options   :  E    seq#      : 8000000c    chksum    : 0x639e  Link count: 1   * Link ID: 10.1.2.1           Data   : 10.1.2.3           Link Type: TransNet           Metric : 1 计入候选网络： 10.1.2.1（已经选择不予考虑） 开销：1，父节点为1.1.1.1 2.2.2.2 ，开销为1562，父节点为1.1.1.1 4.4.4.4，开销为1+0，父节点为10.1.2.1 [r1]display ospf lsdb router 4.4.4.4  OSPF Process 1 with Router ID 1.1.1.1           Area: 0.0.0.0   Link State Database    Type      : Router  Ls id     : 4.4.4.4  Adv rtr   : 4.4.4.4    Ls age    : 480    Len       : 48    Options   :  E    seq#      : 8000000f    chksum    : 0xc80c  Link count: 2   * Link ID: 10.1.5.1           Data   : 10.1.5.2           Link Type: TransNet           Metric : 1   * Link ID: 10.1.2.1           Data   : 10.1.2.2           Link Type: TransNet           Metric : 1 计入候选列表 2.2.2.2 ，开销为1562，父节点为1.1.1.1 10.1.5.2 开销为1+0+1，父节点为4.4.4.4 ​ 第四步： [r1]display ospf lsdb network 10.1.5.1  OSPF Process 1 with Router ID 1.1.1.1           Area: 0.0.0.0   Link State Database    Type      : Network  Ls id     : 10.1.5.1  Adv rtr   : 3.3.3.3    Ls age    : 917    Len       : 32    Options   :  E    seq#      : 80000009    chksum    : 0x76a2  Net mask  : 255.255.255.0  Priority  : Low     Attached Router    3.3.3.3     Attached Router    4.4.4.4 候选列表： 2.2.2.2 ，开销为1562，父节点为1.1.1.1 3.3.3.3，开销为1562+1+0+1，父节点为10.1.5.1 最终SPF树为： ​ 注意：将各个节点全部挂在树上