OSPF拓扑描述及路由计算（4）
内容概要：
1、1类LSA内容分析
2、1类LSA中的4种类型link
3、2类LSA内容分析
4、DR及虚节点作用
5、SPF路由计算
6、iSPF和PRC
在OSPF的逻辑拓扑中，代表路由器的节点叫做实节点，代表transnet网络的节点叫做虚节点，代表stub网络的叫做叶子节点；
一张描述全网络的图上仅包含点和边，表达拓扑的点有代表路由器的实节点、代表transnet网络的虚节点和代表stub网络的叶子节点；
叶子节点与实节点、虚节点的差别在于叶子节点只能在拓扑计算结束后，挂在树的末端；
transnet网络要表达4个节点间全互连的关系，在数学模型的描述中，把中间的Network表述成一个节点，并连接每个节点；
stub网络本身也有成本，其成本就是所在链路的成本；
stub网络包含的类型有loopback接口的网络、点到点链路每个节点连接的网络、无邻居的以太网接口网络和secondary地址网络；
网络分为transnet网络和stub网络，二者的区别是transnet网络上至少有两个节点，流量可以穿越transnet网络；
而stub网络仅代表连在一个节点上的网络，流量只能进或出该网络；
一、1类LSA内容分析
每台路由器会为自己的每个区域产生一份Router LSA，用来描述实节点周边的连接关系和网络；
每份Router LSA包含该路由器在相应区域的所有链路信息；
LS age、Options、LS Type、Link State ID、Advertising Router、SequenceNumber、Checksum前面都有介绍过；
（1）Flags字段：
V比特置1，代表vlink端点；
B比特置1，代表ABR；
E比特置1，代表ASBR；
（2）Number of Links：
Link的数量，代表OSPF画出的有向图上Link的数量，不是物理路由器接口的数量；
二、Link类型及描述
ospf定义了4种类型的Link：p2p、transnet、stub和vlink；
路由器接口的ospf网络类型不同，产生的Link也不同；
路由器把所有接口的Link放到Router LSA中，在区域内泛洪；
（1）p2p类型Link
描述点到点类型链路，Link ID为邻居路由器Router ID，Link Data为自身接口地址；
（2）transnet类型Link 与2类LSA共同描述MA网络上的拓扑关系；
描述实节点到虚节点的连接关系，Link ID为DR接口地址，Link Data为自身接口地址；
多路访问网络上如果有多个ospf节点，会形成全互联的邻居关系；
R1、R2、R3和R4接在同一个以太网络上，ospf将其表达成逻辑拓扑时，N1是虚出来的节点，代表R1、R2、R3和R4之间的网络，TransNet类型Link用来描述MA网络上实节点到虚节点的连接关系；
（3）stub类型Link 可以理解为挂在实节点上的叶子节点；
描述一个网络，Link ID为网络号，Link Data为网络掩码；
不表示任何连接关系，是实节点上的一个网络；
（4）vlink类型Link
描述虚拟的p2p类型链路，Link ID为vlink对端ABR的Router ID，Link Data为自身vlink接口地址；
三、2类LSA内容分析 和Router LSA中的transnet类型Link一起用来描述多点网络上的拓扑关系；
Network LSA，仅出现在网络类型是Broadcast或NBMA的网络上，用来描述虚节点周边的连接关系和网络；
Broadcast和NBMA网络上会选举DR，DR有两个作用，一是用于数据库同步，二是负责产生2类LSA；
LS Age、Options、LS Type、Link State ID、Advertising Router、Sequence Number、Checksum前面以及介绍过；
（1）Netmask字段
通过Netmask字段和LinkStateID字段，可以计算出2类LSA的网络号123.1.1.0/24；
（2）Attached Router字段
描述了该MA网络上所有邻居路由器的RouterID；
1类LSA和2类LSA比较：
1类LSA由实节点产生，描述实节点周边的连接关系和网络；
2类LSA由虚节点产生，描述虚节点周边的连接关系和网络；
四、DR和虚节点作用
五、SPF路由计算
OSPF和ISIS协议在数据库中存储的是自己特定格式的链路信息，这些信息不能直接反映出拓扑的情况以及路由与拓扑的关系，SPF必须通过全部的计算过程来确定最短路径树，并计算出路由。
SPF算法将整个网络信息分为两个部分：
（1）网络的节点（路由器和共享网段）和边（路由器和共享网段之间的链路）组成的网络拓扑；
（2）挂在节点上的叶子（网段路由）；
在SPF计算中，网络是由节点以及边构成的，最终形成一棵以计算路由器为根的最短路径树，而路由则是附着在树的节点上的叶子（节点）。
SPF计算有三步：
（1）画图；
ospf有向拓扑图包含所有的点和边；
通过1类LSA中的p2p、transnet和vlink类型的Link及2类LSA来描述拓扑；
（2）执行SPF计算；
路由器以自己为树根，计算出从树根到树上每个节点的最短路径；
（3）添加叶子节点并计算路由
在树的节点上添加网络信息，并计算由树根到每个网络的成本及下一跳，把计算结果加入到路由表；
叶子节点可以是1类LSA中的Stub类型Link、2类LSA、3类LSA、5/7类LSA中的网络；
1类LSA中的stub网络挂在实节点上；
2类LSA中的网络挂在虚节点上；
3类LSA的网络挂在ABR节点上；
5类LSA的网络依据ASBR是否在当前区域可以挂在ASBR或ABR上；
7类LSA的网络挂在ASBR节点上；
SPF已计算出树根到任何节点的最小距离，再把代表网络的叶子节点挂在SPF树的相应节点上，树根到网络路由成本=树根到相应节点的成本+相应节点到叶子节点的成本；
六、iSPF和PRC
SPF并不保存计算结果，当有信息发送变化时，SPF只能再次重新计算一遍；
OSPF是链路状态路由协议，如果网络规模较大，路由数量众多，链路的抖动或路由的变化对网络的影响都很大，所以要提高网络收敛速度，并降低网络负荷；
（1）iSPF Incremental SPF 增量计算 只计算变化的部分，而不是全部计算
仅对最短路径树上拓扑变化的部分所引入的局部节点的计算，就是增量计算iSPF；
iSPF是拓扑计算的一种，只处理网络拓扑信息，负责计算出最短路径树；
iSPF通过重新组织链路状态信息，形成了一个直接反映网络拓扑的图，而计算出的最短路径树就保存在这个图中；
当网络链路状态发送变化时，iSPF会判断出哪部分网络拓扑受到了影响，从而只计算那些受影响的部分，而不是全部网络拓扑；
（2）PRC Partial Route Calculate
在iSPF计算出的最短路径基础上，计算叶子节点代表的路由，就是部分路由计算PRC；
当有路由信息改变，PRC直接判断在哪个节点的哪个叶子出现变化，之后直接进行路由的计算与更新；
在路由计算方面，iSPF优化了SPF计算过程，可降低计算负荷和收敛时间；
华为采用初次计算过程执行涉及全部节点的Full SPF；
而此后不论发生什么变化，只把故障点及其周边的连接关系重画，执行iSPF计算，只计算变化的部分，而不是全部计算；
iSPF计算完毕后，为变化节点添加叶子节点，执行PRC计算，最后把路由加入到路由表中；
