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