计算机网络原理与实践课件ch4

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

2、棵树第3章 直连连接的网络aedcbf2213112535默认路由器源路由器目的路由器AB路由选择算法分类：自治系统内或外？第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.7MPLS4.8IP多播4.9小结第3章 直连连接的网络计算机网络：原理与实践8RIP(路由选择信息协议)距离矢量算法包括在1982中的 BSD-UNIX Distribution距离测度: 跳的数量(最大 = 15跳)计算机网络：原理与实践9DCBAuvwxyz 目的 跳 u 1 v 2 w 2 x 3 y 3 z 2 RIP特点：仅与相邻路由器交换信息

4、交换本路由器选路表中的更新信息按固定时间间隔交换信息，约30秒根据更新信息，对本地RIP表进行处理第3章 直连连接的网络计算机网络：原理与实践10RIP例子 目的子网下一跳路由器到目的子网的跳数wR12yR32zR36x-1vR42R2中初始选路表目的子网下一跳路由器到目的地的跳数zR13w-x-来自路由器R1的通告目的子网下一跳路由器到目的地的跳数wR12yR32zR14x-1vR42R2更新后的转发表第3章 直连连接的网络计算机网络：原理与实践11距离向量算法基本思想基本思想: 如果邻居知道到达目的地的距离，且自己知道到达邻居的距离，则能算出自己到达目的地的距离每个结点周期性地向其邻居发送

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

6、 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 方程:取最小的结点是在最短路中的下一跳 转发表第3章 直连连接的网络计算机网络：原理与实践13距离矢量算法分布式迭代迭代、异步: 每次引起本地迭代的原因: 本地链路费用改变DV从邻居更新报文分布式:每个结点仅当其DV改变时通知邻居如果必要，邻居则通知它们的邻居等待 (来自邻居本地费用报文的变化)重新计算估计值如果到任何目的地的DV已经变化, 通知邻居 每个结点:第3章 直连连接的网络距离向量算法(DV算法)1.在每个结点x:2.初

7、始化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第3章 直连连接的网络计算机网络：原理与实践1

8、4x y zxyz0 2 7fromcost tofromfromx y zxyz0 x y zxyzcost tox y zxyz710cost to2 0 1 2 0 17 1 0timexz127ynode xtableDx(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 ytablenode ztablecost tofrom第3章 直连连接的网络计算机网络：原理与实践15x y zxy

9、z0 2 3fromcost tox y zxyz0 2 7fromcost tox y zxyz0 2 3fromcost tox y zxyz0 2 3fromcost tox y zxyz0 2 7fromcost to2 0 17 1 02 0 13 1 02 0 13 1 02 0 13 1 02 0 13 1 0timex y zxyz0 2 7fromcost tofromfromx y zxyz0 x y zxyzcost tox y zxyz710cost to2 0 1 2 0 17 1 0timexz127ynode xtableDx(y) = minc(x,y) + D

10、y(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 ytablenode ztablecost tofrom第3章 直连连接的网络计算机网络：原理与实践16计算机网络：原理与实践17距离矢量算法存在的问题及解决链路费用变化:好消息传播得快坏消息传播得慢“计数到无穷”问题!在算法稳定前，反复迭代解决方法：毒性逆转如果Z路由通过Y到 X :Z告诉Y它(Zs)到X的距离是无穷，使Y将不能采用经Z到X的路由这将完全解决计数到无穷问题? xz1

11、450y第3章 直连连接的网络60第4章：内容提要4.1网络层概述4.2网络服务模型4.3网际协议(IP)4.4路由选择协议及其算法RIP和距离矢量路由选择算法OSPF和链路状态路由选择算法BGP和层次路由选择4.5路由器工作原理4.6移动IP技术4.7MPLS4.8IP多播4.9小结第3章 直连连接的网络计算机网络：原理与实践18计算机网络：原理与实践19OSPF (开放最短路优先)“open”: 公共免费可用使用链路状态(link state)算法：网络拓扑和所有链路的费用都已知，可作为LS算法的输入LS算法依靠两种机制进行路由计算：LS信息的可靠传输积累的链路状态知识OSPF两个技术要点

12、：使用洪泛链路状态信息的链路状态协议Dijkstra最低费用路径算法第3章 直连连接的网络计算机网络：原理与实践20OSPF特色安全性: 所有OSPF报文经鉴别(以防攻击) 允许多条费用相同的路径(而RIP仅一条路径)对每条链路，对不同的TOS(服务类型)，设置多种费用测度(如卫星链路费用置为用于尽力而服务为“低”，高为实时服务)综合的单播和多播支持: 多播OSPF (MOSPF)使用与OSPF相同的拓扑数据库在大规模网络中，用层次的OSPF第3章 直连连接的网络计算机网络：原理与实践21具有4个区域的层次结构OSPF自治系统第3章 直连连接的网络计算机网络：原理与实践22层次OSPF两级层次

13、: 本地, 主干链路状态通告仅在本地每个结点具有详细的区域拓扑；仅知道到其他区域网络的方向(最短路)区域边界路由器 : “摘要”到在自己区域网络的距离，向其他区域边界路由器通告主干路由器 : 运行OSPF 路由选择限制到主干边界路由器 : 连接到其他AS第3章 直连连接的网络计算机网络：原理与实践23一种链路状态路由选择算法Dijkstra算法知道网络所有结点的拓扑、链路费用经“链路状态广播”所有结点具有相同信息从一个结点(源)到所有其他结点计算最低费用路径给出对这些结点转发表迭代: k次迭代后，得知到k个目的地的最低费用路径概念:c(x,y): 从结点x到y的链路费用; = 如果非直接邻居D

14、(v):从源到目的地v路径费用的当前值p(v): 从源到v沿路径的前任结点N: 已知在最小费用路径中的结点集合第3章 直连连接的网络计算机网络：原理与实践24Dijsktra算法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

15、until 所有结点在 N中 第3章 直连连接的网络计算机网络：原理与实践25LS例子：结点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,11,b)将试探表中费用最小的记录c加入证实表中。检查证实表中新成员c的链路状态报文。4(d,0,-)(c,2,c)(b,5,c)(a,12,c)通过c到达b的费用是5,记录(b,11,b)被替换为(b,5,c)。c的链路状态报文告知可以费用12到达a。5(d,0,-)(c,2,c)(b,5,c)(a,12,c)把试探表中费用最小的记录b加入证实表中，观察它的链路状态报文。6(d,0,-)(c,2,c)(b,5,c)(a,10,c)因为经过b可以费用5到达a，所以替换试探表中的记录。7(d,0,-)(c,2,c)(b,5,c) (a,10,c)把试探表中费用最小的记录a移入证实表中，结束。第3章 直连连接的网络小 结已学习网络互联的内容:RIP使用最早AS内部路由选择协议，适用范围较小距离矢量路由选择算法根据相邻信息得到全局最优路径OSPF广泛应用AS内部的路由选择协议，适用范围较大将AS