计算机网络(数据链路层)

1、2021年12月8日星期三21时18分3秒1数据链路层一同步通信与异步通信二纠错编码三链路配置和传输控制四流量控制五差错控制六HDLC协议七PPP协议2021年12月8日星期三21时18分3秒2一、同步通信与异步通信在通信过程中，发送方和接收方必须在时间上保持同步，才能准确地传送信在通信过程中，发送方和接收方必须在时间上保持同步，才能准确地传送信息。除过码元同步之外，在传送由多个码元组成的字符以及由许多字符组成息。除过码元同步之外，在传送由多个码元组成的字符以及由许多字符组成的数据块时，通信双方也要就信息传输的起止时间取得一致的数据块时，通信双方也要就信息传输的起止时间取得一致（1）同步传输。

2、发送方在发送数据之前先发送一串同步字符）同步传输。发送方在发送数据之前先发送一串同步字符SYNC。接收。接收方只要检测到连续两个以上方只要检测到连续两个以上SYNC字符就确认已进入同步状态，准备接收信字符就确认已进入同步状态，准备接收信息。随后的传送过程中双方以同一频率工作（信号编码的比特定时作用也表息。随后的传送过程中双方以同一频率工作（信号编码的比特定时作用也表现在这里），直到传送完指示数据结束的控制字符。这种同步方式仅在数据现在这里），直到传送完指示数据结束的控制字符。这种同步方式仅在数据块的前后加入控制字符块的前后加入控制字符SYNC，所以传输效率更高。在短距离高速数据传输，所以传输效

3、率更高。在短距离高速数据传输中，多采用同步传输方式。中，多采用同步传输方式。1117DC1314915181Q1218DC2325025282R1319DC3335135383S1420DC4345245484T1521NAK355355585U1622SYN365465686V1723ETB375575787W1824CAN385685888X1925EM395795989Y1A26SUB3A58:5A90Z1B27ESC3B59;5B912021年12月8日星期三21时18分3秒3同步通信与异步通信（续）（2）异步传输。把各个字符分开传输，字符之间插入同步信息，这种方式）异步传输。把各个字

4、符分开传输，字符之间插入同步信息，这种方式也叫起止式，即在字符的前后分别插入起始位（也叫起止式，即在字符的前后分别插入起始位（“0”）和停止位（）和停止位（“1”）异步制不适合于传送大的数据块（例如磁盘文件），同步传输在传送连续异步制不适合于传送大的数据块（例如磁盘文件），同步传输在传送连续的数据块时比异步传输更有效的数据块时比异步传输更有效异步传输的优点是简单，但是由于起止位和检验位的加入会产生异步传输的优点是简单，但是由于起止位和检验位的加入会产生2030的开销，所以传输的效率不高的开销，所以传输的效率不高起始位起始位字字 符符校验位校验位停止位停止位2021年12月8日星期三21时18分

5、4秒4二、纠错编码 通信过程中出现的差错可大致分为两类：通信过程中出现的差错可大致分为两类： 一类是由热噪声引起的随机错误；通信线路中的热噪声是由电子的热运一类是由热噪声引起的随机错误；通信线路中的热噪声是由电子的热运动产生的。热噪声时刻存在，具有很宽的频谱，且幅度较小。通信线路动产生的。热噪声时刻存在，具有很宽的频谱，且幅度较小。通信线路的信噪比越高，热噪声引起的差错越少。这种差错具有随机性，影响个的信噪比越高，热噪声引起的差错越少。这种差错具有随机性，影响个别位。别位。 另一类是由冲击噪声引起的突发错误。另一类是由冲击噪声引起的突发错误。冲击噪声源是外界的电磁干扰，冲击噪声源是外界的电磁干

6、扰，例如打雷闪电时产生的电磁干扰，电焊机引起的电压波动等。冲击噪声例如打雷闪电时产生的电磁干扰，电焊机引起的电压波动等。冲击噪声持续时间较长而且幅度大，往往引起一个位串出错。根据它的特点，我持续时间较长而且幅度大，往往引起一个位串出错。根据它的特点，我们称其为突发性差错。们称其为突发性差错。 由于信号幅度和传播速率与相位、频率有关而引起的信号失真，以及相由于信号幅度和传播速率与相位、频率有关而引起的信号失真，以及相邻线路之间发生串音等都会产生差错，这些差错也具有突发性的特点。邻线路之间发生串音等都会产生差错，这些差错也具有突发性的特点。 误码率可用下式表示误码率可用下式表示 （传送的总位数）（

7、差错的位数）NNPee2021年12月8日星期三21时18分4秒5纠错编码（续）检错码奇偶校验：在奇偶校验：在7单位的单位的ASCII代码后增加一位，使码字中代码后增加一位，使码字中“1”的个数成奇的个数成奇数（奇校验）或偶数（偶校验）。经过传输后，如果其中一位（甚至奇数数（奇校验）或偶数（偶校验）。经过传输后，如果其中一位（甚至奇数个位）出错，则接收端按同样的规则就可以发现错误。这种方法简单实用，个位）出错，则接收端按同样的规则就可以发现错误。这种方法简单实用，但只能对付少量的随机性错误。但只能对付少量的随机性错误。检查和法：这种方法把数据块中的每个字节当作一个二进制整数，在发送检查和法：这

8、种方法把数据块中的每个字节当作一个二进制整数，在发送过程中按模过程中按模256相加。数据块发送完后，把得到的和作为校验字节发送出相加。数据块发送完后，把得到的和作为校验字节发送出去。实现时可以在校验字节发送前，对累加器中的数取去。实现时可以在校验字节发送前，对累加器中的数取2的补码。这样，的补码。这样，如不出错，接收端校验和后累加器中的数是如不出错，接收端校验和后累加器中的数是0。由于进位的关系，一个错。由于进位的关系，一个错误可以影响到更高的位，从而使出错位对校验字节的影响扩大了。可以粗误可以影响到更高的位，从而使出错位对校验字节的影响扩大了。可以粗略地认为，随机的突发性差错对校验和的影响也

