1、.1.2第第 3 章章 数据链路层数据链路层基本内容：基本内容：数据链路层的基本概念，数据链路层协议的工数据链路层的基本概念，数据链路层协议的工作原理：停止等待协议，连续作原理：停止等待协议，连续ARQ协议，滑动窗口，选择协议，滑动窗口，选择ARQ协议，协议，Internet中的数据链路层协议。中的数据链路层协议。重点掌握：重点掌握：v 数据链路层的基本概念。数据链路层的基本概念。v 数据链路层协议的工作原理。数据链路层协议的工作原理。v 滑动窗口原理。滑动窗口原理。.33.1 3.1 数据链路层的基本概念数据链路层的基本概念v 链路链路(link)是一条无源的点到点的物理线路段，中间没有是一
2、条无源的点到点的物理线路段，中间没有任何其他的交换结点。任何其他的交换结点。v 数据链路数据链路(data link)除了物理线路外，还必须有通信协除了物理线路外，还必须有通信协议来控制这些数据的传输。若把实现这些协议的硬件和软议来控制这些数据的传输。若把实现这些协议的硬件和软件加到链路上，就构成了数据链路。件加到链路上，就构成了数据链路。数据链路数据链路/逻辑链路逻辑链路=物理链路物理链路+通信规程通信规程.4v 该层要解决的问题：如何在有差错的线路上，进行无差该层要解决的问题：如何在有差错的线路上，进行无差错传输。数据链路层协议功能图示。错传输。数据链路层协议功能图示。数据链路层的模型数据
3、链路层的模型.5 数据链路层像个数字管道数据链路层像个数字管道n 常常在两个对等的数据链路层之间画出一个数字管道，常常在两个对等的数据链路层之间画出一个数字管道，而在这条数字管道上传输的数据单位是而在这条数字管道上传输的数据单位是帧帧。n 早期的数据通信协议曾叫作早期的数据通信协议曾叫作通信规程通信规程(procedure)(procedure)。因此。因此在数据链路层，规程和协议是同义语。在数据链路层，规程和协议是同义语。结点结点结点结点帧帧帧帧.6？发送方：？发送方：？接收方：？接收方：？传输过程：？传输过程：！解决这些问题，是数据链路层的主要任务。！解决这些问题，是数据链路层的主要任务。
4、！针对这些问题所制定的通信规程就是数据链路层的通信！针对这些问题所制定的通信规程就是数据链路层的通信协议。协议。以多快的速度发送数据帧，即每帧之间相隔以多快的速度发送数据帧，即每帧之间相隔多长时间？如何确认对方是否收到数据？多长时间？如何确认对方是否收到数据？是否接收到正确的数据帧？如何告诉发送方？是否接收到正确的数据帧？如何告诉发送方？能及时处理接收到的数据帧吗？能及时处理接收到的数据帧吗？会出错吗？会丢失数据帧吗？会出错吗？会丢失数据帧吗？.7 数据链路层的主要功能数据链路层的主要功能 数据链路层最重要的作用就是：通过一些数据链路层数据链路层最重要的作用就是：通过一些数据链路层协议，在不太
5、可靠的物理链路上实现可靠的数据传输。其协议，在不太可靠的物理链路上实现可靠的数据传输。其主要功能可归纳如下：主要功能可归纳如下：(1)链路管理链路管理 (2)帧定界帧定界 (3)流量控制流量控制 (4)差错控制差错控制 (5)将数据和控制信息区分开将数据和控制信息区分开 (6)透明传输透明传输 (7)寻址寻址.8 数据链路层的主要功能数据链路层的主要功能(1)(1)链路管理链路管理-当网络中的两个结点要进行通信时，数据的发方当网络中的两个结点要进行通信时，数据的发方必须确知收方是否已处在准备接受的状态。为此通信的双方必须必须确知收方是否已处在准备接受的状态。为此通信的双方必须先要交换一些必要的
6、信息，先要交换一些必要的信息，用术语讲必须先建立一条数据链路。用术语讲必须先建立一条数据链路。在传输数据时要维持数据链路，而在通信完毕时要释放数据链路。在传输数据时要维持数据链路，而在通信完毕时要释放数据链路。数据链路的建立、维持和释放就叫做链路管理。数据链路的建立、维持和释放就叫做链路管理。(2)(2)帧同步帧同步-在数据链路层，数据的传送单位时帧。数据一帧一在数据链路层，数据的传送单位时帧。数据一帧一帧地传送，就可以在出现差错时，将有差错的帧再重传一次，避帧地传送，就可以在出现差错时，将有差错的帧再重传一次，避免了全部数据的重传。帧同步是指收方应当能从受到的比特流中免了全部数据的重传。帧同
7、步是指收方应当能从受到的比特流中准确地区分出一帧的开始和结束。准确地区分出一帧的开始和结束。.9 数据链路层的主要功能数据链路层的主要功能(3)(3)流量控制流量控制-发方发送数据的速率必须使收方来得及接收。当收发方发送数据的速率必须使收方来得及接收。当收方来不及接收时，就必须及时控制发方发送数据的速率。方来不及接收时，就必须及时控制发方发送数据的速率。(4)(4)差错控制差错控制-在计算机通信中，一般都要求有极低的比特差错率。在计算机通信中，一般都要求有极低的比特差错率。为此广泛地使用了编码技术，主要有两大类，一类是前向纠错，为此广泛地使用了编码技术，主要有两大类，一类是前向纠错，即收方收到
8、有差错的数据帧时能自动将差错改正过来。这种方法即收方收到有差错的数据帧时能自动将差错改正过来。这种方法的开销较大，不适合于计算机通信。另一类是检错重发，即收方的开销较大，不适合于计算机通信。另一类是检错重发，即收方可以检测出收到的帧中有差错，于是就让发方重复发送这一帧，可以检测出收到的帧中有差错，于是就让发方重复发送这一帧，直到收方正确收到这一帧为止。这种方法在计算机通信中是最常直到收方正确收到这一帧为止。这种方法在计算机通信中是最常用的。用的。.10 数据链路层的主要功能数据链路层的主要功能(5)(5)将数据和控制信息区分开将数据和控制信息区分开-由于数据和控制信息都是在同一信由于数据和控制
9、信息都是在同一信道中传输，在许多情况下，数据和控制信息处于同一帧中，因此道中传输，在许多情况下，数据和控制信息处于同一帧中，因此一定要有响应的措施使收方能够将他们区分开来。一定要有响应的措施使收方能够将他们区分开来。(6)(6)透明传输透明传输-所谓透明传输就是不管所传数据是什么样的比特组所谓透明传输就是不管所传数据是什么样的比特组合，都应当能够在链路上传送。当所传数据中的比特组合恰巧与合，都应当能够在链路上传送。当所传数据中的比特组合恰巧与某一个控制信息完全一样时，就必须采取适当的措施，使收方不某一个控制信息完全一样时，就必须采取适当的措施，使收方不会将这样的数据误认为是某种控制信息。这样才
10、能保证数据链路会将这样的数据误认为是某种控制信息。这样才能保证数据链路层的传输是透明的。层的传输是透明的。(7)(7)寻址寻址-在多点连接的情况下，必须保证每一帧都能送到正确在多点连接的情况下，必须保证每一帧都能送到正确的地址。双方也应当知道发方是哪一个站。的地址。双方也应当知道发方是哪一个站。.113.2 3.2 停止等待协议停止等待协议 3.2.1 完全理想化的数据传输完全理想化的数据传输 3.2.2 具有最简单流量控制的数据链路层协议具有最简单流量控制的数据链路层协议 3.2.3 实用的停止等待协议实用的停止等待协议 3.2.4 循环冗余检验的原理循环冗余检验的原理 3.2.5 停止等待
11、协议的算法停止等待协议的算法 3.2.6 停止等待协议的定量分析停止等待协议的定量分析.123.2.1 完全理想化的数据传输完全理想化的数据传输数据链路层的简单模型：数据链路层的简单模型：局域网局域网广域网广域网主机主机 H1主机主机 H2路由器路由器 R1路由器路由器 R2路由器路由器 R3电话网电话网局域网局域网主机主机 H1 向向 H2 发送数据发送数据链路层链路层应用层应用层运输层运输层网络层网络层物理层物理层链路链路层层应用层应用层运输层运输层网络层网络层物理层物理层链路层链路层网络层网络层物理层物理层链路层链路层网络层网络层物理层物理层链路层链路层网络层网络层物理层物理层R1R2R
12、3H1H2从层次上来看数据的流动从层次上来看数据的流动.133.2.1 完全理想化的数据传输完全理想化的数据传输数据链路层的简单模型（续）：数据链路层的简单模型（续）：局域网局域网广域网广域网主机主机 H1主机主机 H2路由器路由器 R1路由器路由器 R2路由器路由器 R3电话网电话网局域网局域网主机主机 H1 向向 H2 发送数据发送数据链路层链路层应用层应用层运输层运输层网络层网络层物理层物理层链路层链路层应用层应用层运输层运输层网络层网络层物理层物理层链路层链路层网络层网络层物理层物理层链路层链路层网络层网络层物理层物理层链路层链路层网络层网络层物理层物理层R1R2R3H1H2仅从数据链
13、路层观察帧的流动仅从数据链路层观察帧的流动.143.2.1 完全理想化的数据传输完全理想化的数据传输两台计算机通过一条通信链路进行通信的筒化模型：两台计算机通过一条通信链路进行通信的筒化模型：数据链路层数据链路层主主机机 A缓存缓存主主机机 B数据链路数据链路AP2AP1缓存缓存发送方发送方接收方接收方帧帧高层高层帧帧.15v完全理想化的数据传输所基于的两个假定完全理想化的数据传输所基于的两个假定 假定假定1 1：链路是理想的传输信道，所传送的任何数据既不：链路是理想的传输信道，所传送的任何数据既不会出差错也不会丢失。会出差错也不会丢失。假定假定2 2：不管发方以多快的速率发送数据，收方总是来
14、得：不管发方以多快的速率发送数据，收方总是来得及收下，并及时上交主机。及收下，并及时上交主机。v 这个假定就相当于认为：接收端向主机交付数据的速这个假定就相当于认为：接收端向主机交付数据的速率永远不会低于发送端发送数据的速率。率永远不会低于发送端发送数据的速率。.163.2.2 具有最简单流量控制的数据链路层协议具有最简单流量控制的数据链路层协议n 现在去掉上述的第二个假定。但是，仍然保留第一个假现在去掉上述的第二个假定。但是，仍然保留第一个假定，即主机定，即主机A A向主机向主机B B传输数据的信道仍然是无差错的理想传输数据的信道仍然是无差错的理想信道。然而现在不能保证接收端向主机交付数据的
15、速率永信道。然而现在不能保证接收端向主机交付数据的速率永远不低于发送端发送数据的速率。远不低于发送端发送数据的速率。n 由收方控制发方的数据流由收方控制发方的数据流，是计算机网络中流量控制的，是计算机网络中流量控制的一个基本方法。一个基本方法。.173.2.2 具有最简单流量控制的数据链路层协议具有最简单流量控制的数据链路层协议在发送结点：在发送结点：(1)从主机取一个数据帧。从主机取一个数据帧。(2)将数据帧送到数据链路层将数据帧送到数据链路层的发送缓存。的发送缓存。(3)将发送缓存中的数据帧发将发送缓存中的数据帧发送出去。送出去。(4)等待。等待。(5)若收到由接收结点发过来若收到由接收结
16、点发过来的信息，则从主机取一个新的的信息，则从主机取一个新的数据帧，然后转到数据帧，然后转到(2)。在接收结点：在接收结点：(1)等待。等待。(2)若收到由发送结点发过来若收到由发送结点发过来的数据帧，则将其放入数据链的数据帧，则将其放入数据链路层的接收缓存。路层的接收缓存。(3)将接收缓存中的数据帧上将接收缓存中的数据帧上交主机。交主机。(4)向发送结点发一信息，表向发送结点发一信息，表示数据帧已经上交给主机。示数据帧已经上交给主机。(5)转到转到(1)。.18v 两种情况的对比（传输均无差错）两种情况的对比（传输均无差错）ABDATADATADATADATA送主机送主机 B送主机送主机 B
17、送主机送主机 B送主机送主机 BABDATA送主机送主机 BDATA送主机送主机 B时时间间不需要流量控制不需要流量控制需要流量控制需要流量控制.193.2.3 实用的停止等待协议实用的停止等待协议时时间间ABDATA0送送主主机机ACKDATA1送送主主机机ACK(a)正常情况正常情况ABDATA0DATA0送送主主机机ACK(c)数据帧丢失数据帧丢失重重传传tout丢丢失失！ABDATA0送送主主机机ACKDATA0丢丢弃弃ACK(d)确认帧丢失确认帧丢失重重传传tout丢丢失失！ABDATA0NAKDATA0送送主主机机ACK(b)数据帧出错数据帧出错重重传传出错出错四种情况四种情况.2
18、0v 解决死锁问题解决死锁问题n 结点结点A发送完一个数据帧时，就启动一个发送完一个数据帧时，就启动一个超时计时器超时计时器(timeout timer)。n 若到了超时计时器所设置的重传时间若到了超时计时器所设置的重传时间 tout而仍收不到结点而仍收不到结点 B 的任何确认帧，则结点的任何确认帧，则结点 A 就重传前面所发送的这一数据就重传前面所发送的这一数据帧。帧。n 一般可将重传时间选为略大于一般可将重传时间选为略大于“从发完数据帧到收到确从发完数据帧到收到确认帧所需的平均时间认帧所需的平均时间”。.21v 解决重复帧的问题解决重复帧的问题n如果是确认帧丢失，则超时重传将使主机如果是确
19、认帧丢失，则超时重传将使主机B收到两个相同收到两个相同的数据帧，这就是的数据帧，这就是重复帧重复帧。n使每一个数据帧带上不同的发送序号。每发送一个新的数使每一个数据帧带上不同的发送序号。每发送一个新的数据帧就把它的发送序号加据帧就把它的发送序号加 1。n 若结点若结点 B 收到发送序号相同的数据帧，就表明出现了重收到发送序号相同的数据帧，就表明出现了重复帧。这时应丢弃重复帧，因为已经收到过同样的数据帧复帧。这时应丢弃重复帧，因为已经收到过同样的数据帧并且也交给了主机并且也交给了主机 B。n 但此时结点但此时结点 B 还必须向还必须向 A 发送确认帧发送确认帧 ACK，因为，因为 B 已已经知道
20、经知道 A 还没有收到上一次发过去的确认帧还没有收到上一次发过去的确认帧 ACK。.22v 帧的编号问题帧的编号问题n 任何一个编号系统的序号所占用的比特数一定是有限的。任何一个编号系统的序号所占用的比特数一定是有限的。因此，经过一段时间后，发送序号就会重复。因此，经过一段时间后，发送序号就会重复。n 序号占用的比特数越少，数据传输的额外开销就越小。序号占用的比特数越少，数据传输的额外开销就越小。n 对于停止等待协议，由于每发送一个数据帧就停止等待，对于停止等待协议，由于每发送一个数据帧就停止等待，因此用一个比特来编号就够了。因此用一个比特来编号就够了。注：一个比特可表示注：一个比特可表示 0
21、 和和 1 两种不同的序号。两种不同的序号。.23v 帧的发送序号帧的发送序号n 数据帧中的发送序号数据帧中的发送序号 N(S)以以 0 和和 1 交替的方式出现在数交替的方式出现在数据帧中。据帧中。n 每发一个新的数据帧，发送序号就和上次发送的不一样。每发一个新的数据帧，发送序号就和上次发送的不一样。用这样的方法就可以使收方能够区分开新的数据帧和重传用这样的方法就可以使收方能够区分开新的数据帧和重传的数据帧了。的数据帧了。.24v 可靠传输可靠传输 虽然物理层在传输比特时会出现差错，但由于数据链路层虽然物理层在传输比特时会出现差错，但由于数据链路层的停止等待协议采用了有效的检错重传机制，数据
22、链路层的停止等待协议采用了有效的检错重传机制，数据链路层对上面的网络层就可以提供对上面的网络层就可以提供可靠传输可靠传输的服务。的服务。.253.2.4 循环冗余检验的原理循环冗余检验的原理n在数据链路层传送的帧中，广泛使用了循环冗余检验在数据链路层传送的帧中，广泛使用了循环冗余检验 CRC 的检错技术。的检错技术。n假设待传送的数据假设待传送的数据 M=1010001101（共（共k bit）。我们在）。我们在M的后面再添加供差错检测用的的后面再添加供差错检测用的 n bit 冗余码冗余码一起发送。一起发送。n冗余码的计算冗余码的计算用二进制的模用二进制的模 2 运算进行运算进行 2n 乘乘
23、 M 的运算，这相当于的运算，这相当于在在 M 后面添加后面添加 n 个个 0。得到的得到的(k+n)bit 的数除以事先选定好的长度为的数除以事先选定好的长度为(n+1)bit 的数的数 P，得出商是，得出商是 Q 而余数是而余数是 R，余数，余数 R 比除数比除数 P 至少要少至少要少1 个比特。个比特。.26v 冗余码的计算举例冗余码的计算举例n 设设 n=5,P=110101，M=1010001101模模 2 运算的结果运算的结果是：是：商商 Q=1101010110，余数，余数R=01110。将余数将余数 R 作为冗余码添加在数据作为冗余码添加在数据 M 的后面发送出去，的后面发送出
24、去，即发送的数据是即发送的数据是101000110101110，或，或 2nM+R。.27v循环冗余检验的原理说明循环冗余检验的原理说明 1101010110 Q 商 除数 P 110101 101000110100000 2nM 被除数 110101 111011 110101 111010 110101 111110 110101 101100 110101 110010 110101 01110 R 余数.28v循环冗余检验的原理说明循环冗余检验的原理说明n 只要得出的余数只要得出的余数 R 不为不为 0，就表示检测到了，就表示检测到了差错差错。n 但这种检测方法并不能确定究竟是哪一个或
25、哪几个比特但这种检测方法并不能确定究竟是哪一个或哪几个比特出现了差错。出现了差错。n 一旦检测出差错，就一旦检测出差错，就丢弃丢弃这个出现差错的帧。这个出现差错的帧。n 只要经过严格的挑选，并使用位数足够多的除数只要经过严格的挑选，并使用位数足够多的除数 P，那，那么出现检测不到的差错的概率就很小很小。么出现检测不到的差错的概率就很小很小。.293.2.5 停止等待协议的算法停止等待协议的算法在发送结点：在发送结点：(1)从主机取一个数据帧，送交发送缓存。从主机取一个数据帧，送交发送缓存。(2)V(S)0。(3)N(S)V(S)。(4)将发送缓存中的数据帧发送出去。将发送缓存中的数据帧发送出去
26、。(5)设置超时计时器。设置超时计时器。(6)等待。等待。等待以下等待以下(7)和和(8)这两个事件中最先出现的一个这两个事件中最先出现的一个(7)收到确认帧收到确认帧 ACKn，若，若 n=1 V(s)，则：，则：从主机取一个新的数据帧，放入发送缓存；从主机取一个新的数据帧，放入发送缓存；V(S)1 V(S)，转到，转到(3)。否则丢弃这个确认帧，转到。否则丢弃这个确认帧，转到(6)。(8)若超时计时器时间到，则转到若超时计时器时间到，则转到(4)。.303.2.5 停止等待协议的算法停止等待协议的算法在接收结点：在接收结点：(1)V(R)0。(2)等待。等待。(3)收到一个数据帧；收到一个
27、数据帧；若若 N(S)=V(R)，则执行，则执行(4)；否则丢弃此数据帧，然后转到否则丢弃此数据帧，然后转到(6)。(4)将收到的数据帧中的数据部分送交上层软件。将收到的数据帧中的数据部分送交上层软件。(5)V(R)1 V(R)。(6)nV(R)；发送确认帧发送确认帧 ACKn，转到，转到(2)。.313.2.6 停止等待协议的定量分析停止等待协议的定量分析n 设设 tf 是一个数据帧的是一个数据帧的发送时间发送时间，且数据帧的长度是固定不，且数据帧的长度是固定不变的。显然，数据帧的发送时间变的。显然，数据帧的发送时间 tf 是数据帧的长度是数据帧的长度 lf(bit)与与数据的发送速率数据的
28、发送速率 C(bit/s)之比，即之比，即 tf=lf/C=lf/C(s)（3-1）n 发送时间发送时间 tf 也就是数据帧的也就是数据帧的发送时延发送时延。n 数据帧沿链路传到结点数据帧沿链路传到结点B还要经历一个还要经历一个传播时延传播时延 tp。n 结点结点 B 收到数据帧要花费时间进行处理，此时间称为处收到数据帧要花费时间进行处理，此时间称为处理时间理时间 tpr，发送确认帧，发送确认帧 ACK 的发送时间为的发送时间为 ta。.32v停止等待协议中数据帧和确认帧的发送时间关系停止等待协议中数据帧和确认帧的发送时间关系ABDATADATAACK传播时延传播时延 tp处理时间处理时间 t
29、pr确认帧发送时间确认帧发送时间 ta传播时延传播时延 tp处理时间处理时间 tprtT时间时间两个成功发送的两个成功发送的数据帧之间的数据帧之间的最小时间间隔最小时间间隔数据帧的数据帧的发送时间发送时间tf设置的设置的重传时间重传时间tout.33v重传时间重传时间n 重传时间的作用是：数据帧发送完毕后若经过了这样长的重传时间的作用是：数据帧发送完毕后若经过了这样长的时间还没有收到确认帧，就重传这个数据帧。时间还没有收到确认帧，就重传这个数据帧。n 为方便起见，我们设重传时间为为方便起见，我们设重传时间为 tout=tp+tpr+ta+tp+tprn 设上式右端的处理时间设上式右端的处理时间
30、 tpr 和确认帧的发送时间和确认帧的发送时间 ta 都远小都远小于传播时延于传播时延 tp，因此可将重传时间取为，因此可将重传时间取为两倍的传播时延两倍的传播时延，即即 tout=2tp.34v简单的数学分析简单的数学分析n 两个发送成功的数据帧之间的最小时间间隔是两个发送成功的数据帧之间的最小时间间隔是 tT=tf+tout=tf +2tpn 设数据帧出现差错设数据帧出现差错(包括帧丢失包括帧丢失)的概率为的概率为 p，但假设确认，但假设确认帧不会出现差错。帧不会出现差错。n 设设正确正确传送一个数据帧所需的传送一个数据帧所需的平均时间平均时间 tav tav=tT(1+一个帧的平均重传次
31、数一个帧的平均重传次数).35v简单的数学分析（续）简单的数学分析（续）一帧的平均重传次数一帧的平均重传次数 =1 P重传次数为重传次数为 1+2 P重传次数为重传次数为 2+3 P重传次数为重传次数为 3+=1 P第第 1 次发送出错次发送出错 P第第 2 次发送成功次发送成功 +2 P第第 1,2 次发送出错次发送出错 P第第 3 次发送成功次发送成功 +3 P第第 1,2,3 次发送出错次发送出错 P第第 4 次发送成功次发送成功+=p(1 p)+2p2(1 p)+3p3(1 p)+这里这里 PX 是出现事件是出现事件 X 的概率。的概率。得出正确传送一个数据帧所需的平均时间：得出正确传
32、送一个数据帧所需的平均时间：当传输差错率增大时，当传输差错率增大时，tav 也随之增大。当无差错时，也随之增大。当无差错时，p=0,tav=tT。)1(/)1(1pttippttiTTiTav.36v停止等待协议停止等待协议 ARQ 的优缺点的优缺点n 优点：优点：比较简单比较简单。n 缺点：通信信道的利用率不高，也就是说，信道还远远没缺点：通信信道的利用率不高，也就是说，信道还远远没有被数据比特填满。有被数据比特填满。n 为了克服这一缺点，就产生了另外两种协议，即连续为了克服这一缺点，就产生了另外两种协议，即连续 ARQ 和选择重传和选择重传 ARQ。.373.3 3.3 连续连续 ARQ
33、ARQ 协议协议 3.3.1 连续连续 ARQ 协议的工作原理协议的工作原理 3.3.2 连续连续 ARQ 协议的吞吐量协议的吞吐量 3.3.3 滑动窗口的概念滑动窗口的概念 3.3.4 信道利用率与最佳帧长信道利用率与最佳帧长.383.3.1 连续连续 ARQ 协议的工作原理协议的工作原理n 在发送完一个数据帧后，不是停下来等待确认帧，而是可在发送完一个数据帧后，不是停下来等待确认帧，而是可以连续再发送若干个数据帧。以连续再发送若干个数据帧。n 如果这时收到了接收端发来的确认帧，那么还可以接着发如果这时收到了接收端发来的确认帧，那么还可以接着发送数据帧。送数据帧。n 若收到对其中某一帧的否认
34、帧，则从该帧开始的后继帧全若收到对其中某一帧的否认帧，则从该帧开始的后继帧全部重发。部重发。n 由于减少了等待时间，整个通信的吞吐量就提高了。由于减少了等待时间，整个通信的吞吐量就提高了。.393.3.1 连续连续 ARQ 协议的工作原理协议的工作原理DATA0DATA1DATA2DATA3DATA4DATA5重传重传 DATA2重传重传 DATA3ACK1ACK2ACK1 确认确认 DATA0ACK2 确认确认 DATA1DATA2 出错，出错，丢弃丢弃DATA3 不按序，不按序，丢弃丢弃，重传重传 ACK2DATA4 不按序，不按序，丢弃丢弃，重传重传 ACK2DATA5 不按序，不按序，
35、丢弃丢弃，重传重传 ACK2ACK3ACK3 确认确认 DATA2ACK4 确认确认 DATA3ACK4重传重传 DATA5重传重传 DATA4超超时时重重传传时时间间ABtout送交主机送交主机送交主机送交主机?ACK2ACK2ACK2.40v 需要注意需要注意(1)接收端接收端只按序接收只按序接收数据帧。虽然在有差错的数据帧。虽然在有差错的 2号帧之后号帧之后接着又收到了正确的接着又收到了正确的 3 个数据帧，但接收端都必须将这些个数据帧，但接收端都必须将这些帧丢弃，因为在这些帧前面有一个帧丢弃，因为在这些帧前面有一个 2 号帧还没有收到。号帧还没有收到。(2)ACK1 表示确认表示确认
36、0 号帧号帧 DATA0，并期望下次收到，并期望下次收到 1 号号帧；帧；ACK2 表示确认表示确认 1 号帧号帧 DATA1，并期望下次收到，并期望下次收到 2号号帧。依此类推。帧。依此类推。.41v 需要注意需要注意(3)结点结点 A 在每发送完一个数据帧时都要设置该帧的在每发送完一个数据帧时都要设置该帧的超时计超时计时器时器。如果在所设置的超时时间内收到确认帧，就立即将。如果在所设置的超时时间内收到确认帧，就立即将超时计时器清零。但若在所设置的超时时间到了而未收到超时计时器清零。但若在所设置的超时时间到了而未收到确认帧，就要重传相应的数据帧。确认帧，就要重传相应的数据帧。在等不到在等不到
37、 2 号帧的确认而重传号帧的确认而重传 2 号数据帧时，虽然结号数据帧时，虽然结点点 A 已经发完了已经发完了 5 号帧，但仍必须向回走，将号帧，但仍必须向回走，将 2号帧及其号帧及其以后的各帧全部进行重传。连续以后的各帧全部进行重传。连续 ARQ 又称为又称为Go-back-N ARQ（又称回退（又称回退N式式ARQ协议）协议），意思是当出现差错必须，意思是当出现差错必须重传时，要向回走重传时，要向回走 N 个帧，然后再开始重传。个帧，然后再开始重传。.42v连续连续ARQ协议的优缺点协议的优缺点v 连续连续ARQ协议一方面因连续发送数据帧而提高了效率，协议一方面因连续发送数据帧而提高了效率
38、，另一方面，在重传时又必须把原来已正确传送过的数据帧另一方面，在重传时又必须把原来已正确传送过的数据帧进行重传，这种做法又使传送效率降低。进行重传，这种做法又使传送效率降低。v 若传输信道的传输质量很差因而误码率较大时，连续若传输信道的传输质量很差因而误码率较大时，连续ARQ协议不一定优于停止等待协议。协议不一定优于停止等待协议。.433.3.2 连续连续 ARQ 协议的吞吐量协议的吞吐量)1(/)1(1)1(1ppattippttifTifav 在连续在连续ARQ协议的情况下，正确传送一个数据帧所需的协议的情况下，正确传送一个数据帧所需的平均时间是：平均时间是：吞吐量的最大值是：吞吐量的最大
39、值是：max=1/tav=(1 p)/tT1+（1)p 而归一化的吞吐量为：而归一化的吞吐量为：=tf (1 p)/1+（1)p 可见，当可见，当 等于等于1时，停止等待时，停止等待ARQ与连续与连续ARQ性能相同。性能相同。.443.3.2 连续连续 ARQ 协议的吞吐量协议的吞吐量 例：若数据帧的差错率例：若数据帧的差错率p=0.01，而参数，而参数 =4，则对于停，则对于停止等待协议，止等待协议，0.99/4，但对于连续，但对于连续ARQ协议，协议，0.96。故即使在数据帧的差错率高达故即使在数据帧的差错率高达0.01时，连续时，连续ARQ的效率也的效率也比停止等待协议的高。比停止等待协
40、议的高。注意：注意：停止等待协议归一化吞吐量停止等待协议归一化吞吐量 (1 p)/连续连续ARQ协议归一化吞吐量协议归一化吞吐量 (1 p)/1+（1)p.453.3.3 滑动窗口的概念滑动窗口的概念 在连续在连续ARQ协议中，应当将已发送出去但未被确认的协议中，应当将已发送出去但未被确认的数据帧的数目加发限制。数据帧的数目加发限制。n 发送端和接收端分别设定发送窗口和接收窗口发送端和接收端分别设定发送窗口和接收窗口。n 发送窗口发送窗口用来对发送端进行流量控制。用来对发送端进行流量控制。n 发送窗口的大小发送窗口的大小 WT 代表在还没有收到对方确认信息的代表在还没有收到对方确认信息的情况下
41、发送端最多可以发送多少个数据帧。情况下发送端最多可以发送多少个数据帧。n 接收窗口接收窗口用来控制接收端可以接收哪些数据帧。只有发送用来控制接收端可以接收哪些数据帧。只有发送序号落入接收窗口内的数据帧才可以收下。序号落入接收窗口内的数据帧才可以收下。.4601234567012发送窗口发送窗口WT不允许发送这些帧不允许发送这些帧允许发送允许发送 5 个帧个帧(a)01234567012不允许发送这些帧不允许发送这些帧还允许发送还允许发送 4 个帧个帧WT已发送已发送(b)01234567012不允许发送这些帧不允许发送这些帧WT已发送已发送(c)01234567012不允许发送这些帧不允许发送
42、这些帧还允许发送还允许发送 3 个帧个帧WT已发送已发送 已发送已发送并已收到确认并已收到确认(d)当发送出数据时，滑动窗口从左边开始收缩；当发送出数据时，滑动窗口从左边开始收缩；当收到确认时，滑动窗口向右扩展。当收到确认时，滑动窗口向右扩展。.47v接收端设置接收窗口接收端设置接收窗口n 在接收端只有当收到的数据帧的发送序号落入接收窗口内在接收端只有当收到的数据帧的发送序号落入接收窗口内才允许将该数据帧收下。才允许将该数据帧收下。n 若接收到的数据帧落在接收窗口之外，则一律将其丢弃。若接收到的数据帧落在接收窗口之外，则一律将其丢弃。n 在连续在连续 ARQ 协议中，接收窗口的大小协议中，接收
43、窗口的大小 WR=1。v 只有当收到的帧的序号与接收窗口一致时才能接收该只有当收到的帧的序号与接收窗口一致时才能接收该帧。否则，就丢弃它。帧。否则，就丢弃它。v 每收到一个序号正确的帧，接收窗口就向前（即向右每收到一个序号正确的帧，接收窗口就向前（即向右方）滑动一个帧的位置。同时发送对该帧的确认。方）滑动一个帧的位置。同时发送对该帧的确认。.48不允许接收这些帧不允许接收这些帧01234567012WR准备接收准备接收 0 号帧号帧(a)不允许接收这些帧不允许接收这些帧01234567012WR准备接收准备接收 1 号帧号帧已收到已收到(b)不允许接收这些帧不允许接收这些帧0123456701
44、2WR准备接收准备接收 4 号帧号帧已收到已收到(c).49v 滑动窗口的重要特性滑动窗口的重要特性n 只有在接收窗口向前滑动时（与此同时也发送了确认），只有在接收窗口向前滑动时（与此同时也发送了确认），发送窗口才有可能向前滑动。发送窗口才有可能向前滑动。n 收发两端的窗口按照以上规律不断地向前滑动，因此这种收发两端的窗口按照以上规律不断地向前滑动，因此这种协议又称为协议又称为滑动窗口协议滑动窗口协议。n 当发送窗口和接收窗口的大小都等于当发送窗口和接收窗口的大小都等于 1时，就是停止等待时，就是停止等待协议。协议。.50v发送窗口的最大值发送窗口的最大值n 当用当用 n 个比特进行编号时，若
45、接收窗口的大小为个比特进行编号时，若接收窗口的大小为 1，则只，则只有在发送窗口的大小有在发送窗口的大小 WT 2n 1时，连续时，连续 ARQ 协议才能协议才能正确运行。正确运行。n 例如，当采用例如，当采用 3 bit 编码时，发送窗口的最大值是编码时，发送窗口的最大值是 7 而不而不是是 8。.51v发送窗口的最大值发送窗口的最大值n 显然显然 WT内不可能有重复编号的帧，所以内不可能有重复编号的帧，所以WT2n。设。设WT=2n；n 注意以下情况：注意以下情况：v 发送窗口：只有当收到对一个帧的确认，才会向前滑动发送窗口：只有当收到对一个帧的确认，才会向前滑动一个帧的位置；一个帧的位置
46、；v 接收窗口：只有收到一个序号正确的帧，才会向前滑动接收窗口：只有收到一个序号正确的帧，才会向前滑动一个帧的位置，且同时向发送端发送对该帧的确认。一个帧的位置，且同时向发送端发送对该帧的确认。v 显然只有接收窗口向前滑动时，发送端口才有可能向前显然只有接收窗口向前滑动时，发送端口才有可能向前滑动。发送端若没有收到该确认，发送窗口就不能滑动。滑动。发送端若没有收到该确认，发送窗口就不能滑动。.52v发送窗口的最大值发送窗口的最大值n 取取n=3。考虑当接收窗口位于。考虑当接收窗口位于0时，发送窗口的两个极端状态。时，发送窗口的两个极端状态。n 状态状态1：全部确认帧收到全部确认帧收到 发送窗口
47、：发送窗口：0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 接收窗口：接收窗口：0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 n 状态状态2：全部确认帧都没收到全部确认帧都没收到 发送窗口：发送窗口：0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 接收窗口：接收窗口：0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 n 可见在状态可见在状态2下，接收过程前移窗口后有效序列号的新范围和下，接收过程前移窗口后有效序列号的新范围和发送窗口的旧范围之间有重叠，致使接收端无法区分是重复帧还发送窗口的旧范围之间有重叠，致使接收端无法区分是重复
48、帧还是新帧。为使旧发送窗口和新接收窗口之间序列号不发生重叠，是新帧。为使旧发送窗口和新接收窗口之间序列号不发生重叠，所以所以WT2n-1。.533.3.4 信道利用率与最佳帧长信道利用率与最佳帧长n 由于每个数据帧都必须包括一定的控制信息由于每个数据帧都必须包括一定的控制信息(如帧的序号、如帧的序号、地址、同步信息以及其他的一些控制信息地址、同步信息以及其他的一些控制信息)，所以即使连续，所以即使连续不停地发送数据帧，信道利用率不停地发送数据帧，信道利用率(即扣除全部的控制信息后即扣除全部的控制信息后的数据率与信道容量之比的数据率与信道容量之比)也不可能达到也不可能达到 100%。n 当出现差
49、错时当出现差错时(这是不可避免的这是不可避免的)，数据帧的不断重传将进，数据帧的不断重传将进一步使信道利用率降低。一步使信道利用率降低。.543.3.4 信道利用率与最佳帧长信道利用率与最佳帧长n 若数据帧的帧长取得很短，那么控制信息在每一帧中所占若数据帧的帧长取得很短，那么控制信息在每一帧中所占的比例就增大，因而额外开销增大，这就导致信道利用率的比例就增大，因而额外开销增大，这就导致信道利用率的下降。的下降。n 若帧长取得太长，则数据帧在传输过程中出错的概率就增若帧长取得太长，则数据帧在传输过程中出错的概率就增大，于是重传次数将增大，这也会使信道利用率下降。大，于是重传次数将增大，这也会使信
50、道利用率下降。n 由此可见，存在一个最佳帧长，在此帧长下信道的利用率由此可见，存在一个最佳帧长，在此帧长下信道的利用率最高。最高。.553.4 3.4 选择重传选择重传 ARQ ARQ 协议协议n 可加大接收窗口，先收下发送序号不连续但仍处在接收可加大接收窗口，先收下发送序号不连续但仍处在接收窗口中的那些数据帧。等到所缺序号的数据帧收到后再一窗口中的那些数据帧。等到所缺序号的数据帧收到后再一并送交主机。并送交主机。n 选择重传选择重传 ARQ 协议可避免重复传送那些本来已经正确到协议可避免重复传送那些本来已经正确到达接收端的数据帧。达接收端的数据帧。n 但我们付出的代价是在接收端要设置具有相当
