下载掌阅APP，畅读海量书库
立即打开
流量(flow)即计算机网络中的通信量(traffic)，是指网络中的报文流或分组流。流量控制这一术语目前还没有统一的确切定义。一些文献提出，流量控制应当包括通信量控制、拥塞控制、路由控制和迟延控制这几部分内容，这里流量控制是总称。但有的文献则将流量控制局限为“收端控制发端的发送数据速率，以及使收端来得及接收，并且使网络不致过载”，而把流量控制、拥塞控制和死锁避免等合在一起，称为通信量控制。在阅读各种文献时应加以注意。本书采用后一种定义，这既是流量控制的目标，也是流量控制的直接原因。其根本原因是，由于我们无法预测并行执行的两个进程的运行和处理速度，这就要求我们采取一定的措施来保证发送方和接收方之间传输速率的同步。
流量控制是很多通信协议中要涉及的一个很重要的问题。本节主要介绍现有的各种流量控制技术的基本原理。
我们先看看有关数据传输的两个理想化的假定：
假定1：链路是理想的传输信道，所传送的任何数据既不会出差错也不会丢失。
假定2：不管发方以多快的速率发送数据，收方总是来得及收下，并及时上交主机。
假定1主要针对前面介绍的差错控制技术，在这样的假定下，传输协议无须进行差错控制。假定2相当于认为：收方接收缓冲区的容量为无限大而永远不会溢出，或者接收速率与发送速率绝对精确相等，在这样的假定下，当然不需进行任何流量控制即可保证数据不会因发方发得太快而导致数据丢失的情况发生。
实际情况当然不是这样的。其一，没有任何一个处理结点有无限的缓冲区；其二，在不加任何控制的情况下要保证发方和收方间传输速率的精确同步是很难的。因此，如果不加以限制，当收方接收并处理发方发送数据的速率略低于发方发送数据的速率时，收方就需要在缓冲区中暂时存放来不及处理的数据帧，缓冲区中的数据帧累积到一定程度后就会造成缓冲区溢出和数据帧丢失。
为了使收方的接收缓冲区在任何情况下都不会溢出，最简单的情况是发方每发送一帧就暂时停下来。收方收到数据帧后就交付给主机，然后发一信息给发方，表示接收的任务已经完成。这时，发方才再发送下一个数据帧。在这种情况下，收方的接收缓冲区的大小只要能够装得下一个数据帧即可。显然，用这样的方法收发双方能够同步得很好，发方发送数据的流量受收方的控制。这就是“停止等待”的流量控制思想，著名的“停等协议(Stop and Wait)”就是采用这种思想来进行流量控制的，该协议的详细情况见参考文献[19]。
在上述协议的控制之下（由收方控制发方发送速率），发方每发完一帧就必须停下来，等待收方的信息，这种“停止等待”使得通信链路在大部分时间内是空闲的，因此协议的传输效率比较低。为了解决传输效率问题，有必要对此进行改进。
本节介绍一种在早期使用的流量控制协议，称为X-on/X-off协议，其原理如下。
发送方连续发送报文，直到收到接收方发来的暂停发送报文(suspend)才停止；发送方重新开始发送的条件是收到接收方发来一个恢复发送报文(resume)。也可将suspend报文称为X-off报文，将resume报文称为X-on报文，X-on/X-off协议因此而得名。接收方设置一个计数器(counter)，每收到一个报文将counter加1，当counter的值大于某一门限值时向发送方发送一个Suspend报文；接收方每处理完一个报文将counter减1，当counter的值小于某一门限值时向发送方发送一个resume报文。
X-on/X-off协议是否能正确运行取决于传输信道的质量。如果suspend报文丢失或延迟到达发送方，仍有可能导致接收方缓冲区溢出。更严重的问题是，如果resume报文丢失将导致发送方处于停止状态。因此，假定1是X-on/X-off协议正确运行的前提条件。同停止等待相比，X-on/X-off协议的运行效率要高一些。
为了提高协议的传输效率，发送端必须尽可能地连续发送数据（单位为帧、分组或字节，下面的讨论以帧为例）。但是，在一个非理想的传输信道（数据有可能出错、丢失）上，以及没有无限接收能力的接收端的情况下，由于信息有可能出错和丢失，因此发送端必须在收到接收端返回的确认后才知道所发送的信息是否已成功到达接收端。如果发送端一直没有收到对方的确认信息，那么实际上发送端并不能无限制地发送其数据。这是因为：
（1）当未被确认的数据的数目太多时，存在两个严重的问题。一方面，只要有一帧出了差错，就可能要有很多的数据帧需要重传，这必然要白白花费较多的时间，因而增大了开销，还有可能加重网络的拥塞程度。另一方面，由于在没有收到确认之前，发送方需要缓存所有发送出去但未收到确认的数据。如果未被确认的数据的数目太多时，需要占用大量的缓存。
（2）为了对所发送出去的大量数据帧进行编号，每个数据帧的发送序号也要占用较多的比特数，这样又增加了一些不必要的开销。
（3）发送端的发送速率一旦超出了接收端的接收能力，则接收端就会将来不及接收的数据丢弃，连续发送就有可能导致更多的数据需要重传，出现与帧出错时一样的后果。
因此，应当将已发送出去但未被确认的数据的数目加以限制。这就是本节 滑动窗口 (slide window)所要研究的内容。
在滑动窗口协议中，对每一个要发送的帧进行编号，编号范围是从零到某个最大值。最大值通常是2n - 1。在每一个帧中，设有一个序列号字段，字段长度为n比特。在最简单的滑动窗口协议，即停止等待协议中，n = 1，因为只需用到0和1两个序列号。但是在复杂的协议中，则使用任意n值。
在滑动窗口协议中，设置两个窗口：发送窗口(sending window)和接收窗口(receiving window)。发送窗口用来对发送端进行流量控制，而发送窗口的大小WT就代表在还没有收到对方确认信息的情况下发送端最多可以发送多少个数据帧。在任何时刻，发送端都保持着一组序列号，对应于允许发送的帧，这些帧落在发送窗口之内。同样，在接收端也要维护一个接收窗口，对应于一组允许接收的帧。在接收端只有当收到的数据帧的发送序号落入接收窗口内时才允许将该数据帧收下。若接收到的数据帧落在接收窗口之外，则一律将其丢弃。发送窗口和接收窗口不需要有相同的窗口上限和下限，甚至不必具有相同的窗口大小。在某些协议中，窗口的大小是固定的，但在另外一些协议中，窗口大小可以根据接收端的接收能力以及网络的拥塞情况而动态地变化，这种滑动窗口协议就称为动态滑动窗口协议。只有在收到接收端发来的数据确认后，发送窗口才能向前移动以允许发送新的数据帧；而接收端只有在收到期望的数据帧时，才有可能移动接收窗口以允许接收新的数据帧，即只有在接收窗口向前移动时，发送窗口才有可能向前移动。
滑动窗口协议主要应用于点对点链路（通常是数据链路层链路）和端到端链路（通常是运输层连接）。在应用于点对点链路时，窗口大小的单位通常是帧（数据链路层的数据传输单位）。在应用于端到端链路时，窗口大小的单位通常有两种：字节和报文（运输层的数据传输单位）。例如，Internet体系结构中的TCP协议的窗口大小单位就是字节。由于端到端链路需要跨越网络，因此，应用于端到端链路的滑动窗口协议还需与网络的拥塞控制机制联系在一起，窗口的大小要考虑到网络的拥塞情况，根据接收端的接收能力和网络的拥塞程度来动态地共同确定窗口的大小。典型的例子便是TCP协议中的拥塞控制机制（慢启动、加速递减和拥塞避免）。
当发送窗口和接收窗口的大小都等于1时，就是停等协议；当发送窗口大于1，接收窗口等于1时，就是连续ARQ协议；当发送窗口和接收窗口均大于1时，就是选择重传ARQ协议。另外，发送窗口和接收窗口的大小必须满足一定的关系才有可能保证正确的数据传输，例如，在连续ARQ协议中，当用n比特进行编号时，发送窗口的大小必须满足条件
；在选择重传ARQ协议中，接收窗口不应该大于发送窗口，且若用n比特进行编号，接收窗口的最大值必须受不等式
的约束。有关停等协议、连续ARQ协议、选择重传ARQ协议的详细情况见参考文献[19]。
TCP的流量控制机制也是采用滑动窗口的思想，并且是一种将拥塞控制和流量控制相给合的机制。这是因为TCP是端到端传输协议，不仅要解决接收端由于大量数据的到来而陷入瘫痪的情况，还要考虑网络的拥塞状况。这也是很多端到端的数据传输协议要解决的问题。有关TCP流量控制机制的详细情况见参考文献[5]的第12章。
2-1 分析克莱顿隧道(Clayton Tunnel)所使用的通信协议，并对其进行改进以避免文中所描述的事故再次发生。分析你所修改的协议，还存在潜在的问题吗？下面是有关这次事故的简要描述。
1861年8月，英国的克莱顿隧道发生了一起严重的火车相撞事故，事故导致21人死亡和176人受伤。
克莱顿隧道全长1.5英里，是当时英国铁路中安全措施最好的铁路隧道。1841年，该隧道配备了一套“空闲／阻塞信号系统”。穿过隧道的轨道有两条，每个方向各一条。在任意时刻，隧道中的每条轨道上只允许有一列火车通过。下面以一条轨道的控制为例说明隧道的控制过程，控制系统由信号灯、红白旗、单针电报系统、信号员构成，系统结构如图2-13所示。
图2-13 克莱顿隧道控制系统结构图
（1）在轨道的入口处(A端）有一个红、绿信号灯。只有当信号灯为绿色时，才允许火车进入，并且任何一列火车通过绿色信号时信号系统会自动将该信号灯置为红色。
（2）如果火车经过后，信号灯系统没有将信号灯置成红色，则信号员会听到告警铃声，然后他使用红色和白色的旗帜来表示信号，“红旗”代表红色信号灯，“白旗”代表绿色信号灯。
（3）当入口处的信号员确信进入隧道的火车已离开隧道，则手工将红色信号灯置成绿色，以允许下列火车通过。信号员通过安装在隧道两端的单针电报系统来交换火车进入、离开隧道的信息。
隧道中应用的单针电报系统由William Cooke发明，他曾在1842年在一本宣传小册子中这样写道：火车可以无所畏惧地行驶，而无论其时间是否正确，也不管其是否在正确的轨道上，因为在使用该系统后，其速度总可以及时地降下来，从而避免了碰撞。电报系统定义了三种信号（报文）：
（a）TT(Train in Tunnel)：表示火车进入了隧道。一般情况下，在入口处的信号员看到火车通过绿色信号灯（或白旗）进入隧道后，会向另一端的信号员发送TT信号。
（b）TF(Tunnel is Free)：表示火车已离开了隧道，隧道为空。一般情况下，当出口处的信号员看到火车离开隧道时，向入口处的信号员发送TF信号。入口处信号员收到TF信号后，将信号灯置成绿色，以允许下列火车通过。
（c）TL(Has the train left the Tunnel?)：询问出口处信号员火车是否已离开了隧道。如果火车已离开，则回复TF信号。
上述控制协议保证了隧道的安全使用，即使在隧道某一端的信号系统功能失效的情况下也能安全进行（通过红白旗来代替）。尽管如此，该系统最终还是由于其控制协议的不完整性导致一起严重的安全事故。下面是1861年8月发生的事故的相关记录。
第一列火车司机看到信号灯为绿色，于是没有停下来，直接进入隧道。经过A端的信号灯时，由于信号系统故障导致信号灯没有变成红色，于是告警铃声响起。信号员A听到铃声时，首先向隧道另一端的信号员发送TT信号告之其有火车进入隧道，然后使用红色旗帜向下一列火车发出警告。
然而，第二列火车因速度太快，已经越过了刚才的绿色信号。幸运的是，火车司机在进入隧道的瞬间瞥见了信号员A的红色旗帜。而紧随其后的第三列火车司机及时看到红色旗帜的警告，在隧道入口处停了下来。
看到第三列火车停下后，信号员A返回到工作室，再次向另一端信号员B发出TT信号表示又有一列火车进入了隧道。由于协议中未考虑到会出现这种事件，所以未规定“两列火车同时在隧道中”如何表示。由于第二列火车不可能超过第一列火车，所以无法表示此信号还不会导致真正的问题。对于信号员A来说，唯一的问题是要从信号员B那里得知两列火车在何时都离开了隧道，以便允许下列火车进入。于是，信号员A向信号员B发出他知道的唯一合适的信号TL。在看到第一列火车在隧道口出现后，信号员B按照协议的约定发出TF信号表示“隧道已空”。
信号员A在收到信号员B发回的TF信号后，不知道自己是应该等待第二个TF信号，还是应按照当初约定的意思认为隧道已空。经过再三考虑后，他最终还是认为两列火车一定都已经离开了隧道，于是举起白旗示意第三列火车可以进入隧道。同时，第二列火车司机因为在进入隧道的时候瞥见了信号员A手中的红旗，所以他决定在隧道中停了下来，并经过深思后为完全起见而将火车往回倒，正好与进入隧道的第三列火车相撞。
专门研究火车灾难事故的历史学家Nock在1967年说过这样一段话：“在事故发生后，我们经常能听到的一句话是：‘我怎么也不会想到这种事会发生！’。然而，严酷的事实告诉我们：这种事会发生，经过无数次事故后，铁路控制系统才渐渐完善起来。”
2-2 占据两个山顶的蓝军与驻扎在这两个山之间的山谷的白军作战。其力量对比是：一个山顶上的蓝军打不过白军，但两个山顶的蓝军协同作战则可战胜白军。一个山顶上的蓝军拟于次日正午向白军发起攻击。于是发送电文给另一山顶上的友军。但通信线路很不好，电文出错或丢失的可能性较大。因此要求收到电文的友军必须送回一个确认电文。但此确认电文也可能出错或丢失。试问能否设计出一种协议使得蓝军能够实现协同作战因而一定（即100 %而不是99.999…%）取得胜利？
2-3 原始的TCP协议于1981年提出后得到了广泛的应用，并与IP协议一起构成了因特网协议体系的核心。同时，基于性能方面的考虑，人们对TCP协议做了大量的改进。例如，TCP协议在传统的具有较小时延和较低误码率的有线信道中具有较好的性能，但是卫星信道具有的特殊通信特性却极大地降低了TCP协议的性能，为此很多文献提出了在卫星信道中改进TCP协议以提高性能的方法。查阅相关文献并就此问题进行研讨。
2-1 简述“协议”与“服务”的关系。
2-2 如何理解“服务原语”？
2-3 以HDLC和FrameRelay为例来讨论协议的通信环境对协议的影响（提示：可以从差错控制机制来考虑）。
2-4 在Internet中，有很多应用层协议利用面向连接的TCP协议，也有很多利用无连接的UDP协议。能否通过一些例子来发现一些带有共性的规律（在选择面向连接的服务还是选择无连接服务方面）？
2-5 HTTP协议利用有连接的TCP作为传输通道，并且不断地建立连接和断开连接。说明这样做的好处和坏处（建议查找与HTTP相关的RFC)。
2-6 分析TCP协议采用的确认机制（提示：参考相关RFC)或分析ATM的信令协议采用的确认机制。
2-7 为什么检验和总是放在被保护对象的后面而不是前面？
2-8 试分析高速传输协议与低速传输协议所采用的确认机制上的差别。要求：先从原理上说明，然后举例说明。
2-9 “在停止等待协议中，应答帧不需要序号（如用ACK0和ACK1)”的观点是否正确？为什么？
2-10 前面提到：一些文献认为“协议由6个元素组成”，另一些文献认为“协议由5个元素组成”，这两者之间有本质区别吗？如果没有，说明为什么？（指出元素之间的对应关系）
2-11 协议由多少元素组成，它们之间有什么联系？请简要表达这种联系。
2-12 协议的组织有几种形式，各有什么特点？
2-13 分析OSI/RM在分层方面存在的问题。
2-14 有哪些差错检测机制或算法？简要说明每种方法的特点及适用场合。
2-15 假定所有的路由器和主机都工作正常，所有软件的运行也都没有错误，那么是否还有可能（尽管概率很小）会把分组投递到错误的目的地？如果一个网络中所有链路的数据链路层协议都能正常工作，试问从源结点到目的结点之间的端到端通信是否一定是可靠的？
2-16 假定一个协议实现需要n个计时器，现在计算机里只有一个硬时钟。设n个计时器的启动时间分别为t 0 ～t n −1，且超时间隔t out 都一样大。试问如何实现这n个超时计时器（这叫软时钟法）？
2-17 是否所有的数据传输协议的PDU中均需要序号字段？如果有数据传输协议的PDU中不需要序号字段，试举例说明。
2-18 在很多协议的PDU首部中有长度字段，试说明长度字段在差错控制机制中的作用。
2-19 有AB和BC两条链路。A经过B向C发送数据。B收到A发来的数据时，可以先向C转发再向A发确认，也可以把这一顺序反过来。也就是说，B要做的三件事的顺序是：收数据→转发→发确认，或者：收数据→发确认→转发。现假定B在做完第二件事后处理机即出故障，内存中所存信息全部丢失，但很快又恢复了工作。试证明：只有采用端到端发确认信息的方法（即从C向A发确认信息），才能保证在任何情况下数据都能从A经B正确无误地交付到C。
2-20 简要说明差错控制机制与层次的关系。
2-21 是否可以将数据链路层的差错控制功能放在网络层或运输层实现？是否可以将运输层的差错控制功能放在应用层实现？如果可以，这种改变有什么优缺点？是否有前提条件？
2-22 当某个路由器发现一数据报的检验和有差错时，为什么采取丢弃的办法而不是要求源站重传该数据报？计算首部检验和为什么不采用CRC检验和？
2-23 有哪些流量控制算法，简述它们的特点及适用场合。
2-24 简述“检测重传”与“纠错”的适用场合。
2-25 AB (Alternating Bit)协议是最早出现的端到端通信协议之一，协议机制如下所述(AB协议有很多种版本，下面给出的是其中之一）。
协议假定：
（1）协议所使用的通道是全双工的，且永远不会中断；
（2）报文在通道中可能会丢失、出错，但是重复发送一个报文n次，总有一次是正确的；
（3）接收方发送的应答报文不会丢失，不会出错，也不会重复；
（4）传输介质不会产生额外报文，也不会损坏报文。
发方的工作过程：发方协议实体从发方用户获取一个报文，将序号寄存器的值赋给报文，然后向收方协议实体发出报文，发送完成后启动超时计时器，等待应答报文。如果在给定时间内未收到应答报文（计时器超时），则重发报文。如果收到应答报文，且其序号值与发出报文的序号值相同，则将序号寄存器的内容按模2加1，然后发方协议实体从发方用户获取下一个报文。
收方的工作过程：收方协议实体在收到报文之后，如果报文无错误，且报文序号和序号寄存器之值相等，则向发方实体发出应答报文（应答报文的序号值等于接收报文的序号值），然后将报文依次给收方用户，序号寄存器的内容按模2加1。如果接收的报文有错误或者序号不正确，则将报文丢弃。
初始状态：发方和收方的序号寄存器均为0。
问题：
（1）序号“0”和“1”有何作用？AB协议与简单的应答式协议有何区别？
（2）对于发方协议实体，当它发出序号为“0”的报文之后，不等应答报文到来，可立即向用户获取下一个报文吗？为什么？
（3）如果应答报文也会丢失或出错，如何修改协议使其能正常工作？
（4）如果通道断路，会出现什么情况？
1 Boecking S. 面向对象的网络协议. 陈葆珏，严伟译. 北京：机械工业出版社，2000
2 Burton H O, et al. Error and Error Control. Proc. IEEE, 1972, 60 (11): 1293-1301
3 陈尚兵，王彬，钱积新. TCP拥塞控制综述. 计算机科学，2002，29 (5): 32～35
4 Comer D. 用TCP/IP进行网际互联第1卷：原理、协议和体系结构（第3版）。 林瑶，蒋慧，杜蔚轩等译. 北京：电子工业出版社，2001
5 Forouzan B A, Fegan S C. TCP/IP协议族. 谢希仁译. 北京：清华大学出版社，2003
6 龚正虎. 计算机网络协议工程. 长沙：国防科技大学出版社，1993
7 古天龙，蔡国永. 网络协议的形式化分析与设计. 北京：电子工业出版社，2003
8 Holzman G J. Design and Validation of Computer Protocol. New Jersey: Prentice Hall,1991
9 Kruse H. Performance of Common Data Communications Protocols over Long Delay Links: An Experimental Examination. In Proceedings of the 3rd International Conference on Telecommunication Systems Modeling and Design, 1995
10 Kwok T. ATM: The New Paradigm for Internet, Intranet, and Residential Broadband Services and Applications. New Jersey: Prentice-Hall, 1998
11 Lai R, Jirachiefpattana A. Communication Protocol Specification and Verification. Dutch:Kluwer Academic Publishers, 1998
12 鲁士文。计算机网络（习题与解析）。 北京：清华大学出版社，2001
13 Roy R, Mudumbai R C, Panwar S S. Analysis of TCP congestion control using a fluid model. In Proceedings of IEEE International Conference On Communications, 2001 8:2396～2403
14 Seddigh N, Devetsikiotis M. Studies of TCP's retransmission timeout mechanism. In Proceedings of IEEE International Conference On Communications, 2001, 6: 1834～1840
15 Stallings W. High-Speed Networks: TCP/IP and ATM Design Principles. London:Macmillan, 1998
16 Veres A, Boda M. Thechaotic nature of TCP congestion control. In Proceedings of 19th Annual Joint Conference of the IEEE Computer and Communications Societies, 2000, 3:1715～1723
17 Wang Haining, Shin K G. Robust TCP congestion recovery. In Proceedings of 21st International Conference On Distributed Computing Systems，2001, pp.199～ 206
18 Wang Haining, et a1. A simple refinement Of slow-start Of TCP congestion control．In Proceedings of Fifth IEEE Symposium On Computers and Communications, 2000,pp.98～105
19 吴礼发，谢希仁. 网络原理与技术教程. 北京：希望电子出版社，2002