计算机网络,路由原理

1、路由原理1第六章 路由原理概述路由原理2Internet是一个巨型复杂系统。过去认为它的拓扑结构是一个随机网络。后来测试结果发现与随机网络预测不符，而是一个无尺度网络。随机网络随机网络节点的连接数是随机分布的无尺度网络无尺度网络(Scale free)少数节点具有很高连接数(集散节点)连接分布遵循“幂次定律” 任何节点与其它k个节点连接概率，与1/k成正比(无尺度特性) 可承受意外故障，无法抗拒协同式攻击 事例 万维网、细胞代谢、语言、人际关系路由原理36.1 概述 在网络上选择一条从源到目的节点的通路 若干中继节点和链路组成的一条路：路径 L2、L3的中继都有选路要求 L2中继选路：依据链路

2、连接 L3中继选路：依据网络拓扑结构RouteRoutingRouted如何选路如何中继路由原理4L2选路 站点在链路上 链路在中继可以产生多条支路 每个站点只能连接到一个链路上 选路的依据是站点在链路上的位置 链路的拓扑是简单的或树状结构 到任一站点只有唯一的一条路 L2的选路方式是简单的 根据链路的方向选路路由原理5L3选路 站点在某个网关处 多个网关构成的网状拓扑结构 站点连接到某个网关上（通过链路连接） 选路的依据是站点所处的网关位置 拓扑结构是复杂的网状拓扑结构 到某个站点有多条路存在 L3的选路是复杂的 按照一定准则，从多条路中选出一条最佳路由路由原理6选路的有关问题选路与路由 网

3、状拓扑结构中的选路问题 以网关为节点、链路为线条的网状拓扑 确定网状结构中所有节点对间的路径 不是确定某个特定的通信路径【选路】 而是确定所有可能的通信路径【路由】 在所有节点对的多条路径中选择合理的路径 路由：全局性的选路方法路由原理7多条路由 节点对（i，j）间存在多条路径 i，j1,6 ij （i，j）的路径与（j，i）的路径不一定相同 （i，j）看成一对序偶 N个节点，就得考虑N（N1）条路由213456(1,6)的可能路径：1-2-4-61-3-5-61-3-4-61-4-61-2-3-4-6需从所有可能的路径中确定： 6530条路径路由原理8选路的有关问题算法与协议 每对节点间可能

4、存在多条路径 各条路径的通信性质 信道速率、时延、费用 路径的优选【“最佳”路由算法】 “最佳”的准则，因应用不同而异（或曰“人为因素”） 全局路径达到最佳准则和算法（局部也许不太合理） 最佳路径随拓扑、通信状况改变而动态变化 算法与协议 所有网关都参与，把握全局性的选路信息 集中或分布(或其它方式)的选路算法【路由算法】 统一选路规则、网关的协作【路由协议】路由原理9最优路由选择 路径的全程传输容量 路径的长度（距离） 路径的费用213456c1c2c3c4c5c6c7c8c9c10节点的流量、线路容量直接影响到路径的容量和时延线路的故障、节点的故障可能影响到路径的可用性费用：c1+c2+c

5、8 或 c1+c4+c10路由原理10选路的有关问题路由体系 多种路由算法和协议客观存在 不同网络的通信需求不同，路由策略和准则不同 大型网络不可能只用一种路由协议 路由体系结构 小网中的路由、网状网的路由、大型网的路由 网络权属机构的管理和路由策略 权属网络间的路由 多层次的路由路由原理11路由体系 多层次的路由 不同的小网可有不同的路由算法和协议 不同的网状网可有不同的路由算法和协议 多种不同权属网络的有不同的路由策略域1域2域3域4小网路由网状网路由大型、不同权属网络间的路由路由原理12本章内容 本章只讨论L3选路问题 选路基本方法 路由协议（算法） 路由体系结构路由原理136.2 选路

6、基本方法路由问题： 源到目的节点之间节点和线路组成的通路 任意一对节点间都可能存在多条路经 从所有路径中计算出每对节点间的最佳路由 什么是最佳路由？ 如何计算？1到6的可能路径：1-2-4-61-3-5-61-3-4-61-4-61-2-3-4-612354613232211331142856385路由原理146.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

