计算机网络第4章-5

《计算机网络第4章-5》由会员分享，可在线阅读，更多相关《计算机网络第4章-5（44页珍藏版）》请在金锄头文库上搜索。

1、课堂研讨：分组到达分组到达到目的地到目的地的的好算法好算法路由选择协议及其算法教学提示教学目的 掌握基础性问题：异构网络互联、路由选择和分组转发重要知识点 虚拟互联网方法 编址 路由选择 移动IP学习方法 理解重要概念，掌握基础性问题3计算机网络：原理与实践分组转发地址映射方法路由器MPLS第4章 网络互联计算机网络：原理与实践4路由选择路由选择算法的图论抽象:结点是路由器边是物理链路链路代价: 时延、费用或 拥塞等级目的：决定从源到目的地通 过网络的“好的路径(路由器序 列)”路由选择协议“好的”路径:通常是最小费用的路径可以有其他定义是从源结点到目的结点的 一棵树aedcbf2 2 131

2、12535默认路由器源路由器目的路由器AB第4章 网络互联路由选择算法分类：自治系统内或外？计算机网络：原理与实践5第4章 网络互联计算机网络：原理与实践6路由选择算法分类：分布式或集中式？分散或全局的信息?分散的: 路由器知道物理相连的邻居 、到邻居的链路费用 计算的迭代过程，与邻居交 换信息 “距离矢量 (distance-vector, DV) ”算法全局的: 所有路由器具有完全的 拓扑、链路费用信息 “链路状态(link state algorithm, LS)”算法其他分类：静态或动态的 ?静态: 路由随时间缓慢变化动态: 路由更快地变化周期的更新适应链路费用变化第4章 网络互联第4

3、章：内容提要4.1网络层概述4.2网络服务模型4.3网际协议(IP)4.4路由选择协议及其路由选择协议及其算法算法 RIP和距离矢量路由选择 算法 OSPF和链路状态路由选 择算法 BGP和层次路由选择4.5路由器工作原理4.6移动IP技术4.7MPLS4.8IP多播4.9小结计算机网络：原理与实践7第4章 网络互联RIP(路由选择信息协议)距离矢量算法包括在1982中的 BSD-UNIX Distribution距离测度: 跳的数量(最大 = 15跳)计算机网络：原理与实践8DCBAuvwxyz目的 跳 u 1v 2w 2x 3y 3z 2RIP特点：仅与相邻路由器交换信息交换本路由器选路表

4、中的更新信息按固定时间间隔交换信息，约30秒根据更新信息，对本地RIP表进行处理第4章 网络互联计算机网络：原理与实践9RIP例子 目的 子网下一跳路 由器到目的子网 的跳数 wR12 yR32 zR36 x-1 vR42 R2中初始选路表目的 子网下一跳路 由器到目的地 的跳数 zR13 w- x- 来自路由器R1的通告目的 子网下一跳 路由器到目的地 的跳数 wR12 yR32 zR14 x-1 vR42 R2更新后的转发表第4章 网络互联计算机网络：原理与实践10距离向量算法基本思想基本思想: 如果邻居知道到达目的地的距离，且自己知道到达邻 居的距离，则能算出自己到达目的地的距离 每个结

5、点周期性地向其邻居发送自己距离矢量 当结点x接收到来自邻居的新DV估计，它使用Bellman-Ford方 程更新其自己的DV :Dx(y) minv c(x,v) + Dv(y) 对每个结点y N在规模较小、正常的条件下，估计值Dx(y)收敛在实际最 小费用 dx(y) 第4章 网络互联计算机网络：原理与实践11距离矢量算法例子Bellman-Ford方程(动态规划)定义dx(y) := 从x到y最低费用路径的费用则dx(y) = minv c(x,v) + dv(y) 其中min对u的所有邻居u uyxwvz2 2 13112535其中 dv(z) = 5, dx(z) = 3, dw(z)

6、 = 3du(z) = min c(u,v) + dv(z),c(u,x) + dx(z),c(u,w) + dw(z) = min 2 + 5,1 + 3,5 + 3 = 4根据B-F 方程:取最小的结点是在最短路中 的下一跳 转发表第4章 网络互联计算机网络：原理与实践12距离矢量算法分布式迭代迭代、异步: 每次引起 本地迭代的原因: 本地链路费用改变 DV从邻居更新报文分布式:每个结点仅当其DV 改变时通知邻居 如果必要，邻居则通 知它们的邻居等待 (来自邻居本地费用 报文的变化)重新计算估计值如果到任何目的地的DV 已经变化, 通知邻居 每个结点:第4章 网络互联距离向量算法(DV算法

7、)1.在每个结点x:2.初始化3. 对所有在N中的目的地y4. Dx(y) = c(x,y) /*如果y不是邻居则c(x,y) = */5. 对每个邻居w6. Dw(y) = 对所有在N中的目的地y7. 对每个邻居w8. 向w发送距离矢量 Dx = Dx(y): N中的y9.loop10. wait (直到发现对某个邻居w链路费用变化或从某邻居w收到一距离矢量)11. 对在N中的每个y：12. Dx(y) = minv c(x, v) +Dv(y)13. if Dx(y) 对任何目的地y变化14. 向所有邻居发送距离矢量 Dx = Dx(y): N中的y15.forever计算机网络：原理与实

