课件1计算机网络第11章

1、Chapter 11 Link-Level Flow and Error Control1第 11 章链路级流量及差错控制Chapter 11 Link-Level Flow and Error Control2流量控制和差错控制概述决定通信链路、网络及互联网性能的主要机制是流量控制和差错控制拥塞控制的基础是控制源端发送PDU的流量以及控制经过中间系统的PDU的流量差错控制技术与流量控制技术密切相关，其目的是将传输过程中丢失或出现拥塞时丢弃的PDU恢复过来可在好几个协议层次上实施：链路级, 网络级 (如X.25), 运输级或某些应用级协议建立流量/差错控制的性能分析模型极其困难Chapter

2、11 Link-Level Flow and Error Control3流量控制和差错控制概述(续)最简单的情况是链路控制协议：运行在由点到点链路连起来的两个设备之间，只需要考虑两台设备之间固定的传播时延、固定的数据率、差错概率，也许还有通信量的统计特性在处理网络或互联网络的流量及差错控制问题时，解析分析要复杂得多，要考虑的因素包括可变传播时延、可变数据率、进入网络的其他通信量源产生的拥塞的影响、动态选路决策的影响、多种逻辑连接之间的相对优先级以及其他因素Chapter 11 Link-Level Flow and Error Control4流量控制流量控制是一种使目的端实体可以调节源端实

3、体发出的PDU流量的机制，它限制数据发送的数量或速率目的端限制流量的目的：源端可能试图以比目的端可以处理的速率更快的速率发送PDU目的端的高层协议用户可能接受数据较慢(缓存被充满)，因而目的端可能需要限制源端的流量目的端可能将到来的数据缓存起来然后重新在另一个I/O端口上发送出去，它可能需要限制入流量以便与出流量相匹配Chapter 11 Link-Level Flow and Error Control5多个协议层次上的流量控制流量控制可以在多个协议级上实施，如多条X.25 虚电路复用到一条LAPB的数据链路上在高级别的逻辑连接上，每条逻辑连接上流量控制的实施是独立的，而所有高级连接上的通信

4、量总和又在低级别上受到进一步的流量控制Chapter 11 Link-Level Flow and Error Control6流量控制实施范围使流量控制研究更复杂的是它可能用于不同的场合，流量控制的协议级别与流量控制的实施范围之间存在一定的关系Chapter 11 Link-Level Flow and Error Control7流量控制实施范围(续)一跳的范围在两个直接连接的中间系统之间，流量控制可以在链路级实施如在两个邻近的分组交换结点之间使用LAPB，为了保证结点缓存不产生溢出，可以使用LAPB流量控制限制进入通信量的大小链路级流量控制也可以用在互联网中直接相连的两个路由器之间，路由

5、器可以使用HDLC之类的链路级协议限制进入数据报的数量以免缓存溢出Chapter 11 Link-Level Flow and Error Control8流量控制实施范围(续)网络接口链路级协议也常用在端系统与一个网络或互联网之间的接口链路上如在X.25分组交换网络中，LAPB使得网络可以限制端系统进入网络的分组流量流量控制也可以在穿过网络接口的网络协议层实施这种情况下，流量控制是针对各个逻辑连接分别实施的，如在X.25中，可在端系统与网络之间对每个单独的虚电路实施流量控制Chapter 11 Link-Level Flow and Error Control9流量控制实施范围(续)进网到出

6、网有些网络有一种进网到出网结点之间的逻辑连接(如虚电路)上实施的流量控制其目的是调节输入通信量以免在出网结点上缓存发生溢出这种机制的细节对端用户是透明的，但可以影响网络接口上的数据流Chapter 11 Link-Level Flow and Error Control10流量控制实施范围(续)端到端在端系统之间的逻辑连接上实施；其目的在于接收端系统调节入流量以避免缓存溢出并满足应用的要求，如TCP在端系统之间的各个TCP连接上提供这样的端到端流量控制，又如X.25网中在虚电路的基础上也可以实施端到端的流量控制也经常用于数据链路层，如LAN上运行的逻辑链路控制(LLC)就是在端系统之间实施的C