7、Lx: C(Lx) = min C(L1), C(Lk)经典最短距离算法：Dijkstra（1959）路由原理15“距离”的解释 C(a,b)的意义 若C(a,b)=1，则最佳路径为经过的节点数最少 若C(a,b)=dt (节点a的中继时延传输时延),则最佳路径为最小传输时延的路径 若C(a,b)为节点a,b间链路上传输的费用，则最佳路径为最小费用的路径 若C(a,b)=1/链路容量, 则最佳路径是一条最大传输容量的路径(不严格) 若C(a,b)=链路使用率，则最佳路径是一条最空闲的路径(不严格)路由原理16路由算法 C(a,b)的不同含义，意味着不同的“最佳”选路 C(a,b)可以是距离、时

8、延、容量、费用等的函数的加权组合 实际中，各种因素的量纲不同，没有一种方法能兼顾所有的因素。路由原理17路由算法 跳数 费用 时延 吞吐量 最短路径路由算法：路径上的节点数最少 最小费用路由算法 最大吞吐量路由算法 最小时延路由算法12354613232211331142856385路由原理18网络流量过于集中，超过信道传输能力网络流量过于集中，超过节点处理能力6.2.2 路由相关问题 网络拥塞 路由过分集中到网络中的某些局部区域 后果：拥塞逐渐蔓延到全网，网络吞吐能力下降流量吞吐量理想路由原理19拓扑结构变化引起网络中多条路径发生改变，需要及时根据变化，进行路由调整X信道故障节点故障新节点加

9、入路由原理20 路由环路 节点间路由配合不当，可能出现路由环路 PDU进入环路后，再也出不来了路由原理21路由不一致性 时延会造成路由的不一致问题 要求所有节点同时掌握各种情况是不现实的故障正常路由链路故障后的一段时间内路由原理22路由协议 需要节点间交换与路由相关的信息，以便形成全网一致的路由【路由协议】，解决： 路由的不一致性 网络拥塞 路由环路 拓扑变化 路由原理236.2.3 路由的基本要求 路由不仅仅是计算最佳路由的算法 实际上，网络拥塞、拓扑结构变化、路由环路问题远比最佳路由的影响大 路由协议的要求 正确性：一致且无环路的路由 公平性：对所有方向的通信等同对待 简洁性：路由算法简单

10、 最优性：一定策略下的最优路由 稳健性：对偶发事件做出正确反应 高效性：路由协议引入的附加通信少 稳定性：路由算法是稳定性、收敛的路由原理246.3 基本路由算法与协议 基本方法 事先计算所有最优路由，形成路由表(转发表） 各节点根据路由表进行PDU的转发213456目的节点 出口 下一节点路由原理25路由方式路由协议静态路由动态路由局部最优路由 全局最优路由路由原理26 静态路由与动态路由 依据网络拓扑结构建立路由表 路由表的内容保持不变（网络变化小的网络） 路由表的内容随网络的变化而更新 静态路由简单可靠、但灵活性较差 动态路由随网络变化而自动变化，可靠性较差 动态路由需在节点间交换路由信

11、息-路由协议 全局最优路由与局部最优路由 全局最优路由-小型网络 局部最优路由-大型网络路由原理276.3.1 静态路由 静态路由在网络发生变化时，由人工修改路由基本方法： 1）计算所有节点间的最优路径，形成中心路由选择表12453613232211331142856385123 4561-15 14522-2 245343-5354445 -455445 5-56445 56-源节点目的节点下一节点路由原理282）为每个节点形成路由转发表节点1目的节点 下一节点2234445464节点2目的节点下一节点1133445464节点3目的节点 下一节点1522455565节点4目的节点 下一节点1

12、122355565节点5目的节点 下一节点1424334466节点6目的节点 下一节点1525354555路由原理296.3.2 动态路由 网络的变化较频繁 网络的规模较大 网络的拓扑复杂根据网络运行的情况，动态更新网络的路由表根据网络运行的情况，动态更新网络的路由表路由原理306.3.2.1 洪泛路由工作方式：某个接口进的PDU，转发到其余所有接口；目的节点会收到多个重复报文。特点： 不需要网络拓扑信息-网络结构无关性 总能够送到目的地-高度稳健性 所有节点都能收到-可用于广播 无休止地转发PDU-PDU生命期（Time To Live, TTL) 网络上PDU几何级数膨胀-网络负担重，小网

