计算机网络_12_网络层_路由协议

null第十二讲林楠电子邮件：lynn_linnan@yahoo.com.cn 办公电话：0371-63887293 办公室：408 网络层 ——路由 协议 离婚协议模板下载合伙人协议 下载渠道分销协议免费下载敬业协议下载授课协议下载 第十二讲路由协议• 可路由协议 一旦选择一条路径后，用来在路由器之间传送用户的数据报。 举例：IP• 路由协议 用来在路由器之间建立维护路由表更新，通过管理路由表使得路由器选择最佳传输路径。 举例: RIP, IGRP, OSPF路由协议路由协议路由选择 路由算法 路由协议 RIP、OSPF、BGP 单播与组播路由选择 路由协议路由选择路由选择路由选择要求一台主机或路由器具有一个路由表(routing table)。 路由表中的每条记录都包含一目的IP地址和下一跳结点地址。 任何一个路由器中都没有到达目的地址的完整路由信息。 当一台主机要发送一个数据报，或者一台路由器接收到一个数据报转发时，就会查看路由表，找出与目的地址匹配的记录，然后按照记录中下一跳地址将数据报转发出去。 为了提高查询路由表的效率，使得路由表的大小易于管理，并解决安全问题，目前有几种路由选择技术： 1）下一跳路由选择 2）特定网络路由选择 3）特定主机路由选择 4）默认路由选择路由协议路由选择 路由算法 路由协议 RIP、OSPF、BGP 单播与组播路由选择 路由协议路由算法路由算法连接成本 c (x, x’) 例如：c (w, z) = 5 （成本一般为1，可以根据不同网络带宽与拥塞情况而改变）路径成本 (x1, x2, x3,…, xp) = c(x1,x2) + c(x2,x3) + … + c(xp-1,xp) 路由算法 Routing Algorithm：在收发双方之间计算最小成本路径。 路由算法路由算法 跳数: 数据报到达目的地，所必须通过的路由器的总数。 Hop count越少，该路由线路就越好。 带宽: 连接的速度。100Mbps 的速度优于64Kbps的专线。 延迟: 把数据报从发送主机传送到接收主机所需要的时间。 负载: 路由器或网络上数据流通的数量。 可靠性: 每条网络连接上的差错率。 等等…… 答：成本是一变化值，通过一些网络度量 metric 决定。 问: 什么是u与z之间最小成本路径? 路由算法常用路由算法： 最短路径算法 Dijkstra 静态的 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 （给定网络的拓扑结构， 路由变化很少） 扩散法 flooding 静态的方法 距离向量算法 D-V 动态的方法（网络拓扑结构有变化， 路由变化较多） 链路状态算法 L-S 动态的方法路由算法路由算法：1）最短路径算法 最短路径算法 Dijkstra（1959）：静态的方法 以边的权值为距离来度量最短路径，即权值和最小的路径。 经过边数最少的路径不一定是最短路径。路由算法：1）最短路径算法 路由算法：1）最短路径算法 最短路径算法采用的数据结构 集合S：尚未找到最短路径的结点集合； 数组R：记录路径，R[i] 为指定 源点 到 结点i 的路径上 结点i 的前一个结点； 数组D：D[i] 为从指定 源点 到 结点i 的最短距离。 算法初始化 初始化集合S：为除源点外的所有结点； 初始化数组R：如果从源点到结点v存在连接，则R(v)=源点，否则为0； 初始化数组D：如果从源点到结点v存在连接，则D(v)=该边的权值， 否则为无穷大。 路由算法：1）最短路径算法 路由算法：1）最短路径算法 从5出发到4的最短路径问：从该图中看结点5到结点1、2、3、4、6、7分别怎么走? 例如到结点4路径：5-2-3-6-7-4路由算法：1）最短路径算法 路由算法路由算法常用路由算法： 最短路径算法 Dijkstra 静态的方法（给定网络的拓扑结构， 路由变化很少） 扩散法 flooding 静态的方法 距离向量算法 D-V 动态的方法（网络拓扑结构有变化， 路由变化较多） 链路状态算法 L-S 动态的方法路由算法：2）扩散法 扩散法 flooding：不计算路径，有路就走。 例如：5到1/2；2到3/6；3到6/4；6到3/7；7到4。 存在问题：数据报重复到达某一结点。如3/6数据报循环往复发送。 解决方法： 1）在数据报头设一计数器，每经过一个结点自动加1，达到 规定 关于下班后关闭电源的规定党章中关于入党时间的规定公务员考核规定下载规定办法文件下载宁波关于闷顶的规定 值时， 丢弃数据报； 2）在每个结点上建立一个登记表，则数据报再次经过时丢弃。 缺点： 重复数据报多，浪费带宽。 优点： 可靠性高，路径最短， 常用与军事网络。 路由算法：2）扩散法 路由算法路由算法常用路由算法： 最短路径算法 Dijkstra 静态的方法（给定网络的拓扑结构， 路由变化很少） 扩散法 flooding 静态的方法 距离向量算法 D-V 动态的方法（网络拓扑结构有变化， 路由变化较多） 链路状态算法 L-S 动态的方法路由算法：3）距离向量法距离向量法（D-V Distance Vector Routing ）： 分散: 每台路由器只了解到达邻近路由器的链路成本，通过迭代计算 与相邻路由器交换信息。 动态、分布式算法、在RIP协议中使用，应用于较小的系统。 实现算法三 步骤 新产品开发流程的步骤课题研究的五个步骤成本核算步骤微型课题研究步骤数控铣床操作步骤 ：1）测量、2）更新邻结点距离向量、3）计算。 工作原理： 每个路由器用两个向量 Di Si 来表示该点到网上所有结点的路径 距离及其下一跳结点。 （如果网络中有n个路由器，则向量 Di Si 有n个分量； Di 表示到第i个结点的最短路径， Si 表示按此最短路径到达第i个结点的下一跳。 一个数据来了，根据Di 找最短路径，根据Si 找下一个跳结点。） 相邻路由器之间交换路径信息( 即交换向量 Di )； 各结点根据路径信息更新自己的路由表。路由算法：3）距离向量法路由算法：3）距离向量法以 J 结点为例子路由算法：3）距离向量法J 结点的新路由表从J结点测量值 J到A：8 J到I：10 J到H：12 J到K：6 J 的邻居结点交换的向量信息路由算法路由算法常用路由算法： 最短路径算法 Dijkstra 静态的方法（给定网络的拓扑结构， 路由变化很少） 扩散法 flooding 静态的方法 距离向量算法 D-V 动态的方法（网络拓扑结构有变化， 路由变化较多） 链路状态算法 L-S 动态的方法路由算法：4）链路状态算法链路状态算法 “link state” 动态算法；在OSPF协议中使用，应用于较大系统。 全局: 每台路由器都具有整个网络的拓扑图，具有所有链路成本信息。 与其他所有路由器共享信息，当有变化时共享变化信息 基本工作思想: 1）发现它的邻结点，并得到其网络地址； 当一个路由器启动后，向每个端口发送hello数据报，另一端的路由器发回 一 个应答来说明它是谁；因此得知它有多少邻居。 2）测量它到各邻结点的延迟或开销； 发送一个echo数据报要求对方立即响应，通过测量一个来回时间再除以2， 就可以得到一个延迟估计值，想要更精确，可重复这一过程，取平均值。路由算法：4）链路状态算法路由算法：4）链路状态算法基本工作思想: 3）组装一个数据报以告知它刚知道的所有信息； 路由算法：4）链路状态算法A结点的数据报 序号：数据报的序号路由算法：4）链路状态算法基本工作思想: 4）将这个数据报发给所有其他路由器；（与距离向量法不同） 用扩散法（向邻接的结点）发布链路状态数据报。 每个结点中有个表，记录已经收到过的数据报，不再重复转发。 例如：结点B的邻结点有A，C，F；所以有A/C/F三个发送和ACK标志。 发送标志 =0：从该结点收到数据报；ACK =1 向该结点发一个应答。 路由算法：4）链路状态算法5）用最短路径算法计算到每个其他路由器的最短路径。路由协议路由选择 路由算法 路由协议 RIP、OSPF、BGP 单播与组播路由选择 路由协议路由协议 Routing Protocols（ RIP、OSPF、BGP ） 应用范围：路由器 主要功能：路由器之间使用的协议，主要用来更新路由表。路由协议 Routing Protocols（ RIP、OSPF、BGP ） 应用范围：路由器 主要功能：路由器之间使用的协议，主要用来更新路由表。 传输层: TCP, UDP链路层物理层网络层路由协议路由协议两层路由选择: 内部自治系统 Intra-AS : AS之内的路由选择，由网管决定。 在同一AS中的路由器运行同样的路由选择协议/内部网关协议 不同AS中的路由器可以运行不同的内部路由选择协议。 外部自治系统 Inter-AS: AS之间的路由选择，符合唯一性 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 。 在不同AS之间的路由器只能运行一种路由选择协议/外部网关协议。 因特网的分层路由选择： 因为，一种路由选择协议不能完成更新所有的路由器中的路由表！ 所以，因特网被分成诸多自治系统 AS autonomous systems。 自治系统 AS：是一组具有单一管理权限的网络和路由器，类似一个 城市中的交通管理，每个自治系统受单一管理机构控制，由一组网络构成，AS之间由路由器连接。路由协议因特网是由诸多AS互联而成路由协议内部网关协议 IGP Interior Gateway Protocols： 更新一个AS内部路由器中的路由表。 RIP: 路由选择信息协议 Routing Information Protocol OSPF: 开放式最短路径优先协议 Open Shortest Path First IGRP: 内部网关路由选择协议（Cisco产权） Interior Gateway Routing Protocol外部网关协议 EGP Exterior Gateway Protocol 更新连接多个AS的路由器中的路由表。 BGP 边界网关协议 Border Gateway Protocol 路由协议路由协议Inter-AS 边界路由器(外部网关)Intra-AS 内部路由器边界路由器: 与其他同一AS中的路由器使用内部网关协议进行通信。 同时运行外部网关协议与其他的边界路由器进行通信。路由协议路由协议边界路由器R1，R2，R3，R4使用了一种内部网关和一种外部网关路由协议，其他路由器只使用内部网关协议。路由协议RIP 路由信息协议 Routing Information ProtocolRIP 路由信息协议 Routing Information Protocol是一种在AS内部使用的内部网关协议，适用于较小的网络。 使用 “ 距离向量 ” 路由算法来更新AS内的路由表。 RIP路由表通过应用层的进程 route-d 来管理。 路由协议： RIPRIP 路由信息协议 Routing Information ProtocolRIP 路由信息协议 Routing Information Protocol度量：视每个网络的成本都一样，使用跳数度量。 跳数：数据报到达目的地所经过的网络数。 (最大 15 hops) 路由协议： RIP路由协议： RIP 目的网络 下一路由器 到目的网络的跳数 w A 2 y B 2 z B 7 x -- 1 …. …. .... 路由D中的路由表路由协议： RIPOSPF 开放最短路径优先协议 Open Shortest Path FirstOSPF 开放最短路径优先协议 Open Shortest Path First是一种在AS内部使用的内部路由协议，适用于大型的网络。 采用分层管理方法，将一个AS分成若干个区域，一个区域内的路由器之间交换所有的信息，而对同一AS内的其他区域则隐藏其详细拓扑结构。 使用 “ 链路状态 ” 路由选择算法来更新AS内的路由表，结点之间传送路由数据报，结点得到数据报以后得到整个网络的拓扑结构。 度量：允许管理员根据所要求的服务类型分配网络成本。 例如：最大吞吐量服务，一卫星链路成本小于一光纤链路 例如：最小延迟服务，一卫星链路成本大于一光纤链路 根据不同的服务要求，一个路由器可能有多个路由表。 路由协议：OSPF路由协议：OSPF链路状态的路由选择表：路由协议：OSPFBGP 边界网关协议 （Border Gateway Protocol ）是用于AS之间的inter-AS路由协议，把每个AS看成一个结点。 使用路径向量路由选择来更新AS之间路由器的路由表。 只是在路由状态发生变化时才发送变化信息。BGP 边界网关协议 （Border Gateway Protocol ）Inter-AS路由选择路由协议： BGP路由协议： BGP路径向量的路由选择表：路由协议： BGPBGP是力求寻找一条能够到达目的网络且比较好的路由，并非寻找一条最佳路由，所以它采用的是路径向量路由选择。 在BGP协议中，每个自治系统选出一个BGP发言人，这些发言人通过相互交换自己的路径向量后，就可以找出到达各自治系统比较好的路径。路由协议： BGP路由协议： BGP路由协议：对比路由协议：对比为什么要区分内部网关协议IGP和外部网关协议EGP？ AS是由不同的机构管理运行，AS之间的通信会受到很多人为因素的影响，这些因素称为路由决策，由AS管理者设置。路由协议路由选择 路由算法 路由协议 RIP、OSPF、BGP 单播与组播路由选择 路由协议null单播与组播路由选择IP数据报传播方式视频会议IPTV 利用组播的方式发送电视信号。