7、hapter 11 Link-Level Flow and Error Control11差错控制差错控制技术的用途是将信源与目的地之间传送的PDU的丢失或损坏恢复过来它包括基于FCS的差错检测以及PDU重传差错控制和流量控制通常在一个单一的机制中一起实现，这个机制调节PDU的流量并确定什么时候需要重传一个或多个PDU同流量控制一样，差错控制也可以在多种协议级别上实现Chapter 11 Link-Level Flow and Error Control12链路控制机制在链路级有3种常用的流量及差错控制技术:停止等待(Stop-and-wait)退N步(Go-back-N)拒选(Selecti

8、ve-reject)后两种是滑动窗技术的两个特例Chapter 11 Link-Level Flow and Error Control13几点假设假设两个端系统是由一条直接链路连接的源系统将报文分解成一系列帧进行发送，因为接收端的缓存大小可能有限传输越长，出错的可能性越大，而出错会引起整个帧重传，用较小的帧就可以更快地检测出差错，而需要重传的数据量也较小在共享媒体上(如LAN)，通常不允许一个站占据媒体过长的时间，以免造成其他发送站很长的时延Chapter 11 Link-Level Flow and Error Control14停止等待一个源端实体发送一个帧目的端实体收到后就发回一个对收

9、到帧的确认来表示它愿意接收另一帧源端在发送下一帧之前必须等待直到收到这一确认目的端因此仅仅通过不发确认就可以让数据流停下来Chapter 11 Link-Level Flow and Error Control15停止等待(续)考虑两类差错:到达目的端的帧损坏了 帧中包含FCS，接收端检测到差错就丢弃这一帧；源站设置一个定时器，发完一帧后就等待确认，如果定时器超时了还没有收到确认，就将同一帧再发一次，需要保留帧的副本到达源端的确认帧损坏了 源端超时重发，接收端收到同一帧的两个副本；为了避免这个问题，数据帧用0和1交替标记，而确认帧分为ACK0和ACK1两种：ACK0对收到编号为1的帧做出确认，

10、表示接收端准备接收编号为0的帧Chapter 11 Link-Level Flow and Error Control16停止等待ARQ自动重传请求，在所有链路级流量及差错控制技术中出现使用:差错检测定时器确认重传停止等待ARQChapter 11 Link-Level Flow and Error Control17Figure 11.3Chapter 11 Link-Level Flow and Error Control18停止等待的效率停止等待技术由于低效率很少得到实际应用低效率的根源是在一个时刻只能有一个正在传输的帧如果传播时延相对于传输时间很长，那么线路在大部分时间都是空闲的Cha

11、pter 11 Link-Level Flow and Error Control19Figure 11.4Chapter 11 Link-Level Flow and Error Control20停止等待的效率(续)这种情况下很明显线路的利用率不高假定不发生差错，A将能以1/Tframe的速率发送数据帧因为要等待确认，所以最大速率就降为1/(Tframe+2*Tprop+Tack)如果Tprop 相对于Tframe大得多，则吞吐量会降低很多Chapter 11 Link-Level Flow and Error Control21滑动窗技术通过允许多个帧同时传输以提高传输效率目的站分配了可

12、容纳n个帧的缓存空间，因此可以接受n个帧源站可以连续发送n个帧而不需要等待任何确认为了记录下来到底哪些帧已经被确认过了，每个帧都用一个序号做标记目的站确认一个帧的方式是发送一个包含它期望收到的下一帧的序号的确认(隐含地宣布它准备接收下面的从指定的号码开始的n个帧)这种方案可以用来确认多个帧(累积确认)Chapter 11 Link-Level Flow and Error Control22滑动窗技术(续)源站维护着一张允许发送的序号表，目的站维护着一张允许接收的序号表，这种表可认为是一个帧的窗口，故称为滑动窗流量控制序号要占帧中的一个字段，故其大小是有限的，对k bit字段，序号从0编到2k

13、-1滑动窗的工作过程(图11.5)对于一个给定的序号长度实际窗口大小不必等于其最大可能值例子：3 bit序号字段，7帧的最大窗口(图11.6)Chapter 11 Link-Level Flow and Error Control23Figure 11.5Chapter 11 Link-Level Flow and Error Control24Figure 11.6Chapter 11 Link-Level Flow and Error Control25Go-back-N ARQ链路控制协议中用到两种滑动窗技术：go-back-N ARQ和拒选ARQ，它们的差别在于处理差错的方式不同；其中

14、最常用的是前者一个站点可能发送一系列的帧，如果没有出差错，目的端就用一个RR帧确认来到的帧如果目的站收到一个出错的帧，就对此帧发送一个否认(REJ)，并将丢弃这一帧以及所有即将到来的帧，直到出错的帧被正确收到为止因此，源站收到一个REJ报文后，必须重传出错帧以及在此期间已发出的后续各帧Chapter 11 Link-Level Flow and Error Control26Go-back-N ARQ规则站A向站B发送帧，假定B已经成功收到帧(i-1)而A刚发送完帧i，则考虑下列意外事件：损坏的帧，则B丢弃该帧并且不采取其他行动一段时间内，A随后发送帧(i+1)，B收到失序的帧(i+1)并发送

