计算机网络课件第五章网络层新

第五章网络层第五章网络层5.1基本概念和提供的服务5.2路由算法5.3internet路由5.4Internet中的网络层5.1基本概念和提供的服务基本概念ISO给网络层的定义网络层为一个网络连接的两个传送实体间交换网络服务数据单元提供功能和规程的方法，它使传送实体独立于路由选择和交换的方式。网络层要解决的关键问题是了解通信子网的拓扑结构，选择路由。网络层的功能在收发主机之间传输分组网络层协议必须在每一台主机和路由器上实现三项重要功能:路径决策:为分组在收发双方之间确定路径，路由选择算法交换:在路由器的输入、输出端口传递分组建立连接:某些网络的体系结构要求在数据流经之前，在所经由的路由器中建立连接（callsetup）networkdatalinkphysicalnetworkdatalinkphysicalnetworkdatalinkphysicalnetworkdatalinkphysicalnetworkdatalinkphysicalnetworkdatalinkphysicalnetworkdatalinkphysicalnetworkdatalinkphysicalapplicationtransportnetworkdatalinkphysicalapplicationtransportnetworkdatalinkphysical虚电路在数据流动前，需要建立连接（callsetup）,流动结束后要断开（teardown）每个分组携带VC标识(而不是信宿主机的ID)每个在收发双方路径上的路由器需要为正在传输中的连接维持“状态”传输层的连接仅涉及到两个端系统（endsystem）链路,路由器资源(带宽,缓存等)可被分配给VC目的：为了达到类似线路交换的性能“使收发双方之间的路径表现得如同电话线路一般”网络内部有较多的智能和性能指标沿收发路径上的网络结点的操作比较复杂虚电路:信令协议（signalingprotocols）用来建立、维护、断开VC应用在ATM,帧中继,X.25（电信级服务）不是应用在今天的Internetapplicationtransportnetworkdatalinkphysicalapplicationtransportnetworkdatalinkphysical1.Initiatecall2.incomingcall3.Acceptcall4.Callconnected5.Dataflowbegins6.Receivedata数据报（Datagram）网络:因特网模型在网络层没有联接建立过程路由器:没有端对端的连接状态在网络层不存在“联接”的概念一般分组使用信宿主机的ID进行路由选择同样收发双方的不同分组可能经由的路径可能不同applicationtransportnetworkdatalinkphysicalapplicationtransportnetworkdatalinkphysical1.Senddata2.Receivedata数据报和虚电路比较数据报还是VC网络:why?因特网数据交换在计算机之间进行“弹性”服务,没有严格的实时性要求“聪明”的端系统(计算机)可进行自适应,执行控制,出错恢复网络内部比较简单,“边缘上”比较复杂利用了许多链路类型各具有不同的特性统一服务标准十分困难ATM电话网络演化而来人们的交流:严格要求实时性,和可靠需要服务承诺“傻瓜式”的端系统电话机复杂性在网络内部网络层的服务模型:网络体系结构InternetATMATMATMATM服务模型besteffortCBRVBRABRUBR带宽noneconstantrateguaranteedrateguaranteedminimumnone无损noyesyesnono有序noyesyesyesyes实时noyesyesnono拥塞反馈no(inferredvialoss)nocongestionnocongestionyesno承诺?Internet正在进化:Intserv,Diffserv5.2路由算法路由算法是网络层软件的一部分子网采用数据报，每个包都要做路由选择；子网采用虚电路，只需在建立连接时做一次路由选择。路由算法应具有的特性正确性（Correctness）简单性（Simplicity）健壮性（Robustness）稳定性（Stability）公平性（Fairness）最优性（Optimality）路由选择路由选择算法的图形抽象:图中的结点是路由器图中的线条为物理链路链路成本:延迟,￥费用,或拥塞的程度目标:在收发双方的通信过程中为分组（所经由的一系列路由器中）确定一条“好”的路径路由选择协议AEDCBF2213112535“好”路:一般为费用最低的路径也可以另行定义路由算法分类全局或分散的信息?全局:所有路由器都有完整的拓扑逻辑,链路成本信息“linkstate”算法分散:路由器只了解物理上邻接的路由器，了解到达这些路由器的链路成本通过迭代计算处理,可与相邻路由器交换信息“distancevector”算法静态或动态的?静态:路由变化较少的情况动态:路由变化较快的情况定期更新为了响应链路成本的变化介绍相关的路由算法最短路径算法（Dijkstra）扩散法(flooding)距离矢量算法链路状态算法最短路由选择Dijkstra算法（1959）：通过用边的权值作为距离的度量来计算最短路径，有最少边数的路径不一定是最短路径1674329115328635如下图：5和4之间边数最少的路径是5234但最短路径是523674最短路径路由算法（ShortestPathRouting）Dijkstra算法举例1243561225331152最短路径路由算法（ShortestPathRouting）Dijkstra算法举例)(vDv最短路径路由算法（ShortestPathRouting）Dijkstra算法举例最短路径路由算法（ShortestPathRouting）Dijkstra算法举例最短路径路由算法（ShortestPathRouting）Dijkstra算法举例最短通路树(汇集树)及对应路由表124356目的节点后继节点2234445464介绍相关的路由算法最短路径算法（Dijkstra）扩散法(flooding)距离矢量算法链路状态算法扩散法(flooding)不计算路径，有路就走1567432911532863如从5出发到4：数据包从51,2；23,6；36,4；63,7；74要解决的问题：数据包重复到达某一节点，如3，6扩散法（续）解决方法在数据包头设一计数器，每经过一个节点自动加1，达到规定值时，丢弃数据包在每个节点上建立登记表，则数据包再次经过时丢弃缺点：重复数据包多，浪费带宽优点：可靠性高，路径最短，常用于军事介绍相关的路由算法最短路径算法（Dijkstra）扩散法(flooding)距离矢量算法链路状态算法D-V（距离矢量）算法（DistanceVectorRouting）是动态、分布式算法。实现分布式算法的三要素：Themeasurementprocess（测量）Theupdateprotocol（更新邻接点距离矢量）Thecalculation（计算）D-V算法的工作原理每个路由器用两个向量Di和Si来表示该节点到网上所有节点的路径距离及其下一个节点相邻路由器之间交换路径信息各节点根据路径信息更新路由表di1：从节点i到节点1的时延向量di2：从节点i到节点2的时延向量Di=di1di2di3…dinSi=si1si2si3…sinsi1：从节点i到节点1的一条最小时延路径上的下一个节点si2：从节点i到节点2的一条最小时延路径上的下一个节点其中：n—网络中的节点数Di—节点i的时延向量dij—节点i到j的最小时延的当前估计值Si—节点i的后继节点向量sij—从节点i到j的最小时延路径上的下一节点路由表的更新dij=min(dix+dxj)(xA)（从i到j的时延取途经每个节点时的时延的最小值）Sij=x（从i到j途经的下一个节点为x）其中：A—与i相邻的所有节点的集合dij—i到j的最短距离dix—i到x的距离dxj—x到j的最短距离To通过A通过I通过H通过KA0242021B12363128C25181936D4027824E1473022F23201940G1831631H1720019I2101422J911710K2422220L293399J到A延时为8J到I延时为10J到H延时为12J到K延时为6线路8A20A28I20H17I30I18H12H10I0-6K15K节点J的新路由表AEIHGFDCBLKJJ重新估计的延时注意：AI为21；IA为24因为：节点A和I都是各自测得的距离，且不一定是同一时刻测得的，线路状态是动态变化的当前节点为JD-V算法的缺点交换的路径信息量大路径信息不一致收敛速度慢（坏消息）距离矢量中不考虑带宽因子不适合大型网络无穷计算问题好消息传播得快，坏消息传播得慢ABCDE∞∞∞∞初始时1∞∞∞第1次交换后12∞∞第2次交换后123∞第3次交换后1234第4次交换后ABCDE1234初始时3234第1次交换后3434第2次交换后5454第3次交换后5656第4次交换后7676第5次交换后7878第6次交换后…………∞∞∞∞A下网了克服收敛速度慢的方法水平分裂Holddown同距离矢量法，只是到X的距离并不是真正的距离，对下方点通知真正的距离，对上方点，给出无穷大如上图中的C点，它向D通知到A的真正距离，而向B通知到A的距离是无穷大当发现不通时，不重新选路径，而是把它设成无穷大介绍相关的路由算法最短路径算法（Dijkstra）扩散法(flooding)基于流量的路由选择距离矢量算法链路状态算法L-S（链路状态）算法（LinkStateRouting）基本思想发现它的邻接节点，并得到其网络地址测量它到各邻接节点的延迟或开销组装一个分组以告知它刚知道的所有信息将这个分组发给所有其他路由器计算到每个其他路由器的最短路径发现邻接节点当一个路由器启动后，向每个点到点线路发送HELLO分组，另一端的路由器发送回来一个应答来说明它是谁L-S（链路状态）算法（LinkStateRouting）基本思想发现它的邻接节点，并得到其网络地址测量它到各邻接节点的延迟或开销组装一个分组以告知它刚知道的所有信息将这个分组发给所有其他路由器计算到每个其他路由器的最短路径测量线路开销发送一个ECHO分组要求对方立即响应，通过测量一个来回时间再除以2，发送方就可以得到一个延迟估计值，想要更精确些，可以重复这一过程，取其平均值L-S（链路状态）算法（LinkStateRouting）基本思想发现它的邻接节点，并得到其网络地址测量它到各邻接节点的延迟或开销组装一个分组以告知它刚知道的所有信息将这个分组发给所有其他路由器计算到每个其他路由器的最短路径构造分组子网及其节点到其邻节点（路由器）的线路开销测量值（即延时，假设以ms计）ABCDEF序号序号序号序号序号序号年龄年龄年龄年龄年龄年龄B4A4B2C3A5B6E5C2D3F7C1D7F6E1F8E8AE324FDCB56187子网的链路、状态及分组情况：节点A仅与节点B和E相邻AB的时延为4msAE的时延为5msL-S（链路状态）算法（LinkStateRouting）基本思想发现它的邻接节点，并得到其网络地址测量它到各邻接节点的延迟或开销组装一个分组以告知它刚知道的所有信息将这个分组发给所有其他路由器计算到每个其他路由器的最短路径发布链路状态用扩散法（向邻接的节点）发布链路状态分组（以B为例，B的邻接点有A、C、F）源序号年