网络体系6路由原理.ppt

路由原理 第六章 路由原理 6.1 概述 在网络上选择一条从源到目的节点的通路 若干中继节点和链路组成的一条路：路径 L2、L3的中继都有选路要求 L2中继选路：依据链路连接 L3中继选路：依据网络拓扑结构 L2选路 站点在链路上 链路在中继可以产生多条支路 每个站点只能连接到一个链路上 选路的依据是站点在链路上的位置 链路的拓扑是简单的或树状结构 到任一站点只有唯一的一条路 L2的选路方式是简单的 根据链路的方向选路 L3选路 站点在某个网关处 多个网关构成的网状拓扑结构 站点连接到某个网关上（通过链路连接） 选路的依据是站点所处的网关位置 拓扑结构是复杂的网状拓扑结构 到某个站点有多条路存在 L3的选路是复杂的 按照一定准则，从多条路中选出一条最佳路由 选路的有关问题－选路与路由 网状拓扑结构中的选路问题 以网关为节点、链路为线条的网状拓扑 确定网状结构中所有节点对间的路径 不是确定某个特定的通信路径【选路】 而是确定所有可能的通信路径【路由】 在所有节点对的多条路径中选择合理的路径 路由：全局性的选路方法 多条路由 节点对（i，j）间存在多条路径 i，j＝1,…,6 i≠j （i，j）的路径与（j，i）的路径不一定相同 （i，j）看成一对序偶 N个节点，就得考虑N×（N－1）条路由 选路的有关问题－算法与协议 每对节点间可能存在多条路径 各条路径的通信性质 信道速率、时延、费用 路径的优选【“最佳”路由算法】 “最佳”的准则，因应用不同而异（或曰“人为因素”） 全局路径达到最佳准则和算法（局部也许不太合理） 最佳路径随拓扑、通信状况改变而动态变化 算法与协议 所有网关都参与，把握全局性的选路信息 集中或分布(或其它方式)的选路算法【路由算法】 统一选路规则、网关的协作【路由协议】 最优路由选择 路径的全程传输容量 路径的长度（距离） 路径的费用 选路的有关问题－路由体系 多种路由算法和协议客观存在 不同网络的通信需求不同，路由策略和准则不同 大型网络不可能只用一种路由协议 路由体系结构 小网中的路由、网状网的路由、大型网的路由 网络权属机构的管理和路由策略 权属网络间的路由 多层次的路由 路由体系 多层次的路由 不同的小网可有不同的路由算法和协议 不同的网状网可有不同的路由算法和协议 多种不同权属网络的有不同的路由策略 本章内容 本章只讨论L3选路问题 选路基本方法 路由协议（算法） 路由体系结构 6.2 选路基本方法 路由问题： 源到目的节点之间节点和线路组成的通路 任意一对节点间都可能存在多条路经 从所有路径中计算出每对节点间的最佳路由 什么是最佳路由？ 如何计算？ 6.2.1 最佳路由 记：Lx为一条经过节点ax,0,ax,1,…ax,n的路径， Cx(a,b)为节点对(a,b)的“距离” C(Lx)为路径Lx的总距离，且： C(Lx) = ∑Cx (ax,i,ax,i+1) 假定节点a，b之间存在k条路径{L1,… Lk}, 则最佳路径为其中的一条，满足: Lm＝ Lx: C(Lx) = min {C(L1),…, C(Lk)} 经典最短距离算法：Dijkstra（1959） “距离”的解释 C(a,b)的意义 若C(a,b)=1，则最佳路径为经过的节点数最少 若C(a,b)=dt (节点a的中继时延＋传输时延),则最佳路径为最小传输时延的路径 若C(a,b)为节点a,b间链路上传输的费用，则最佳路径为最小费用的路径 若C(a,b)=1/链路容量, 则最佳路径是一条最大传输容量的路径(不严格) 若C(a,b)=链路使用率，则最佳路径是一条最空闲的路径(不严格) 路由算法 C(a,b)的不同含义，意味着不同的“最佳”选路 C(a,b)可以是距离、时延、容量、费用等的函数的加权组合 实际中，各种因素的量纲不同，没有一种方法能兼顾所有的因素。 路由算法 跳数 费用 时延 吞吐量 最短路径路由算法：路径上的节点数最少 最小费用路由算法 最大吞吐量路由算法 最小时延路由算法 6.2.2 路由相关问题 网络拥塞 路由过分集中到网络中的某些局部区域 后果：拥塞逐渐蔓延到全网，网络吞吐能力下降 拓扑结构变化 引起网络中多条路径发生改变，需要及时根据变化，进行路由调整 路由环路 节点间路由配合不当，可能出现路由环路 PDU进入环路后，再也出不来了 路由不一致性 时延会造成路由的不一致问题 要求所有节点同时掌握各种情况是不现实的 路由协议 需要节点间交换与路由相关的信息，以便形成全网一致的路由【路由协议】，解决： 路由的不一致性 网络拥塞 路由环路 拓扑变化 …… 6.2.3 路由的基本要求 路由不仅仅是计算最佳路由的算法 实际上，网络拥塞、拓扑结构变化