《计算机通信网-》-网络层Part2.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,#,1,5.3.4,几个动态路由算法,动态路由算法,依据网络动态改变计算路由，形成路由表,路由表自动形成并依据拓扑改变自动更新,适应于网拓扑改变网络、大网,如广域网、互联网,包括问题,节点之间交换路由信息,快速适应拓扑改变,感知拓扑改变,快速传递改变信息,快速形成新稳定路由（无环路、不震荡，快速收敛）,1/40,5.3.4,几个动态路由算法,中心路由算法,逆向学习法,分布式路由算法（重点）,距离矢量法,链路状态法,2/40,中心路由算法（集中路由）,原理,各个节点定时将本节点信道及,相邻节点信息汇报给中心路由计算机,由中心路由计算机计算出各节点到其它节点最正确路由，然后分配到各个节点,特点,理论上讲能够得到全网最优路由（因算法考虑了流量、节点等全网信息）,但实现困难，极难在大网中使用，适应于小网，原因有三：,信息上传困难（各节点定时上传信息会造成中心路由计算机附近节点及线路拥塞）,同时困难（节点很多，中心反馈新路由时，各节点接收时间不一样，可能会造成同一网里有节点使用新路由，有使用老路由）,路由更新过时（可能会出现路由更新抵达时，节点情况已变）,2,1,3,4,5,中心路由,计算机,3/40,逆向（反向）学习法,原理,依据接收分组中源地址和接收端口号，形成转发表，方便下次作为目标节点时转发路径,特点,能动态适应新节点加入,对线路故障、节点损坏反应迟钝,适应拓扑结构相对稳定、小网,目标节点,端口,距离,A,n,Dn,C,A,收到从,A,送来分组,路由表中统计从该接口能够抵达,A,4/40,分布式动态路由算法,基本原理,节点之间需相互交换路由信息,节点单独计算路由,基本特点,局部最优，全局不一定最优,相互交换信息越详细、越频繁，路由优化越好，但造成额外开销也越大。,需要在额外开销和路由更新频率之间进行折中,优点,动态反应网络改变，路由表自动形成与更新（不需人工干预）,局部最优，路由开销少,缺点,局部最优路由，不是全局最优路由,可能出现不一致（矛盾）路由,可能出现路由震荡（路由表改变太快）,可能,出现路由发散（不能收敛）,5/40,分布式路由算法关键点,交换路由信息：,分布式计算：,节点依据交换路由信息，采取最优路由计算,方法计算最正确路由,哪些信息？,与谁交换？,边交换信息边计算,可达、距离、费用、负载、延时,与邻居、与全部节点,何时交换？,定时、拓扑改变时,6/40,两种经典分布式路由算法,基于网络距离分布式路由算法,-,矢量距离法,基于信道状态分布式路由算法,-,链路状态法,7/40,矢量距离法（,V-D,：,Vector Distance,）,依据协议设计者命名，也称为,Bellman-Ford,路由算法,Ford-Fulkerson,路由算法,基本思想,每个节点都保持一张到其它节点路由表,（目标节点，下一节点，距离）,“,距离,”,度量标准能够是跳数或时延等,邻居之间交换路由信息（目标节点，距离）,依据收到相邻节点信息，判断并决定是否更新路由,算法包括内容,初始路由表怎样建立？,邻居交换哪些信息,?,怎样依据邻居信息计算并更新自己路由表？,8/40,矢量距离法,算法几个步骤,初始化,建立初始路由表,扩散,向邻居扩散自己路由表信息,计算,依据收到相邻节点信息，计算最短路径，更新路由表,再扩散、再计算,这么就逐步形成了全网拓扑结构,使每个节点都计算出了到其它节点路径信息,值得注意是：何时向邻居扩散路由信息？,定时,拓扑发生改变时,9/40,距离矢量算法,1,）初始路由表建立,（目标节点，下一节点，距离）,=,（,V,0,，,G,0,，,D,0,）,2,）路由表向邻居扩散,2,1,3,4,5,6,1,1,2,1,1,1,1,1,1,4,6,5,3,2,1,3,3,3,1,1,2,2,4,4,4,4,6,5,5,注意：,度量值能够是节点跳数、时延等度量参数,10/40,距离矢量算法,各节点初始路由表：直接相连节点路由信息,2,1,3,4,5,6,1,1,1,1,1,1,1,1,2,目标,节点,下一,节点,距离,2,2,1,3,3,1,目标,节点,下一,节点,距离,1,1,1,3,3,1,4,4,1,目标,节点,下一,节点,距离,4,4,2,5,5,1,目标,节点,下一,节点,距离,3,3,1,4,4,1,6,6,1,目标,节点,下一,节点,距离,1,1,1,2,2,1,4,4,1,5,5,1,目标,节点,下一,节点,距离,2,2,1,3,3,1,5,5,1,6,6,2,11/40,距离矢量算法,3,）节点计算并更新本节点路由表,相邻节点定时交换信息（,目标节点，距离）,=,（,V,，,D,）,当某节点,A,收到相邻节点,j,信息（,Vx,，,D,jX,）时,（,Vx,表示目标地为,X,节点，,Djx,为,j,到,X,节点距离）,A,节点更新情况以下：,如,A,路由表中无此项，则添加表项（,Vx,，,j,，,D,0,+D,Xj,）,（,D,0,为,A,与邻居,j,距离）,如,A,路由表中有,Vx,项，（,Vx,，,k,，,D,A,x,）,若,kj,DAx D0+Djx,，则表项更新为（,Vx,，,j,，,D,0,+D,jX,）（新、短路径）,DAx D0+Djx,，则此表项保持不变,若,k=j,不论,DAx,大小怎样，都应更新为（,Vx,，,j,，,D0+DjX,）,（,原路径可能改变，需更新）,12/40,距离矢量算法,目标节点,下一节点,距离,2,2,1,3,3,1,信息公布者,2,目标节点,距离,1,1,3,1,4,1,节点,1,路由表初始值,收到节点,3,路由信息,目标节点,下一节点,距离,2,2,1,3,3,1,更新后,公布者,3,目标节点,距离,1,1,2,1,4,1,5,1,收到节点,2,路由信息,目标节点,下一节点,距离,2,2,1,3,3,1,4,2,2,距离更新,=,到邻居节点距离,+,邻居节点到目标节点距离,更新后,2,1,3,4,5,6,1,1,2,1,1,1,1,1,1,4,2,2,5,3,2,关,13/40,距离矢量算法,2,1,3,4,5,6,1,1,2,1,1,1,1,1,1,目标节点,下一节点,距离,2,2,1,3,3,1,4,2,2,5,3,2,节点,1,当前路由表,节点,1,向节点,2,公布路由信息,信息公布者,1,目标节点,距离,2,1,3,1,4,2,5,2,节点,1,向节点,3,公布路由信息,信息公布者,1,目标节点,距离,2,1,3,1,4,2,5,2,关,14/40,距离矢量算法,2,1,3,4,5,6,1,1,2,1,1,1,1,1,1,目标节点,下一节点,距离,2,2,1,3,3,1,4,2,2,5,3,2,节点,1,路由表更新,距离更新,=,到邻居节点距离,+,邻居节点到目标节点距离,收到节点,2,路由信息,公布者,2,目标节点,距离,1,1,3,1,4,1,5,2,6,3,目标节点,下一节点,距离,2,2,1,3,3,1,4,2,2,5,3,2,更新后,6,2,4,公布者,3,目标节点,距离,1,1,2,1,4,1,5,1,6,2,目标节点,下一节点,距离,2,21,3,3,1,4,2,2,5,3,2,更新后,6,2,4,3,3,关,15/40,距离矢量算法,4,）各节点将更新后路由表分别向自己邻居扩散，然后计算并再次更新路由表,当每个节点路由表包含了全部其它节点路由时，就形成了一个稳定路由，只要拓扑不改变，路由表就保持不变，不然会重新计算。,16/40,距离矢量算法,相关问题,水平分割,节点没有必要将从某节点收到信息再传回给该节点,无穷计数,距离矢量算法会出现路由环路,设计最大路径长度（跳数），以减轻环路出现时带来损害,用毒性反转方法，破坏路由,环路,17/40,水平分割,2,1,3,4,5,6,1,1,1,1,1,1,1,1,1,目标节点,下一节点,距离,2,2,1,3,3,1,4,2,2,5,3,2,节点,1,当前路由表,节点,1,向节点,2,公布路由信息,信息公布者,1,目标节点,距离,2,1,3,1,4,2,5,2,节点,1,向节点,3,公布路由信息,信息公布者,1,目标节点,距离,2,1,3,1,4,2,5,2,节点没有必要将从某节点,收到信息再传回给该节点,18/40,无穷计数,在某种情况下，距离矢量算法可能出现路由环路，其现象是路由表项随路由信息更新，不停增加。,A,C,B,D,正常情况：,A,认为到,D,经过,B,C,认为到,D,经过,B,B,认为到,D,经过,D,路由环路：,A,认为到,D,经过,B,C,认为到,D,经过,A,B,认为到,D,经过,C,19/40,A,C,B,D,平时：,A,收到,C,通知：,D,有两跳,A,收到,B,通知：,D,有一跳,选,B,C,收到,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,毒性反转处理路由环路,2,1,3,4,5,6,1,1,2,1,1,1,1,1,1,目标节点,下一节点,距离,2,2,1,3,3,1,4,2,2,5,3,2,6,3,3,节点,1,当前路由表,节点,1,向节点,2,公布路由信息,信息公布者,1,目标节点,距离,3,1,4,2,5,2,6,3,节点,1,向节点,3,公布路由信息,信息公布者,1,目标节点,距离,2,1,4,2,5,2,6,3,节点将从某节点收到信息再传回给该节点时，告诉对方不能从我这里过,无穷大,无穷大,无穷大,21/40,DV,协议,其它,改进,触发,更新,收到路由,信息,有没有穷大,路由项，直接更新对应路由表,项,更新,抑制,无穷大距离路由项保留一段时间不更新,(,直到,该信息传遍整个,网络,),22/40,距离矢量算法小节,特点：,只与邻节点交换路由信息,各节点独立计算最优路径（但依赖邻居计算结果）,能适应网络拓扑改变,稳定后，形成最短路径,算法简单,缺点：,网络改变扩散到全网速度慢,扩散速度：全部节点都发觉改变速度,路由收敛慢,收敛速度：大家分别计算，结果到达统一速度,存在路由环在网络改变未扩散完全时。,小网,23/40,链路状态,路由,（L,-S,：,link-state,）,定理,若节点掌握了全网全部节点链路情况，节点就掌握了网络拓扑结构,节点链路情况：有几条链路，连接对端节点,例：,节点,R0,得到了节点,Rk,链路情况，,R0,就可画出它拓扑,对端节点 链路距离,Rx dx,Ry dy,Rz dz,Rk,链路情况,Rk,Rx,Ry,Rz,dx,dy,dz,若知道,Ry,链路情况，就知道它是否与,Rx,、,Rz,相连,24/40,链路状态路由,关键问题,需要在以下情况下与全部节点交互,不知道存在哪些,节点,没有建立路由,假如处理了上述,问题，每个节点都能够,构建网络拓扑视图,用拓扑视图计算到各节点最短路由,计算结果形成自己转发表,因为掌握了网络拓扑结构，节点能够计算出最短路由，当然也能够计算出次短路由，以及更多条路由,路由策略：最短路由优先,SPF,，,S,hortest Path First,25/40,SPF,路由功效框图,依据上述描述，能够画出,SPF,功效框图,SPF,路由,SPF,路由协议,网络拓扑视图,功效,当地链路状态,功效,最短路由计算,功效,与全部节点交互,与邻居节点交互,(,掌握链路状态,),转发表,链路增减,链路通断,状态改变,送出自己链路状态,获取节点链路状态,数据分组转发,26/40,链路状态,算法,基本思想,普通以时延作为度量参数,发觉邻居并测量与邻居时延（延迟，链路状态）,与全部节点交流与邻居链路状态信息,独立计算出到其它节点最正确路径,注意影响时延可能原因,线路速率,当前负载节点处理能力,互联网中普遍使用,OSPF,算法采取,L-S,法,链路状态：了解为,链路开销,链路质量,延迟等度量,27/40,链路状态算法,算法基本步骤，每个节点都进行以下工作：,发觉邻居,探寻邻居，得到邻居唯一地址,测量链路开销,测量到各邻居节点延迟（链路质量）,交换路由信息,形成链路状态分组，向全部节点扩散,充实路由信息库,依据收到各节点链路状态信息，进而得出全网拓扑,计算路由表,依据自己掌握路由信息，独立计算本节点到其它节点最正确路由（最小时延）,尤其注意：链路状态算法,交流路由信息：链路状态信息（本节点到邻居延迟）,交流对象：向全部节点,交流方法：扩散法,路由计算：只依据自己掌握路由信息，独立计算最正确路由（不依赖他人计算）,28/40,链路状态算法,发觉邻居节点,初始时，每个节点都向每个出口（点到点线路）发送,“,Hello,”,分组，通知自己地址,收到分组节点则回应一个分组通知自己地址,尤其强调：每个节点地址必须唯一,A,B,Hello,，,I am A,Hello,，,I am B,29/40,链路状态算法,测量链路开销（链路延迟）,向邻居发送,“,Echo,”,分组（对方必须应答）,对方发送应答,计算往返延时除以,2,，得到时延（可计算几次得平均值）,计算链路开销时值得讨论问题,是否考虑负荷？,两种观念,考虑负荷，从进入发送队列排队开始算,忽略负荷，从发送开始算,正反方向延时是否一样？,可能不一样,为分析简便，通常忽略差异，用平均值,A,B,T,“Echo”,“Echo”Response,30/40,链路状态算法,经过测试计算出到邻居开销,假设各节点测得开销以下所表示,A,节点,B,节点,4,C,3,B,开销,邻居,6,C,5,D,3,A,开销,邻居,2,D,6,B,1,E,4,A,开销,邻居,3,E,2,C,2,F,5,B,开销,邻居,3,D,2,F,1,C,开销,邻居,2,E,2,D,开销,邻居,C,节点,D,节点,F,节点,E,节点,31/40,链路状态算法,创建链路状态分组,依据测得到全部邻居延时，形成链路状态分组,链路状态分组内容,公布者：公布信息节点名称,序号：序号大小表示信息新旧,时间：一个分组在网络中存活时间,B,A,C,D,E,F,1,2,2,5,6,2,4,3,3,4,C,3,B,时间,序号,A,公布者,6,C,3,A,时间,序号,B,公布者,5,D,6,B,4,A,时间,序号,C,公布者,2,D,1,E,2,C,5,B,时间,序号,D,公布者,3,E,2,F,3,D,1,C,时间,序号,E,公布者,2,F,2,E,2,D,时间,序号,F,公布者,32/40,链路状态算法,公布链路状态分组,公布对象：全部节点,公布时间：定时，链路状态发生改变时,公布方法：扩散法（洪泛）,采取扩散法一定能够抵达全网各节点,节点可能收到多个相同分组,可依据序号判别，相同序号则丢弃重复,节点也可能收到同一个公布者不一样序号分组,依据公布时间判别，丢弃老，处理新,为防止分组可能在网中循环,经过时间（年纪）字段防止（按时间递减，到,0,时将被丢弃）,各节点依据逐步收到链路分组，充实路由信息库，逐步,“,绘出,”,拓扑图,33/40,链路状态算法,计算到各节点最正确路由,计算方法：,把本节点作为源节点，计算到其它节点路由,采取著名,Dijkstra,算法（最短路径算法）,计算依据,只依据自己掌握路由信息库（拓扑）,独立计算最正确路由（不依赖他人计算）,34/40,链路状态算法,怎样计算最正确路由,最短路径算法,Dijkstra,算法,A1,A2,A4,A3,A5,2,6,5,1,2,1,5,1,）初始化时，设,A1,到其它,不,直连,节,点距离为,寻找,A1,到全部节点最短路径,A2,A3,A4,A5,顶点,距离,路径,2,）选择距离,A1,最短节点及其路径,3,）观察经过新选择路径是否能更短抵达其它顶点,4,）已选择出节点和最短路径将不参加下一轮比较,5,）重复,2-4,步，直到不剩有,节,点,2,6,5,A2,A3,A4,A1 A2 A3,3,更新,A1 A2 A3,3,A1 A2 A4,A1 A2 A5,4,A1 A2 A3 A4,4,更新,A1 A2 A3 A4,4,A1 A2 A3 A5,8,A1 A2 A5,4,A1 A2 A3 A4 A5更新,35/40,Dijkstra,s Algorithm,1,Initialization:,2 N,=u,3 for all nodes v,4 if v adjacent to u,5 then D(v)=c(u,v),6 else D(v)=,7,8,Loop,9 find w not in N,such that D(w)is a minimum,10 add w to N,11 update D(v)for all v not in N,:,12,D(v)=min(D(v),D(w)+c(w,v),13 /*new cost to v is either old cost to v or known,14 shortest path cost to w plus cost from w to v*/,15,until all nodes in N,Notation:,c(x,y):,link cost from node x to y;=if not direct neighbors,D(v):,current value of cost of path from source to dest.v,N,:,set of nodes whose least cost path definitively known,36/40,链路状态算法,最短路径算法计算思想,每一步都取出当前最短路径，计算该路径对其它路径改变,从最近开始逐步计算到最远,2,1,3,4,5,6,37/40,使用逻辑链路,SPF,图中是若干个网络连接在一起情况,虚线代表节点间“逻辑”链路,节点在,SPF,协议中，宣告自己,LSA(,逻辑链路,),从而实现了网间,SPF,路由算法,38,SPF,路由,区域,1,区域,2,区域,3,区域,4,区域,5,区域,6,区域,7,区域,4,区域,5,区域,6,区域,7,38/40,链路状态算法小结,特点,与全网节点交换路由信息路由信息扩散,各节点独立计算最优路径一致性、准确性有很好确保,不是建立在他人计算结果上（如距离矢量算法）,能适应网络拓扑改变，稳定后能形成最短路径,收敛速度快可在大网中使用,不是计算之后再扩散,算法复杂，存放空间需求大,需要统计全网全部链路状态,39/40,链路状态算法与距离矢量算法比较,距离矢量算法,链路状态算法,交换路由信息,交换对象,交换时间,路由计算及计算依据,应用场所,到其它节点路由（路由表信息）,到相邻节点链路开销,仅向邻居,向全部节点扩散,定时或发生改变时,定时或链路发生改变时,各点自己计算，但依赖邻居计算结果,各点自己计算，不依赖其它节点计算,小网,大网,40/40,