1 .链路状态数据库(LSDB ) )。
除洪泛扩频LSA外,除发现邻居外,链路状态协议的第三个任务是建立链路状态数据库。 链接状态数据库将接收到的LSA作为一系列记录保存。 LSA包括年龄、序列号和其他信息,但所有这些信息都用于管理LSA的扩散过程。 对于最短路径的决策过程,告知路由器ID,连接网络和邻居路由器,与网络和邻居相关的成本是非常重要的信息。
LSA中的两种通用信息:
路由器信息——使用三组(路由器ID、邻居ID、成本)通知邻居路由器。 这里的代价是链接邻居的代价。
末梢网络信息——使用三元组(路由器ID、网络ID、代价)通知路由器直接连接的末梢网络。
最短路径优先算法计算路由器的链路信息,建立到达每个路由器的最短路径树,并使用末梢网络信息添加网络。
上图所示的网络包含路由器和路由器之间的链路。 为了简单,没有末梢网络。 请注意,在几个链接的两端,成本是不同的。 因为成本是根据接口的出站方向计算的,一个网络中的所有成本不必完全相同。 例如,虽然从RB到RC链路的成本为1,但是对于同一链路,从RC到RB的成本为5。
拓扑图中所示的网络链路状态数据库大致如下。
2.SPF算法
SPF算法的三个数据库:
1 )树数据库——通过在数据库中添加链接,向最短根树添加分支。 算法完成后,该数据库可以描述最短路径树。
2 )候选数据库——从链接状态数据库中按照预定顺序将链接复制到该数据库中,作为要添加到树形数据库中的候选。 算法完成后,数据库将为空。
3 )链路状态数据库——保存网络中的所有链路。
SPF算法的计算过程:
步骤1 :路由器初始化树数据库,把自己作为树的根。 成本是0。
步骤2 )显示链路状态数据库,将所有描述路由的路由器邻居链路三元组添加到候选数据库中。
步骤3 :计算从根到每个链路的成本,并将候选数据库中成本最小的链路添加到树数据库中。 如果两个或多个链路距离根的最小成本相同,请选择“添加”。
步骤4 )检查被添加到树形数据库中的近邻ID,除了已经被添加到树形数据库中的三元组之外,还将在链接状态数据库中描述路由器近邻的三元组添加到候选对象数据库中。
步骤5 :如果候选人数据库中仍有表条目,请返回步骤3。 如果候选数据库为空,算法将终止。 算法结束后,树数据库中的各个邻居ID表条目表示路由器。 这样就完成了最短根树的构建。
步骤6 :添加末梢网络。 这样就完成了SPF算法。
以拓扑图路由器a为例,计算最短路由树: