《计算机通信网-》-网络层Part2省公开课金奖全国赛课一等奖微课获奖课件

5.3.4几个动态路由算法动态路由算法依据网络动态改变计算路由，形成路由表路由表自动形成并依据拓扑改变自动更新适应于网拓扑改变网络、大网如广域网、互联网包括问题节点之间交换路由信息快速适应拓扑改变感知拓扑改变快速传递改变信息快速形成新稳定路由（无环路、不震荡，快速收敛）

★1/405.3.4几个动态路由算法中心路由算法逆向学习法分布式路由算法（重点）距离矢量法链路状态法

2/40中心路由算法（集中路由）原理各个节点定时将本节点信道及相邻节点信息汇报给中心路由计算机由中心路由计算机计算出各节点到其它节点最正确路由，然后分配到各个节点特点理论上讲能够得到全网最优路由（因算法考虑了流量、节点等全网信息）但实现困难，极难在大网中使用，适应于小网，原因有三：信息上传困难（各节点定时上传信息会造成中心路由计算机附近节点及线路拥塞）同时困难（节点很多，中心反馈新路由时，各节点接收时间不一样，可能会造成同一网里有节点使用新路由，有使用老路由）路由更新过时（可能会出现路由更新抵达时，节点情况已变）

21345中心路由计算机★3/40逆向（反向）学习法原理依据接收分组中源地址和接收端口号，形成转发表，方便下次作为目标节点时转发路径特点能动态适应新节点加入对线路故障、节点损坏反应迟钝适应拓扑结构相对稳定、小网目标节点端口距离………………AnDn

CA收到从A送来分组路由表中统计从该接口能够抵达A★4/40分布式动态路由算法基本原理节点之间需相互交换路由信息节点单独计算路由基本特点局部最优，全局不一定最优相互交换信息越详细、越频繁，路由优化越好，但造成额外开销也越大。需要在额外开销和路由更新频率之间进行折中优点动态反应网络改变，路由表自动形成与更新（不需人工干预）局部最优，路由开销少缺点局部最优路由，不是全局最优路由可能出现不一致（矛盾）路由可能出现路由震荡（路由表改变太快）可能出现路由发散（不能收敛）

★5/40分布式路由算法关键点

交换路由信息：分布式计算：节点依据交换路由信息，采取最优路由计算方法计算最正确路由哪些信息？与谁交换？边交换信息边计算可达、距离、费用、负载、延时……与邻居、与全部节点何时交换？定时、拓扑改变时★6/40两种经典分布式路由算法基于网络距离分布式路由算法---矢量距离法基于信道状态分布式路由算法---链路状态法

7/40矢量距离法（V-D：VectorDistance）依据协议设计者命名，也称为Bellman-Ford路由算法Ford-Fulkerson路由算法基本思想每个节点都保持一张到其它节点路由表（目标节点，下一节点，距离）“距离”度量标准能够是跳数或时延等邻居之间交换路由信息（目标节点，距离）依据收到相邻节点信息，判断并决定是否更新路由算法包括内容初始路由表怎样建立？邻居交换哪些信息?怎样依据邻居信息计算并更新自己路由表？

★8/40矢量距离法算法几个步骤初始化建立初始路由表扩散向邻居扩散自己路由表信息计算依据收到相邻节点信息，计算最短路径，更新路由表再扩散、再计算这么就逐步形成了全网拓扑结构使每个节点都计算出了到其它节点路径信息值得注意是：何时向邻居扩散路由信息？定时拓扑发生改变时

★9/40距离矢量算法1）初始路由表建立（目标节点，下一节点，距离）=（V0，G0，D0）2）路由表向邻居扩散

21345611211111146532133311224444655注意：度量值能够是节点跳数、时延等度量参数★10/40距离矢量算法各节点初始路由表：直接相连节点路由信息

213456111111112目标节点下一节点距离221331目标节点下一节点距离111331441目标节点下一节点距离442551目标节点下一节点距离331441661目标节点下一节点距离111221441551目标节点下一节点距离221331551662★11/40距离矢量算法3）节点计算并更新本节点路由表相邻节点定时交换信息（目标节点，距离）=（V，D）当某节点A收到相邻节点j信息（Vx，DjX）时

（Vx表示目标地为X节点，Djx为j到X节点距离）

A节点更新情况以下：如A路由表中无此项，则添加表项（Vx，j，D0+DXj）

（D0为A与邻居j距离）如A路由表中有Vx项，（Vx，k，DAx）若k≠jDAx>D0+Djx，则表项更新为（Vx，j，D0+DjX

）（新、短路径）DAx≦D0+Djx，则此表项保持不变若k=j不论DAx大小怎样，都应更新为（Vx，j，D0+DjX）（原路径可能改变，需更新）

★12/40距离矢量算法

目标节点下一节点距离221331信息公布者2目标节点距离113141节点1路由表初始值收到节点3路由信息目标节点下一节点距离221331更新后公布者3目标节点距离11214151收到节点2路由信息目标节点下一节点距离221331422距离更新=到邻居节点距离+邻居节点到目标节点距离更新后213456112111111422532关13/40距离矢量算法

213456112111111目标节点下一节点距离221331422532节点1当前路由表节点1向节点2公布路由信息信息公布者1目标节点距离21314252节点1向节点3公布路由信息信息公布者1目标节点距离21314252关14/40距离矢量算法

213456112111111目标节点下一节点距离221331422532节点1路由表更新距离更新=到邻居节点距离+邻居节点到目标节点距离收到节点2路由信息公布者2目标节点距离1131415263目标节点下一节点距离221331422532更新后624公布者3目标节点距离1121415162目标节点下一节点距离221331422532更新后62433关15/40距离矢量算法

4）各节点将更新后路由表分别向自己邻居扩散，然后计算并再次更新路由表当每个节点路由表包含了全部其它节点路由时，就形成了一个稳定路由，只要拓扑不改变，路由表就保持不变，不然会重新计算。16/40距离矢量算法相关问题水平分割节点没有必要将从某节点收到信息再传回给该节点无穷计数距离矢量算法会出现路由环路设计最大路径长度（跳数），以减轻环路出现时带来损害用毒性反转方法，破坏路由环路

17/40水平分割

213456111111111目标节点下一节点距离221331422532节点1当前路由表节点1向节点2公布路由信息信息公布者1目标节点距离21314252节点1向节点3公布路由信息信息公布者1目标节点距离21314252节点没有必要将从某节点收到信息再传回给该节点18/40无穷计数在某种情况下，距离矢量算法可能出现路由环路，其现象是路由表项随路由信息更新，不停增加。

ACBD正常情况：A认为到D经过BC认为到D经过BB认为到D经过D路由环路：A认为到D经过BC认为到D经过AB认为到D经过C19/40

ACBD平时：A收到C通知：D有两跳A收到B通知：D有一跳选BC收到A通知：D有两跳C收到B通知：D有一跳选B当B到D链路断掉后，一个可能情形：B告诉A、C：D不可达A重新选路，恰好收到C通知D有两跳（C还没收到B更新信息）A选择到D经过C，距离为三跳A通知B：D有三跳B选择到D经过A，距离为四跳C收到B先前D不可达更新，重新选路B通知C：D有四跳C选择到D经过B，距离为五跳出现路由环路，并计数到无穷大20/40毒性反转－－处理路由环路

213456112111111目标节点下一节点距离221331422532633节点1当前路由表节点1向节点2公布路由信息信息公布者1目标节点距离31425263节点1向节点3公布路由信息信息公布者1目标节点距离21425263节点将从某节点收到信息再传回给该节点时，告诉对方不能从我这里过无穷大无穷大无穷大21/40DV协议其它改进触发更新收到路由信息有没有穷大路由项，直接更新对应路由表项更新抑制无穷大距离路由项保留一段时间不更新(直到该信息传遍整个网络)22/40距离矢量算法小节特点：只与邻节点交换路由信息各节点独立计算最优路径（但依赖邻居计算结果）能适应网络拓扑改变稳定后，形成最短路径算法简单缺点：网络改变扩散到全网速度慢扩散速度：全部节点都发觉改变速度路由收敛慢收敛速度：大家分别计算，结果到达统一速度存在路由环－－在网络改变未扩散完全时。

小网★23/40链路状态路由（L-S：link-state）定理若节点掌握了全网全部节点链路情况，节点就掌握了网络拓扑结构节点链路情况：有几条链路，连接对端节点例：节点R0得到了节点Rk链路情况，R0就可画出它拓扑对端节点链路距离RxdxRydyRzdzRk链路情况RkRxRyRzdxdydz若知道Ry链路情况，就知道它是否与Rx、Rz相连24/40链路状态路由关键问题需要在以下情况下与全部节点交互不知道存在哪些节点没有建立路由假如处理了上述问题，每个节点都能够构建网络拓扑视图用拓扑视图计算到各节点最短路由计算结果形成自己转发表因为掌握了网络拓扑结构，节点能够计算出最短路由，当然也能够计算出次短路由，以及更多条路由路由策略：最短路由优先SPF，ShortestPathFirst25/40SPF路由功效框图依据上述描述，能够画出SPF功效框图SPF路由SPF路由协议网络拓扑视图功效当地链路状态功效最短路由计算功效与全部节点交互与邻居节点交互(掌握链路状态)转发表链路增减链路通断状态改变…送出自己链路状态获取节点链路状态数据分组转发26/40链路状态算法基本思想普通以时延作为度量参数发觉邻居并测量与邻居时延（延迟，链路状态）与全部节点交流与邻居链路状态信息独立计算出到其它节点最正确路径注意影响时延可能原因线路速率当前负载节点处理能力互联网中普遍使用OSPF算法采取L-S法

链路状态：了解为链路开销链路质量延迟等度量★27/40链路状态算法算法基本步骤，每个节点都进行以下工作：发觉邻居探寻邻居，得到邻居唯一地址测量链路开销测量到各邻居节点延迟（链路质量）交换路由信息形成链路状态分组，向全部节点扩散充实路由信息库依据收到各节点链路状态信息，进而得出全网拓扑计算路由表依据自己掌握路由信息，独立计算本节点到其它节点最正确路由（最小时延）尤其注意：链路状态算法交流路由信息：链路状态信息（本节点到邻居延迟）交流对象：向全部节点交流方法：扩散法路由计算：只依据自己掌握路由信息，独立计算最正确路由（不依赖他人计算）

★28/40链路状态算法发觉邻居节点初始时，每个节点都向每个出口（点到点线路）发送“Hello”分组，通知自己地址收到分组节点则回应一个分组通知自己地址尤其强调：每个节点地址必须唯一

ABHello，IamAHello，IamB★29/40链路状态算法测量链路开销（链路延迟）向邻居发送“Echo”分组（对方必须应答）对方发送应答计算往返延时除以2，得到时延（可计算几次得平均值）计算链路开销时值得讨论问题是否考虑负荷？两种观念考虑负荷，从进入发送队列排队开始算忽略负荷，从发送开始算正反方向延时是否一样？可能不一样为分析简便，通常忽略差异，用平均值

ABT“Echo”“Echo”Response★30/40链路状态算法经过测试计算出到邻居开销假设各节点测得开销以下所表示

A节点B节点4C3B开销邻居6C5D3A开销邻居2D6B1E4A开销邻居3E2C2F5B开销邻居3D2F1C开销邻居2E2D开销邻居C节点D节点F节点E节点★31/40链路状态算法创建链路状态分组依据测得到全部邻居延时，形成链路状态分组链路状态分组内容公布者：公布信息节点名称序号：序号大小表示信息新旧时间：一个分组在网络中存活时间

BACDEF1225624334C3B时间序号A公布者6C3A时间序号B公布者5D6B4A时间序号C公布者2D1E2C5B时间序号D公布者3E2F3D1C时间序号E公布者2F2E2D时间序号F公布者★32/40链路状态算法公布链路状态分组公布对象：全部节点公布时间：定时，链路状态发生改变时公布方法：扩散法（洪泛）采取扩散法一定能够抵达全网各节点节点可能收到多个相同分组可依据序号判别，相同序号则丢弃重复节点也可能收到同一个公布者不一样序号分组依据公布时间判别，丢弃老，处理新为防止分组可能在网中循环经过时间（年纪）字段防止（按时间递减，到0时将被丢弃）各节点依据逐步收到链路分组，充实路由信息库，逐步“绘出”拓扑图

★33/40链路状态算法计算到各节点最正确路由计算方法：把本节点作为源节点，计算到其它节点路由采取著名Dijkstra算法（最短路径算法）计算依据只依据自己掌握路由信息库（拓扑）独立计算最正确路由（不依赖他人计算）

★34/40链路状态算法怎样计算最正确路由最短路径算法－－Dijkstra算法

A1A2A4A3A526512151）初始化时，设A1到其它不直连节点距离为∞寻找A1到全部节点最短路径A2A3A4A5顶点距离路径2）选择距离A1最短节点及其路径3）观察经过新选择路径是否能更短抵达其它顶点4）已选择出节点和最短路径将不参加下一轮比较5）重复2-4步，直到不剩有节点265∞A2A3A4A1A2A3－－3更新A1A2A33A1A2A4－－∞A1A2A5－－4A1A2A3A4－－4更新A1A2A3A44A1A2A3A5－－8A1A2A54A1A2A3A4A5－－∞更新35/40Dijkstra’sAlgorithm

1Initialization:

2N'={u}3forallnodesv4ifvadjacenttou5thenD(v)=c(u,v)6elseD(v)=∞

78Loop

9findwnotinN'suchthatD(w)isaminimum10addwtoN'

11updateD(v)forallvnotinN':12D(v)=min(D(v),D(w)+c(w,v))13/*newcosttoviseitheroldcosttovorknown14sho