第6章路由协议与路由算法祥解.ppt

计算机网络原理与技术 谢谢 　 ⑥从L集合中，查找与节点R1最近的节点。由D1可以看出，与R1最近的节点只有节点R4，将最后一个节点R4加入到最短路径树上如图6.7（ f）.至此最短路径树已包含了所有的节点： D1＝（〈0〉，1，3，4,2,2 ）就是以节点R1为根的最短路径树。 五、距离向量路由算法与链路状态路由算法 2、链路状态路由算法LSR 第六讲：路由协议与路由算法 R1 R2 R1 1 R2 R1 R5 1 1 （a） （b） （c） 五、距离向量路由算法与链路状态路由算法 2、链路状态路由算法LSR 第六讲：路由协议与路由算法 R2 R1 R6 R5 1 1 1 R2 R1 R3 R6 R5 2 1 1 1 （d） （e） 五、距离向量路由算法与链路状态路由算法 2、链路状态路由算法LSR 第六讲：路由协议与路由算法 R2 R1 R3 R6 R5 2 2 1 1 R4 1 （f） 五、距离向量路由算法与链路状态路由算法 2、链路状态路由算法LSR 第六讲：路由协议与路由算法 R2 2 R6 R2 2 R5 R2 4 R4 R2 3 R3 R2 1 R2 － 0 R1 下一站 距离 目标路由 链路状态路由算法分析 链路状态包可以周期性地构造，它可以随着网络拓扑的变化而更新。每个路由节点都必须： 周期地学习它的相邻节点和相邻节点的网络地址。 度量他到相邻节点的距离，即与其相连的所有链路的当前状态 构造链路状态包LSP，描述与其相连的所有链路的当前状态 在接收到所有的LSP后，计算到其他节点的最短距离 五、距离向量路由算法与链路状态路由算法 2、链路状态路由算法LSR 第六讲：路由协议与路由算法 负重奋进 笃行求实 开放最短路径优先路由算法的分组类型： （1）问候分组：用来发现和维持邻居的可达性关系。OSPF每隔10S进行一次问候分组的交换，若40S内没应答，则视为邻居路由不可达。 （2）数据库描述分组：向邻居发送自己链路状态数据库中所有链路状态项的摘要信息。 （3）链路状态请求：向邻居请求发送其链路状态项的详细信息。 （4）链路状态更新：采用洪泛法进行整个网络链路状态的更新. （5）链路状态确认：对收到的邻站发来的链路状态信息进行确认。 后边四个分组主要是实现两路状态数据库的同步！ 四、OSPF协议与BGP协议 1、开放最短路径优先路由协议OSPF 第六讲：路由协议与路由算法 OSPF当前采用的路由信息表的建立与更新方法： 第一步：采用数据描述分组与相邻路由器交换当前路由器已有链路状态摘要信息。摘要信息描述了当前哪些相邻路由器的链路状态信息已经写入数据库。 第二步：使用链路状态请求分组，向对方请求发送自己缺少的链路状态项目的详细信息。 第三步：通过反复交换，最终形成全网的同步链路数据库。 第四步：只要有一个路由的链路状态发生变化，就要使用链路状态更新分组，通过可靠洪泛算法进行全网两路状态更新。如下图 四、OSPF协议与BGP协议 1、开放最短路径优先路由协议OSPF 第六讲：路由协议与路由算法 OSPF当前采用的路由信息表的建立与更新方法： 四、OSPF协议与BGP协议 1、开放最短路径优先路由协议OSPF 第六讲：路由协议与路由算法 更新报文 t ACK报文 R R R R t1 t2 t3 t4 基于可靠洪泛法进行更新分组 　 BGP边界网关协议用于自治系统之间交换AS边界路由信息，是Cisco设备的核心，BGP是连接大多数Internet骨干网的路由协议，BGP一般采用改进的距离向量路由算法。对于BGP协议制定来说面临着两个大的问题： （1）因特网规模巨大，是的AS之间路由选择非常困难。核心路由需要维护大量的网络标识，若采用链路状态路由算法，很难构造一个最短路径树；AS内部运行自己的内部路由协议，当要通过多个AS时，想要计算出有效的距离是不可能的，所以AS间的路由选择，只能用是否可达的信息进行判断。 （2）AS之间的路由选择必需考虑相关策略。主要考虑政治、经济问题。 四、OSPF协议与BGP协议 2、边界网关路由协议BGP 第六讲：路由协议与路由算法 　 BGP边界网关协议只能力求寻找一条可达且比较好的路径，而并非要寻找一条最佳路径。所以，BGP采用了一种路径向量路由算法，在BGP网络中，每个自治系统都被分配一个唯一的组号，每个路由器必须配置一个表，其中定义了他的邻居IP地址和自治系统的组号，路由器可以识别具有相同组号的邻居属于同一个自治系统。BGP可以根据连接速度，延时和可用带宽平衡多个路径之间的负载。BGP协议有三个功能： 邻居关系的建立、邻居关系的维持、可达网络数据库的建立与维护 四、OSPF协议与BGP协议 2、边界网关路由协议BGP 第六讲