9、是随机的。出现突发错误略地认为，随机的突发性差错对校验和的影响也是随机的。出现突发错误而得到正确的校验字节的概率是而得到正确的校验字节的概率是1/256。于是我们就有。于是我们就有255比比1的机会能检的机会能检查出任何错误。查出任何错误。2021年12月8日星期三21时18分4秒6纠错编码（续）海明码1950年，海明（年，海明（Hamming）研究了用冗余数据位来检测和纠正代码差错的）研究了用冗余数据位来检测和纠正代码差错的理论和方法。按照海明的理论，可以在数据代码上添加若干冗余位组成码字。理论和方法。按照海明的理论，可以在数据代码上添加若干冗余位组成码字。码字之间的海明距离是一个码字要变成

10、另一个码字时必须改变的最小位数。码字之间的海明距离是一个码字要变成另一个码字时必须改变的最小位数。例如例如7单位单位ASCII码增加一位奇偶位成为码增加一位奇偶位成为8位的码字，这位的码字，这128个个8位的码字之间位的码字之间的海明距离是的海明距离是2。所以当其中。所以当其中1位出错时便能检测出来。两位出错时就变成另位出错时便能检测出来。两位出错时就变成另一个有效码字了。一个有效码字了。海明用数学分析的方法说明了海明距离的几何意义，海明用数学分析的方法说明了海明距离的几何意义，n位的码字可以用位的码字可以用n维超维超立方体的一个顶点来表示。两个码字之间的海明距离就是超立方体的两个对立方体的一

11、个顶点来表示。两个码字之间的海明距离就是超立方体的两个对应顶点之间的一条边，而且是两顶点（从而两个码字）之间的最短距离，出应顶点之间的一条边，而且是两顶点（从而两个码字）之间的最短距离，出错的位数小于这个距离都可以被判断为就近的码字。这就是海明码纠错的原错的位数小于这个距离都可以被判断为就近的码字。这就是海明码纠错的原理，它用码位的增加（因而通信量的增加）来换取正确率的提高。理，它用码位的增加（因而通信量的增加）来换取正确率的提高。2021年12月8日星期三21时18分4秒7纠错编码（续）按照海明的理论，纠错编码就是要把所有合法的码字尽量安排在按照海明的理论，纠错编码就是要把所有合法的码字尽量

12、安排在n维超立方维超立方体的顶点上。使得任一对码字之间的距离尽可能大。如果任意两个码字之间体的顶点上。使得任一对码字之间的距离尽可能大。如果任意两个码字之间的海明距离是的海明距离是d，则所有少于等于，则所有少于等于d-1位的错误都可以检查出来，所有少于位的错误都可以检查出来，所有少于d2位的错误都可以得到纠正。位的错误都可以得到纠正。对某种长度的错误串，要纠正它就要用比仅仅检测它多一倍的冗余位。对某种长度的错误串，要纠正它就要用比仅仅检测它多一倍的冗余位。如果对于如果对于m位的数据，增加位的数据，增加k位冗余位，则组成位冗余位，则组成 n=m十十k位的纠错码。对于位的纠错码。对于 2m个有效码

13、字中的任意一个，都有个有效码字中的任意一个，都有n个无效但可以纠错的码字。这些可纠错个无效但可以纠错的码字。这些可纠错的码字与有效码字的距离是的码字与有效码字的距离是1，含单个错误位。，含单个错误位。对于一个有效码字总共有对于一个有效码字总共有n1个可识别的码字。这个可识别的码字。这n1个码字相对于其他个码字相对于其他2m-1个有效码字的距离都大于个有效码字的距离都大于1。这意味着总共有。这意味着总共有2m (n+1)个有效的或是可纠个有效的或是可纠错的码字。显然这个数应小于等于码字的所有可能的个数，即错的码字。显然这个数应小于等于码字的所有可能的个数，即2n。于是，我。于是，我们有们有 2m

14、（n+1） 2n因为因为n=mk，所以得出，所以得出 mk1 2k2021年12月8日星期三21时18分4秒8纠错编码（续）设传送的信息为设传送的信息为“1 0 0 1 0 1 1”，把各个数据位放在，把各个数据位放在3、5、6、7、9、10、11等等位置上，位置上，1、2、4、8位留做效验位位留做效验位 根据规则写入校验码根据规则写入校验码如果这个码字传输中出错，比如说如果这个码字传输中出错，比如说6号位出错。即变成号位出错。即变成当接收端按照同样规则计算奇偶位时，发现当接收端按照同样规则计算奇偶位时，发现1和和8号位的奇偶性正确。而号位的奇偶性正确。而2和和4号号位的奇偶性不对，于是位的奇

15、偶性不对，于是24= 6，立即可确认错在，立即可确认错在6号位号位2021年12月8日星期三21时18分4秒9纠错编码（续）通常用监督关系式来实现海明纠错。设通常用监督关系式来实现海明纠错。设m=4，k=3，n=m+k=7，如果组成的码，如果组成的码字为字为a6 a5a4 a3 a2 a1 a0，则监督关系式可设计如下，则监督关系式可设计如下 S2=a2+ a4+a5+ a6 S1= a1+ a3+a5+ a6 S0= a0+ a3+a4+ a6监督关系式与出错位的对应关系如下：监督关系式与出错位的对应关系如下：所以更直观的排列方式如下所以更直观的排列方式如下 S2 S1 S011111010

