《计算机网络：原理与实践教学课件ppt作者 陈鸣ch4-13》由会员分享，可在线阅读，更多相关《计算机网络：原理与实践教学课件ppt作者 陈鸣ch4-13（28页珍藏版）》请在金锄头文库上搜索。
1、,第4章 网络互联,解放军理工大学 陈 鸣 博士 ,计算机网络原理课程,课堂研讨： 分组到达到目的地的好算法,第13讲 路由选择协议及其算法,教学提示,教学目的 掌握基础性问题：异构网络互联、路由选择和分组转发 重要知识点 虚拟互联网方法 编址 路由选择 移动IP 学习方法 理解重要概念，掌握基础性问题,4,计算机网络：原理与实践,第3章 直连连接的网络,分组转发 地址映射方法 路由器 MPLS,计算机网络：原理与实践,5,路由选择,路由选择算法的图论抽象: 结点是路由器 边是物理链路 链路代价: 时延、费用或拥塞等级,目的：决定从源到目的地通过网络的“好的路径(路由器序列)”,“好的”路径:
2、 通常是最小费用的路径 可以有其他定义 是从源结点到目的结点的一棵树,第3章 直连连接的网络,路由选择算法分类：自治系统内或外？,第3章 直连连接的网络,计算机网络：原理与实践,6,计算机网络：原理与实践,7,路由选择算法分类：分布式或集中式？,分散或全局的信息? 分散的: 路由器知道物理相连的邻居、到邻居的链路费用 计算的迭代过程，与邻居交换信息 “距离矢量 (distance-vector, DV) ”算法,全局的: 所有路由器具有完全的拓扑、链路费用信息 “链路状态(link state algorithm, LS)”算法 其他分类：静态或动态的? 静态: 路由随时间缓慢变化 动态: 路
3、由更快地变化 周期的更新 适应链路费用变化,第3章 直连连接的网络,第4章：内容提要,4.1网络层概述 4.2网络服务模型 4.3网际协议(IP) 4.4路由选择协议及其算法 RIP和距离矢量路由选择算法 OSPF和链路状态路由选择算法 BGP和层次路由选择,4.5路由器工作原理 4.6移动IP技术 4.7MPLS 4.8IP多播 4.9小结,第3章 直连连接的网络,计算机网络：原理与实践,8,RIP(路由选择信息协议),距离矢量算法 包括在1982中的 BSD-UNIX Distribution 距离测度: 跳的数量(最大 = 15跳),计算机网络：原理与实践,9,RIP特点： 仅与相邻路由
4、器交换信息 交换本路由器选路表中的更新信息 按固定时间间隔交换信息，约30秒 根据更新信息，对本地RIP表进行处理,第3章 直连连接的网络,计算机网络：原理与实践,10,RIP例子,R2中初始选路表,来自路由器R1的通告,R2更新后的转发表,第3章 直连连接的网络,计算机网络：原理与实践,11,距离向量算法基本思想,基本思想: 如果邻居知道到达目的地的距离，且自己知道到达邻居的距离，则能算出自己到达目的地的距离 每个结点周期性地向其邻居发送自己距离矢量 当结点x接收到来自邻居的新DV估计，它使用Bellman-Ford方程更新其自己的DV :,Dx(y) minv c(x,v) + Dv(y)
5、 对每个结点y N,在规模较小、正常的条件下，估计值Dx(y)收敛在实际最小费用 dx(y),第3章 直连连接的网络,计算机网络：原理与实践,12,距离矢量算法例子,Bellman-Ford方程(动态规划) 定义 dx(y) := 从x到y最低费用路径的费用 则 dx(y) = minv c(x,v) + dv(y) 其中min对u的所有邻居,其中 dv(z) = 5, dx(z) = 3, dw(z) = 3,du(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
6、-F 方程:,取最小的结点是在最短路中的下一跳 转发表,第3章 直连连接的网络,计算机网络：原理与实践,13,距离矢量算法分布式迭代,迭代、异步: 每次引起本地迭代的原因: 本地链路费用改变 DV从邻居更新报文 分布式: 每个结点仅当其DV改变时通知邻居 如果必要，邻居则通知它们的邻居,每个结点:,第3章 直连连接的网络,距离向量算法(DV算法),1. 在每个结点x: 2. 初始化 3. 对所有在N中的目的地y 4. Dx(y) = c(x,y) /*如果y不是邻居则c(x,y) = */ 5. 对每个邻居w 6. Dw(y) = 对所有在N中的目的地y 7. 对每个邻居w 8. 向w发送距离
7、矢量 Dx = Dx(y): N中的y 9. loop 10. 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中的y 15. forever,第3章 直连连接的网络,计算机网络：原理与实践,14,x y z,x,y,z,0 2 7,from,cost to,from,from,x y z,x,y,z,0,x y z,x,y,z,cost to,x y z,x,y,z,7,1
8、,0,cost to, 2 0 1, ,2 0 1,7 1 0,time,node x table,Dx(y) = minc(x,y) + Dy(y), c(x,z) + Dz(y) = min2+0 , 7+1 = 2,Dx(z) = minc(x,y) + Dy(z), c(x,z) + Dz(z) = min2+1 , 7+0 = 3,3,2,node y table,node z table,cost to,from,第3章 直连连接的网络,计算机网络：原理与实践,15,x y z,x,y,z,0 2 3,from,cost to,x y z,x,y,z,0 2 7,from,cost
9、 to,x y z,x,y,z,0 2 3,from,cost to,x y z,x,y,z,0 2 3,from,cost to,x y z,x,y,z,0 2 7,from,cost to,2 0 1,7 1 0,2 0 1,3 1 0,2 0 1,3 1 0,2 0 1,3 1 0,2 0 1,3 1 0,time,x y z,x,y,z,0 2 7,from,cost to,from,from,x y z,x,y,z,0,x y z,x,y,z,cost to,x y z,x,y,z,7,1,0,cost to, 2 0 1, ,2 0 1,7 1 0,time,node x tabl
10、e,Dx(y) = minc(x,y) + Dy(y), c(x,z) + Dz(y) = min2+0 , 7+1 = 2,Dx(z) = minc(x,y) + Dy(z), c(x,z) + Dz(z) = min2+1 , 7+0 = 3,3,2,node y table,node z table,cost to,from,第3章 直连连接的网络,计算机网络：原理与实践,16,计算机网络：原理与实践,17,距离矢量算法存在的问题及解决,链路费用变化: 好消息传播得快 坏消息传播得慢“计数到无穷”问题! 在算法稳定前，反复迭代 解决方法：毒性逆转 如果Z路由通过Y到 X : Z告诉Y它(
11、Zs)到X的距离是无穷，使Y将不能采用经Z到X的路由 这将完全解决计数到无穷问题?,1,4,50,第3章 直连连接的网络,60,第4章：内容提要,4.1网络层概述 4.2网络服务模型 4.3网际协议(IP) 4.4路由选择协议及其算法 RIP和距离矢量路由选择算法 OSPF和链路状态路由选择算法 BGP和层次路由选择,4.5路由器工作原理 4.6移动IP技术 4.7MPLS 4.8IP多播 4.9小结,第3章 直连连接的网络,计算机网络：原理与实践,18,计算机网络：原理与实践,19,OSPF (开放最短路优先),“open”: 公共免费可用 使用链路状态(link state)算法： 网络拓
12、扑和所有链路的费用都已知，可作为LS算法的输入 LS算法依靠两种机制进行路由计算： LS信息的可靠传输 积累的链路状态知识 OSPF两个技术要点： 使用洪泛链路状态信息的链路状态协议 Dijkstra最低费用路径算法,第3章 直连连接的网络,计算机网络：原理与实践,20,OSPF特色,安全性: 所有OSPF报文经鉴别(以防攻击) 允许多条费用相同的路径(而RIP仅一条路径) 对每条链路，对不同的TOS(服务类型)，设置多种费用测度(如卫星链路费用置为用于尽力而服务为“低”，高为实时服务) 综合的单播和多播支持: 多播OSPF (MOSPF)使用与OSPF相同的拓扑数据库 在大规模网络中，用层次
13、的OSPF,第3章 直连连接的网络,计算机网络：原理与实践,21,具有4个区域的层次结构OSPF自治系统,第3章 直连连接的网络,计算机网络：原理与实践,22,层次OSPF,两级层次: 本地, 主干 链路状态通告仅在本地 每个结点具有详细的区域拓扑；仅知道到其他区域网络的方向(最短路) 区域边界路由器 : “摘要”到在自己区域网络的距离，向其他区域边界路由器通告 主干路由器 : 运行OSPF 路由选择限制到主干 边界路由器 : 连接到其他AS,第3章 直连连接的网络,计算机网络：原理与实践,23,一种链路状态路由选择算法,Dijkstra算法 知道网络所有结点的拓扑、链路费用 经“链路状态广播
14、” 所有结点具有相同信息 从一个结点(源)到所有其他结点计算最低费用路径 给出对这些结点转发表 迭代: k次迭代后，得知到k个目的地的最低费用路径,概念: c(x,y): 从结点x到y的链路费用; = 如果非直接邻居 D(v):从源到目的地v路径费用的当前值 p(v): 从源到v沿路径的前任结点 N: 已知在最小费用路径中的结点集合,第3章 直连连接的网络,计算机网络：原理与实践,24,Dijsktra算法,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)
15、最小 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中,第3章 直连连接的网络,计算机网络：原理与实践,25,LS例子：结点d建立转发表的过程,第3章 直连连接的网络,小 结,已学习网络互联的内容: RIP 使用最早AS内部路由选择协议，适用范围较小 距离矢量路由选择算法 根据相邻信息得到全局最优路径,OSPF 广泛应用AS内部的路由选择协议，适用范围较大 将AS划为若干区域 链路状态路由选择算法 知道网络所有结点的拓扑、链路费用，集中计算最优路径,第3章 直连连接的网络,计算机网络：原理与实践,26,课后作业,考虑图4-27上的网络。试用距离矢量算法给出结点b的距离表表项生成过程。 考虑图4-27的网络。用Dijkstra的最短路算法计算出从b到所有网络结点的最短
