计算机网络第5章课件

第五章.网络层5.1 网络层概述5.2 路由算法5.2.1 最优化原则5.2.2 最短路径路由算法5.2.3 洪泛算法5.2.5 距离向量路由算法5.2.6 链路状态路由算法5.2.7 分层路由第五章.网络层5.3 拥塞控制算法5.3.1 拥塞控制的基本原理5.3.2 拥塞控制算法5.5 INTERNET网络层协议

5.5.1IP协议

5.5.2Internet控制协议

回顾CSMA以太网网络设备。。。5.1 网络层概述ISO定义网络层为一个网络连接的两个传送实体间交换网络服务数据单元提供功能和规程的方法，它使传送实体独立于路由选择和交换的方式。网络层是处理端到端传输的最低层。网络层要解决的关键问题是了解通信子网的拓扑结构，选择路由。LAN与WAN中网络层功能上的差别●LAN中的网络功能有限○在LAN中，使用广播信道，相邻节点与源-目标节点的通信没有区别。○在LAN中，将流量控制功能,差错控制功能和网络互联等功能一般放入DL层，所以网络层功能没有必要或很弱。●WAN中的网络功能强大○WAN使用点-点信道,单独设立一层解决END-END数据传输问题，所以网络层功能强大。网络层的地位位于数据链路层和传输层之间，使用数据链路层提供的服务，为传输层提供服务；通信子网的最高层；处理端到端传输的最低层。网络层的作用屏蔽各种不同类型网络之间的差异，实现互连了解通信子网的拓扑结构，选择路由，实现报文的网络传输5.1 网络层概述网络层设计的有关问题为传输层提供服务面向连接服务传统电信的观点：通信子网应该提供可靠的、面向连接的服务。无连接服务

Internet的观点：通信子网无论怎么设计都是不可靠的，因此网络层只需提供无连接服务。无连接服务:主机在传输数据之前无需建立连接,主机有数据就交给网络层,网络层实体直接发送出去，每一个分组独立选择路由,由上层进行排序和流控。applicationtransportnetworkdatalinkphysicalapplicationtransportnetworkdatalinkphysical1.Senddata2.ReceivedataConnectionlessService无连接服务理由：●不管如何设计,网络层所提供的服务都是不可靠的，与其在网络层和传输层做两遍可靠性的工作，不如在网络层放弃可靠性的工作，只在传输层做差错控制和流量控制等可靠性工作。●用户的计算机已有足够的能力处理复杂的可靠性的工作，在用户计算机中安装复杂的传输层的软件是可以接受的。●将可靠性的工作放在网络层可能会导致子网所提供的服务昂贵。ConnectionlessServiceConnection-OrientedService面向连接服务通信过程：1、在主机通信之前,双方应建立起连接2、在建立起的连接上进行数据的传递3、传输完毕,拆除连接applicationtransportnetworkdatalinkphysicalapplicationtransportnetworkdatalinkphysical1.Initiatecall2.incomingcall3.Acceptcall4.Callconnected5.Dataflowbegins6.ReceivedataConnection-OrientedService面向连接服务理由:1、在网络层提供面向连接的通信是具备电信背景的集团提出的，子网应该提供可靠的,面向连接的服务。2、用户对在计算机中装配复杂的传输层软件可能不感兴趣。3、网络层所提供的服务是面向连接的可靠的服务，减少了用户主机的复杂性。网络层的两种实现方式：数据报和虚电路都属于分组交换，采用存储转发机制。数据报(datagram)：每个分组被单独路由，分组带有全网唯一的地址虚电路(virtualcircuit)：先在源端和目的端之间建立一条虚电路，所有分组沿虚电路按次序存储转发，最后拆除虚电路。在虚电路中，每个分组无须进行路径选择。数据报：ImplementationofConnectionlessServiceFigure5-2.Routingwithinadatagramsubnet.虚电路：ImplementationofConnection-OrientedServiceFigure5-3.Routingwithinavirtual-circuitsubnet.labelswitching5.1 网络层概述网络层提供的服务虚电路子网与数据报子网的比较路由器内存空间与带宽的权衡虚电路方式，路由器需要维护虚电路的状态信息；数据报方式，每个数据报都携带完整的目的/源地址，浪费带宽连接建立时间与地址查找时间的权衡虚电路需要在建立连接时花费时间数据报则在每次路由时过程复杂服务质量与可靠性的权衡虚电路方式很容易保证服务质量QoS(QualityofService)，适用于实时操作，但比较脆弱。数据报不太容易保证服务质量，但是对于通信线路的故障，适应性很强。