16、1011100010001000出错位出错位a6a5a4a3a2a1a0无错无错a2a1a022=421=220=1a67111a56110a45101a33011a6a5a4a2a3a1a0 7 6 5 4 3 2 12021年12月8日星期三21时18分4秒10纠错编码（续）循环冗余校验码循环冗余校验码CRC 所谓循环码是这样一组代码，其中任一有效码字经过循环移位后得到的码字所谓循环码是这样一组代码，其中任一有效码字经过循环移位后得到的码字仍然是有效码字，不论是右移或左移，也不论移多少位。仍然是有效码字，不论是右移或左移，也不论移多少位。例如，若（例如，若（an-1 an-2 a1 a0）

17、是有效码字，则（）是有效码字，则（an-2 an-3 a0 an-1），（），（an-3 an-4 an-1 an-2），），等都是有效码字。等都是有效码字。循环冗余校验码循环冗余校验码CRC（Cyclic Redundancy Check）是一种循环码，它有很）是一种循环码，它有很强的检错能力，而且容易用硬件实现，在局域网中有广泛应用强的检错能力，而且容易用硬件实现，在局域网中有广泛应用2021年12月8日星期三21时18分4秒11纠错编码（续）生成多项式生成多项式x16x12x51数据码字数据码字00101011对应的多项式是对应的多项式是x5x3十十xl 0010 1011 0000 0

18、000 0000 0000 10 0010 0000 0100 001 00 1001 0000 0100 0010 0000 1000 1000 0001 0000 1 0001 1000 0101 0010 1000 1 0001 0000 0010 0001 0 1001 0101 0000 1001（余数）（余数） 得到的校验和是得到的校验和是0 x95092021年12月8日星期三21时18分4秒12纠错编码（续）数学分析表明，数学分析表明，G(X)应该有某些简单的特性，才能检测出各种错误。应该有某些简单的特性，才能检测出各种错误。例如，若例如，若G(X)包含的项数大于包含的项数大于

19、1，则可以检测单个错，若，则可以检测单个错，若G(X)含有因子含有因子X1，则可检测出所有奇数个错。最后，也是最重要的结论是，具有，则可检测出所有奇数个错。最后，也是最重要的结论是，具有r个校验个校验位的多项式能检测出所有长度小于等于位的多项式能检测出所有长度小于等于r的突发性差错。的突发性差错。为了能对不同场合下的各种错误模式进行校验，已经研究出了几种为了能对不同场合下的各种错误模式进行校验，已经研究出了几种CRC生生成多项式的国际标准；成多项式的国际标准； CRC-CCITT G(X)=X16 +X12 +X5 +1 CRC-16 G(X)=X16 +X15 +X2 +1 CRC-12 G

20、(X)=X12+X11+X3+X2+X+1 CRC-32 G(X)=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X+1 CRC-32用在许多局域网中用在许多局域网中2021年12月8日星期三21时18分4秒13三、链路配置和传输控制相邻站之间的数据链路控制要实现的主要功能有：相邻站之间的数据链路控制要实现的主要功能有： （1）把数据组织成一定大小的数据块）把数据组织成一定大小的数据块帧，以帧为单位进行发送、接收、帧，以帧为单位进行发送、接收、校验和应答；校验和应答； （2）对发送数据的速率进行控制，以免发送得过快，使得接收站来不及处理）对发送数

21、据的速率进行控制，以免发送得过快，使得接收站来不及处理而丢失数据，这个功能叫流量控制；而丢失数据，这个功能叫流量控制； （3）接收站对收到的数据帧要进行检验，如发现差错，则必须重传，这个功）接收站对收到的数据帧要进行检验，如发现差错，则必须重传，这个功能叫做差错控制；能叫做差错控制； （4）发送站和接收站之间必须通过某种形式的对话来建立、维护和终止一批）发送站和接收站之间必须通过某种形式的对话来建立、维护和终止一批数据的传输过程，这是对数据链路的管理。数据的传输过程，这是对数据链路的管理。2021年12月8日星期三21时18分4秒14链路配置和传输控制（续）数据链路层协议能够适应各种数据链路配

22、置，例如点对点链路和多点链路、半数据链路层协议能够适应各种数据链路配置，例如点对点链路和多点链路、半双工链路和全双工链路等。数据和控制信息都要在同一链路上传送，因而数据双工链路和全双工链路等。数据和控制信息都要在同一链路上传送，因而数据链路协议应能区分不同类型的帧。链路协议应能区分不同类型的帧。在多点链路配置中，各个终端分时地向在多点链路配置中，各个终端分时地向计算机发送或从计算机接收数据。计算计算机发送或从计算机接收数据。计算机负责链路的控制，称为机负责链路的控制，称为主站主站，各个终，各个终端对计算机发出的命令给予响应，叫做端对计算机发出的命令给予响应，叫做从站从站。在任意时刻，通信链路上

23、只能有。在任意时刻，通信链路上只能有一个主站，可以有多个从站。两个站之一个主站，可以有多个从站。两个站之间的通信可以是半双工的，也可以是全间的通信可以是半双工的，也可以是全双工的。单工通信不适用于数据链路的双工的。单工通信不适用于数据链路的控制，因为主站要向从站发送控制信号，控制，因为主站要向从站发送控制信号，从站则要向主站发送响应信号。从站则要向主站发送响应信号。2021年12月8日星期三21时18分4秒15链路配置和传输控制（续）在点对点链路上进行数据传送：当任意一个站要向对方发送数据时，它就占在点对点链路上进行数据传送：当任意一个站要向对方发送数据时，它就占据主站地位，并向从站发出询问（

