Internet核心原理与应用技术 第6章 Internet路由算法.ppt

《Internet核心原理与应用技术 第6章 Internet路由算法.ppt》由会员分享，可在线阅读，更多相关《Internet核心原理与应用技术 第6章 Internet路由算法.ppt（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第6 6章章 InternetInternet路由算法路由算法6.26.3 6.4基本概念基本概念6.16.1距离向量路由算法距离向量路由算法6.26.2链路状态路路选择算法链路状态路路选择算法6.36.3其他路由选择算法其他路由选择算法6.46.4 6.1 6.1 基基 本本 概概 念念 6.1.1 6.1.1 网际互连的基本概念网际互连的基本概念图图6.1 Internet6.1 Internet的物理网络互连示意图的物理网络互连示意图 1 1同构网络的网际互连同构网络的网际互连 2 2相似网络的网际互连相似网络的网际互连 3 3异构网络的网际互连异构网络的网际互连图图6.2 6.2 基

2、于转发器的同构网络网际互连基于转发器的同构网络网际互连图图6.3 6.3 基于网桥基于网桥/交换机的相似网络网际互连交换机的相似网络网际互连图图6.4 6.4 基于路由器基于路由器/3/3层交换机的异构网络网际互连层交换机的异构网络网际互连6.1.2 6.1.2 路由选择的基本概念路由选择的基本概念1 1路由选择的通信设备路由选择的通信设备2 2路由选择的原理路由选择的原理路路由由选选择择包包括括两两项项基基本本内内容容：选选择择最最优优路路径径和和转转发发IPIP分分组组。选选择择最最优优路路径径就就是是判判定定到到达达目目标标端端的的最最佳佳路路径径的的下下一一站站，由由路由选择算法来实现

3、。路由选择算法来实现。转转发发IPIP分分组组就就是是按按照照选选择择好好的的最最佳佳路路径径传传送信息分组。送信息分组。3 3路由选择考虑的问题路由选择考虑的问题（1）路由选择由谁完成）路由选择由谁完成（2）路由选择什么时间完成）路由选择什么时间完成（3）“最佳路径最佳路径”的标准是什么的标准是什么4 4路由选择的方式路由选择的方式典型的路由选择方式有两种：静态路典型的路由选择方式有两种：静态路由和动态路由。由和动态路由。（1）路由表中在计算和设置后不）路由表中在计算和设置后不再改变，称为静态路由。再改变，称为静态路由。图图6.5 56.5 5个路由器组成的网络的图示个路由器组成的网络的图示

4、（2 2）当网络变化时路由表的信息）当网络变化时路由表的信息要随时进行更新，称为动态路由。要随时进行更新，称为动态路由。6.2 6.2 距离向量路由算法距离向量路由算法6.2.1 6.2.1 距离向量路由算法描述距离向量路由算法描述距离向量路由算法（距离向量路由算法（Distance Vector Distance Vector RoutingRouting）是最早采用的一种路由选择算法。）是最早采用的一种路由选择算法。变量定义：源节点变量定义：源节点i i的距离向量的距离向量DiDi，后，后继节点向量继节点向量SiSi表示为表示为 ，其中，其中，Dij表示从节点到节点的最小距离；表示从节点到

5、节点的最小距离；Sij表示从节点到节点的最短路径的下表示从节点到节点的最短路径的下一站；一站；n 表示网络中的路由节点数。表示网络中的路由节点数。初始值：初始值：Dii=0，Sii=若若i与与j为相邻节点，则为相邻节点，则Dij的初值为的初值为i与与j之间的距离，而之间的距离，而Sij的初始值为的初始值为j；若；若i与与j不不相邻，则相邻，则Dij的初值为的初值为，而，而Sij的初始值待的初始值待定（空值）。定（空值）。算法：节点算法：节点i收到各相邻节点收到各相邻节点k的距离的距离向量向量Dk和后继节点向量和后继节点向量Sk后后,把把Dk Sk更换更换为和为和对于对于j从从1到到n，选取相邻

6、节点，满足选取相邻节点，满足Div+Dvj=(Dik+Dkj)，则，则 6.2.2 6.2.2 距离向量路由算法举例距离向量路由算法举例图图6.6 66.6 6个路由节点的网络拓扑图个路由节点的网络拓扑图6.3 6.3 链路状态路由选择算法链路状态路由选择算法6.3.1 6.3.1 链路状态路由算法描述链路状态路由算法描述链路状态路由算法的基本思想是：每个链路状态路由算法的基本思想是：每个路由节点维持一个网络拓扑信息数据库，这路由节点维持一个网络拓扑信息数据库，这个数据库也称为链路状态库，它包含各个节个数据库也称为链路状态库，它包含各个节点的链路状态包。典型的链路状态包包括包点的链路状态包。典

7、型的链路状态包包括包的序号、该节点的标识、该节点的相邻节点的序号、该节点的标识、该节点的相邻节点和该节点到相邻节点的距离。和该节点到相邻节点的距离。6.3.2 6.3.2 链路状态路由算法实例链路状态路由算法实例图图6.7 6.7 链路状态路由算法构建的最短路径节点树链路状态路由算法构建的最短路径节点树6.4 6.4 其他路由选择算法其他路由选择算法1 1单路径与多路径路由选择算法单路径与多路径路由选择算法单路径路由选择算法，是通过路由器单路径路由选择算法，是通过路由器中的路由表选择一条最优路径来转发数据中的路由表选择一条最优路径来转发数据包。包。2 2平面结构与分层结构路由选择平面结构与分层结构路由选择算法算法平面结构路由选择算法应用于单层次平面结构路由选择算法应用于单层次的路由系统，单层次的路由系统中所有的的路由系统，单层次的路由系统中所有的路由器都是对等的，没有主次之分。路由器都是对等的，没有主次之分。3 3主机智能与路由器智能路由选主机智能与路由器智能路由选择算法择算法主机智能算法就是指由数据包的发送主机智能算法就是指由数据包的发送方决定整个传输过程中的完整路由，通常方决定整个传输过程中的完整路由，通常也被称为源路由。也被称为源路由。4 4域间与域内路由选择算法域间与域内路由选择算法