13、适用 树形，星形网络路由原理316.3.2.2 随机路由工作方式： 从多个（能到达目的地的）出口中随机选中一个来转发PDU。 不需要网络拓扑信息-网络结构无关性 每次路径是随机变化的路由原理326.3.2.3 反向学习路由法CA收到从A送来的报文路由表中记录下从该接口可以到达A 在PDU中增加距离记录，每经过一个节点，距离加1，供反向学习选择最佳路由。特点： 自适应路由算法，能逐渐形成最佳路由 动态适应新节点的加入 对节点、链路故障反应迟钝 对拓扑稳定、小型网络适用目的节点接口距离A An ndndn路由原理336.3.2.4 中心路由（集中路由）213456中心路由计算机工作方式： 各个节点

14、定期把自己的信道、相邻节点情况报告中心路由计算机，由计算机计算出各节点到其余节点的最佳路由，然后把路由表分发到各个节点上。特点：最佳路由-理想路由信息上报、更新同步困难（特别是大网）路由原理346.3.2.5 分布式路由 主动与其他节点交换路由信息-路由协议路由协议 节点独立计算最优路由 放弃全局最优、寻求局部最优化 交换的信息越详细、交换的频率越快，路由优化越好，对网络带来的额外开销也越大。 寻求在额外开销和反应速度间的平衡路由原理35分布式路由的不利之处不利之处： 利用部分路由信息，无法得到全局最优路由 可能出现相互矛盾的路由 反应快会造成路由震荡，反应慢则好处不大有利方面： 局部范围，网

15、络额外开销少 可在局部获得最佳路由路由原理36（距离、信道费用、信道负载、信道延时）常见的分布式路由： 基于网络距离的分布式路由算法-矢量距离法 基于信道状态的分布式路由算法-线路状态法路由原理37矢量距离法(VD算法)以中继节点个数为距离度量21345611111111工作方式： 每个节点自动找出相邻节点，形成初始路由表，距离为1 每个节点定期和相邻节点交换路由信息 根据收到的路由信息，更新到其他节点的路径（最短距离） 通过不断扩散，逐渐形成到所有节点的路由交换路由信息1目的节点下一节点距离3路由原理38目的节点下一节点距离221331443目的节点距离113141节点1路由表更新初始值收到

16、节点3路由信息目的节点下一节点距离221331422更新后目的节点距离11214151收到节点2路由信息目的节点下一节点距离221331422532距离更新=到中继节点的距离+中继节点到目的节点的距离更新后路由原理39特点：特点： 只与邻节点交换路由信息 各节点独立计算最优路径 能适应网络拓扑的变化 稳定后，形成最短路径 路由PDU长度与节点数成正比缺点：缺点： 网络变化扩散到全网速度慢（收敛慢）-限制在小网使用 存在路由环-PDU用最大跳数限制转发次数路由原理40线路状态法（SPF算法）Shortest Path First以链路的某些特征作为距离度量 信道速率、信道负载、发送队列长度、通信

17、费用等，都可作为度量距离的因素 每个节点定期向所有邻居发送自己链路的距离值 每个节点需掌握全网的拓扑结构和所有链路的距离值，用Dijkstra算法计算出到所有目的地的最佳路由（仅供自己使用） 路由PDU长度与节点的链路数成正比，与网络的节点数无关路由原理41SPF的特点 算法收敛较快 距离度量方式灵活，适应多种路由策略，如： 链路容量、当前链路流量 通信费用、链路容量 接近全局最佳路由 由全网拓扑结构得到的路由 路由环的可能性较小路由原理426.4 路由体系结构 路由协议总是在一定范围来考虑的 各个小网不一定使用相同的路由协议 网状网上用另一种协议(如SPF)来通信 不同权属组织的网络间的路由

18、则还需另外的路由协议域1域2域3域4小网路由路由原理43 路由存在一种层次结构的概念 IGP： Interior Gateway Protocol EGP：Exterior Gateway Protocol小网路由小网路由小网路由网间路由小网路由小网路由小网路由网间路由外部路由IGPEGP路由原理446.4.1 IGP IGP：内部网关协议 在内部网络上形成最佳路由 所有节点为了同一个目的：最佳路由 节点间无保留地交换路由信息 6.3节的路由都是IGP IGP是内部网关协议的统称 SPF既可用于小网路由，也可用于内网的网间路由路由原理456.4.2 EGP EGP：外部网关协议 为外部网络间的通信提供路由 没有义务为外网提供内部的路由信息 没有义务提供如何得到最佳路由的信息 体现和满足网络所有者之间的约定 向外部网络提供的路由信息只包括 可达性，可以到达哪些目的地 Inte