计算机网络教程(第2版)/新视野电子电气科技丛书

作者简介

无

内容简介

第3章数据链路控制及其协议 数据链路层是OSI的7层模型中所定义的第2层，而在TCP/IP模型中，并没有明确划分数据链路层，而是将OSI所定义的物理层和数据链路层统称为网络接口层。但是，数据链路层的许多概念都属于计算机网络中很重要的知识点。因此，有必要将该层独立出来介绍。 3．1数据链路层的定义和功能 3．1．1数据链路层的定义 在具体介绍数据链路层的功能之前，首先需要明确两个基本概念。 链路： 是指一条无源的点到点的物理线路段，中间没有任何其他的交换节点。两个端点之间的通信信道由多条链路串接而成。 数据链路(Data Link)： 是指从数据发送点到数据接收点(点到点，point to point)所经过的传输途径。数据链路的概念外延除了物理链路以外，还包括实现控制数据传输规程(Procedure)的硬件和软件。 数据链路控制规程： 是指为使数据能迅速、正确、有效地从发送点到达接收点所采用的控制方式。 因此，也可以这样理解： 链路是一段不可靠的物理传输线路，而数据链路是指能可靠传输的逻辑链路。通过复用技术，一条链路上可以有多条数据链路。 OSI/RM将数据链路的目标定义为： 通过制定一些数据链路层协议(即链路控制规程)，以便建立、维护和释放网络实体间的数据链路，从而在不可靠的物理链路上实现可靠的数据传输。因此，数据链路层实现的主要功能包括： 链路管理，成帧与帧同步，差错控制，流量控制以及为网络层提供服务等。 3．1．2数据链路实现的功能 1. 为网络层提供服务 数据链路层作为网络层的底层，需要为网络层的通信实体提供服务。主要体现为3种类型的服务： 无确认无连接服务，适用于误码率很低的线路，将错误恢复留给高层，或者是实时业务，大部分局域网也提供该类型服务。 有确认无连接服务，适用于不可靠的信道，如无线网。 有确认有连接服务。 2. 链路管理 主要是指数据链路的建立、维护和释放。当两个节点要进行通信时，数据的发送方需要了解接收方是否能够接收。为此，通信的双方必须先要交换一些必要的信息，即建立一条数据链路。在通信的过程中，还需要对链路进行维护，在通信完成之后，还需要拆除链路。 3. 成帧与帧同步 在数据链路层，数据的传输单位是帧。发送方将比特流分成离散的帧，并计算每个帧的校验和，然后一帧接一帧地发送，一旦某一帧出现错误时，只需要重传错误帧即可。 所谓帧同步是指如何使接收方在收到的比特流中区分出一帧的开始与结束位置，这与成帧方法有关。目前，主要成帧方法有： 字符计数法： 在帧头中用一个域表示整个帧的字符个数，其缺点是： 若计数出错，对本帧和后面的帧有影响。 带字符填充的首尾字符定界法： 在帧的头部和尾部分别采用一些特殊字符表示，例如，起始字符DLE STX，结束字符DLE ETX。缺点是局限于8位字符和ASCII字符传送，还需要解决字符填充问题。 带位填充的首尾标记定界法： 在帧的起始和结束都用一个特殊的位串“01111110”，称为标记(flag)。该方法需要解决“0”比特插入/删除问题(在前面章节已介绍)。 物理层编码违例法： 在编码时，将一些非规定的编码状态来表示一个帧的开始与结束。例如： 在802局域网中，Manchester编码和差分Manchester编码用高低的电平跳变表示数据1，而用低高的电平跳变表示0，“高高”或者“低低”不表示数据，则可以用来做定界符。该方法只适用于物理层编码有冗余的网络。 4. 差错控制 对于计算机通信来说，数据传输的正确性很重要。一般要求错误率比较低。对于数据帧来说，出错的情况有两种： 帧内个别比特出错，帧丢失。 对于帧内个别比特出错情况，采用编码技术中的前向纠错，即接收方在收到有错误的数据帧时，能够自动地将差错比特改正过来。或者采用检错重发方法，即接收方可以检测出收到的帧中有错误，但无法确定是哪个比特有错，于是要求对方重新发送一次，直到接收方正确地接收到该帧为止。 对于帧的丢失问题，可以采用接收方给发送方一个反馈(响应)或者是通过计时器和序号保证每帧*终交给目标端的网络层。 5. 流量控制 主要是通过控制发送方发送数据的速率，来保证接收方能及时地处理发送方发送的数据。目前采用的方法主要是基于反馈机制来实现。数据链路层的流量控制主要是解决节点之间的流量问题，真正的端到端之间的流量控制主要是在传输层实现。 6. 数据的透明传输 不管上层是什么类型的数据，也不管所传输的数据的比特组合形式，数据链路层都能采用相同的机制进行传送。当所传输数据中的比特组合恰好与某种控制信息**一样时，必须采用相应的措施进行区分，使接收方不会将这样的数据误认为是某种控制信息，从而来实现所谓的“数据透明传输”。例如，在HDLC协议中使用的“见5个1插入0”就属于这种技术。 7. 寻址 数据链路层可以实现点到点和多点连接。对于多点连接的情况下，必须有相应的寻址机制来保证每帧能发送到正确的目标站点。而且也要求接收方也能知道发送方是哪个站点。 3．2错误检测和纠正 在通信过程中出现的差错可大致分为两类，一类是由热噪声引起的随机错误； 另一类是由冲击噪声引起的突发错误。热噪声是由电子热运动产生的，时刻存在(香农的结论)，而且频谱很宽，幅度很小。因此，通信链路的信噪比越高，热噪声引起的差错越小。这种错误具有很大随机性，影响个别比特。冲击噪声来自外界的电磁干扰，一般持续时间短，而且幅度大，往往引发一个位串错误，也就是我们常说“突发性差错”。 突发性差错影响局部，而随机性差错总是断续存在，影响全局。处理差错的两个策略是： （1） 使用纠错码： 发送方在每个数据块中加入足够的冗余信息，使得接收方能够判断接收到的数据是否有错，并能纠正错误。 （2） 使用检错码： 发送方在每个数据块中加入足够的冗余信息，使得接收方能够判断接收到的数据是否有错，但不能判断错在哪个比特。 3．2．1纠错码 在具体介绍纠错码之前，先介绍两个概念。 （1） 码字(codeword)： 一个帧包括m个数据位，r个校验位，n=m+r，则此n比特单元称为n位码字。 （2） 海明距离(Hamming distance)： 两个码字之间不同的比特位数目。例如，0000000000与0000011111的海明距离为5。 如果两个码字的海明距离为d，则只要d个单比特错就可以把一个码字转换成另一个码字； 因此，为了检查出d个错(单比特错)，需要使用海明距离为d+1的编码； 为了纠正d个错，需要使用海明距离为2d+1的编码。 1. 奇偶校验 奇偶校验分为水平奇偶校验和垂直奇偶校验两种。水平奇偶校验是在数据后添加一个奇偶位(parity bit)，使码字中1的个数成为奇数(奇校验)或者偶数(偶校验)。经过传输后，如果其中一位(甚至奇数个数多位)出错，则接收方按同样的规则(奇校验或偶校验)就能发现错误。 例如，使用偶校验(“1”的个数为偶数) 10110101—>101101011 10110001—>101100010 水平奇偶校验可以用来检查少量的随机性错误，但是，无法实现纠错。使用垂直奇偶校验不仅可以检查错误，还可以实现纠错。有关垂直奇偶校验编码内容在此不再做介绍，读者不妨自己设计一下。 2. 海明码 1950年海明(Hamming)研究了用冗余数据位检测和纠正代码差错的理论和方法。按照海明的理论，纠错码的编码就是要把所有合法的码字尽量安排在N维空间的超立方体的顶点上，使得任一对码字之间的距离尽可能大。如果任意两个码字之间的海明距离是d，则所有少于等于d-1位的错误都可以检查出来，所有少于d/2位的错误都可以纠正。因此可以得到一个推论： 对于某种长度的错误串，要纠正它就要用比仅检测它多一倍的冗余位。 如果对于m位的数据，增加k位冗余位，则组成n=m+k位纠错码，对于2m个有效码字中的每一个，都有n个无效但可以纠错的码字。这些可纠错的码字与有效码字的距离是1，含单个错误位。这样，对于一个有效的信息总共有n+1个可识别的码字，这n+1个码字相对于其他的2m-1个有效消息的距离都大于1。这意味着总共有2m (n+1)个有效的或者是可以纠错的码字。显然这个数小于等于码字的所有可能的个数，即2n。于是，有 2m (n+1)≤2n 因为n=m+k，因此有m+k+1≤2n。 对于给定的数据(消息)位m，上述公式给出了k的下限，即要纠正单个错误k必须要取的*小值。 海明建议了一种方案： 码位从左边开始编号，从“1”开始； 位号为2的幂的位是校验位，其余是信息位； 每个校验位使得包括自己在内的一些位的奇偶值为偶数(或奇数)； 为看清数据位k对哪些校验位有影响，将k写成2的幂的和。 例： 11=1+2+8。 海明码工作过程如下（见图31）： 每个码字到来前，接收方计数器清零； 接收方检查每个校验位k (k=1,2,4，…)的奇偶值是否正确； 若第k位奇偶值不对，计数器加k； 所有校验位检查完后，若计数器值为0，则码字有效； 若计数器值为m，则第m位出错； 若校验位1、2、8出错，则**1位变反; 图31海明纠错实例 使用海明码纠正突发错误： 可采用k个码字(n=m+r)组成k×n矩阵，按列发送，接收方恢复成k×n矩阵； k×r个校验位，k×m个数据位，可纠正*多为k个的突发性连续比特错。 3．2．2检错码 使用纠错码传数据，效率低，适用于不可能重传的场合，大多数情况采用检错码加重传来实现错误的纠正。其中检错码使用*普遍的是循环冗余码(CRC码，也称多项式编码)和校验和。 1. 校验和 为了校验突发性错误，可以使用校验和的方法。该方式是将数据块中的每个8位字节当作一个二进制整数，在发送过程中按模256相加(即将超出8位的进位丢掉)。数据块发送完后，把得到的数据和作为校验直接发送出去。接收方在接收的过程中进行同样的加法，数据块加完后用自己得到的校验和与接收到的校验和比较，从而发现是否出错。 2. 循环冗余码 所谓循环码是这样一组代码，其中任一有效码字经过循环移位后得到的码字仍然是有效码字，无论是右移或左移，也无论移多少位。 循环冗余码是一种循环码，它有很强的检错能力，而且硬件实现也很容易。在循环冗余码中，引入了如下两个概念： 数据多项式D(x)： 即数据字形成的多项式，例如，对于“110001”的数据多项式可以表示成x5+x4+1。 生成多项式G(x)： 由发送方和接收方事前商定的一种多项式，要求生成多项式的高位和低位必须为1，而且必须比要传输的数据所对应的数据多项式短。 CRC码基本思想： 将校验和(checksum)附加在数据帧尾部，并使带有校验和的帧所对应的多项式能被G(x)整除。然后将带有校验和的帧发送出去。当接收方接收时，用G(x)去除它，若有余数，则表示传输出错。 其中： 校验和计算算法如下： 设G(x)为r阶，在帧的末尾加r个0，使帧变为m+r位，则对应多项式为xrM(x)； 按模2除法用对应于G(x)的位串去除对应于xrM(x)的位串； 按模2减法从对应于xrM(x)的位串中减去余数(等于或小于r位)，结果就是要传送的带校验和的多项式T(x)。例如，数据帧1101011011的校验和计算过程如图32所示。 图32CRC计算过程 CRC的检错能力分析： 假设发送的多项式为T(x)； 接收到的多项式为T(x)+E(x)； 余数((T(x)+E(x))/G(x)=0+余数(E(x)/G(x))，则存在下列情况： 若余数(E(x)/G(x)) = 0，则不能发现差错； 否则，可以发现。如果只有单比特错，即E(x)=xi，而G(x)中至少有两项，余数E(x)/G(x)≠0，所以可以查出单比特错； 如果发生两个孤立单比特错，即E(x)=xi+xj=xj(xi-j+1)，假定G(x)不能被x整除，那么能够发现两个比特错的充分条件是： xk+1不能被G(x)整除(k≤i-j)； 如果有奇数个比特错，即E(x)包括奇数个项，G(x)选(x+1)的倍数就能查出奇数个比特错； 具有r个校验位的多项式能检查出所有长度≤r的突发性差错。长度为k的突发性连续差错(并不表示有k个单比特错)可表示为xi(xk-1+… +1)，若G(x)包括x0项，且k-1小于G(x)的阶，则余数E(x)/G(x)≠0; 如果突发差错长度为r+1，当且仅当突发差错和G(x)一样时，余数E(x)/G(x)=0，概率为1/2r-1;长度大于r+1的突发差错或几个较短的突发差错发生后，坏帧被接收的概率为1/2r。 为了能对不同场合的各种错误模式进行校验，目前已经研究出4个CRC生成多项式，并已成为**标准。 CRC-12 G(X)= X12 + X11+X3+X2+X+1； CRC-16 G(X)= X16+X12 +X15+X2+1； CRC-CCITT G(X)= X16+X12 +X5+1； CRC-32 G(X)= X32+ X26+X23+X22+X16+X12 + X11+X10+ X8+X7+X5+X4+X2+X+1。 3．3基本的数据链路层协议 两台主机通信时，应用进程将要传输的数据从应用层往下传，经过各层到物理层，通过通信线路将数据传输到对方主机的物理层，再逐层往上传，*后由应用层交给远程的应用进程。但是，为了清楚地介绍数据链路层协议，可以将通信过程简化为图33所示的通信模型。该模型中，将数据链路层以上的各层简化为AP实体表示，AP将需要传输的数据直接发送给数据链路层，然后通过数据链路直接传送给对方的数据链路层，再由数据链路层传递给对方的AP。 图33两台主机之间的简化通信模型 对于图33所示的简化模型，主机A要将数据发送给主机B，由于考虑到两台主机之间的发送数据和接收数据的速率可能不一致，就需要在各自的数据链路层分别设置一定大小的缓冲区。缓冲区大小与具体的链路通信协议有关。 3．3．1无约束单工协议 无约束单工协议(An Unrestricted Simplex Protocol)是一种理想状态下的通信协议，它建立在下列假设条件之上： 单工传输，通信的双方采用单工方式工作。 发送方无休止工作(要发送的信息无限多)。 接收方无休止工作，并且假设接收缓冲区无限大，不会发生数据溢出。 通信线路(信道)不损坏或丢失信息帧，也不会出现数据错误。 无约束单工协议的工作过程如下： 发送程序。从AP实体取得数据，然后构成数据链路层的数据帧，并发送数据帧。 接收程序。先是等待，然后从接收缓冲区中接收数据帧，并将数据帧上传给AP实体。 发送程序和接收程序反复重复上述过程。 3．3．2单工停等协议 在上述的无约束单工协议中，假设接收方无休止工作，并且接收缓冲区无限大，不会发生数据溢出。在这种假设条件下，通信的双方就不需要进行流量控制。但是，这种情况在现实中是根本不存在的。因此，产生了一个比较接近实际的数据链路层通信协议，即单工停等协议(Simplex StopandWait Protocol)。 单工停等协议的假设条件是： 接收方不能无休止接收，而且接收缓冲区的大小是有限的。 通信线路(信道)不损坏或丢失信息帧，也不会出现数据错误。 根据上述假设条件，分析可以知道，对于单工停等协议需要解决的问题是通信过程中的流量控制问题。因为，接收缓冲区的容量是有限的，在发送方的发送数据速率与接收方的数据速率差别太大的情况下，就会产生接收缓冲区的数据溢出现象。解决方法是控制发方的发送数据速率大小，即所谓的“流量控制”。 目前，在计算机网络中，流量控制*基本的方法是采用接收方来控制发送方的数据流量。方法是： 接收方每收到一个帧后，给发送方回送一个响应帧(ACK)，发送方只有在收到响应帧后才能发下一个数据帧。 因此，单工停等协议的工作过程如下： 发送程序。取数据，成帧，发送帧，等待响应帧； 一旦收到一个响应帧，就立即发送下一个数据帧。 接收程序。等待，从接收缓冲区接收帧，送数据给高层，给发送方回送响应帧。 两者重复上述过程，直至数据传输完毕。 无约束单工协议和单工停等协议的工作过程的差别如图34所示。 图34无约束单工协议和单工停等协议的工作过程 （a） 无约束单工协议的工作过程； (b) 单工停等协议的工作过程 3．3．3有噪声信道的单工协议 单工停等协议假设条件中的第2点与实际情况还是有一定差距的，在实际通信线路中，信道(线路)有差错，数据帧可能损坏或丢失。因此，单工停等协议还是属于理想状态下的一种协议，还无法应用在实际通信系统中。于是，在前两者的基础上，产生了具有实用价值的有噪声信道的单工协议(A Simplex Protocol for a Noisy Channel)。 在该协议中，对错误帧的解决办法是出错重传，然而，随之会带来一些问题： 什么时候重传？ 响应帧丢失怎么办？ 序号取多少位？ 对于重传的时间问题，可以采用否定响应帧(NACK)或定时器来解决。发送方在发送完一个数据帧后，立即启动一个超时定时器。若到了超时定时器所设置的重发时间内仍没有收到对方的响应帧，则发送方就重新发送该数据帧。这就是所谓的“超时重传”机制，或者是收到对方的一个否定响应帧，也要进行重发。其中，需要注意的问题是如何确定超时时间的长短。一般情况将超时时间设置为略大于“从发送完数据帧到接收到响应帧所需要的平均时间”。 “超时重传”能很好地解决数据帧的出错和丢失问题，然而，如果响应帧丢失了，“超时重发”则会产生重复帧问题。解决重复帧的方法是在发送的数据帧头部中放入序号，不同帧的编号不同。接收方发现两个帧的编号相同，就可以确定它们是重复帧，则可以丢弃其中的一个。 发送方与接收方传送的数据帧的数目可能很大，那么，每个帧的编号应该取多大呢？因为，任何一个编号系统的序号所占用的比特数一定是有限的。因此，经过一段时间后，发送序号就会重复。例如，如果序号采用3位表示，则只能构成8个序号。对于停等协议，每发送一个帧就要停止等待。因此，序号只要一个比特就可以了，一个比特可以表示两个序号。 发送方在发下一个帧之前需要等待一个肯定响应帧的协议叫作PAR(Positive Acknowledgement with Retran**ission)或ARQ(Automatic Repeat reQuest)。 有噪声信道的单工协议工作过程如图35所示。至此，读者不妨考虑一下： 对于有噪声信道的半双工和全双工协议的工作过程。 图35噪声信道的单工协议几种出错情况 (a) 数据帧出错； (b) 数据帧丢失； (c) 响应帧丢失 3．3．4停等协议的吞吐量分析 图36描绘了停等协议中数据帧和响应帧的时间关系。其中： 图36停等协议中数据帧和响应帧的时间关系 假设tf表示一个数据帧的发送时间，则tf等于数据帧的长度lf(bit)与数据的发送速率C(bps)之比，如式(31)所示。 tf=lf/C(31) 发送时间也是数据帧的发送时延。数据在数据链路上还要经历一个传播时间tp到达B，它是由电信号在物理线路上传播所造成的时延。节点B收到数据帧后要花费一个处理时间tpr后，才能发送响应帧ACK，响应帧的发送时间假设为ta，传播时间为tp。节点A收到响应帧ACK后也要花费一定的处理时间，假设这个处理时间也等于tpr，然后再发下一个数据帧。我们能得到超时重发时间tout为 tout=2tp+ta+2tpr(32) 一般情况下,数据帧的处理时间tpr和响应帧的发送时间ta都很小,要比传播时间tp小很多,为了研究问题方便起见，将其忽略不考虑。这样，重发时间为传播时间的2倍，即存在式(33)： tout=2tp(33) 从图36可以看出,两个成功的数据帧之间的*小时间间隔如式(34)所示： tT=tf+ tout= tf +2tp(34) 如果出现数据帧丢失,则成功发送1个数据帧所需要的时间显然要超过tT。假设数据出错的概率为p，但由于肯定响应帧和否定响应帧都比较小,出错的概率很小,因此在此假设为0。另外,我们允许重发无限次，这样能计算出正确传送一个数据帧所需的平均时间t**如式(35)所示： t** =tT+(1-p)∑+∞i=1ipitT= tT/(1-p)(35) 不难看出,当传输差错率越大时, t**也随之增大； 当无差错时,p=0, t**=tT。 每秒成功发送的*大帧数就是链路的*大吞吐量λmax，如式(36)所示: λmax=1/t**=(1-p)/tT(36) 在发送端,假设数据帧的实际到达率为每秒λ个帧,帧的到达速率不应该超过发送速率,即 λ≤(1-p)/tT(37) 3．4滑动窗口协议 3.3节中介绍的3个协议都是基于单工工作方式，在实际情况下,数据链路层*多是处于全双工工作方式。在全双工方式下,通信的双方同时存在数据帧和响应帧的发送和接收,因此接收方在接收到一个数据帧后,可以暂时延迟待发响应帧,以便将响应帧附加在下一个待发数据帧，这种技术称为确认捎带/载答(piggybacking)技术。该技术的优点是，充分利用信道带宽，减少帧的数目意味着减少“帧到达”中断； 同时,也使协议变得*加复杂。 本节将介绍3种滑动窗口协议，这些协议都能在实际(非理想)环境下正常工作，区别仅在于效率、复杂性和对缓冲区的要求不同。 连续的ARQ协议工作要点就是在发送一个数据帧后，不是停下来等待响应帧，而是连续再发送若干个数据帧，如果这时收到了接收端发来的响应帧(一个编号的响应帧能响应编号以前的数据帧)，那么还可以接着发送数据帧。由于减少了等待时间，整个通信的吞吐量提高了。 但是，在使用连续的ARQ协议时，如果发送端一直没有收到对方的响应帧，那么实际上发送端并不能无限制地发送其数据帧。主要原因如下： (1) 当未被确认的数据帧的数目太多时，只要有一帧出了差错，就可能要有很多的数据帧需要重传，这必然就要花费很多时间，因此增大了开销。 (2) 为了对所发送出去的大量数据帧进行编号，每个数据帧的发送序号也要占用较多的比特数，这样又增加一些不必要的开销。 (3) 由于无论是发送方还是收收方，都需要存储一定的数据帧，这与未确认的数据帧的数目有关，因此，未确认的数据帧数目越多，要求的缓冲区也就越大。 因此，为了解决上述问题，在综合停等协议和连续ARQ协议优点的基础上，引入了滑动窗口协议(Sliding Window Protocol)。其工作原理如下： (1) 发送的信息帧都有一个序号，从0到某个*大值，如0~2n-1，一般用n个二进制位表示。 (2) 发送端始终保持一个已发送但尚未确认帧的序号表，称为发送窗口。发送窗口的上界表示要发送的下一个帧的序号，下界表示未得到确认帧的*小编号。发送窗口大小=上界-下界，大小可变。 (3) 发送端每发送一个帧，序号取上界值，上界加1； 每接收到一个正确响应帧，下界加1。 (4) 接收端有一个接收窗口，大小固定，但不一定与发送窗口相同。接收窗口的上界表示允许接收的序号*大的帧，下界表示希望接收的帧。 (5) 接收窗口容纳允许接收的信息帧，落在窗口外的帧均被丢弃。序号等于下界的帧被正确接收，并产生一个响应帧，上界、下界都加1。接收窗口大小不变。 3位编号、窗口大小为1的滑动窗口如图37所示。 图373位编号、窗口大小为1的滑动窗口 (a) 开始状态； (b) 发送方发送一帧数据； (c) 接收方收到一帧数据； (d) 发送方收到一帧响应 3．4．1一比特滑动窗口协议 一比特滑动窗口协议(An One Bit Sliding Window Protocol)是指数据帧编号只采用1位表示。该协议特点如下： (1) 窗口大小为N=1，发送序号和接收序号的取值范围为0，1； (2) 可进行数据双向传输，信息帧中可含有确认信息(piggybacking技术)； (3) 信息帧中包括两个序号域： 发送序号和接收序号(已经正确收到帧的序号)。 一比特滑动窗口协议的工作过程采用伪代码表示如图38所示。 一比特的滑动窗口协议存在以下一些问题： 能保证无差错传输，但是基于停等方式； 若双方同时开始发送，则会有一半重复帧，如图39所示； 效率低，传输时间长。 图38一比特滑动窗口协议的工作过程 图39一比特滑动窗口协议的两种传输情形 注： 符号格式为(编号，响应，帧数)，*表示是网络层接收的分组。 3．4．2后退n帧协议 针对一比特的滑动窗口协议存在的缺点，为提高传输效率而设计后退n帧滑动窗口协议(A Protocol Using Go Back n)。 例如，卫星信道传输速率为50kbps，往返传输延迟为500ms，若传1000b的帧，使用一比特的滑动窗口协议，则传输一个帧所需时间为： 发送时间+信息信道延迟+确认信道延迟(确认帧很短，忽略发送时间)=1000b/50kbps+250ms+250ms=520ms。则信道利用率=20/520 =4%。 一般情况，信道带宽b（bps），帧长度L（bit），往返传输延迟R(s)，则信道利用率p的公式为: p= (L/b)/(L/b+R) =L/(L + Rb)(38) 分析式(38)，可以得出的结论是： 传输延迟大，信道带宽高，帧短时，信道利用率低。 为了提高信道的传输效率，解决的办法是采用所谓的连续流水线技术(pipelining)来发送多帧后再等待确认。 然而，也带来一些问题，如信道误码率高时，对损坏帧和非损坏帧的重传**多。从而也会降低传输效率。两种基本方法，其中一种方法是退后n帧(go back n)滑动窗口协议； 另外一种方法是选择重传(selective repeat)滑动窗口协议。 后退n帧(go back n)滑动窗口协议，当接收方发现某一编号帧出错后，则从出错帧起丢弃所有后继帧； 例如，如果接收方已经接收2、3、4、5、6、7、8后，发现第2帧有错误，则接收方丢失第2、3、4、5、6、7和8帧，要求发送方重传上述帧，如图310所示。 图310后退n帧的滑动窗口协议 在后退n帧的滑动窗口协议中，要求发送方有流量控制，并为重传设缓冲； 也就是说： 当发送窗口未满，可以允许网络层下传数据到数据链路层，但是当发送窗口满时，则禁止网络层下传数据。 另外，要求发送窗口大小<序号个数(MaxSeq + 1)； 接收窗口为1。 例如，对于MaxSeq = 7的情况，数据的传输过程如图311所示。在该过程中，发送方发送帧0~7，接收方在接收到这8帧数据并检测没有错误后，发送一个序号为7的响应帧给发送方； 则发送方发送另外8个帧，序号为0~7等。 在图311的协议实现过程中，定义了两种机制： 事件驱动机制和计时器处理机制。 图311后退n帧的滑动窗口协议实现过程 图311（续） 在事件驱动机制中，定义了内部事件(Network_layer_ready、timeout)，同时定义了外部事件(Frame_arrival和Cksum_err)。 当内部事件(Network_layer_ready)到达时，发送一个数据帧(帧序号，确认序号，数据)。 当外部事件(Frame_arrival)产生时，表示有一个数据帧或响应帧到达，如果是数据帧，则检查帧序号，如帧序号落在接收窗口内则接收，否则丢弃； 如果是响应帧，则检查确认序号，序号落在发送窗口内则移动发送窗口，否则不做处理。 当产生外部事件(Cksum_err)时，则丢弃出错帧。 如果产生内部事件(timeout)，则后退n帧重传。 设置计时器机制是为了解决响应帧的丢失问题。由于有多个未响应帧，因此要求设多个计时器。计时器是通过软件来实现的，如图312所示。 图312多个计时器的软件仿真 计时器处理如下： 当发送帧启动时，则计时器启动计时； 当收到正确确认时，则计时器停止计时，超时则产生timeout事件。 后退n帧的滑动窗口协议对于出错率较高的信道，特别浪费带宽。 3．4．3选择重传协议 针对后退n帧的滑动窗口协议不适合出错率较高的信道特点，发明了选择重传协议(A Protocol Using Selective Repeat)。该协议的目的是在不可靠信道上有效传输时，不会因重传而浪费信道资源。 选择重传协议的基本原理： 发送窗口*大为MaxSeq； 接收窗口大于1，但接收窗口*大为(MaxSeq+1)/2，目的是保证接收窗口前移后与原窗口没有重叠； 另外，该协议要求在接收端设置较大的数据缓冲区，先暂存出错帧的后继帧，并要求只重传坏帧； 基本过程如图313所示。 图313选择重传的滑动窗口协议 之所以对接收窗口的*大值有要求，下面通过实例来分析。例如： 设MaxSeq =7,若接收窗口=7，发送方发帧0、1、2、3、4、5、6，接收方全部收到，接收窗口前移(7~5)，确认帧丢失，发送方重传帧0，接收方作为新帧接收，并对帧6确认，发送方发新帧7、0、1、2、3、4、5，接收方已收过帧0，丢弃新帧0，则协议出错。 选择重传协议的实现过程如图314所示。在下列实现代码中，发送窗口下界为AckExpected，上界为NextFrameToSend； 接收窗口下界为FrameExpected，上界为TooFar； 发送方和接收方的缓冲区大小应等于各自窗口大小； 另外，增加了响应计时器，解决两个方向负载不平衡带来的阻塞问题； 可随时发送否定性响应帧NAK。 图314选择重传的滑动窗口协议的实现过程 图314(续) 图314(续) 3．5协议说明与验证 前面介绍了一些简单的数据链路层协议，实际上，对于计算机网络来说，网络协议是**复杂的问题。开发一个新的网络协议过程，就是我们常说的“协议工程”。一个协议工程包括如下几个方面： 协议说明(Protocol Specification)。定义一个协议实体为其用户提供的服务，并同时定义该协议实体的内部*作。 协议验证(Protocol Verification /Validation)。验证协议说明是否完整、正确。包括协议的语法和语义的验证。 协议实现(Protocol Implementation)。用硬件和/或软件实现协议说明中规定的功能。 协议测试(Protocol Testing)。用测试的方法来检查协议实现是否满足要求。包括一致性测试(Conformance Testing)、互*作性测试(Interoperability Testing)、性能测试(Performance Testing)等。 在协议的说明、验证、实现和测试过程中使用形式化描述技术(Formal Description Technique，FDT)/形式化方法(Formal Method，FM)，不仅可以比较容易地理解协议，且可以使协议描述*加**，大大简化了协议的研究工作。并能克服自然语言描述协议所存在的冗余、多义性、结构性不好和不便于自动验证、测试、实现等缺点。 一种形式化方法总是以一种形式体系为基础，只是在具体应用时，大都做了便于描述的改进和扩充。常用的形式化方法有： 有限状态机(Finite State Machine，F**)，包括扩展有限状态机(EF**)。 形式化语言模型，包括LOTOS、Estelle、SDL等。 Petri网，包括时间Petri网，随机Petri网，**Petri网。 过程代数(Process Algebra)，包括随机过程代数等。 3．5．1有限状态机模型 有限状态机可以采用多种方法来表示，其中一种方法是采用一个4元组(S,M,I,T)，S是状态的集合，M是标号的集合，I是初始状态的集合，T是变迁的集合。 通信协议建模是基于通信协议的实现过程，主要是由响应多个“事件”的相对简单的处理过程组成。其中事件主要包括命令(来自用户)、信息到达(来自低层)和内部超时。 例如： 有噪声信道的半双工协议(参见3．3．3节)通信过程的有限状态机如图315所示。 在图315中，只是描述了半双工停等协议一些主要状态，对于有些差别不大的状态进行了合并。因此称为有限状态图。每个状态用3个字母表示： XYZ。其中，X表示发送方正发送的帧序号，为0或1； Y表示接收方正等待的帧序号，为0或1； Z表示信道状态，为0(传送［0］)，1(传送［1］)，A(传送ACK)或-(空)。初始状态为(0 0 0)。在弧线或者直线旁边注明的数字是状态变迁的序号，也可理解为导致变迁的输入事件的序号。 假设系统一开始处于状态(0 0 0)。该状态表示通信中的发送方发完［0］，乙方期望接收［0］，信道此时正在传送［0］； 在无差错的情况下，整个通信过程体现为4个状态的循环： (0 0 0)>(0 1 A)>(1 1 1)>(1 0 A)>(0 0 0)>…。因此，从理论上计算，应共有2×2×4=16种不同的系统状态，去掉一些没意义的组合，还剩下10种。相应地，导致状态变迁的输入事件共有9种。 图315有限状态机 对于图315，也可以采用有限状态变迁表来描述，如表31所列。 表31半双工停等协议的有限状态变迁表 变迁序号 运行方 接收帧类型 发送帧类型 传递给网络否 0 - 帧丢失 帧丢失 - 1 R 0 A 是 2 S A 1 - 3 R 1 A 是4 S A 0 - 续表 变迁序号 运行方 接收帧类型 发送帧类型 传递给网络否 5 R 0 A 否 6 R 1 A 否 7 S 超时 0 - 8 S 超时 1 - 有限状态模型在协议比较复杂时，系统的状态数目将急剧增加，以致很难用它清晰地描述协议。因此，下面介绍第2种方法： Petri网模型。 3．5．2Petri网模型简介 Petri网模型*早在1962年Carl Adam Petri的博士论文中提出来，主要特性是对并行、不确定性、异步和分布具有较强的描述能力和分析能力。它也是一种状态变迁模型，允许同时发生多个状态变迁，因此，Petri网是一种并发模型。 Petri网描述的系统模型行为包括： 状态的可达性(reachability)； 位置的有界性(boundedness)； 变迁的活动性(liveness)； 初始状态的可逆达性(reversibility)； 标识(marking)之间的可达性(reachability)； 事件之间的同步距离(synchronic distance)； 公平性(fairness)。 一个Petri网的结构元素包括： 位置(place)： 描述系统状态，用一个圆圈表示； 变迁(transition)： 描述修改系统状态的事件，用一个长方形或线段表示； 弧(arc)： 描述状态与事件之间的关系，包括输入弧和输出弧，用有向弧表示。 标记(token)是Petri网中一种活动元素，它包含在位置中，用点表示，用来表示处理的信息单元、资源单元和顾客、用户等对象。如果位置用来描述条件，它可以包含一个标记或不包含标记，当包含标记时，条件为真，否则，为假。如果位置用来定义状态，位置中的标记个数用于规定某一状态。 Petri网的变迁实施规则(firing rule)为： 如果一个变迁的所有输入位置至少包含一个标记，则这个变迁可能实施。 一个可实施变迁的“点火(fire)”将导致从它所有输入位置中均取出标记，每个位置取出的标记数等于该位置指向的弧线数； 然后再将标记送入该变迁的所有输出位置中去，送入每个位置的标记数等于变迁指向该位置的弧线数。因此，“点火”前后的Petri网内的标记总数一般是不守恒的。 当使用大于1的弧权(weight)时，在变迁的所有输入位置中都要包含至少等于连接弧权的标记个数它才可实施，并根据弧权，在每个输出位置中产生相应标记个数。 变迁的实施是一个原子*作，输入位置清除标记和输出位置产生标记是一个不可分割的完整*作。 图316具有2个位置和变迁的Petri网络模型 图316是具有2个位置和2个变迁的Petri网，在位置A中有一个标记，当变迁1发生“点火”后，从位置A中取出一个标记，送入到位置B中。 一个Petri网中的状态变迁大致有如下3种类型，分别是顺序变迁、并发变迁和互斥变迁。在互斥变迁中，只能有一个变迁“点火”，一个点火后另一个就不能再点火了，如图317所示。 《计算机网络教程》由清华大学黄永峰、李星教授等编著，**版获中国电子教育学会**教材一等奖。本书具有如下特点：