24、据主站地位，并向从站发出询问（ENQ）消息，看它是否准备好接收数据。）消息，看它是否准备好接收数据。从站可以根据自己的情况（忙或闲）给予肯定应答（从站可以根据自己的情况（忙或闲）给予肯定应答（ACK）或否定应答）或否定应答（NAK）。主站收到肯定应答信号就开始发送数据，在发送过程中，主站可）。主站收到肯定应答信号就开始发送数据，在发送过程中，主站可能要在某一时刻停下来等待从站的响应，看它是否正确地接收了已发出的数能要在某一时刻停下来等待从站的响应，看它是否正确地接收了已发出的数据。主站对出错的数据要重新发送，直到正确接收为止。当主站的数据发送据。主站对出错的数据要重新发送，直到正确接收为止。当

25、主站的数据发送完毕后，发出传输结束（完毕后，发出传输结束（EOT）信号，双方释放连接，一次数据传送便告完）信号，双方释放连接，一次数据传送便告完成成2021年12月8日星期三21时18分4秒16链路配置和传输控制（续） 数据传送过程由三个阶段组成。数据传送过程由三个阶段组成。第一个阶段是建立连接的阶段，通过主站询问和从站应答使双方都处于准第一个阶段是建立连接的阶段，通过主站询问和从站应答使双方都处于准备好的状态；备好的状态；第二个阶段是数据传送阶段，这个阶段由发送、接收数据和对数据的应答第二个阶段是数据传送阶段，这个阶段由发送、接收数据和对数据的应答组成；组成；最后一个阶段是释放连接阶段，由任

26、一方发出传输结束信号，双方都知道最后一个阶段是释放连接阶段，由任一方发出传输结束信号，双方都知道数据传输已完成，这意味着释放了连接。数据传输已完成，这意味着释放了连接。2021年12月8日星期三21时18分4秒17链路配置和传输控制（续） 多点链路的控制分成两种情况多点链路的控制分成两种情况一种情况是所有的站都是对等的，没有主从站之分。当一个站有数据要一种情况是所有的站都是对等的，没有主从站之分。当一个站有数据要发送时必须查看链路是否空闲，空闲则立即发送，链路忙则等待。如果发送时必须查看链路是否空闲，空闲则立即发送，链路忙则等待。如果同时有几个站都要发送数据，则按照某种规则竞争链路的使用权。这

27、种同时有几个站都要发送数据，则按照某种规则竞争链路的使用权。这种竞争发送技术用在总线型局域网中竞争发送技术用在总线型局域网中另外一种情况是有主从站之分，并且通信总是在主站和从站之间进行，另外一种情况是有主从站之分，并且通信总是在主站和从站之间进行，两个从站之间不发生数据交换。两个从站之间不发生数据交换。多点链路上的主站和从站之间的链路控制通常采用两种方法：一种是询多点链路上的主站和从站之间的链路控制通常采用两种方法：一种是询问法，即主站询问从站是否有数据要发送；另一种是选择法，即主站发问法，即主站询问从站是否有数据要发送；另一种是选择法，即主站发送数据并选择一个从站接收数据。送数据并选择一个从

28、站接收数据。快速选择快速选择2021年12月8日星期三21时18分5秒18四、流量控制 流量控制是一种协调发送站和接收站工作步调的技术，其目的是避免发流量控制是一种协调发送站和接收站工作步调的技术，其目的是避免发送速度过快，使得接收站来不及处理而丢失数据。通常接收站维持一定送速度过快，使得接收站来不及处理而丢失数据。通常接收站维持一定大小的接收缓冲区，当收到的数据进入缓冲区后，接收器要进行简单的大小的接收缓冲区，当收到的数据进入缓冲区后，接收器要进行简单的处理，然后把数据提交给上层并清除缓冲区，再开始接收下一批数据。处理，然后把数据提交给上层并清除缓冲区，再开始接收下一批数据。如果在接收器没取

29、走缓冲区中的数据之前下一批数据来到，缓冲区就会如果在接收器没取走缓冲区中的数据之前下一批数据来到，缓冲区就会溢出，从而引起数据丢失。流控机制可以避免发生这种情况。溢出，从而引起数据丢失。流控机制可以避免发生这种情况。数据是分帧传输的。每一个帧中除了要传送的数据之外还包含一些控制数据是分帧传输的。每一个帧中除了要传送的数据之外还包含一些控制信息。把长的消息分成短帧的好处是可以分帧应答和重传，减少了出错信息。把长的消息分成短帧的好处是可以分帧应答和重传，减少了出错时重传的数据量，同时接收缓冲区也可以小一些。时重传的数据量，同时接收缓冲区也可以小一些。2021年12月8日星期三21时18分5秒19流

30、量控制（续）停等协议：发送站发出一帧，然后等待应答信号到达后再发送下一帧；接收站停等协议：发送站发出一帧，然后等待应答信号到达后再发送下一帧；接收站每收到一帧后送回一个应答信号，表示它愿意接收下一帧，如果接收站不送回每收到一帧后送回一个应答信号，表示它愿意接收下一帧，如果接收站不送回应答，则发送站必须等待。这样，帧在源和目标之间的数据流动是由接收站控应答，则发送站必须等待。这样，帧在源和目标之间的数据流动是由接收站控制的。假设在半双工的点对点链路上，站制的。假设在半双工的点对点链路上，站S1向站向站S2发送发送n个数据帧，个数据帧，S1每发出每发出一个帧就等待一个帧就等待S2送回应答信号。设一

31、个帧从送回应答信号。设一个帧从S1到达到达S2的时间为的时间为 TF = tp tf另外应答信号（另外应答信号（ACK）从）从S2到达到达S1也要经过一个传播延迟时间也要经过一个传播延迟时间tp。发送应答信。发送应答信号的时间可以忽略不计，所以完成一帧传输和应答的时间间隔为号的时间可以忽略不计，所以完成一帧传输和应答的时间间隔为 TFA= TF十十TA=（tp tf）十）十tp=2 tp tf传送完传送完n帧的时间为帧的时间为 TD= nTFA =n（2tp tf）数据帧传输的时间为数据帧传输的时间为ntf 于是链路的利用率为于是链路的利用率为我们定义我们定义a= tp / tf 则则 202

