计算机网络(上交)翁慧玉 第5章 网络层

《ComputerNetworksv4》cs.sjtu2/24/2020第5章网络层1/290第5章网络层网络层主要解决的问题路由选择网络互连拥塞控制为上层提供服务《ComputerNetworksv4》cs.sjtu2/24/2020第5章网络层2/290第5章网络层网络层设计的相关问题路由算法拥塞控制服务质量网络互联因特网中的网络层《ComputerNetworksv4》cs.sjtu2/24/2020第5章网络层3/290网络层的设计存储转发的数据包交换为传输层提供的服务面向无连接服务的实现面向连接服务的实现虚电路子网和数据报子网的比较《ComputerNetworksv4》cs.sjtu2/24/2020第5章网络层4/290存储转发的数据包交换数据包Packet存储转发StoreandForward路由器Router交换Switching通信子网CommunicationSubnet资源子网ResourceSubnet《ComputerNetworksv4》cs.sjtu2/24/2020第5章网络层5/290网络层协议环境ABCDEFRouterCarrier’sequipmentLANPacketH1H2ProcessP1ProcessP1TnbmP344Fig.5-1网络层协议环境《ComputerNetworksv4》cs.sjtu2/24/2020第5章网络层6/290网络层的设计存储转发的数据包交换为传输层提供的服务面向无连接服务的实现面向连接服务的实现虚电路子网和数据报子网的比较《ComputerNetworksv4》cs.sjtu2/24/2020第5章网络层7/290为传输层提供的服务服务应与路由器技术无关路由器的数量、类型和拓扑结构对于传输层来说应是不可见的传输层所能获得的网络地址应采用统一的编址方式，并允许跨越多个LAN和WAN《ComputerNetworksv4》cs.sjtu2/24/2020第5章网络层8/290网络层提供的服务类型面向无连接服务：网络是不可靠的，网络服务不应面向连接，分组的排序和流控制应不属于网络层，每个分组都单独寻径，所以必须携带完整的目的地址如Internet面向连接的服务：网络应该提供可靠的、面向连接的服务，否则服务质量将无从谈起，尤其对于多媒体应用如ATM对于网络层提供的服务有两种观点：《ComputerNetworksv4》cs.sjtu2/24/2020第5章网络层9/290网络层的设计存储转发的数据包交换为传输层提供的服务面向无连接服务的实现面向连接服务的实现虚电路子网和数据报子网的比较《ComputerNetworksv4》cs.sjtu2/24/2020第5章网络层10/290面向无连接服务的实现（数据报子网）路由器A按左边的路由表运行，后来发现如到E和F应该走B才更好，于是更新路由表ABCDEFRouterCarrier’sequipmentLANPacketH1H2ProcessP1ProcessP11A-BBCCDBECFCA-BBCCDBEBFBAABAC-DDEEFEACBDCCDDE-FFA的路由表E的路由表C的路由表TnbmP346Fig.5-2数据报子网中分组的寻径《ComputerNetworksv4》cs.sjtu2/24/2020第5章网络层11/290网络层的设计存储转发的数据包交换为传输层提供的服务面向无连接服务的实现面向连接服务的实现虚电路子网和数据报子网的比较《ComputerNetworksv4》cs.sjtu2/24/2020第5章网络层12/290面向连接服务的实现（虚电路子网）H1和H2已建立了1#连接H3要和H2建立连接只能是2#H11H31入口F1F2出口E1E2出口C1C2出口A的路由表TnbmP348Fig.5-3虚电路子网中分组的寻径ABCDEFRouterCarrier’sequipmentLANPacketH1H2ProcessP1ProcessP11H3ProcessP3A1A2入口C的路由表C1C2入口E的路由表《ComputerNetworksv4》cs.sjtu2/24/2020第5章网络层13/290网络层的设计存储转发的数据包交换为传输层提供的服务面向无连接服务的实现面向连接服务的实现虚电路子网和数据报子网的比较《ComputerNetworksv4》cs.sjtu2/24/2020第5章网络层14/290虚电路子网和数据报子网的比较数据报子网虚电路子网建立电路连接不需要需要寻址每个分组包含完整的源和目的地址每个分组包含一个很短的虚电路号状态信息路由器不保留连接的状态信息每条虚电路要求为每个连接提供路由表空间寻径路由器为每个分组独立寻径寻径在虚电路建立时完成，此后，所以分组按此路径传输路由器故障的影响除路由器崩溃，所以分组丢失，否则无影响所有通过该故障路由器的虚电路全部终止服务质量困难对每条虚电路，沿途的路由器如有足够的资源可分配，则很容易实现拥塞控制困难对每条虚电路，沿途的路由器如有足够的资源可分配，则很容易实现TnbmP349Fig.5-4虚电路子网和数据报子网的比较《ComputerNetworksv4》cs.sjtu2/24/2020第5章网络层15/290虚电路子网/数据报子网的比较(续)虚电路子网通过路径选择后建立连接分组按序传输服务质量能得到保证通信后撤销连接适合于实时传输数据报子网每个分组分别选择最佳路径，健壮性较好整个网络系统的信道利用率高，成本低差错控制和排序工作由协议高层（主机）完成适合于非实时传输《ComputerNetworksv4》cs.sjtu2/24/2020第5章网络层16/290第5章网络层网络层设计的相关问题路由算法拥塞控制服务质量网络互联因特网中的网络层《ComputerNetworksv4》cs.sjtu2/24/2020第5章网络层17/290路由算法路由算法是网络层软件的一个重要部分，它决定进入的分组应从哪一根输出线传输如果是数据报子网，将在每一个分组到达时作此决定如果是虚电路子网，是在虚电路建立时决定，该连接上所有分组都将沿此线路传输路由与转发：路由是寻径，转发是当一个分组到达时发生的动作《ComputerNetworksv4》cs.sjtu2/24/2020第5章网络层18/290路由算法（续）路由算法设计必须考虑的问题正确性简单性健壮性稳定性公平性最优性路由算法中的度量标准路径长度hop数延迟时间《ComputerNetworksv4》cs.sjtu2/24/2020第5章网络层19/290路由算法的分类静态算法自适应算法拓扑相关的路由算法移动节点的路由Ad-hoc网络的路由《ComputerNetworksv4》cs.sjtu2/24/2020第5章网络层20/290静态算法（staticrouting）最短路径算法（Dijkstra）扩散法（flooding）为路由器配置一张最优的路由表《ComputerNetworksv4》cs.sjtu2/24/2020第5章网络层21/290最短路由选择（Dijkstra）Dijkstra算法（1959）：通过用边的权值作为距离的度量来计算最短路径，有最少边数的路径不一定是最短路径1674329115328635如下图：5和4之间边数最少的路径是5234但最短路径是523674《ComputerNetworksv4》cs.sjtu2/24/2020第5章网络层22/290采用的数据结构集合S：尚未找到最短路径的节点的集合数组R：R[i]为从指定源点去节点i的路径上，节点i的前一个节点数组D：D[i]为从指定源点到节点i的最短距离《ComputerNetworksv4》cs.sjtu2/24/2020第5章网络层23/290算法的初始化初始化集合S为除源节点外的所有节点初始化数组D：如果从源节点到节点v的边存在，则D(v)为该边的权值，否则为无穷大初始化数组R：如果从源节点到节点v的边存在，则R(v)为源节点，否则为0《ComputerNetworksv4》cs.sjtu2/24/2020第5章网络层24/290算法WHILE（集合S非空）{从S中选一节点u，使D[u]最小；如果（D[u]为无穷大）{错误！无路径存在，退出}把u从S中删去；对(u,v)是边的每个节点v{如果（v仍在S中）C=D[u]+weight(u,v);如果（CD[v]）/*v找到了一条更短的路径*/{R[v]=u;/*替换v的最短路径及长度*/D[v]=C;}}}《ComputerNetworksv4》cs.sjtu2/24/2020第5章网络层25/290从5出发到各个节点的最短路径SR1D1R2D2R3D3R4D4R6D6R7D7u{1,2,3,4,6,7}59560∞0∞0∞0∞2{1,3,4,6,7}5956290∞2140∞1{3,4,6,7}5956290∞2140∞3{4,6,7}5956293203110∞6{4,7}5956293203116167{4}5956297193116164《ComputerNetworksv4》cs.sjtu2/24/2020第5章网络层26/290静态算法（staticrouting）最短路径算法（Dijkstra）扩散法（flooding）为路由器配置一张最优的路由表《ComputerNetworksv4》cs.sjtu2/24/2020第5章网络层27/290扩散法（flooding）不计算路径，有路就走1567432911532863如从5出发到4：数据包从51,2；23,6；36,4；63,7；74要解决的问题：数据包重复到达某一节点，如3，6《ComputerNetworksv4》cs.sjtu2/24/2020第5章网络层28/290扩散法（续）解决方法在数据包头设一计数器初值，每经过一个节点自动减1，计数值为0时，丢弃该数据包在每个节点上建立登记表，则数据包再次经过时丢弃缺点：重复数据包多，浪费带宽优点：可靠性高，路径最短，常用于军事《ComputerNetworksv4》cs.sjtu2/24/2020第5章网络层29/290路由算法的分类静态算法自适应算法拓扑相关的路由算法移动节点的路由Ad-hoc网络的路由《ComputerNetworksv4》cs.sjtu2/24/2020第5章网络层30/290自适应算法是动态的、分布式的算法实现分布式算法的三要素：Themeasurementprocess（测量）Theupdateprotocol（更新协议）Thecalculation（计算）自适应算法（adaptivealgorithm）《ComputerNetworksv4》cs.sjtu2/24/2020第5章网络层31/290自适应算法（adaptivealgorithm）距离矢量算法（D-V）链路状态算法（L-S）路由器动态建立和维护一张最优的路由表《ComputerNetworksv4》cs.sjtu2/24/2020第5章网络层32/290D-V算法的工作原理每个路由器用两个向量Di和Si来表示该点到网上所有节点的路径距离及其下一个节点相邻路由器之间交换路径信息各节点根据路径信息更新路由表《ComputerNetworksv4》cs.sjtu2/24/2020第5章网络层33/290di1：从节点i到节点1的时延向量di2：从节点i到节点2的时延向量Di=di1di2di3…dinSi=si1si2si3…sinsi1：从节点i到节点1的一条最小时延路径上的下一个节点si2：从节点i到节点2的一条最小时延路径上的下一个节点其中：n—网络中的节点数Di—节点i的时延向量dij—节点i到j的最小时延的当前估计值S