OSPF Calculation

链路状态陆游协议使用Dijkstra算法来查找到达目标网络中的最佳路径.所有的路由器拥有相同的LSDB后,把自己放进SPF tree中的root里,然后根据每条链路的耗费(cost),选出耗费最低的做为最佳路径,最后把最佳路径放进forwarding database(路由表)里

下图就是一个SPF计算的例子:

1.LSA遵循split horizon原则,H对E宣告它的存在,E把H的宣告和它自己的宣告再传给C和G;C和G再和之前类似,继续传播开来……
2.X有4个邻居:A,B,C和D,假设这里都是以太网,每条网链路的耗费为10,经过计算,路由器可以算出最佳路径.上图的右半部分实线所标即为最佳路径

LS Data Structures: LSA Options

关于LSA的操作流程图如下:

如图可以看出当路由器收到一个LSA以后,先会查看它自己的LSDB看有没有相应的条目,如果没有就加进自己的LSDB中去,并反馈LSA确认包(LSAck),接着再继续洪泛LSA,最后运行SPF算法算出新的路由表，如果当它收到LSA的时候,自己的LSDB有该条目而且版本号一样,就忽略这个LSA;如果有相应条目,但是收到的LSA的版本号更新,就加进自己的LSDB中,发回LSAck,洪泛LSA,最后用SPF计算最佳路径;如果版本号没有自己LSDB中那条新,就反馈LSU信息给发送源。