面向连接和无连接服务之争本质:将可靠性的功能放置于何层的问题●面向连接的服务:放置在网络层●无连接的服务:放置在传输层5.2路由算法Mainissue:Routersthatconstitutethenetworklayerofanetwork,shouldcooperatetofindthebestroutes

betweenallpairsofstations.●路由:按照某种指标(传输延迟,所经过的站点数目等)找到一条从源节点到目标节点的较好路径●较好路径:按照某种指标较小的路径●路由的时机：○虚电路:在建立虚电路时使用○数据报:每个分组独立路由5.2路由算法●路由算法：指管理路由表并作出路由选择的算法。①非自适应算法：不会根据当前测量或者估计的流量和拓扑结构，来调整它们的路由决策，所有的路由选择是预先在离线情况下计算好的，在网络启动的时候被下载到路由器中，所以又称这种算法是静态路由。②自适应算法：随拓扑结构和流量的变化和而改变它们的路由决策，又称这种算法是动态路由。5.2路由算法路由选择算法的原则:●正确性(correctness):算法必须是正确的和完整的,使分组一站一站接力，正确发向目标站；完整：目标所有的站地址，在路由表中都能找到相应的表项；没有处理不了的目标站地址；●简单性(simplicity):算法在计算机上应简单；最优但复杂的算法，时间上延迟很大，不实用，不应为了获取路由信息增加很多的通信量；5.2路由算法●稳定性(stability)：产生的路由不应该摇摆●公平性(fairness)：对每一个站点都公平●最优性(optimality)：某一个指标的最优，时间上，费用上等指标，或综合指标；实际上，获取最优的结果代价较高，可以选择次优的●健壮性(robustness):算法应能适应通信量和网络拓扑的变化。通信量变化，网络拓扑的变化算法能很快适应；不向很拥挤的链路发数据，不向断了的链路发送数据；路由选择算法的原则:5.2.1最优化原则最优化原则：已知I到K的最优路径,如果节点J在这条路径上,则这条路径上从J到K的路径也一定是最优路径证明:如果从J到K还存在一条其它路径,则也存在一条从I到K的最优路径,与前提矛盾IJK5.2.1最优化原则汇集树(sinktree)●一个节点的汇集树指的是:所有其它节点到此节点的最优路径形成的树●路由选择算法就是为所有路由器找到并使用汇集树Figure5-6.(a)Asubnet.(b)AsinktreeforrouterB.5.2.2最短路径路由算法●属于静态路由选择算法●路由算法的图形抽象○节点表示路由器○边用于表示路由器之间的链路○链路的代价(linkcost):表示链路上的距离、信道带宽、通信开销、延迟,队列平均长度等参数。5.2.2最短路径路由算法●最优的指标:○路由指按照某种指标寻找出从源站点到目标站点的较好路径。○指标:站数,延迟,开销,队列长度等,或者是一些单纯指标的加权平均。○采用什么样的指标,表示网络使用者希望网络在什么方面表现突出,什么指标网络使用者比较重视。5.2.2最短路径路由算法配置最短路由选择算法的路由器的工作过程●各点通过各种渠道获得整个网络拓扑,网络中所有链路代价等信息。●使用最短路由算法,计算本站点到其它站点的最优路径(汇集树),得到路由表。●按照此路由表转发分组(datagram方式)或建立VC。获得网络拓扑和链路代价信息使用此路由表使用最短路由算法得到路由表5.2.2最短路径路由算法最短路由选择算法的工作原理:●节点标记:每一个节点使用从源节点出发经过已知的最优路径到达本节点的距离,和前序节点来标注:(2,A) ●临时节点(tentativenode):还没有找到从源节点到此节点的最优路径的节点●永久节点(permanentnode):已经找到了从源节点到此节点的最优路径的节点5.2.2最短路径路由算法最短路由选择算法的工作原理●初始化○除了源节点外,所有节点都为临时节点○节点代价除了与源节点代价相邻的节点外,都为INF(infinite)●从所有临时节点中找到一个节点代价最小的临时节点,将之变成永久节点(当前节点,currentnode)W●对于永久节点的所有相邻节点V,如果D(v)>D(w)+c(w,v),则重新标注此节点,(D(W)+C(W,V),W)●开始一个新的循环