32、1年12月8日星期三21时18分5秒20流量控制（续）由于由于a是链路传播延迟和一个帧时的比（是链路传播延迟和一个帧时的比（a= tp / tf），故在链路长度一定和帧，故在链路长度一定和帧长固定的情况下长固定的情况下a是常数。又由于链路传播延迟是链路长度是常数。又由于链路传播延迟是链路长度d和信号传播速度和信号传播速度v的比值，而一帧时是帧长的比值，而一帧时是帧长L和数据速率和数据速率R的比，因而有的比，因而有 分子分子Rd/v的单位为比特，其物理意义是的单位为比特，其物理意义是链路上能容纳的最大比特数链路上能容纳的最大比特数，亦即链，亦即链路的比特长度，它是由链路的物理特性决定的。因而路的

33、比特长度，它是由链路的物理特性决定的。因而a可理解为链路比特长和可理解为链路比特长和帧长的比，或者说帧长的比，或者说链路的帧计数长度链路的帧计数长度2021年12月8日星期三21时18分5秒21流量控制（续）通常卫星信道的传播延迟是通常卫星信道的传播延迟是270ms，假设数据速率是，假设数据速率是64kb/s，帧长为，帧长为4 000 比比特。因而得到：特。因而得到： a642704 0004.32 l因而卫星链路的利用率为因而卫星链路的利用率为可见卫星链路的利用率仅为可见卫星链路的利用率仅为1/10左右，大量的时间用在等待应答信号上了左右，大量的时间用在等待应答信号上了2021年12月8日星

34、期三21时18分5秒22流量控制（续）局域网的局域网的例子：链路长度例子：链路长度d一般为一般为0.110 km，传播速度，传播速度v=2108m/s。设数。设数据速率据速率R=10Mb/s，帧长，帧长L=500 比特，则比特，则a的取值范围为的取值范围为10-5到到1。如果取。如果取a=0.1，则链路利用率则链路利用率如果取如果取a=0.01，则链路利用率为，则链路利用率为0.98。可见在局域网上利用停等协议时，效。可见在局域网上利用停等协议时，效率要高得多。率要高得多。最后考查一下利用最后考查一下利用Modem在话音信道上进行数据传输的情况。话音信道典型在话音信道上进行数据传输的情况。话音

35、信道典型的数据速率的数据速率R=9 600b/s，仍然取，仍然取v=2108m/s，L=500bit。如果传输距离。如果传输距离d是是100m，则，则2021年12月8日星期三21时18分5秒23流量控制（续）滑动窗口协议滑动窗口协议 其其主要思想是允许连续发送多个帧而无需等待应答。假设两个站主要思想是允许连续发送多个帧而无需等待应答。假设两个站S1和和S2通过通过全双工链路连接，站全双工链路连接，站S2维持能容纳维持能容纳n个帧的缓冲区，则站个帧的缓冲区，则站S2可连续接收可连续接收n个数个数据帧，因而站据帧，因而站S1也可以连续发送也可以连续发送n个帧而不必等待应答信号。个帧而不必等待应答

36、信号。 为了使为了使S2能够表示哪些帧已被成功地接收，每个帧都给予一个顺序号。能够表示哪些帧已被成功地接收，每个帧都给予一个顺序号。S2发发出一个带有帧编号的应答信号，就表明该编号之前的帧已正确接收，它期望出一个带有帧编号的应答信号，就表明该编号之前的帧已正确接收，它期望下面要接收具有该编号的帧及其后续帧。下面要接收具有该编号的帧及其后续帧。 例如，例如，S2已经接收了已经接收了1、2、3、4四个帧，它发出带有顺序号四个帧，它发出带有顺序号5的应答信号，的应答信号，表明前面四个帧都已正确接收，并要求表明前面四个帧都已正确接收，并要求S1发送从发送从5号帧开始的号帧开始的n个帧。显然，个帧。显然

37、，这样就允许这样就允许S2一次应答多个帧，从而减少了传送应答信号的通信量。一次应答多个帧，从而减少了传送应答信号的通信量。 站站S1和和S2中都保存一个帧编号表，中都保存一个帧编号表，S1的表指明它可以连续发送而不必等待应的表指明它可以连续发送而不必等待应答的所有帧的编号，答的所有帧的编号，S2的表指明它准备连续接收的所有帧的编号。这些表都的表指明它准备连续接收的所有帧的编号。这些表都可以看作是加在帧编号序列上的窗口。可以看作是加在帧编号序列上的窗口。2021年12月8日星期三21时18分5秒24流量控制（续）我们假定帧编号字段为我们假定帧编号字段为3位长（位长（k=3），帧编号取值范围为），

38、帧编号取值范围为07，窗口最大，窗口最大为为W=7。发送窗口随着接收到的应答信号向前移动，。发送窗口随着接收到的应答信号向前移动，S1每收到一个应答信号每收到一个应答信号ACKi，窗口的后沿就推进到第，窗口的后沿就推进到第i 帧的位置，窗口的前沿则推进到（帧的位置，窗口的前沿则推进到（W+i1）mod 2k的位置。例如在下图中，若的位置。例如在下图中，若S1收到编号收到编号6的应答信号的应答信号ACK6，则，则 S1的的窗口前沿只能为窗口前沿只能为4。如果接收站发出某个应答信号后，不再发出新的应答信号，则两个窗口都如果接收站发出某个应答信号后，不再发出新的应答信号，则两个窗口都不再向前滑动，这