15、一个REJ i，A必须重传帧i及所有后续帧随后一段时间A并没有发出更多的帧，B什么也没收到，它既不返回RR也不返回REJ。当A的定时器超时时，它传送一个RR帧，其中的P位置1(要求B必须确认)，B以RR i进行确认，A收到这个RR后就重传帧i；另外一种情况是当A的定时器超时时它也可能会重传帧iChapter 11 Link-Level Flow and Error Control27Go-back-N ARQ规则(续)2. 损坏的RR，B收到帧并发送RR(i+1)，但这个RR帧在传送过程中丢失了因为确认是累积的，所以A可能会收到后续的一个帧的RR，这个RR帧在与帧i相关的定时器超时前就到达了如

16、果A的定时器超时了，它就象在1b中那样发送一个RR命令，并设置P位定时器。如果B没能对RR命令做出反应，或它的响应损坏了，那么A的P位定时器就会超时，P位定时器超时后可以重发RR命令，这个过程可试多次，超过最大尝试次数后就启动一个复位过程3. REJ的损坏，同1b情形Chapter 11 Link-Level Flow and Error Control28Figure 11.7Chapter 11 Link-Level Flow and Error Control29拒选ARQ在拒选ARQ中，需要重传的只有那些收到否定应答(用SREJ表示)或那些超时的帧拒选看起来要比go-back-N效率更

17、高，因为它减少了重传的量但接收端必须维持一个足够大的缓存以便存放SREJ发过之后收到的各帧，直到出错的帧被重传；而且必须具有将收到的重传帧插入到正确位置的逻辑功能发送端也要求更复杂的逻辑功能以便能够不按顺序发送一个帧由于其复杂性，拒选远不如go-back-N用的广泛Chapter 11 Link-Level Flow and Error Control30ARQ的性能下面讨论点到点链路上使用ARQ技术的一些性能问题停止等待ARQ无差错停止等待有差错的停止等待ARQ定义一个重要参数a，它抓住了数据链路性能特征的本质，使用它可以简化对go-back-N和拒选性能的讨论滑动窗ARQ：无差错滑动窗流量

18、控制、拒选ARQ和go-back-N ARQChapter 11 Link-Level Flow and Error Control31无差错停止等待我们的目的是求出使用停止等待协议时一条线路上的最大帧发送速率，假定无差错发生从A到B以一系列定长帧F1,F2,Fn的形式发送一个长报文的过程如下：A发送F1，B发送一个确认A发送F2，B发送一个确认A发送Fn，B发送一个确认Chapter 11 Link-Level Flow and Error Control32发送数据的总时间可表达为nT，其中T是发送一个帧和收到一个确认并准备好发送下一个帧的时间T = Tframe + Tprop + Tp

19、roc + Tack + Tprop + Tproc其中：Tframe = 传送一帧的时间 Tprop = 两个站之间的传播时延 Tproc = 每个站对一个到来的事件做出反应的处理时延 Tack = 传送一个确认的时间假设处理时间可忽略，确认帧比数据帧小得多 T Tframe + 2TpropChapter 11 Link-Level Flow and Error Control33Figure 11.4Chapter 11 Link-Level Flow and Error Control34吞吐量 = 1/T = 1/(Tframe + 2Tprop) 帧/sec以链路数据率规格化: 1

20、/ Tframe 帧/sec S = 1/(Tframe + 2Tprop) = Tframe = 1 1/ Tframe Tframe + 2Tprop 1 + 2a这里 a = Tprop / TframeS就是使用停止等待技术的链路的最大可能归一化吞吐量，由于帧包含开销位，有效吞吐量只会更低如果Tprop和Tframe都是常数，则参数a就是一个常数；这个条件通常能够成立，因为通常除了一个序列中的最后一帧，其他帧都是固定长度的，而对于点到点的链路，传播时延是一个常量Chapter 11 Link-Level Flow and Error Control35有差错的停止等待ARQ如前，成功发

21、送一帧的时间是(Tframe + 2Tprop)如果一个帧丢失或它的ACK丢失，并假设传送成功需两次传输，则帧的传输时间为 T= Tframe + Timeout + Tframe + 2Tprop假定超时时间值等于两倍的传播时延值，则 T=2(Tframe + 2Tprop)定义Nx是每个帧需要传输的平均次数，那么 T=Nx(Tframe + 2Tprop)归一化吞吐量：S = 1 Nx (1 + 2a)Chapter 11 Link-Level Flow and Error Control36设P = 单个帧出错的概率，并假定ACK从不出错，则于是得到有差错停止等待的吞吐量： Chapte

