ospf 中的SPF（small path frist）算法（ospf工作原理）

ospf 中的SPF（small path frist）算法（ospf工作原理）

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树为：

注意：将各个节点全部挂在树上

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。