39、时发送站不再发出帧，接收站也不再接收，从而达到了不再向前滑动，这时发送站不再发出帧，接收站也不再接收，从而达到了流控的目的。我们注意到，这种流控作用有一个滞后的时间：发送器一直流控的目的。我们注意到，这种流控作用有一个滞后的时间：发送器一直发送到窗口中的帧都发送完才能停止发送发送到窗口中的帧都发送完才能停止发送2021年12月8日星期三21时18分5秒25流量控制（续）窗口大小窗口大小W对协议效率的影响对协议效率的影响由于参数由于参数a是链路的帧计数长度，如果把帧的发送时间是链路的帧计数长度，如果把帧的发送时间tf=L/R归一化，则归一化，则a就是链就是链路延迟。在这种假设下，我们可用图路延迟

40、。在这种假设下，我们可用图3-10说明在全双工链路上协议的效率。说明在全双工链路上协议的效率。当窗口大小当窗口大小W2al时，发送器在发送完窗口中的帧之前就可接收到最先发送的时，发送器在发送完窗口中的帧之前就可接收到最先发送的应答信号，窗口可向前滑动，又有新的帧进入窗口，因而发送站可不停顿地连续应答信号，窗口可向前滑动，又有新的帧进入窗口，因而发送站可不停顿地连续发送。这时链路上充满了帧，链路的利用率达到最大值发送。这时链路上充满了帧，链路的利用率达到最大值1。当当W2a1时，发送器在接收到最早的应答信号之前已用完窗口中的帧号，停止时，发送器在接收到最早的应答信号之前已用完窗口中的帧号，停止了

41、发送，因而链路不能百分之百地充分利用。我们得到链路的利用率了发送，因而链路不能百分之百地充分利用。我们得到链路的利用率2021年12月8日星期三21时18分5秒26流量控制（续）在以上讨论中，我们都假定发送应答信号的时间可忽略不计。其实应答信号是在以上讨论中，我们都假定发送应答信号的时间可忽略不计。其实应答信号是用专门的控制帧传输的，也需要一定的时间来发送和处理。在利用全双工链路用专门的控制帧传输的，也需要一定的时间来发送和处理。在利用全双工链路进行双向通信的情况下，应答信号可以放在进行双向通信的情况下，应答信号可以放在S2到到S1方向发送的数据帧中，这种方向发送的数据帧中，这种技术叫技术叫“

42、捎带应答捎带应答”。如果应答信号被捎带送回发送站，则应答信号的传送时。如果应答信号被捎带送回发送站，则应答信号的传送时间可计入反向传送的数据帧的时间中，因而上面的假定是符合实际情况的。间可计入反向传送的数据帧的时间中，因而上面的假定是符合实际情况的。图图3-11画出了在不同窗口尺画出了在不同窗口尺寸下链路利用率和寸下链路利用率和a值的函数值的函数关系。关系。W= 1相当于停等协议，相当于停等协议，W= 7适用于局域网和电信网适用于局域网和电信网络的情况，络的情况，W= 127可用于卫可用于卫星信道。星信道。2021年12月8日星期三21时18分6秒27五、差错控制 差错控制是检测和纠正传输错误

43、的机制。在数据传输过程中有的帧可能丢失，差错控制是检测和纠正传输错误的机制。在数据传输过程中有的帧可能丢失，有的帧可能包含错误，这样的帧经接收器校验后会被拒绝。通常应付传输差错有的帧可能包含错误，这样的帧经接收器校验后会被拒绝。通常应付传输差错的办法如下：的办法如下：（1）肯定应答。接收器对收到的帧校验无误后送回肯定应答信号）肯定应答。接收器对收到的帧校验无误后送回肯定应答信号ACK，发送器，发送器收到肯定应答信号后继续发送后续帧；收到肯定应答信号后继续发送后续帧；（2）否定应答重发。接收器收到一个帧后，经校验发现错误，则送回一个否定）否定应答重发。接收器收到一个帧后，经校验发现错误，则送回一

44、个否定应答信号应答信号NAK。发送器重新发送出错帧；。发送器重新发送出错帧；（3）超时重发。发送器发送一个帧时开始计时，在一定的时间内没有收到关于）超时重发。发送器发送一个帧时开始计时，在一定的时间内没有收到关于该帧的应答信号，则认为该帧丢失并重新发送。该帧的应答信号，则认为该帧丢失并重新发送。 这种技术的主要思想是利用差错检测技术自动地对丢失帧和错误帧请求重发，这种技术的主要思想是利用差错检测技术自动地对丢失帧和错误帧请求重发，因而叫做因而叫做ARQ（Automatic Repeat reQuest）技术。结合流控技术，可以组）技术。结合流控技术，可以组成三种形式的成三种形式的ARQ协议：停

45、等协议：停等ARQ协议，后退协议，后退N帧帧ARQ协议和选择性协议和选择性ARQ协协议。议。2021年12月8日星期三21时18分6秒28差错控制（续）停等停等ARQ协议协议停等停等ARQ协议是停等流控技术和自动请求重发技术的结合。根据停等协议是停等流控技术和自动请求重发技术的结合。根据停等ARQ协协议，发送站发出一个帧后必须等待应答信号，收到肯定应答信号议，发送站发出一个帧后必须等待应答信号，收到肯定应答信号ACK后继续后继续发送下一帧；收到否定应答信号发送下一帧；收到否定应答信号NAK后重发出错帧；在一定的时间间隔内没后重发出错帧；在一定的时间间隔内没有收到应答信号也必须重发。最后一种情况

46、值得注意，没有收到应答信号的有收到应答信号也必须重发。最后一种情况值得注意，没有收到应答信号的原因可能是帧丢失了，也可能是应答信号丢失了。无论哪一种原因使得发送原因可能是帧丢失了，也可能是应答信号丢失了。无论哪一种原因使得发送站收不到应答信号，都必须重新发送原来的帧站收不到应答信号，都必须重新发送原来的帧2021年12月8日星期三21时18分6秒29差错控制（续）为了实现停等为了实现停等ARQ协议，发送站必须有一个计时器，每发出一帧就开始计时。协议，发送站必须有一个计时器，每发出一帧就开始计时。计时间隔的长度不能小于帧在链路上旅行一个来回的时间。发送站必须把已计时间隔的长度不能小于帧在链路上旅

