第3章：数据链路控制

1、计算机网络计算机网络第第3 3章章 数据链路层数据链路层23.1 3.1 数据链路层的基本概念数据链路层的基本概念 链路链路(link)(link)是一条无源的点到点的物理线路段，是一条无源的点到点的物理线路段，中间没有任何其他的交换结点。中间没有任何其他的交换结点。 一条链路只是一条通路的一个组成部分一条链路只是一条通路的一个组成部分。 数据链路数据链路(data link) (data link) 除了物理线路外，还必除了物理线路外，还必须有通信协议来控制这些数据的传输。若把实须有通信协议来控制这些数据的传输。若把实现这些协议的硬件和软件加到链路上，就构成现这些协议的硬件和软件加到链路上，

2、就构成了数据链路。了数据链路。 现在最常用的方法是使用适配器（即网卡）来实现现在最常用的方法是使用适配器（即网卡）来实现这些协议的硬件和软件。这些协议的硬件和软件。 一般的适配器都包括了数据链路层和物理层这两层一般的适配器都包括了数据链路层和物理层这两层的功能。的功能。 计算机网络计算机网络第第3 3章章 数据链路层数据链路层3数据链路层像个数字管道数据链路层像个数字管道 常常在两个对等的数据链路层之间画出一个数常常在两个对等的数据链路层之间画出一个数字管道，而在这条数字管道上传输的数据单位字管道，而在这条数字管道上传输的数据单位是是帧帧。 早期的数据通信协议曾叫作早期的数据通信协议曾叫作通信

3、规程通信规程(procedure)(procedure)。因此在数据链路层，规程和协。因此在数据链路层，规程和协议是同义语。议是同义语。 结点结点帧帧计算机网络计算机网络第第3 3章章 数据链路层数据链路层4数据链路层的主要功能数据链路层的主要功能(1) 链路管理链路管理 (2) (2) 帧定界帧定界 (3) (3) 流量控制流量控制(4) (4) 差错控制差错控制 (5) (5) 将数据和控制信息区分开将数据和控制信息区分开 (6) (6) 透明传输透明传输 (7) (7) 寻址寻址 计算机网络计算机网络第第3 3章章 数据链路层数据链路层53.2 3.2 停止等待协议停止等待协议 4.2.