5.2.2最短路径路由算法Figure5-5.ThefirstfivestepsusedincomputingtheshortestpathfromAtoD.Thearrowsindicatetheworkingnode.TestTheshortestpathfromAtoG5.2.3洪泛算法工作原理:路由器从一条线路中收到分组,将此分组向所有其它线路发送出去属于静态路由选择算法问题在网络中将产生大量的重复分组解决办法:方法1:计数器法,在分组中设置计数器字段,每经过一个路由器,该计数器减1,如果计数器值为0,则抛弃该分组5.2.3洪泛算法选择性洪泛算法（selectiveflooding）洪泛法的一种改进。将进来的每个包仅发送到与正确方向接近的线路上。应用情况对路由器和线路的资源过于浪费，实际很少直接采用；具有极好的健壮性，可用于军事应用；作为衡量标准评价其它路由算法。5.2.4距离矢量路由算法●Basicidea:●动态路由选择算法○各路由器维护一张路由表,给出了到每个目的地的已知的最佳距离和路线（表项的两部分）○各路由器与相邻路由器交换路由表○根据获得的路由信息,更新路由表ToNextdelayAZ14…………5.2.4距离矢量路由算法Figure5-9.(a)Asubnet.(b)InputfromA,I,H,K,andthenewroutingtableforJ.5.2.4距离矢量路由算法举例网络拓扑以节点J为例,相邻节点A,I,H,KJ测得到A,I,H,K的延迟为8ms,10ms,12ms,6ms从A,I,H,K获得到它们到G的延迟为18ms,31ms,6ms,31ms因此从J经过A,I,H,K到G的延迟为26ms,41ms,18ms,37ms将到G的路由表项更新为18ms,下一个节点经过H5.2.4距离矢量路由算法无限计算问题俗话说：“好事不出门，坏事传千里”。而这里是好消息传播非常快，对坏消息却是反应迟钝。Figure5-10.Thecount-to-infinityproblem.5.2.4距离矢量路由算法假设A停机：1，首先是B，C告诉它有到A的长度为2的路径，故为3。2，C注意到它的邻居B有到A的长度为3的路径，更新，故为4。3，B和D都收到C的消息：“到A的长度为2的路径”，故都更新，故为54，通过逐步交换下去，得到余下的记录历史。5.2.5链路状态路由算法链路状态路由算法（LinkStateRouting）距离向量路由算法的主要问题选择路由时，没有考虑线路带宽；路由收敛速度慢。链路状态路由算法发现邻居结点，并学习它们的网络地址；路由器启动后，通过发送HELLO包发现邻居结点；两个或多个路由器连在一个LAN时,引入人工结点；5.2.5链路状态路由算法测量到每个邻居结点的延迟或开销；一种直接的方法是：发送一个要对方立即响应的ECHO包，来回时间除以2即为延迟。将所有学习到的内容封装成一个包；包以发送方的标识符开头，后面是序号、年龄和一个邻居结点列表；列表中对应每个邻居结点，都有发送方到它们的延迟或开销；链路状态包定期创建或发生重大事件时创建。组装一个分组,描述相邻节点的情况发送者名称;序号;年龄列表:给出它相邻节点,和它到相邻节点的延迟链路状态定期创建或发生重大事件时创建5.2.5链路状态路由算法将这个包发送给所有其它路由器；基本思想：洪泛链路状态包，为控制洪泛，每个包包含一个序号，每次发送新包时加1。路由器记录信息对(源路由器，序号)，当一个链路状态包到达时，若是新的，则分发；若是重复的，则丢弃；若序号比路由器记录中的最大序号小，则认为过时而丢弃；改进序号循环使用会混淆，解决办法：使用32位序号；路由器崩溃后，序号重置；序号出错；5.2.5链路状态路由算法第二、三问题的解决办法：增加年龄（age）域，每秒钟年龄减1，为零则丢弃。链路状态包到达后，延迟一段时间，并与其它已到达的来自同一路由器的链路状态包比较序号，丢弃重复包，保留新包；链路状态包需要应答；计算到每个其它路由器的最短路径。根据Dijkstra算法计算最短路径；实用协议OSPFIS-IS5.2.6HierarchicalRouting▲分级的必要性当网络数目比较多时,路由表的项目就多路由表的扫描,发布和计算路由代价比较高▲类似于电话网络5.2.6分层路由●二级网络将整个网络分成区域(region)区域内部路由器知道到本区所有其它路由器的路由,不知道其它区域内部的结构但知道到其它区域的路由大大减少了路由表中的项目数5.2.6分层路由多级网络区域（regions）、簇（clusters）、区（zones）和组（groups）…一个例子:不分级,1A的路由表要有17表项分两级,到其它区域的路由信息被压缩成了1项,路由表有7表项分级的代价增加了有些路径的长度习题3.Datagramsubnetsrouteeachpacketasaseparateunit,independentofallothers.Virtual-circuitsubnetsdonothavetodothis,sinceeachdatapacketfollowsapredeterminedroute.Doesthisobservationmeanthatvirtual-circuitsubnetsdonotneedthecapabilitytorouteisolatedpacketsfromanarbitrarysourcetoanarbitrarydestination?Explainyouranswer.习题9.ConsiderthesubnetofFig.5-13(a).Distancevectorroutingisused,andthefollowingvectorshavejustcomeintorouterC:fromB:(5,0,8,12,6,2);fromD:(16,12,6,0,9,10);andfromE:(7,6,3,9,0,4).ThemeasureddelaystoB,D,andE,are6,3,and5,respectively.WhatisC'snewroutingtable?Giveboththeoutgoinglinetouseandtheexpecteddelay.5.3 拥塞控制算法拥塞（congestion）网络上有太多的包时，性能会下降，这种情况称为拥塞。拥塞产生的原因多个输入对应一个输出；慢速处理器；低带宽线路。解决办法针对某个因素的解决方案，只能对提高网络性能起到一点点好处，甚至可能仅仅是转移了影响性能的瓶颈；需要全面考虑各个因素。5.3 拥塞控制算法拥塞控制与流量控制的差别拥塞控制（congestioncontrol）需要确保通信子网能够承载用户提交的通信量，是一个全局性问题，涉及主机、路由器等很多因素；流量控制（flowcontrol）与点到点的通信量有关，主要解决快速发送方与慢速接收方的问题，是局部问题，一般都是基于反馈进行控制的。5.3 拥塞控制算法5.3.1 拥塞控制的基本原理根据控制论，拥塞控制方法分为两类开环控制通过好的设计来解决问题，避免拥塞发生；拥塞控制时，不考虑网络当前状态。闭环控制基于反馈机制；工作过程监控系统，发现何时何地发生拥塞； 把发生拥塞的消息传给能采取动作的站点调整系统操作，解决问题。5.3 拥塞控制算法衡量网络是否拥塞的参数缺乏缓冲区造成的丢包率；平均队列长度；超时重传的包的数目；平均包延迟；包延迟变化（Jitter）。反馈方法向负载发生源发送一个告警包；包结构中保留一个位或域用来表示发生拥塞，一旦发生拥塞，路由器将所有的输出包置位，向邻居告警；主机或路由器主动地、周期性地发送探报（probe），查询是否发生拥塞。5.3 拥塞控制算法5.3.2 拥塞控制算法拥塞预防策略开环控制影响拥塞的网络设计策略5.3 拥塞控制算法流量整形（TrafficShaping）开环控制基本思想造成拥塞的主要原因是网络流量通常是突发性的；强迫包以一种可预测的速率发送；在ATM网中广泛使用。5.3 拥塞控制算法漏桶算法（TheLeakyBucketAlgorithm）将用户发出的不平滑的数据包流转变成网络中平滑的数据包流；可用于固定包长的协议，如ATM；也可用于可变包长的协议，如IP，使用字节计数；无论负载突发性如何，漏桶算法强迫输出按平均速率进行，不灵活。5.3 拥塞控制算法令牌桶算法（TheTokenBucketAlgorithm）漏桶算法不够灵活，因此加入令牌机制；基本思想：漏桶存放令牌，每T秒产生一个令牌，令牌累积到超过漏桶上界时就不再增加。包传输之前必须获得一个令牌，传输之后删除该令牌；5.3 拥塞控制算法漏桶算法与令牌桶算法的区别流量整形策略不同：漏桶算法不允许空闲主机积累发送权，以便以后发送大的突发数据；令牌桶算法允许，最大为桶的大小。漏桶中存放的是数据包，桶满了丢弃数据包；令牌桶中存放的是令牌，桶满了丢弃令牌，不丢弃数据包。5.5网络互联Figure5-42.Acollectionofinterconnectednetworks.5.5.2网络如何互联Figure5-44.(a)TwoEthernetsconnectedbyaswitch.(b)TwoEthernetsconnectedbyrouters.5.6Internet网络层协议5.6.1IP协议5.6.2IP地址5.6.3Internet控制协议5.6.1IP协议Version:协议的版本号； IHL:表明标头的长度；Typeofservice:服务类型; Totallength:标头以及数据；Identification:数据报的序列号； DF：分段标志；5.6.1TheIPProtocolMF：最后段标志； Fragmentoffset：分段在数据报的位置；Timetolive：用来计算包的存活期的计数器；Protocol：协议； Headerchecksum：用于校验包头；5.6.1TheIPProtocol5.6.2IPAddressesIP地址（IPAddress）地址组成：网络号+主机号；地址分类:1.掌握给出一个IP地址，能指出是那类地址。2.构成。3.每类地址最大网络数和最大主机数。5.6.2IP地址▲点分十进制表示法每字节用1个0-255的整数表示字节之间使用点隔离223.1.1.1=11011111000000010000000100000001223111DF010101特殊的IP地址Figure5-56.SpecialIPaddresses.一般约定：(0表示所有比特位全为0，-1表示所有比特位全为1)网络号为0---本网络主机号为0---本主机主机号为-1---广播地址，网络中的所有主机子网子网（Subnets）分而治之的思想：为了便于管理和使用，可以将网络分成若干供内部使用的部分，称为子网。对外界，该网络还是一个单独的网络。子网●