22、r 11 Link-Level Flow and Error Control37参数aa = 传播时间 = d/V = Rd 传输时间 L/R VL 这里：d = 两站间链路的距离 V = 信号沿链路传播的速度 L = 帧的长度，以位计 R = 链路的数据率，单位是bpsa在评价各种链路控制方案的性能方面很有用，它对影响性能的各种因素提供了深刻的解释对于固定长度的帧，a与数据率乘以媒体长度成正比；看待a的一种有用的方式是将它看做代表了以位计数的媒体长度与帧长的比率Chapter 11 Link-Level Flow and Error Control38Chapter 11 Link-Leve

23、l Flow and Error Control39几个例子ATM广域网：两个站之间的距离是1000 km；标准ATM信元大小为424 bit；标准数据率155.52 Mbps；光纤的传播速度2*108 m/s 可以求得a=1850，归一化吞吐量只有0.00027LAN：距离从0.1 km到10 km，数据率从10 Mbps到1 Gbps，假定V= 2*108 m/s；帧大小是1000 bit，数据率为10 Mbps a为0.005-0.5，而吞吐量在0.5-0.991之间；对于100 Mbps的LAN，可以得到差不多的利用率可以看到LAN通常效率相当高，而高速广域网则效率不高Chapter

24、11 Link-Level Flow and Error Control40几个例子(续)通过Modem在话音质量的线路上进行的数字数据传输：通常的数据率为28.8 kbps，仍然考虑1000 bit的帧长，链路距离可以从几十m到几千km，如果选取距离d=1000 m，可求出a为1.44*10-4，而归一化吞吐量约等于1；即使选取d=5000km，可求出a为0.72，归一化吞吐量为0.4表11.1列出a的若干取值ISDN的64 kbps链路帧中继网络链路LAN链路Chapter 11 Link-Level Flow and Error Control41Table 11.1Chapter 11

25、 Link-Level Flow and Error Control42停止等待再讨论在数据率很高和发送端与接收端距离很远的情况下，停止等待流量控制的线路利用率不高为了观察a对于归一化吞吐量的影响，可以将S=(1-P)/(1+2a)画出来虽然S的值依赖于P，但P在很宽的取值范围里对结果都没有太大影响，我们随便选取P=10-3从图中看到：当a1时，吞吐量严重降低；当a10时，停止等待的效率如此之低，以至于它变得没有什么用途Chapter 11 Link-Level Flow and Error Control43Figure 11.9Chapter 11 Link-Level Flow and

26、Error Control44无差错滑动窗ARQ对于滑动窗流量控制来说，线路的吞吐量取决于窗口的大小W和a的值将帧传输时间归一化为1，故传播时延就是a情况 1: W 2a + 1对帧1的确认在A消耗完其窗口前就到达了A，因此A可以不停地连续传输，而归一化吞吐量是1情况 2: W 2a +1A 在t = W 时刻就耗尽了它的窗口，因此直到t = 2a + 1时刻前都不能再发送帧Chapter 11 Link-Level Flow and Error Control45Figure 11.10Chapter 11 Link-Level Flow and Error Control46规格化吞吐量

27、1 W 2a + 1 S = W W 2a +1 2a + 1 Chapter 11 Link-Level Flow and Error Control47滑动窗吞吐量与a的关系通常序号是用一个n位字段提供的，这时最大窗口大小是W=2n-1图11.11示出了窗口大小是1，7和127时最大吞吐量与a的关系W=1对应于停止等待W=7对于许多应用就足够了W=127可用于较大的a值(如高速广域网的情况)Chapter 11 Link-Level Flow and Error Control48Figure 11.11Chapter 11 Link-Level Flow and Error Contro

28、l49拒选ARQ对于拒选ARQ，可以使用在停止等待ARQ上使用的相同的推导，即，将无差错的方程式除以Nx，而且仍有Nx=1/(1-P) 1 - P W 2a + 1 S = W(1 - P) W 2a +1 2a + 1 Chapter 11 Link-Level Flow and Error Control50Go-Back-N ARQ使用类似的推导，但在计算Nx的近似值时有所不同，每个差错都要求重传K帧而不是仅仅一帧，因此其中f(i)是如果原来的帧必须传输i次所传输的总帧数，为：f(i)=1+(i-1)K=(1-K)+KiChapter 11 Link-Level Flow and Error Control51Go-Back-N ARQ(续)由上面公式代换得到：研究图11.10，可以得到：Chapter 11 Link-Level Flow and Error Control52Chapter 11 Link-Level Flow and Error Control53Go-Back-N ARQ(续) 1 - P W 2a + 1 S = 1 + 2aP W(1 - P)