4、1 4.2.1 完全理想化的数据传输完全理想化的数据传输先研究一下数据链路层的模型。先研究一下数据链路层的模型。计算机网络计算机网络第第3 3章章 数据链路层数据链路层6数据链路层的简单模型数据链路层的简单模型局域网广域网主机 H1主机 H2路由器 R1路由器 R2路由器 R3电话网局域网主机 H1 向 H2 发送数据链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层R1R2R3H1H2从层次上来看数据的流动计算机网络计算机网络第第3 3章章 数据链路层数据链路层7数据链路层的简单模型数据链路层的简单模型( ( 续）续）局域网广域

5、网主机 H1主机 H2路由器 R1路由器 R2路由器 R3电话网局域网主机 H1 向 H2 发送数据链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层R1R2R3H1H2仅从数据链路层观察帧的流动计算机网络计算机网络第第3 3章章 数据链路层数据链路层8 完全理想化的数据传输完全理想化的数据传输数据链路层主机 A缓存主机 B数据链路AP2AP1缓存发送方接收方帧高层帧计算机网络计算机网络第第3 3章章 数据链路层数据链路层9完全理想化的数据传输完全理想化的数据传输所基于的两个假定所基于的两个假定 假定假定 1 1： 链路是理想的传

6、输信道，所传送的链路是理想的传输信道，所传送的 任何数据既不会出差错也不会丢失。任何数据既不会出差错也不会丢失。 假定假定 2 2： 不管发方以多快的速率发送数据，不管发方以多快的速率发送数据， 收方总是来得及收下，并及时上交主机。收方总是来得及收下，并及时上交主机。 这个假定就相当于认为：接收端向主机交付数据这个假定就相当于认为：接收端向主机交付数据的速率永远不会低于发送端发送数据的速率。的速率永远不会低于发送端发送数据的速率。 结果：既不需要流量控制，也不需要差错控制结果：既不需要流量控制，也不需要差错控制 计算机网络计算机网络第第3 3章章 数据链路层数据链路层10完全理想化的数据传输完

7、全理想化的数据传输ABDATADATADATADATA送主机 B送主机 B送主机 B送主机 B时间计算机网络计算机网络第第3 3章章 数据链路层数据链路层113.2.2 3.2.2 具有最简单流量控制的具有最简单流量控制的数据链路层协议数据链路层协议 现在去掉上述的第二个假定现在去掉上述的第二个假定。但是，仍然保。但是，仍然保留第一个假定，即主机留第一个假定，即主机 A A 向主机向主机 B B传输数据传输数据的信道仍然是无差错的理想信道。然而现在的信道仍然是无差错的理想信道。然而现在不能保证接收端向主机交付数据的速率永远不能保证接收端向主机交付数据的速率永远不低于发送端发送数据的速率。不低于

8、发送端发送数据的速率。 由收方控制发方的数据流由收方控制发方的数据流，乃是计算机网络，乃是计算机网络中流量控制的一个基本方法。中流量控制的一个基本方法。 计算机网络计算机网络第第3 3章章 数据链路层数据链路层12具有最简单流量控制的具有最简单流量控制的数据链路层协议算法数据链路层协议算法在发送结点：在发送结点： (1) (1) 从主机取一个数据帧。从主机取一个数据帧。 (2) (2) 将数据帧送到数据链路层的发送缓存。将数据帧送到数据链路层的发送缓存。 (3) (3) 将发送缓存中的数据帧发送出去。将发送缓存中的数据帧发送出去。 (4) (4) 等待。等待。 (5) (5) 若收到由接收结点

9、发过来的信息若收到由接收结点发过来的信息( (此信息此信息 的格式与内容可由双方事先商定好的格式与内容可由双方事先商定好) )， 则从主机取一个新的数据帧，然后转到则从主机取一个新的数据帧，然后转到(2)(2)。计算机网络计算机网络第第3 3章章 数据链路层数据链路层13具有最简单流量控制的具有最简单流量控制的数据链路层协议算法（续）数据链路层协议算法（续）在接收结点：在接收结点： (1) (1) 等待。等待。 (2) (2) 若收到由发送结点发过来的数据帧，若收到由发送结点发过来的数据帧， 则将其放入数据链路层的接收缓存。则将其放入数据链路层的接收缓存。 (3) (3) 将接收缓存中的数据帧

10、上交主机。将接收缓存中的数据帧上交主机。 (4) (4) 向发送结点发一信息，表示数据帧已向发送结点发一信息，表示数据帧已 经上交给主机。经上交给主机。 (5) (5) 转到转到(1)(1)。计算机网络计算机网络第第3 3章章 数据链路层数据链路层14两种情况的对比（传输均无差错）两种情况的对比（传输均无差错）ABDATADATADATADATA送主机 B送主机 B送主机 B送主机 BABDATA送主机 BDATA送主机 B时间不需要流量控制需要流量控制计算机网络计算机网络第第3 3章章 数据链路层数据链路层153.2.3 3.2.3 实用的停止等待协议实用的停止等待协议去掉上述的二个假定去掉

11、上述的二个假定 策略：策略：当发送方发完一帧后，即停止发送，等待当发送方发完一帧后，即停止发送，等待对方的应答，如果收到对方的对方的应答，如果收到对方的肯定应答肯定应答，则接着，则接着发发送下一个帧送下一个帧；如果收到；如果收到否定应答否定应答或或超过规定的时间超过规定的时间没有收到没有收到肯定应答，则肯定应答，则重发重发该帧。该帧。 特点：特点：在进行流量控制的同时也进行了差错控制，在进行流量控制的同时也进行了差错控制，实现可靠的数据传输。实现可靠的数据传输。计算机网络计算机网络第第3 3章章 数据链路层数据链路层16时间ABDATA0送主机ACKDATA1送主机ACK(a) 正常情况ABD

12、ATA0DATA0送主机ACK(c) 数据帧丢失重传tout丢失 ！ABDATA0送主机ACKDATA0丢弃ACK(d) 确认帧丢失重传tout丢失 ！ABDATA0NAKDATA0送主机ACK(b) 数据帧出错重传出错四种情况四种情况计算机网络计算机网络第第3 3章章 数据链路层数据链路层17讨论几种数据传输的情况讨论几种数据传输的情况1 1、正常情况。、正常情况。传输可靠、不出错不丢失。传输可靠、不出错不丢失。2 2、数据帧出错。、数据帧出错。通过通过出错重发出错重发机制来解决，若机制来解决，若连续重传超过一定次数则停止发送，向上一级连续重传超过一定次数则停止发送，向上一级报告故障情况。报

13、告故障情况。3 3、数据帧丢失。、数据帧丢失。发送方发送的数据帧因严重干发送方发送的数据帧因严重干扰不能到达接收方，接收方不回答确认帧扰不能到达接收方，接收方不回答确认帧ACKACK，通过通过超时重发超时重发机制来解决。机制来解决。4 4、数据帧无误但返回的确认帧丢失，、数据帧无误但返回的确认帧丢失，通过通过超时超时重发重发机制来解决。机制来解决。 解决重复帧：解决重复帧：对每个数据帧对每个数据帧赋序号赋序号，即每发一，即每发一帧，序号加帧，序号加1 1。计算机网络计算机网络第第3 3章章 数据链路层数据链路层18超时计时器的作用超时计时器的作用 结点结点A A发送完一个数据帧时，就启动一个发

14、送完一个数据帧时，就启动一个超时超时计时器计时器(timeout timer)(timeout timer)。 计时器又称为计时器又称为定时器定时器。 若到了超时计时器所设置的重传时间若到了超时计时器所设置的重传时间 t toutout而仍而仍收不到结点收不到结点 B B 的任何确认帧，则结点的任何确认帧，则结点 A A 就重就重传前面所发送的这一数据帧。传前面所发送的这一数据帧。 一般可将重传时间选为略大于一般可将重传时间选为略大于“从发完数据帧从发完数据帧到收到确认帧所需的平均时间到收到确认帧所需的平均时间”。 计算机网络计算机网络第第3 3章章 数据链路层数据链路层19解决重复帧的问题解

15、决重复帧的问题 使每一个数据帧带上不同的发送序号。每发送使每一个数据帧带上不同的发送序号。每发送一个新的数据帧就把它的发送序号加一个新的数据帧就把它的发送序号加 1 1。 若结点若结点 B B 收到发送序号相同的数据帧，就表收到发送序号相同的数据帧，就表明出现了重复帧。这时应丢弃重复帧，因为已明出现了重复帧。这时应丢弃重复帧，因为已经收到过同样的数据帧并且也交给了主机经收到过同样的数据帧并且也交给了主机 B B。 但此时结点但此时结点 B B 还必须向还必须向 A A 发送确认帧发送确认帧 ACKACK，因为因为 B B 已经知道已经知道 A A 还没有收到上一次发过去还没有收到上一次发过去的

16、确认帧的确认帧 ACKACK。 计算机网络计算机网络第第3 3章章 数据链路层数据链路层20帧的编号问题帧的编号问题 任何一个编号系统的序号所占用的比特数一定任何一个编号系统的序号所占用的比特数一定是有限的。因此，经过一段时间后，发送序号是有限的。因此，经过一段时间后，发送序号就会重复。就会重复。 序号占用的比特数越少，数据传输的额外开销序号占用的比特数越少，数据传输的额外开销就越小。就越小。 对于停止等待协议，由于每发送一个数据帧就对于停止等待协议，由于每发送一个数据帧就停止等待，因此用一个比特来编号就够了。停止等待，因此用一个比特来编号就够了。 一个比特可表示一个比特可表示 0 和和 1

17、两种不同的序号。两种不同的序号。 计算机网络计算机网络第第3 3章章 数据链路层数据链路层21帧的发送序号帧的发送序号 数据帧中的发送序号数据帧中的发送序号 N(S) N(S) 以以 0 0 和和 1 1 交替的交替的方式出现在数据帧中。方式出现在数据帧中。 每发一个新的数据帧，发送序号就和上次发送每发一个新的数据帧，发送序号就和上次发送的不一样。用这样的方法就可以使收方能够区的不一样。用这样的方法就可以使收方能够区分开新的数据帧和重传的数据帧了。分开新的数据帧和重传的数据帧了。 计算机网络计算机网络第第3 3章章 数据链路层数据链路层22可靠传输可靠传输 虽然物理层在传输比特时会出现差错，虽

18、然物理层在传输比特时会出现差错，但由于数据链路层的停止等待协议采用但由于数据链路层的停止等待协议采用了有效的检错重传机制，数据链路层对了有效的检错重传机制，数据链路层对上面的网络层就可以提供上面的网络层就可以提供可靠传输可靠传输的服的服务。务。 计算机网络计算机网络第第3 3章章 数据链路层数据链路层23停止等待协议停止等待协议 ARQ ARQ 的优缺点的优缺点 优点：比较简单优点：比较简单 。 缺点：通信信道的利用率不高，也就是说，缺点：通信信道的利用率不高，也就是说，信道还远远没有被数据比特填满。信道还远远没有被数据比特填满。 为了克服这一缺点，就产生了另外两种协议，为了克服这一缺点，就产

19、生了另外两种协议，即连续即连续 ARQ ARQ 和选择重传和选择重传 ARQARQ。这将在后面进。这将在后面进一步讨论。一步讨论。 计算机网络计算机网络第第3 3章章 数据链路层数据链路层243.3 差错检测差错检测 奇偶校验码奇偶校验码 奇（偶）校验奇（偶）校验 垂直奇（偶）校验垂直奇（偶）校验 水平奇（偶）校验水平奇（偶）校验 水平垂直奇（偶）校验（方阵码）水平垂直奇（偶）校验（方阵码） 循环冗余编码循环冗余编码CRC 目前应用最广的检错码编码方法之一目前应用最广的检错码编码方法之一计算机网络计算机网络第第3 3章章 数据链路层数据链路层25计算机网络计算机网络第第3 3章章 数据链路层数

20、据链路层263.3.1 3.3.1 奇偶校验码奇偶校验码编码规则编码规则：在信源输出的信息码后面附加一个校：在信源输出的信息码后面附加一个校验元，使得码组中验元，使得码组中“1”“1”的个数是奇数或偶数；的个数是奇数或偶数；在接收端再检测在接收端再检测“1”“1”的个数，根据是否与发的个数，根据是否与发送端原则相符判断传送中是否出现错码。送端原则相符判断传送中是否出现错码。 奇校验：奇校验： 11001101 11001101 11001101 110011010 0 偶校验：偶校验： 11001101 11001101 11001101 110011011 1 奇偶校验能查出传输中任意奇偶校

21、验能查出传输中任意奇数奇数个错，但个错，但不能发现偶数个错误。不能发现偶数个错误。计算机网络计算机网络第第3 3章章 数据链路层数据链路层27垂直奇偶校验垂直奇偶校验原理：原理：把要发送的信息码元按定长把要发送的信息码元按定长m m比特分为若干段，比特分为若干段，每段每段纵向排列纵向排列，对，对每列每列的信息元进行奇偶校验，得到的信息元进行奇偶校验，得到的校验元附在每列后面，传输时按的校验元附在每列后面，传输时按列列的次序传输的次序传输 。小小 组组码码 字字信信 息息 元元1 11 1 0 1 11 1 0 1 1 2 20 1 1 0 10 1 1 0 13 31 1 0 0 01 1 0

22、 0 04 41 1 0 0 01 1 0 0 05 51 0 0 1 01 0 0 1 0校验元校验元0 0 1 0 00 0 1 0 0传输数据：传输数据：101110 111100 010001 100010 110000计算机网络计算机网络第第3 3章章 数据链路层数据链路层28水平奇偶校验水平奇偶校验原理：原理：把要发送的信息码元按定长把要发送的信息码元按定长m m比特分为若干段，比特分为若干段，然后每段然后每段纵向排列纵向排列，共计，共计n n行，对行，对每行每行的信息元进行奇的信息元进行奇偶校验，得到的校验元附在每行后面；传输时也按偶校验，得到的校验元附在每行后面；传输时也按列列

23、的次序传输。的次序传输。小组小组码码 字字 信息元信息元校验元校验元1 11 1 0 1 11 1 0 1 1 0 02 20 1 1 0 10 1 1 0 1 1 13 31 1 0 0 01 1 0 0 0 0 04 41 1 0 0 01 1 0 0 0 0 05 51 0 0 1 01 0 0 1 0 0 0传输数据：传输数据：10111 11110 01000 10001 11000 01000计算机网络计算机网络第第3 3章章 数据链路层数据链路层29水平垂直奇偶校验水平垂直奇偶校验原理：是原理：是水平和垂直水平和垂直两个方向的奇偶校验的结合，两个方向的奇偶校验的结合，又称又称纵横

24、奇偶检验纵横奇偶检验和和方阵奇偶校验方阵奇偶校验。传输时也。传输时也按按列列的次序传输。的次序传输。小组小组码码 字字信信 息息 元元校验元校验元1 11 1 0 1 11 1 0 1 10 02 20 1 1 0 10 1 1 0 11 13 31 1 0 0 01 1 0 0 00 04 41 1 0 0 01 1 0 0 00 05 51 0 0 1 01 0 0 1 00 0校验元校验元0 0 1 0 00 0 1 0 01 1传输数据：传输数据：101110 111100 010001 100010 110000 010001计算机网络计算机网络第第3 3章章 数据链路层数据链路层3

25、03.3.2 3.3.2 循环冗余检验的原理循环冗余检验的原理 在数据链路层传送的帧中，广泛使用了在数据链路层传送的帧中，广泛使用了循环冗余检验循环冗余检验 CRC CRC 的检错技术。的检错技术。 假设待传送的数据假设待传送的数据 M M = 1010001101 = 1010001101（共（共k k bit bit）。我们在）。我们在M M 的后面再添加供差错的后面再添加供差错检测用的检测用的 n n bit bit 冗余码冗余码一起发送。一起发送。 计算机网络计算机网络第第3 3章章 数据链路层数据链路层31冗余码的计算冗余码的计算 用二进制的模用二进制的模 2 2 运算进行运算进行

26、2 2n n 乘乘 M M 的运的运算，这相当于在算，这相当于在 M M 后面添加后面添加 n n 个个 0 0。 得到的得到的 ( (k k + + n n) bit ) bit 的数除以事先选定的数除以事先选定好的长度为好的长度为 ( (n n + 1) bit + 1) bit 的数的数 P P，得出，得出商是商是 Q Q 而余数是而余数是 R R，余数，余数 R R 比除数比除数 P P 至少要少至少要少1 1 个比特。个比特。 计算机网络计算机网络第第3 3章章 数据链路层数据链路层32冗余码的计算举例冗余码的计算举例 设设 n n = 5, = 5, P P = 110101 =

27、110101，模，模 2 2 运算的结运算的结果是：商果是：商 Q Q = 1101010110 = 1101010110， 余数余数R R = 01110 = 01110。 将余数将余数 R R 作为冗余码添加在数据作为冗余码添加在数据 M M 的的后面发送出去，即发送的数据是后面发送出去，即发送的数据是101000110101110101000110101110，或，或 2 2n nM M + + R R。 计算机网络计算机网络第第3 3章章 数据链路层数据链路层33 1101010110 Q 商 除数 P 110101 101000110100000 2nM 被除数 110101 111

28、011 110101 111010 110101 111110 110101 101100 110101 110010 110101 01110 R 余数循环冗余检验的原理说明循环冗余检验的原理说明 计算机网络计算机网络第第3 3章章 数据链路层数据链路层34标准标准CRCCRC生成多项式生成多项式G G（x x） CRC-12 G（x）= x12+x11+x3+x2+x+1 CRC-16 G（x）= x16+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

29、+x4 + x2+x+1 计算机网络计算机网络第第3 3章章 数据链路层数据链路层35帧检验序列帧检验序列 FCSFCS 在数据后面添加上的冗余码称为在数据后面添加上的冗余码称为帧检验帧检验序列序列 FCS (Frame Check Sequence)FCS (Frame Check Sequence)。 循环冗余检验循环冗余检验 CRC CRC 和帧检验序列和帧检验序列 FCSFCS并并不等同。不等同。 CRC CRC 是一种常用的是一种常用的检错方法检错方法，而，而 FCS FCS 是添是添加在数据后面的加在数据后面的冗余码冗余码。 FCS FCS 可以用可以用 CRC CRC 这种方法得

30、出，但这种方法得出，但 CRC CRC 并并非用来获得非用来获得 FCS FCS 的惟一方法。的惟一方法。 计算机网络计算机网络第第3 3章章 数据链路层数据链路层36检测出差错检测出差错 只要得出的余数只要得出的余数 R R 不为不为 0 0，就表示检测，就表示检测到了到了差错差错。 但这种检测方法并不能确定究竟是哪一但这种检测方法并不能确定究竟是哪一个或哪几个比特出现了差错。个或哪几个比特出现了差错。 一旦检测出差错，就一旦检测出差错，就丢弃丢弃这个出现差错这个出现差错的帧。的帧。 只要经过严格的挑选，并使用位数足够只要经过严格的挑选，并使用位数足够多的除数多的除数 P P，那么出现检测不

31、到的差错，那么出现检测不到的差错的概率就很小很小。的概率就很小很小。 计算机网络计算机网络第第3 3章章 数据链路层数据链路层37应当注意应当注意 仅用循环冗余检验仅用循环冗余检验 CRC CRC 差错检测技术只能做差错检测技术只能做到无差错到无差错接受接受(accept)(accept)。 “无差错接受无差错接受”是指：是指：“凡是接受的帧（即凡是接受的帧（即不不包括丢弃的帧包括丢弃的帧），我们都能以非常接近于），我们都能以非常接近于 1 1 的的概率认为这些帧在传输过程中没有产生差错概率认为这些帧在传输过程中没有产生差错”。 也就是说：也就是说：“凡是接受的帧都没有传输差错凡是接受的帧都没

32、有传输差错”（有差错的帧就丢弃而不接受）。（有差错的帧就丢弃而不接受）。 要做到要做到“可靠传输可靠传输”（即发送什么就收到什么）（即发送什么就收到什么）就必须再加上就必须再加上确认确认和和重传重传机制。机制。 计算机网络计算机网络第第3 3章章 数据链路层数据链路层383.4“滑动窗口滑动窗口”方式流量控制方式流量控制 允许进行多帧传送允许进行多帧传送 接收方的缓冲空间为接收方的缓冲空间为W W 帧帧 发送方无需收到对方的应答（发送方无需收到对方的应答（ACKACK）可最多连续发送）可最多连续发送W W 帧帧数据数据 每一帧都用一个序号每一帧都用一个序号( (亦称亦称“序列号序列号”) )加

33、以标识加以标识 接收方的接收方的ACKACK帧中包括了下一个希望接收的帧的序号帧中包括了下一个希望接收的帧的序号 这个这个ACKACK也隐含地表明接收方准备接收下一组也隐含地表明接收方准备接收下一组W W 帧的数据，帧的数据，其起始帧的序号已在其起始帧的序号已在ACKACK中指定了。中指定了。 序号大小受字段长度（序号大小受字段长度（k k位）限制位）限制 帧以帧以2 2k k 为模编号，字段长度为为模编号，字段长度为k k 比特时，序号范围为比特时，序号范围为0 0 2 2k k -1-1。计算机网络计算机网络第第3 3章章 数据链路层数据链路层39何谓何谓“滑动窗口滑动窗口” 术语术语“滑

34、动窗口滑动窗口”中的中的“窗口窗口”一词，指的是发一词，指的是发送方和接收方各自建立的额外缓冲区。这个窗口送方和接收方各自建立的额外缓冲区。这个窗口在收发两方均可存储数据帧，并且对请求确认前在收发两方均可存储数据帧，并且对请求确认前可以传送的最大帧数进行了限制。帧的确认可在可以传送的最大帧数进行了限制。帧的确认可在窗口被填满前随时进行，并且只要窗口未满，传窗口被填满前随时进行，并且只要窗口未满，传输就可以继续进行。输就可以继续进行。 术语术语“滑动窗口滑动窗口”中的中的“滑动滑动”一词，指的是在一词，指的是在帧的收发过程中，这个帧的收发过程中，这个“窗口窗口”的大小和位置都的大小和位置都是可以

35、变动的。是可以变动的。计算机网络计算机网络第第3 3章章 数据链路层数据链路层40“滑动窗口滑动窗口”流量控制示意图流量控制示意图计算机网络计算机网络第第3 3章章 数据链路层数据链路层41发送方滑动窗口发送方滑动窗口计算机网络计算机网络第第3 3章章 数据链路层数据链路层42接收方滑动窗口接收方滑动窗口计算机网络计算机网络第第3 3章章 数据链路层数据链路层43“滑动窗口滑动窗口”流量控制示例流量控制示例 (1)(1)P168图7.4计算机网络计算机网络第第3 3章章 数据链路层数据链路层44“滑动窗口滑动窗口”流量控制示例流量控制示例 (2)(2)计算机网络计算机网络第第3 3章章 数据链

36、路层数据链路层45滑动窗口技术的增强滑动窗口技术的增强 至此所叙述的机制的确提供了一种流量控制方至此所叙述的机制的确提供了一种流量控制方式：使接收方只能接收在它最后确认的那一帧式：使接收方只能接收在它最后确认的那一帧之后的之后的W W帧数据。大部分协议还允许站点发送帧数据。大部分协议还允许站点发送RNRRNR（接收方未准备好）的信息来中止帧的传（接收方未准备好）的信息来中止帧的传送，该信息对之前（已接收）的各帧进行了确送，该信息对之前（已接收）的各帧进行了确认，但禁止发送后续各帧。以后，该站点必须认，但禁止发送后续各帧。以后，该站点必须发送一个正常的确认信息才能使（滑动）窗口发送一个正常的确认

37、信息才能使（滑动）窗口重新开启。重新开启。计算机网络计算机网络第第3 3章章 数据链路层数据链路层46“稍带稍带”技术技术 双工通信使用所谓双工通信使用所谓“稍带技术稍带技术”。每一个数据帧都有两。每一个数据帧都有两个字段：一个存放个字段：一个存放该帧的序号该帧的序号，一个存放，一个存放确认用的序号确认用的序号。 如果某个站点既要发送数据也要发送应答，如果某个站点既要发送数据也要发送应答， 它可以把它可以把数据和确认放在一个帧里发送，以减少通信流量。数据和确认放在一个帧里发送，以减少通信流量。 如果某个站点没有数据发送，它便发送一个独立的确认如果某个站点没有数据发送，它便发送一个独立的确认帧。

38、帧。 如果某个站点只需发送数据但不需要发送确认，它要如果某个站点只需发送数据但不需要发送确认，它要将上一次确认时发过的序号重新发送一下。这是因为数将上一次确认时发过的序号重新发送一下。这是因为数据帧含有一个确认用的序号字段，而且这个字段中必须据帧含有一个确认用的序号字段，而且这个字段中必须存放在数据。当一个站点收到重复的确认时，只是简单存放在数据。当一个站点收到重复的确认时，只是简单地忽略这个重复的确认。地忽略这个重复的确认。计算机网络计算机网络第第3 3章章 数据链路层数据链路层473.5 3.5 连续连续 ARQ ARQ 协议协议4.5.1 4.5.1 连续连续 ARQ ARQ 协议的工作

39、原理协议的工作原理 在发送完一个数据帧后，不是停下来等待确在发送完一个数据帧后，不是停下来等待确认帧，而是可以连续再发送若干个数据帧。认帧，而是可以连续再发送若干个数据帧。 如果这时收到了接收端发来的确认帧，那么如果这时收到了接收端发来的确认帧，那么还可以接着发送数据帧。还可以接着发送数据帧。 由于减少了等待时间，整个通信的吞吐量就由于减少了等待时间，整个通信的吞吐量就提高了。提高了。 计算机网络计算机网络第第3 3章章 数据链路层数据链路层48连续连续 ARQ ARQ 协议的工作原理协议的工作原理 DATA0DATA1DATA2DATA3DATA4DATA5重传 DATA2重传 DATA3A

40、CK1ACK2ACK1 确认 DATA0ACK2 确认 DATA1DATA2 出错，丢弃DATA3 不按序，丢弃，重传 ACK2DATA4 不按序，丢弃，重传丢弃，重传 ACK2DATA5 不按序，丢弃，重传 ACK2ACK3ACK3 确认 DATA2ACK4 确认 DATA3ACK4重传 DATA5重传 DATA4超时重传时间ABtout送交主机送交主机?ACK2ACK2ACK2计算机网络计算机网络第第3 3章章 数据链路层数据链路层49需要注意：需要注意： (1) (1) 接收端接收端只按序接收只按序接收数据帧。虽然在有差错的数据帧。虽然在有差错的 2 2号帧号帧之后接着又收到了正确的之后

41、接着又收到了正确的 3 3 个数据帧，但接收端都必个数据帧，但接收端都必须将这些帧丢弃，因为在这些帧前面有一个须将这些帧丢弃，因为在这些帧前面有一个 2 2 号帧还号帧还没有收到。虽然丢弃了这些不按序的无差错帧，但应没有收到。虽然丢弃了这些不按序的无差错帧，但应重复发送已发送过的最后一个确认帧（防止确认帧丢重复发送已发送过的最后一个确认帧（防止确认帧丢失）。失）。(2) ACK1 (2) ACK1 表示确认表示确认 0 0 号帧号帧 DATA0DATA0，并期望下次收到，并期望下次收到 1 1 号帧；号帧；ACK2 ACK2 表示确认表示确认 1 1 号帧号帧 DATA1DATA1，并期望下次

42、收，并期望下次收到到 2 2 号帧。依此类推。号帧。依此类推。 计算机网络计算机网络第第3 3章章 数据链路层数据链路层50需要注意：需要注意： (3) 结点结点 A A 在每发送完一个数据帧时都要设置该帧的在每发送完一个数据帧时都要设置该帧的超超时计时器时计时器。如果在所设置的超时时间内收到确认帧，。如果在所设置的超时时间内收到确认帧，就立即将超时计时器清零。但若在所设置的超时时间就立即将超时计时器清零。但若在所设置的超时时间到了而未收到确认帧，就要重传相应的数据帧（仍需到了而未收到确认帧，就要重传相应的数据帧（仍需重新设置超时计时器）。重新设置超时计时器）。 在等不到在等不到 2 2 号帧

43、的确认而重传号帧的确认而重传 2 2 号数据帧时，号数据帧时，虽然结点虽然结点 A A 已经发完了已经发完了 5 5 号帧，但仍必须向回走，号帧，但仍必须向回走，将将 2 2号帧及其以后的各帧全部进行重传。连续号帧及其以后的各帧全部进行重传。连续 ARQ ARQ 又又称为称为Go-back-N ARQGo-back-N ARQ，意思是当出现差错必须重传时，意思是当出现差错必须重传时，要向回走要向回走 N N 个帧，然后再开始重传。个帧，然后再开始重传。 计算机网络计算机网络第第3 3章章 数据链路层数据链路层51需要注意：需要注意： (4) 4) 以上讲述的仅仅是连续以上讲述的仅仅是连续 AR

44、Q ARQ 协议的工作原协议的工作原理。协议在具体实现时还有许多的细节。例如，理。协议在具体实现时还有许多的细节。例如，用一个计时器就可实现相当于用一个计时器就可实现相当于 N N 个独立的超个独立的超时计时器的功能。时计时器的功能。 计算机网络计算机网络第第3 3章章 数据链路层数据链路层523.5.2 3.5.2 信道利用率信道利用率 由于每个数据帧都必须包括一定的控制信息由于每个数据帧都必须包括一定的控制信息( (如帧的序号、地址、同步信息以及其他的一如帧的序号、地址、同步信息以及其他的一些控制信息些控制信息) )，所以即使连续不停地发送数据，所以即使连续不停地发送数据帧，信道利用率帧，

45、信道利用率( (即扣除全部的控制信息后的即扣除全部的控制信息后的数据率与信道容量之比数据率与信道容量之比) )也不可能达到也不可能达到 100 %100 %。 当出现差错时当出现差错时( (这是不可避免的这是不可避免的) )，数据帧的不，数据帧的不断重传将进一步使信道利用率降低。断重传将进一步使信道利用率降低。 计算机网络计算机网络第第3 3章章 数据链路层数据链路层53最佳帧长最佳帧长 若数据帧的帧长取得很短，那么控制信若数据帧的帧长取得很短，那么控制信息在每一帧中所占的比例就增大，因而息在每一帧中所占的比例就增大，因而额外开销增大，这就导致信道利用率的额外开销增大，这就导致信道利用率的下降

46、。下降。 若帧长取得太长，则数据帧在传输过程若帧长取得太长，则数据帧在传输过程中出错的概率就增大，于是重传次数将中出错的概率就增大，于是重传次数将增大，这也会使信道利用率下降。增大，这也会使信道利用率下降。 由此可见，存在一个由此可见，存在一个最佳帧长最佳帧长，在此帧，在此帧长下信道的利用率最高。长下信道的利用率最高。 计算机网络计算机网络第第3 3章章 数据链路层数据链路层54发送窗口的最大值发送窗口的最大值 当用当用 n n 个比特进行编号时，则只有在发送窗个比特进行编号时，则只有在发送窗口的大小口的大小 W WT T 2 2n n 1 1时，连续时，连续 ARQ ARQ 协议才协议才能正

47、确运行。能正确运行。 例如，当采用例如，当采用 3 bit 3 bit 编码时，发送窗口的最编码时，发送窗口的最大值是大值是 7 7 而不是而不是 8 8。 假定：发送窗口为假定：发送窗口为8 8，发送方连续发送，发送方连续发送8 8个数据个数据幀幀，且全部正确到达接收方，但所有确认帧都，且全部正确到达接收方，但所有确认帧都丢失了，会出现什末情况？丢失了，会出现什末情况？计算机网络计算机网络第第3 3章章 数据链路层数据链路层553.3.3 “3.3.3 “选择拒绝选择拒绝”自动重传请求协自动重传请求协议议Selective Reject ARQSelective Reject ARQ 亦称为

48、亦称为“选择性重传选择性重传”（SREJSREJ） 只需重传被拒收的帧只需重传被拒收的帧 后续各帧仍由接收方接收并被缓存后续各帧仍由接收方接收并被缓存 优点优点 重传帧数降到了最小重传帧数降到了最小 缺点缺点 接收方必须保持一个足够大的缓冲存储区接收方必须保持一个足够大的缓冲存储区 接收方需要将重传的帧按正确顺序重新插入缓冲存接收方需要将重传的帧按正确顺序重新插入缓冲存储区的帧组中；发送方需要具有发送失序帧的能力。储区的帧组中；发送方需要具有发送失序帧的能力。 因此更复杂。通常用于卫星链路等。因此更复杂。通常用于卫星链路等。计算机网络计算机网络第第3 3章章 数据链路层数据链路层56选择拒绝协

49、议：数据帧损坏情况选择拒绝协议：数据帧损坏情况计算机网络计算机网络第第3 3章章 数据链路层数据链路层57选择拒绝选择拒绝 ARQ窗口的最大范围是：窗口的最大范围是： WR 2n/23.6 高级数据链路控制协议高级数据链路控制协议High Level Data Link Control 计算机网络计算机网络第第3 3章章 数据链路层数据链路层59数据链路协议数据链路协议Data Link Protocols计算机网络计算机网络第第3 3章章 数据链路层数据链路层60面向比特的协议面向比特的协议Bit-oriented ProtocolsBit-oriented Protocols计算机网络计算

50、机网络第第3 3章章 数据链路层数据链路层61 HDLCHDLC是由国际标准化组织（是由国际标准化组织（ISOISO）制订的最重要的面向比）制订的最重要的面向比特的数据链路协议特的数据链路协议(ISO 330099(ISO 330099和和ISO 4335)ISO 4335)，支持点对点，支持点对点或多点半双工和全双工通信，主要用于广域网技术。或多点半双工和全双工通信，主要用于广域网技术。 HDLCHDLC的主要目标是：的主要目标是： 保证发送的比特流具有透明性保证发送的比特流具有透明性 确定发送帧的格式及帧内字段的含义确定发送帧的格式及帧内字段的含义 实现链路上站点之间的协调，保证传输有序实

51、现链路上站点之间的协调，保证传输有序 学习广域网协议原理及配置，需要了解学习广域网协议原理及配置，需要了解HDLC HDLC 的帧结构和的帧结构和简单原理，并掌握简单原理，并掌握HDLC HDLC 的基本配置命令（如在的基本配置命令（如在DDNDDN专线上，专线上，CiscoCisco 路由器之间采用路由器之间采用CiscoCisco HDLCHDLC协议。对路由器高速同协议。对路由器高速同步串口进行步串口进行HDLCHDLC配置：配置：encapsulationencapsulation hdlchdlc ）。）。高级数据链路控制协议高级数据链路控制协议(HDLC)(HDLC)计算机网络计算

52、机网络第第3 3章章 数据链路层数据链路层62HDLCHDLC的站点类型的站点类型 HDLCHDLC定义了三种站点类型：定义了三种站点类型： 主站主站 (primary station)(primary station) 控制链路的运行控制链路的运行 所发布的帧称为所发布的帧称为“命令命令” 在物理线路上保持与每个从站的独立的逻辑链路在物理线路上保持与每个从站的独立的逻辑链路 从站从站 (secondary station)(secondary station) 受控于主站受控于主站 所发布的帧称为所发布的帧称为“响应响应” 混合站混合站 (combined station(combined

53、station，亦称，亦称“复合站复合站”) ) 可以发布可以发布“命令命令”和和“响应响应”计算机网络计算机网络第第3 3章章 数据链路层数据链路层63HDLCHDLC的链路组合的链路组合 HDLCHDLC定义了二种链路配置：定义了二种链路配置： 非平衡式非平衡式 (unbalanced)(unbalanced) 一个主站和一个或几个从站一个主站和一个或几个从站 平衡式平衡式 (balanced)(balanced) 两个混合站两个混合站所有这些配置都支持全双工和半双工传输。所有这些配置都支持全双工和半双工传输。HDLCHDLC不支持平衡式多点配置，所以在局域网中不支持平衡式多点配置，所以在

54、局域网中必须引入所谓的必须引入所谓的“媒体接入控制协议媒体接入控制协议”。计算机网络计算机网络第第3 3章章 数据链路层数据链路层64非平衡式配置非平衡式配置 非平衡配置在只涉及两台设备时可以是点到点的，更非平衡配置在只涉及两台设备时可以是点到点的，更多情况下是多点的，即由一台计算机控制多个外部设多情况下是多点的，即由一台计算机控制多个外部设备，如，一台计算机和一台或几台终端。备，如，一台计算机和一台或几台终端。计算机网络计算机网络第第3 3章章 数据链路层数据链路层65平衡式配置平衡式配置 点对点链路上的两个站点都是混合站。两个站点对点链路上的两个站点都是混合站。两个站点通过一条线路连接，可

55、以由任一方控制。点通过一条线路连接，可以由任一方控制。计算机网络计算机网络第第3 3章章 数据链路层数据链路层66HDLCHDLC的数据传送工作方式的数据传送工作方式 HDLCHDLC定义了三种数据传送的工作方式。定义了三种数据传送的工作方式。HDLCHDLC中中的方式指的是两个相互交换的设备之间的关系；的方式指的是两个相互交换的设备之间的关系；这种方式说明是谁控制链路。这种方式说明是谁控制链路。计算机网络计算机网络第第3 3章章 数据链路层数据链路层67正常响应方式正常响应方式(NRM)(NRM) 使用非平衡配置使用非平衡配置 主站可以向从站启动数据传输主站可以向从站启动数据传输 从站只能在

56、响应主站命令（被许可）时才能传输数据从站只能在响应主站命令（被许可）时才能传输数据 一旦获得主站许可，从站可以开始一次响应性的一帧一旦获得主站许可，从站可以开始一次响应性的一帧或多帧数据的传输或多帧数据的传输 可在多站线路上使用可在多站线路上使用 主机作主站主机作主站 终端作从站终端作从站计算机网络计算机网络第第3 3章章 数据链路层数据链路层68异步响应方式异步响应方式(ARM)(ARM) 使用非平衡配置使用非平衡配置 从站可以不经主站许可而启动传输过程，只要从站可以不经主站许可而启动传输过程，只要线路是空闲的。线路是空闲的。 主站仍对线路全权负责，包括初始化，差错恢主站仍对线路全权负责，包

57、括初始化，差错恢复，以及链路的逻辑断开。复，以及链路的逻辑断开。 很少使用。仅当某些从站需要发起传输的特殊很少使用。仅当某些从站需要发起传输的特殊场合。场合。计算机网络计算机网络第第3 3章章 数据链路层数据链路层69异步平衡方式异步平衡方式 (ABM)(ABM) 使用平衡式配置使用平衡式配置 所有站点都是平等的，所以只能用于两个点对所有站点都是平等的，所以只能用于两个点对点连接的混合站。点连接的混合站。 两站中任一个都可启动传输而无需先得到其他两站中任一个都可启动传输而无需先得到其他混合站的许可。混合站的许可。 应用最广泛应用最广泛 全双工点对点链路利用率较高，因为没有请求全双工点对点链路利

58、用率较高，因为没有请求方面的开销。方面的开销。计算机网络计算机网络第第3 3章章 数据链路层数据链路层70HDLCHDLC的帧结构的帧结构 HDLCHDLC使用同步传输。所有的传输都是以帧的形式进行的，使用同步传输。所有的传输都是以帧的形式进行的，只要一种帧格式就可以满足各种类型数据和控制交换的只要一种帧格式就可以满足各种类型数据和控制交换的要求。要求。 信息字段前的标志字段、地址字段和控制字段叫做信息字段前的标志字段、地址字段和控制字段叫做“帧帧头头” ” ( (首部首部) )。信息字段后面的。信息字段后面的FCSFCS（帧校验序列）字段（帧校验序列）字段和标志字段叫做和标志字段叫做“帧尾帧

59、尾” ” ( (尾部尾部) )。计算机网络计算机网络第第3 3章章 数据链路层数据链路层71帧标志字段帧标志字段 在帧的两端起定界作用。在帧的两端起定界作用。 接收方搜寻标志字段用于同步（判断帧之起始）。接收方搜寻标志字段用于同步（判断帧之起始）。 标志字段是标志字段是8 8个比特的固定模式，即个比特的固定模式，即0111111001111110。 帧的首尾各有一个标志字段。一个帧的结束标志可以用帧的首尾各有一个标志字段。一个帧的结束标志可以用作下一帧的起始标志。作下一帧的起始标志。计算机网络计算机网络第第3 3章章 数据链路层数据链路层72比特填充技术比特填充技术 使用使用“比特填充比特填充

60、”技术以避免含有比特序列技术以避免含有比特序列0111111001111110的的数据不会与帧标志字段混淆。数据不会与帧标志字段混淆。 发送前在每五个比特发送前在每五个比特1 1后自动插入一个附加的比特后自动插入一个附加的比特0 0。 接收方如果收到连续五个接收方如果收到连续五个1 1，将检查下一个比特。，将检查下一个比特。 如果下一个比特是如果下一个比特是0 0，就删除之。，就删除之。 如果下一个比特是如果下一个比特是1 1且第七个比特是且第七个比特是0 0，则被视为帧标，则被视为帧标志。志。 如果第六个和第七个比特都是如果第六个和第七个比特都是1 1，表示传输被取消，表示传输被取消( (连