子网掩码子网的位数由各个单位确定，如何在IP地址中区分哪些是网络号，哪些主机号。Subnetmask:32Bits，1和0组成，1表示IP地址所在的位为网络号或子网号，0表示IP地址所在的位为主机号。上例：将16位主机号分成6位子网号，10位主机号。(255.255.252/22)不划分子网的网络的子网掩码：A：255.0.0.0B：255.255.0.0C：255.255.255.0子网●未划分子网路由器对分组的转发到本网络的主机，路由器直接发送。到其它网络的IP分组，路由器知道去该网络的下一跳IP地址，将整个网络压缩成一条记录(层次路由)。如果一个分组IP地址，路由器不知道关于它的信息，将这个分组发向默认表项的下一跳。网络号主机号下一跳(interface)本网络主机直接其它网络任何yDefaultz子网划分子网路由器对分组的转发到本子网络的主机，路由器直接发送到本网络的其它子网的IP分组，路由器知道去该网络的下一跳IP地址，将整个子网压缩成一条记录(层次路由)到其它网络的IP分组，路由器知道去该网络的下一跳IP地址，将整个网络压缩成一条记录(层次路由)网络号子网号主机号下一跳(interface)本网络本子网某主机直接本网络其它子网任何Y其它网络任何任何ZDefaultwDESMaskNextinterface150.1.1.0255.255.255.0-150.1.1.4150.1.2.0255.255.255.0-150.1.2.9150.1.3.0255.255.255.0-150.1.3.27DESMaskNext150.1.0.0255.255.0.0123.1.1.3……150.1.1.1150.1.1.2150.1.1.3150.1.1.4150.1.2.9150.1.2.2150.1.2.1150.1.3.2150.1.3.1150.1.3.27123.1.1.3123.1.1.4ExampleNAT—NetworkAddressTranslationReason:IPaddressesarescarce.Solution:(1)IPv6(2)DHCP(3)NATThebasicidea:assigneachcompanyasingleIPaddressforInternettraffic.Withinthecompany,everycomputergetsauniqueIPaddress,whichisusedforroutingintramuraltraffic.However,whenapacketexitsthecompanyandgoestotheISP,anaddresstranslationtakesplace.NAT10.0.0.0–10.255.255.255/8(16,777,216hosts)172.16.0.0–172.31.255.255/12(1,048,576hosts)192.168.0.0–192.168.255.255/16(65,536hosts)ThreerangesofIPaddresseshavebeendeclaredasprivate：NATExample:Whenaconnectionissetupfromaddress10.0.0.1,portX,theroutersendsitoffusingsourceaddress198.60.42.12(it’sISP-suppliedaddress)onportY,andregistersthemappingX<－>Y.WhenareplycomesinforportY,itissentbackto10.0.0.1onportX.5.6.3Internet控制协议ICMP(InternetControlMessageProtocol)ICMP和IP的关系ICMP使用IP协议传输ICMP报文，ICMP报文被封装在IP数据报中；ICMP协议和IP协议同处于一个互联网层ICMP报文的格式5.6.3Internet控制协议ARP(AddressResolutionProtocol)ARP的必要性DL层是不理解IP地址的，它只能够按照MAC地址来发送和接收帧IP层将IP分组交给DL层，同时还应该给出该目标IP地址所对应的MAC地址，只有这样DL层才能够顺利地将IP分组封装成帧传送出去如何进行IP地址和MAC地址的翻译—ARP5.6.3Internet控制协议ARP(AddressResolutionProtocol)ARP的目的：