8、践13第4章 网络互联x y zx y z0 2 7 fromcost tofromfromx y zx y z0x y zx y z cost tox y zx y z 7 10cost to 2 0 1 2 0 17 1 0timexz127ynode x tableDx(y) = minc(x,y) + Dy(y), c(x,z) + Dz(y) = min2+0 , 7+1 = 2Dx(z) = minc(x,y) + Dy(z), c(x,z) + Dz(z) = min2+1 , 7+0 = 332 node y tablenode z tablecost tofrom计算机网络：

9、原理与实践14第4章 网络互联x y zx y z0 2 3fromcost tox y zx y z0 2 7fromcost to x y zx y z0 2 3fromcost tox y zx y z0 2 3fromcost tox y zx y z0 2 7fromcost to2 0 17 1 02 0 1 3 1 02 0 13 1 02 0 13 1 02 0 13 1 0timex y zx y z0 2 7 fromcost tofromfromx y zx y z0x y zx y z cost tox y zx y z 7 10cost to 2 0 1 2 0 17

10、 1 0timexz127ynode x tableDx(y) = minc(x,y) + Dy(y), c(x,z) + Dz(y) = min2+0 , 7+1 = 2Dx(z) = minc(x,y) + Dy(z), c(x,z) + Dz(z) = min2+1 , 7+0 = 332 node y tablenode z tablecost tofrom计算机网络：原理与实践15第4章 网络互联计算机网络：原理与实践16距离矢量算法存在的问题及解决链路费用变化:好消息传播得快坏消息传播得慢“计数到无穷”问题!在算法稳定前，反复迭代解决方法：毒性逆转如果Z路由通过Y到 X :Z告诉Y

11、它(Zs)到X的距离是无穷，使Y将不能采用经Z到X的路由这将完全解决计数到无穷问题? xz1450y60第4章 网络互联第4章：内容提要4.1网络层概述4.2网络服务模型4.3网际协议(IP)4.4路由选择协议及其路由选择协议及其算法算法 RIP和距离矢量路由选择 算法 OSPF和链路状态路由选 择算法 BGP和层次路由选择4.5路由器工作原理4.6移动IP技术4.7MPLS4.8IP多播4.9小结计算机网络：原理与实践17第4章 网络互联计算机网络：原理与实践18OSPF (开放最短路优先)“open”: 公共免费可用使用链路状态(link state)算法： 网络拓扑和所有链路的费用都已知

12、，可作为LS算法的 输入LS算法依靠两种机制进行路由计算： LS信息的可靠传输 积累的链路状态知识OSPF两个技术要点： 使用洪泛链路状态信息的链路状态协议 Dijkstra最低费用路径算法第4章 网络互联计算机网络：原理与实践19OSPF特色安全性: 所有OSPF报文经鉴别(以防攻击) 允许多条费用相同的路径(而RIP仅一条路径)对每条链路，对不同的TOS(服务类型)，设置多种 费用测度(如卫星链路费用置为用于尽力而服务为“ 低”，高为实时服务)综合的单播和多播支持: 多播OSPF (MOSPF)使用与OSPF相同的拓扑数 据库在大规模网络中，用层次的OSPF第4章 网络互联计算机网络：原理

13、与实践20具有4个区域的层次结构OSPF自治系统第4章 网络互联计算机网络：原理与实践21层次OSPF两级层次: 本地, 主干 链路状态通告仅在本地 每个结点具有详细的区域拓扑；仅知道到其他区域网络 的方向(最短路)区域边界路由器 : “摘要”到在自己区域网络的距离 ，向其他区域边界路由器通告主干路由器 : 运行OSPF 路由选择限制到主干边界路由器 : 连接到其他AS第4章 网络互联计算机网络：原理与实践22一种链路状态路由选择算法Dijkstra算法知道网络所有结点的拓扑、 链路费用 经“链路状态广播” 所有结点具有相同信息从一个结点(源)到所有其他 结点计算最低费用路径 给出对这些结点转

14、发表迭代: k次迭代后，得知到k 个目的地的最低费用路径概念:c(x,y): 从结点x到y的链路 费用; = 如果非直接邻居D(v):从源到目的地v路径 费用的当前值p(v): 从源到v沿路径的前 任结点N: 已知在最小费用路径中 的结点集合第4章 网络互联计算机网络：原理与实践23Dijsktra算法1 初始化: 2 N = u 3 对所有结点v 4 if v 邻近u 5 then D(v) = c(u,v) 6 else D(v) = 7 8 Loop 9 找出w不在N中使得D(w)最小 10 将w加入N 11 对于所有v临近w并不在N中，更新D(v): 12 D(v) = min( D(v), D(w) + c(w,v) ) 13 /* 到v的新费用或是到v的老费用或到w加上从w到v的已知 最短路费用*/ 15 until 所有结点在 N中 第4章 网络互联计算机网络：原理与实践24LS例子：结点d建立转发表的过程步骤证实表试探表注释 1(d,0,-) 因为d是证实表中唯一新成员，等待链路状态报文2(d,0,-)(b,11,b)(c,2,c)链路状态报文告诉d，可以费用11通过b到达b，这是表中最好的路径，因此将其加入试探表中。同理c也加入。3(d,0,-)(c,2,c)(b