47、行一个来回的时间。发送站必须把已发出帧的保存到计时器超时，以便需要时重发。接收站则必须记住已收到的发出帧的保存到计时器超时，以便需要时重发。接收站则必须记住已收到的帧编号，直到下一个帧来到并进行了比较之后。尽管增加了这些发送和接收帧编号，直到下一个帧来到并进行了比较之后。尽管增加了这些发送和接收的开销，但是这种协议比起下边要讨论的协议仍以其简单性见长。然而它的的开销，但是这种协议比起下边要讨论的协议仍以其简单性见长。然而它的缺点也是明显的：有些情况下效率不高缺点也是明显的：有些情况下效率不高2021年12月8日星期三21时18分6秒30差错控制（续）后退后退N帧帧ARQ协议协议滑动窗口技术和自

48、动请求重发技术的结合称为连续滑动窗口技术和自动请求重发技术的结合称为连续ARQ协议，分为后退协议，分为后退N帧帧ARQ协议和选择重发协议和选择重发ARQ协议。协议。后退后退N帧帧ARQ就是从出错处重发已发出过的就是从出错处重发已发出过的N个帧。我们可以用下面的方个帧。我们可以用下面的方案实现后退案实现后退N帧帧ARQ协议：协议：（1）发送站按照窗口中的帧编号顺序地连续发送帧。收到一个肯定应答信）发送站按照窗口中的帧编号顺序地连续发送帧。收到一个肯定应答信号窗口向前滑动，使其后沿对准尚未得到肯定应答的最小帧编号，窗口大号窗口向前滑动，使其后沿对准尚未得到肯定应答的最小帧编号，窗口大小保持为小保持

49、为W。（2）接收站的窗口大小为）接收站的窗口大小为1。每接收到一个帧后进行校验，并与窗口中的。每接收到一个帧后进行校验，并与窗口中的帧编号进行比较，若校验无误且编号落在窗口之内，则送回肯定应答信号帧编号进行比较，若校验无误且编号落在窗口之内，则送回肯定应答信号ACK，并把窗口向前滑动一格；若校验有错则发回否定应答信号，并把窗口向前滑动一格；若校验有错则发回否定应答信号NAK，窗，窗口保持不动；若收到的帧编号与窗口中的帧编号不符则丢弃该帧，不予应口保持不动；若收到的帧编号与窗口中的帧编号不符则丢弃该帧，不予应答，窗口仍保持不动。答，窗口仍保持不动。2021年12月8日星期三21时18分6秒31差

50、错控制（续） （3）如果发送站收到窗口中某个帧的否定应答信号，无论当时已发送到）如果发送站收到窗口中某个帧的否定应答信号，无论当时已发送到哪个帧，都退回到出错帧重发该帧及其后续帧。由于从一个帧发出到收到哪个帧，都退回到出错帧重发该帧及其后续帧。由于从一个帧发出到收到该帧的否定应答信号的时间最少为该帧的否定应答信号的时间最少为 2a1个帧时，所以要后退个帧时，所以要后退 N=2a1个个帧，因此这个协议叫做后退帧，因此这个协议叫做后退N帧帧ARQ协议。协议。（4）如果发送站发出的某个帧丢失了，或是应答信号丢失了，则发送）如果发送站发出的某个帧丢失了，或是应答信号丢失了，则发送站的计时器会发现这种情

51、况，这时也要后退站的计时器会发现这种情况，这时也要后退N帧重发。由于发送站是连续帧重发。由于发送站是连续地发送，所以要对已发出而尚没有得到应答的每个帧保持一个计时器。并地发送，所以要对已发出而尚没有得到应答的每个帧保持一个计时器。并且所有计时器的计时间隔都等于或大于且所有计时器的计时间隔都等于或大于2a1个帧时。个帧时。040321ACK1654325DDE107432D165ACK4ACK3NAK2ACK2ACK6ACK52021年12月8日星期三21时18分6秒32差错控制（续）在全双工通信中应答信号可以由反方向传送的数据帧在全双工通信中应答信号可以由反方向传送的数据帧“捎带捎带”送回，这

52、种机制送回，这种机制进一步减小了通信开销，然而也带来了一定的问题。在很多捎带方案中，无论进一步减小了通信开销，然而也带来了一定的问题。在很多捎带方案中，无论是否发送单独的应答信号，反向数据帧中的应答字段都要捎带一个应答，这样是否发送单独的应答信号，反向数据帧中的应答字段都要捎带一个应答，这样就可能出现对同一个帧的重复应答。就可能出现对同一个帧的重复应答。假定帧编号字段为假定帧编号字段为3位长，发送窗口尺寸为位长，发送窗口尺寸为8（显然不能大于（显然不能大于8）。当发送器收）。当发送器收到一个单独的到一个单独的ACK1后，把窗口推进到后沿为后，把窗口推进到后沿为1，前沿为，前沿为0的位置。即发送

53、窗口的位置。即发送窗口现在包含的帧号为现在包含的帧号为l、2、3、4、5、6、7和和0。如果这时又收到一个捎带回的。如果这时又收到一个捎带回的ACK1，发送器如何动作呢？这后一个，发送器如何动作呢？这后一个ACK1可能表示窗口中的所有帧都未曾接可能表示窗口中的所有帧都未曾接收，也可能意味着窗口中的帧都已正确接收。然而，如果规定窗口的大小为收，也可能意味着窗口中的帧都已正确接收。然而，如果规定窗口的大小为7，则就可以避免这种二义性。这就解释了我们为什么限制窗口大小则就可以避免这种二义性。这就解释了我们为什么限制窗口大小W2k-1。2021年12月8日星期三21时18分6秒33差错控制（续）选择重

54、发选择重发ARQ协议协议在后退在后退N帧帧ARQ协议中，接收方的窗口大小总是协议中，接收方的窗口大小总是1。这意味着接收站只能按。这意味着接收站只能按顺序地接收，按顺序地发回肯定应答信号，对于没有按顺序到达的帧则丢顺序地接收，按顺序地发回肯定应答信号，对于没有按顺序到达的帧则丢弃之，以后还要重新发送和接收，这将浪费很多链路带宽。如果接收方的弃之，以后还要重新发送和接收，这将浪费很多链路带宽。如果接收方的窗口也可以开到窗口也可以开到W那么大，则允许不按顺序的接收，只是选择性地重发出那么大，则允许不按顺序的接收，只是选择性地重发出错或丢失的帧。这样我们得到一种更有效的协议错或丢失的帧。这样我们得到

55、一种更有效的协议选择重发选择重发ARQ协议。协议。040321ACK110762543E1327625410ACK7ACK6NAK2ACK2ACK1ACK02021年12月8日星期三21时18分6秒34差错控制（续）对于选择重发对于选择重发ARQ协议，窗口的大小会受到更多的限制。若假设帧编号为协议，窗口的大小会受到更多的限制。若假设帧编号为3位，发送和接收窗口大小都是位，发送和接收窗口大小都是7，考虑下面的情况；，考虑下面的情况；（1）发送窗口和接收窗口中的帧编号都是）发送窗口和接收窗口中的帧编号都是0到到6；（2）发送站发出）发送站发出0到到6号帧，但尚未得到肯定应答，窗口不能向前滑动；号帧

56、，但尚未得到肯定应答，窗口不能向前滑动；（3）接收站正确地接收了）接收站正确地接收了0至至6号帧，发出了肯定应答号帧，发出了肯定应答ACK7，因而接收窗，因而接收窗口向前滑动，新的窗口中的帧编号为口向前滑动，新的窗口中的帧编号为7、0、1、2、3、4和和5；（4）ACK7丢失，发送站定时器超时，重发丢失，发送站定时器超时，重发0号帧；号帧；（5）接收站收到）接收站收到0号帧并看到该帧编号落在接收窗口内，以为是新的号帧并看到该帧编号落在接收窗口内，以为是新的0号号帧而保存起来。认为帧而保存起来。认为7号帧丢失了（其实发送站从未发出过），并继续接收号帧丢失了（其实发送站从未发出过），并继续接收重复

57、发来的重复发来的1、2、3、4和和5号帧。号帧。2021年12月8日星期三21时18分6秒35差错控制（续）协议失败的原因是由于发送站没有收到肯定应答窗口没有向前滑动，而接收协议失败的原因是由于发送站没有收到肯定应答窗口没有向前滑动，而接收窗口向前滑动了最大的距离（原窗口中的帧已全部接收）。这时，在新的接窗口向前滑动了最大的距离（原窗口中的帧已全部接收）。这时，在新的接收窗口和原来的发送窗口中仍有相同的帧编号，造成了接收器误把重发的老收窗口和原来的发送窗口中仍有相同的帧编号，造成了接收器误把重发的老帧当作新帧的错误。避免这种错误的办法是缩小窗口，使得接收窗口向前滑帧当作新帧的错误。避免这种错误

58、的办法是缩小窗口，使得接收窗口向前滑动最大距离后不再与老的接收窗口重叠，显然当窗口大小为帧编号数的一半动最大距离后不再与老的接收窗口重叠，显然当窗口大小为帧编号数的一半时就可达到这个效果，所以采用选择重发时就可达到这个效果，所以采用选择重发ARQ协议时窗口的最大值应为帧编协议时窗口的最大值应为帧编号数的一半，即号数的一半，即W发发=W收收 2k-1。2021年12月8日星期三21时18分6秒36差错控制（续）没有错误时，停等协议的效率为没有错误时，停等协议的效率为有错误的情况下，一个帧可能要经过多次传输才能成功。因而上式的分母乘以有错误的情况下，一个帧可能要经过多次传输才能成功。因而上式的分母

59、乘以传输的次数就得到停等传输的次数就得到停等 ARQ协议的效率协议的效率 为了对为了对Nr给出一个数量的表示，我们假设帧出错的概率为给出一个数量的表示，我们假设帧出错的概率为P，并假设应答信号会，并假设应答信号会出错，则经过出错，则经过i次尝试才能成功地传送一帧的概率为次尝试才能成功地传送一帧的概率为Pi-1（1P）。于是有）。于是有 因而因而 这是停等这是停等 ARQ协议的最大效率协议的最大效率fpftttE2)2(fprfttNtEPpiiPrNi11)1 (11121apE2021年12月8日星期三21时18分6秒37差错控制（续）对于选择对于选择ARQ协议可用类似的方法处理。前面提到，

60、当窗口尺寸协议可用类似的方法处理。前面提到，当窗口尺寸W大于大于 2a1时，链路利用率为时，链路利用率为 1，当窗口尺寸，当窗口尺寸W小于小于 2al时，链路利用率为时，链路利用率为 E= W(2a1)。如果假定一个帧选择性地重传。如果假定一个帧选择性地重传Nr次，我们得到选择重发次，我们得到选择重发ARQ协协议的最大效率为议的最大效率为 2021年12月8日星期三21时18分6秒38差错控制（续）121aPPE)1)(12()1 (WPPaPWE若考虑到当若考虑到当W2a+1时，时，N近似等于近似等于2a+1，则有，则有当当W2a+1时，时，N= W，故有，故有后退后退N帧帧ARQ协议的协率