计算机网络课件：第4章 数据链路层

2022年2月 1本章知识点：本章知识点：1.数据链路层的功能与组帧；数据链路层的功能与组帧；2.错误检测和纠正；错误检测和纠正；3.停停-等协议和滑动窗口协议；等协议和滑动窗口协议；4.局域网的数据链路层和广域网的数据链路层。局域网的数据链路层和广域网的数据链路层。 第4章 数据链路层 2022年2月 2l物理层提供的是不可靠的数据传输因为物理层提供的是不可靠的数据传输因为物理层只关心原始比特流的传送，不能识物理层只关心原始比特流的传送，不能识别或判断数据在传输过程中是否损坏或丢别或判断数据在传输过程中是否损坏或丢失。数据链路层定义了控制数据传输的规失。数据链路层定义了控制数据传输的规程程(procedure)，能保证数据在物理线路上，能保证数据在物理线路上可靠传输。可靠传输。 l物理层缺点：没有差错和流量控制，只关物理层缺点：没有差错和流量控制，只关心比特流的传送。心比特流的传送。4.1 数据链路层的设计要点 2022年2月 3 数据链路层是数据链路层是OSI参考模型中的第二层，数参考模型中的第二层，数据链路层的模型如图据链路层的模型如图4-1所示，在物理层提供服所示，在物理层提供服务的基础上向网络层提供服务。数据链路层最务的基础上向网络层提供服务。数据链路层最重要的作用就是：通过一些数据链路层协议重要的作用就是：通过一些数据链路层协议(即即链路控制过程），在不可靠的物理链路上实现链路控制过程），在不可靠的物理链路上实现可靠的、无差错的数据传输。当使用了数据链可靠的、无差错的数据传输。当使用了数据链路控制时，站与站之间的传输通道称为数据链路控制时，站与站之间的传输通道称为数据链路。数据链路层的主要功能是：帧同步、差错路。数据链路层的主要功能是：帧同步、差错控制、流量控制、链路管理，并向网络层提供控制、流量控制、链路管理，并向网络层提供服务接口。服务接口。4.1 数据链路层的设计要点 2022年2月 4 链路指的是从一个节点到相邻节点的一段物理线路，并且链路指的是从一个节点到相邻节点的一段物理线路，并且在这段物理线路的中间，没有任何其他的交换节点。在进行在这段物理线路的中间，没有任何其他的交换节点。在进行数据通信时，两个计算机之间的通信路径往往要经过许多段数据通信时，两个计算机之间的通信路径往往要经过许多段这样的链路。也就是说，链路只是一条路径的组成部分。这样的链路。也就是说，链路只是一条路径的组成部分。 当两个节点在一条路径上传输数据时，它们之间除了必须当两个节点在一条路径上传输数据时，它们之间除了必须要有一条物理线路以外，还必须要有一些必不可少的通信协要有一条物理线路以外，还必须要有一些必不可少的通信协议，来控制数据的传输过程。附加了实现这些协议的硬件和议，来控制数据的传输过程。附加了实现这些协议的硬件和软件的链路，才能被称为数据链路。我们可以将数据链路想软件的链路，才能被称为数据链路。我们可以将数据链路想象成一条数字管道，从而可以借助于它，进行数据通信。象成一条数字管道，从而可以借助于它，进行数据通信。 当采用各种复用技术时，一条链路上可以有多条数据链路。当采用各种复用技术时，一条链路上可以有多条数据链路。 也有人将链路和数据链路，分别称之为物理链路和逻辑链也有人将链路和数据链路，分别称之为物理链路和逻辑链路。这两种划分方法，没有什么实质性的区别，名称不同，路。这两种划分方法，没有什么实质性的区别，名称不同，意思基本一致。意思基本一致。 链路和数据链路2022年2月 5在两个对等的数据链路层之间的连线称为数在两个对等的数据链路层之间的连线称为数字管道，其上传输的数据单位是字管道，其上传输的数据单位是帧帧。结点结点帧帧早期的数据通信协议曾叫作通信规程(procedure)。因此在数据链路层，规程和协议是同义语。数据链路层类似数字管道2022年2月 6(1) 链路管理链路管理 链路的建立、维持、释放。链路的建立、维持、释放。(2) 帧定界帧定界 又称帧同步，指接收方能从接收到的比特流中准确提又称帧同步，指接收方能从接收到的比特流中准确提取数据帧。取数据帧。(3) 流量控制流量控制发送与接收数据同步发送与接收数据同步(4) 差错控制差错控制 采用编码技术采用编码技术(如如CRC)来检测或纠正传输中的错误。来检测或纠正传输中的错误。其中前向纠错具有检测与纠错的功能、开销大。差错其中前向纠错具有检测与纠错的功能、开销大。差错检测只检错，不纠错，并通知发送方重传出错帧。检测只检错，不纠错，并通知发送方重传出错帧。数据链路层的作用2022年2月 7(5) 将数据和控制信息区分开 由于数据和控制信息于同一帧传输，接收端要能从比特流中区分数据信息与控制信息，以进行不同的处理。(6) 透明传输 比特数据的任何组合都能在链路上传输，当数据的比特组合与控制字符相同时，采用相应的处理。(7) 寻址数据能发送到正确的目的地接收方知道发送方的地址由于局域网有多种媒体接入控制，无法采用统一的数据链路层，局域网的数据链路层分为逻辑链路控制和接入链路控制两层。数据链路层的作用2022年2月 8 帧帧(frame)是数据链路层的信息传输单位，由于计算是数据链路层的信息传输单位，由于计算机网络的数据交换方式是分组交换，所以帧是分组在机网络的数据交换方式是分组交换，所以帧是分组在数据链路层的具体体现，它包括按协议规定划分好的数据链路层的具体体现，它包括按协议规定划分好的数据部分、发送和接收站点的地址以及处理控制部分。数据部分、发送和接收站点的地址以及处理控制部分。 帧同步（定界）指接收方能从接收到的比特流中准帧同步（定界）指接收方能从接收到的比特流中准确地区分出一帧的开始和结束位置。确地区分出一帧的开始和结束位置。 尽管不同的数据链路层协议给出的帧格式存在一定尽管不同的数据链路层协议给出的帧格式存在一定的差异，但基本格式大体是相同的，如图的差异，但基本格式大体是相同的，如图4-2所示。组所示。组成帧的那些具有特定意义的部分称为域或字段。成帧的那些具有特定意义的部分称为域或字段。 帧开始地址长度/类型控制数据FCS帧结束图4-2 帧的基本格式2022年2月 9帧同步帧同步(定界定界)在帧的传输过程中，帧同步主要有在帧的传输过程中，帧同步主要有4种方法：种方法：l字符计数法字符计数法字节计数法首先用一个特殊字符来表示一帧的开始，字节计数法首先用一个特殊字符来表示一帧的开始，然后使用一个计数字段来标明帧内数据的字节数。然后使用一个计数字段来标明帧内数据的字节数。 l带填充字符的首尾界符法带填充字符的首尾界符法带填充字符的首尾界符法使用特定字符来定位一帧的带填充字符的首尾界符法使用特定字符来定位一帧的开始与结束。开始与结束。 l带填充位的首尾标志法带填充位的首尾标志法带填充位的首尾标志法是用一组特定的比特模式带填充位的首尾标志法是用一组特定的比特模式(如如01111110)来标志一帧的开头和结束。来标志一帧的开头和结束。 l物理层编码违例法。物理层编码违例法。物理层编码违例法是在物理层采用特定比特编码方法物理层编码违例法是在物理层采用特定比特编码方法时采用。时采用。 2022年2月 10 违规编码法不需要任何填充技术便能实现透违规编码法不需要任何填充技术便能实现透明性，但它只适用于采用冗余编码的环境。明性，但它只适用于采用冗余编码的环境。 由于字节计数法中计数字段的脆弱性和字符由于字节计数法中计数字段的脆弱性和字符填充实现上的复杂性和不兼容性，目前较普遍填充实现上的复杂性和不兼容性，目前较普遍使用的帧同步法是带填充位的首尾标志法和物使用的帧同步法是带填充位的首尾标志法和物理层编码违例法。理层编码违例法。 2022年2月 114.1.2 差错控制差错控制l差错控制功能是数据链路层的主要功能之一差错控制功能是数据链路层的主要功能之一 所谓的差错控制功能是指将错误的出现控制在所能所谓的差错控制功能是指将错误的出现控制在所能允许的尽可能小的范围内。数据链路层将物理层提供允许的尽可能小的范围内。数据链路层将物理层提供的可能出错的物理连接，改造成为逻辑上无差错的数的可能出错的物理连接，改造成为逻辑上无差错的数据链路，从而向网络层提供透明的和可靠的数据传输据链路，从而向网络层提供透明的和可靠的数据传输服务。服务。检错重发是差错控制最常用的方法，即接收方通过检检错重发是差错控制最常用的方法，即接收方通过检测收到帧的校验码测收到帧的校验码(奇偶校验码或奇偶校验码或CRC码码)，验证收到帧，验证收到帧是否发生了差错，若有差错，则通知发送方重发该帧。是否发生了差错，若有差错，则通知发送方重发该帧。 超时重发也是差错控制的一种方法。超时重发可以超时重发也是差错控制的一种方法。超时重发可以解决链路上整个数据帧或反馈信息帧丢失的情况。解决链路上整个数据帧或反馈信息帧丢失的情况。数据链路层通过使用定时器和序号来保证每一帧最终数据链路层通过使用定时器和序号来保证每一帧最终能被正确地提交给接收方的网络层。能被正确地提交给接收方的网络层。 2022年2月 124.1.3 流量控制流量控制 流量控制是指采用一定技术措施，使通信网络中部分流量控制是指采用一定技术措施，使通信网络中部分或全部链路，以及节点上的信息流量不超过某限制值，从或全部链路，以及节点上的信息流量不超过某限制值，从而来保证信息流动顺畅，避免由于信息流量过大而造成信而来保证信息流动顺畅，避免由于信息流量过大而造成信息拥挤，使信息通过能力下降，甚至造成系统息拥挤，使信息通过能力下降，甚至造成系统“死锁死锁”的的情况发生。情况发生。 在许多高层协议中都有流量控制的功能，但是流量控制在许多高层协议中都有流量控制的功能，但是流量控制的对象不同。对于数据链路层，控制的是相邻两节点间数的对象不同。对于数据链路层，控制的是相邻两节点间数据链路上的流量，即发送端发送数据要能使接收端来得及据链路上的流量，即发送端发送数据要能使接收端来得及接收，当接收方来不及接收时，要及时控制发送方发送数接收，当接收方来不及接收时，要及时控制发送方发送数据的速率，同时使帧的接收顺序与发送顺序一致。据的速率，同时使帧的接收顺序与发送顺序一致。常用的办法有两种：常用的办法有两种：第一种是基于反馈的流量控制。第一种是基于反馈的流量控制。第二种方法是基于速率的流控制。第二种方法是基于速率的流控制。2022年2月 134.1.4 链路管理链路管理 数据链路层链路管理功能包括链接的建立、数据链路层链路管理功能包括链接的建立、维持和释放。维持和释放。4.1.5 数据链路层提供的服务数据链路层提供的服务基本的服务有三种：基本的服务有三种： （1）无确认的无连接服务（局域网）无确认的无连接服务（局域网） 源节点向目的节点发送帧时，不需要建立链源节点向目的节点发送帧时，不需要建立链路连接，每个帧首部都携带有目的地址，目的路连接，每个帧首部都携带有目的地址，目的节点对收到的帧不作确认。这类服务适合于误节点对收到的帧不作确认。这类服务适合于误码率低码率低(如局域网如局域网)的数据传输。的数据传输。 2022年2月 144.1.5 数据链路层提供的服务数据链路层提供的服务（2）有确认的无连接服务（无线系统）有确认的无连接服务（无线系统 ）在无确认的无连接服务中引入了确认功能，即目的节点对在无确认的无连接服务中引入了确认功能，即目的节点对收到的每一帧都要向发送方发确认信号，并对发送方在规收到的每一帧都要向发送方发确认信号，并对发送方在规定的时间内没有收到确认信号的帧，采用超时重发机制。定的时间内没有收到确认信号的帧，采用超时重发机制。这类服务适用于传输可靠性不高的信道这类服务适用于传输可靠性不高的信道(如无线系统如无线系统)。 （3）有确认的面向连接的服务（三阶段）有确认的面向连接的服务（三阶段 ）将源节点和目的节点之间传送数据的过程分成三个阶段来将源节点和目的节点之间传送数据的过程分成三个阶段来完成。第一阶段是建立数据链路，第二阶段是进行数据帧完成。第一阶段是建立数据链路，第二阶段是进行数据帧传输，第三阶段是释放数据链路。传输，第三阶段是释放数据链路。 网络层和数据链路层之间的通信使用了标准的网络层和数据链路层之间的通信使用了标准的OSI服务服务原语：请求原语：请求(request)，指示，指示(indication)，响应，响应(response),证实证实(confirm)。 图图4-4用两种不同方式来说明这四种原语的使用关系。用两种不同方式来说明这四种原语的使用关系。 2022年2月 154.2.1检错码检错码 仅用来发现错误的码称为检错码仅用来发现错误的码称为检错码(error-detecting code)。在数据链路层常用的是循环冗余编码。在数据链路层常用的是循环冗余编码(Cycle Redundancy Code，CRC)，它具有检错能力强与实，它具有检错能力强与实现起来容易的特点。现起来容易的特点。 在数据后面添加上的冗余码称为在数据后面添加上的冗余码称为帧检验序列帧检验序列FCS (Frame Check Sequence)。 循环冗余检验循环冗余检验 CRC 和帧检验序列和帧检验序列 FCS并不等同。并不等同。CRC是一种常用的是一种常用的检错方法检错方法，而，而 FCS 是添加在数据后是添加在数据后面的面的冗余码冗余码。 FCS 可以用可以用 CRC 这种方法得出，但这种方法得出，但 CRC 并非用并非用来获得来获得 FCS 的惟一方法。的惟一方法。 2022年2月 16l假设待传送的数据为假设待传送的数据为F：1010001101（共（共M bit）。在数据位的后面再添加供差错检测用的）。在数据位的后面再添加供差错检测用的R bit 冗余码一起发送。总编码长度为冗余码一起发送。总编码长度为:N=M+R。l用二进制的模用二进制的模 2 运算进行运算进行 2n 乘乘 F 的运算，这相当的运算，这相当于在于在 F后面添加后面添加 R 个个 0。l得到的得到的 (M + R) bit 的数除以事先选定好的长度为的数除以事先选定好的长度为 (R + 1) bit 的数的数 G(x)【生成多项式】，得出商是【生成多项式】，得出商是 Q(x) 而余数是而余数是 R(x)，余数，余数 R(x) 比除数比除数 G(x) 至少要少至少要少1 个比特。个比特。lCRC生成多项式生成多项式G(x)由协议规定，目前已有多种生由协议规定，目前已有多种生成多项式列入国际标准中。成多项式列入国际标准中。2022年2月 17lCRC校验的具体步骤为：校验的具体步骤为： 实际的实际的CRC校验码的生成是采用二进制模校验码的生成是采用二进制模2算法，即减法不借位，加法不进位，是一种异算法，即减法不借位，加法不进位，是一种异或操作。或操作。l模二运算，加减规则：模二运算，加减规则： 两数相同为两数相同为0，两数相异为，两数相异为1，相当于逻辑，相当于逻辑异或运算。异或运算。2022年2月 18下面用一个例子来说明下面用一个例子来说明CRC检错方法。检错方法。（1）发送数据比特序列为）发送数据比特序列为110011（6比特）。比特）。（2）生成多项式比特序列为）生成多项式比特序列为11001（5比特，）。比特，）。（3）将发送数据比特序列乘以）将发送数据比特序列乘以24，那么产生的乘积应，那么产生的乘积应为为1100110000。（4）将乘积用生成多项式比特序列去除，则得到：）将乘积用生成多项式比特序列去除，则得到：求得余数比特序列为10012022年2月 19l将余数比特序列加到乘积中将余数比特序列加到乘积中, 得到实际的带校得到实际的带校验码的发送数据比特序列。验码的发送数据比特序列。l如果在数据传输过程中没有发生传输错误，如果在数据传输过程中没有发生传输错误，那么接收端接收到的带有那么接收端接收到的带有CRC校验码的接收校验码的接收数据比特序列一定能被相同的生成多项式整数据比特序列一定能被相同的生成多项式整除。除。l在在CRC校验码的实际应用中，校验码的生成校验码的实际应用中，校验码的生成与校验过程既可以用软件实现，也可以用硬与校验过程既可以用软件实现，也可以用硬件实现。件实现。2022年2月 202022年2月 21常用的几种生成多项式的国际标准为：常用的几种生成多项式的国际标准为：CRC-12: G(X)=XCRC-12: G(X)=X1212+X+X1111+X+X3 3+X+X2 2+X+1+X+1CRC-16(IBMCRC-16(IBM公司所采用的公司所采用的): G(X)=X): G(X)=X1616+X+X1515+X+X2 2+1+1CRC-16(CCITTCRC-16(CCITT所采用的所采用的): G(X)=X): G(X)=X1616+X+X1212+X+X5 5+1+1CRC-32: G(X)=XCRC-32: G(X)=X3232+X+X2626+X+X2323+X+X2222+X+X1616+X+X1212+X+X1111+X+X1010+X+X8 8+X+X7 7+X+X5 5+X+X4 4+X+X2 2+X+1+X+1 2022年2月 22G(x)R(x)Q(x) G(x)xf(x)kG(x)(x)RQ(x) G(x)x(x)fk2022年2月 232022年2月 24 )()()(1001110011000011001110011000011001)(1000014xRxxfxQxG 对应的代码是: 2022年2月 25检验码发送数据CRC10011100111001110011000001100111001110011100111001110011000012022年2月 2699.997%)21(-11-162022年2月 274.2.2 纠错码纠错码 纠错码纠错码(error-correcting code)是指在传输是指在传输过程中发生错误后能在接收端自行发现并纠正过程中发生错误后能在接收端自行发现并纠正的编码，使用纠错码的技术通常也称为前向纠的编码，使用纠错码的技术通常也称为前向纠错错(forward error correction)。具体实现时，。具体实现时，发送方在每一个要发送的数据块上附加足够的发送方在每一个要发送的数据块上附加足够的冗余信息，使接收方能够根据冗余信息推导出冗余信息，使接收方能够根据冗余信息推导出正确的接收数据应该是什么，达到纠错的目的。正确的接收数据应该是什么，达到纠错的目的。 2022年2月 284.3 基本数据链路协议4.3.1无限制单工协议无限制单工协议首先，讨论一个尽可能理想、简单的协议无限制单工协议：数据仅仅单向传输，发送端和接收端主机始终处于就绪状态；处理时间略去不计；缓冲器空间无限大。通信信道绝对可靠，从不丢失和损坏报文帧。此协议是一个空想的例子，故又称为乌托邦协议。2022年2月 29链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层R1R2R3H1H2局域网主机 H1主机 H2路由器 R1路由器 R2路由器 R3电话网局域网广域网从层次上来看数据的流动4.3 基本数据链路协议网络中的数据传输过程4.3.1无限制单工协议无限制单工协议2022年2月 30局域网广域网主机 H1主机 H2路由器 R1路由器 R2路由器 R3电话网局域网主机 H1 向 H2 发送数据链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层R1R2R3H1H2仅从数据链路层观察帧的流动数据链路层的简单模型2022年2月 314.3.1无限制单工协议无限制单工协议 完全理想化的数据传输是指链路为理想的传输信道，所传送的数据既不会出差错也不会丢失，而且不管发送端以多快的速率发送数据，接收端总是来得及收下，并及时上交主机。这样，数据的传输既不需要流量控制，也不需要差错控制。2022年2月 324.3.2 单工停单工停等协议等协议 单工停等协议的流程如图4-6所示。 单工停等协议是最简单流量控制的数据链路层协议。为了使接收端在任何情况下都有充足的时间处理接收数据帧，最简单的控制方法就是发送端每发送一帧就暂停发送，等待接收端传回确认信息，即确认接收端已正确接收后再发送下一帧，接收端收到数据帧后就交付给主机，然后向发送端传回一个确认信息，表示发送来的帧接收完成，发送端可以发送下一个数据帧了。 这种由接收端控制发送端发送数据流量的方法是计算机网络中流量控制的一种基本方法。 2022年2月 334.3.2 单工停单工停等协议等协议 基于图4-5的简化模型，单工停-等协议在发送节点和接收节点的工作流程如下： 图4-7分别示出了具有最简单流量控制的数据链路层协议以及没有任何流量控制的数据链路层协议的数据传输过程。图4-7a的接收端控制发送端的发送速率，发送端每发一帧就暂停下来，等待接收端的确认信息；图4-7b是没有任何流量控制的理想化情况，主机A将数据帧(data)连续发出，接收端总能正确、及时接收，并交付给主机B。显然，图4-7b的传输效率高。2022年2月 344.3.2 单工停单工停等协议等协议a) 具有最简单的流量控制的数据链路层协议 b) 没有任何流量控制数据链路层协议的数据传输 图4-7 两种不同情况的数据链路层协议 2022年2月 35时间ABDATA0送主机ACKDATA1送主机ACK(a) 正常情况ABDATA0DATA0送主机ACK(c) 数据帧丢失重传tout丢失 ！ABDATA0送主机ACKDATA0丢弃ACK(d) 确认帧丢失重传tout丢失 ！ABDATA0NAKDATA0送主机ACK(b) 数据帧出错重传出错四种情况4.3.3有噪声信道的单工协议有噪声信道的单工协议 图4-8数据帧在链路上传输的状态2022年2月 364.3.3有噪声信道的单工协议有噪声信道的单工协议 数据帧在链路上传输时可能出现的传输状态如图4-8所示。图4-8a是数据帧在链路传输过程中不出差错的传输状态，利用ACK帧的控制实现了接收端对发送端的流量控制。 图4-8b是数据帧在链路传输过程中出现差错的传输状态。当然，如果通信线路质量太差，主机A在重传一定的次数后，不再重传，而是向上一层报告，由上层处理。 图4-8c是在链路传输过程中发送的数据帧丢失的传输状态。发生帧丢失时接收节点不可能向发送节点发送任何回应信息帧(ACK帧或NAK帧)，发送节点也不可能接收到任何回应信息帧，这样将造成发送节点一直处于等待状态的死锁现象。同理，若接收节点发过来的回应信息帧丢失，如图4-8d所示，也同样会出现这种死锁现象。 2022年2月 37一般采用超时重传解决死锁问题。一般采用超时重传解决死锁问题。 l结点结点A发送完一个数据帧时，就启动一个发送完一个数据帧时，就启动一个超超时计时器时计时器(timeout timer)。l若到了超时计时器所设置的重传时间若到了超时计时器所设置的重传时间 tout而而仍收不到结点仍收不到结点 B 的任何确认帧，则结点的任何确认帧，则结点 A 就就重传前面所发送的这一数据帧。重传前面所发送的这一数据帧。l一般可将重传时间选为略大于一般可将重传时间选为略大于“从发完数据从发完数据帧到收到确认帧所需的平均时间帧到收到确认帧所需的平均时间”。 超时计时器的作用2022年2月 38 超时重传还有一种特殊情况重复帧。若丢失的是确认帧，则超时重传将使接收节点收到两个或多个同样的数据帧，即出现了重复帧，重复帧也是一种不允许出现的差错。 l使每一个数据帧带上不同的发送序号。每发送一个新的数据帧就把它的发送序号加 1。 l若结点 B 收到发送序号相同的数据帧，就表明出现了重复帧。这时应丢弃重复帧，因为已经收到过同样的数据帧并且也交给了主机 B。l但此时结点 B 还必须向 A 发送确认帧 ACK，因为 B 已经知道 A 还没有收到上一次发过去的确认帧 ACK。 l何种情况会出现重复帧？何种情况会出现重复帧？ 丢失的是确认帧，则超时重传将使接收节点收到两个或多个同样的数据帧，即出现了重复帧。 解决重复帧的问题2022年2月 39l任何一个编号系统的序号所占用的比特数一任何一个编号系统的序号所占用的比特数一定是有限的。因此，经过一段时间后，发送序定是有限的。因此，经过一段时间后，发送序号就会重复。号就会重复。 l序号占用的比特数越少，数据传输的额外开序号占用的比特数越少，数据传输的额外开销就越小。销就越小。 l对于停止等待协议，由于每发送一个数据帧对于停止等待协议，由于每发送一个数据帧就停止等待，因此用就停止等待，因此用一个比特来编号就够了一个比特来编号就够了。 一个比特可表示一个比特可表示 0 和和 1 两种不同的序号。两种不同的序号。l但序号选多少比特合适，主要依据是接收缓但序号选多少比特合适，主要依据是接收缓存的大小。存的大小。 帧的编号问题2022年2月 40 数据帧中的发送序号数据帧中的发送序号 N(S) 以以 0 和和 1 交替的方交替的方式出现在数据帧中。式出现在数据帧中。 每发一个新的数据帧，发送序号就和上次发送每发一个新的数据帧，发送序号就和上次发送的不一样。用这样的方法就可以使收方能够区的不一样。用这样的方法就可以使收方能够区分开新的数据帧和重传的数据帧了。分开新的数据帧和重传的数据帧了。 虽然物理层在传输比特时会出现差错，但由虽然物理层在传输比特时会出现差错，但由于数据链路层的停止等待协议采用了有效的检于数据链路层的停止等待协议采用了有效的检错重传机制，数据链路层对上面的网络层就可错重传机制，数据链路层对上面的网络层就可以提供以提供可靠传输可靠传输的服务。的服务。帧的发送序号与可靠传输2022年2月 41l在在“有噪声信道的单工协议有噪声信道的单工协议”的算法中一般的算法中一般不使用否认帧不使用否认帧(实用的数据链路层协议大都是这实用的数据链路层协议大都是这样的样的)，而且确认帧带有序号，而且确认帧带有序号 n。l按照习惯的表示法，按照习惯的表示法，ACKn 表示表示“第第 n 1 号号帧已经收到，现在帧已经收到，现在期望接收期望接收第第 n 号帧号帧”。lACK1 表示“0 号帧已收到，现在期望接收的下一帧是 1 号帧”；lACK0 表示“1 号帧已收到，现在期望接收的下一帧是 0 号帧”。(因为停止等待协议使用因为停止等待协议使用1位位ACK位，循环使用位，循环使用) 停止等待协议的算法2022年2月 42(1) 从主机取一个数据帧，送交发送缓存。从主机取一个数据帧，送交发送缓存。(2) V(S)0。：。：发送状态变量发送状态变量 (3) N(S)V(S)。：。：数据帧中的发送序号数据帧中的发送序号(4) 将发送缓存中的数据帧发送出去。将发送缓存中的数据帧发送出去。 (5) 设置超时计时器。设置超时计时器。(6) 等待。等待。 等待以下等待以下(7)和和(8)这两个事件中最先出现的一个这两个事件中最先出现的一个(7) 收到确认帧收到确认帧 ACKn， 若若 n = 1 V(s)，则：，则： 从主机取一个新的数据帧，放入发送缓存；从主机取一个新的数据帧，放入发送缓存； V(S)1 V(S)，转到，转到 (3)。 ：表明收到确认才修改发表明收到确认才修改发送变量送变量 否则，丢弃这个确认帧，转到否则，丢弃这个确认帧，转到(6)。：。：表明发送的数据帧没表明发送的数据帧没有被接收有被接收 (8) 若超时计时器时间到，则转到若超时计时器时间到，则转到(4)。发送结点算法2022年2月 43(1) V(R)0。：。：接收状态变量，初值为欲接收的发送接收状态变量，初值为欲接收的发送帧的序号帧的序号(2) 等待。等待。(3) 收到一个数据帧；收到一个数据帧； 若若 N(S) = V(R)，则执行，则执行(4)； 否则丢弃此数据帧，然后转到否则丢弃此数据帧，然后转到(6)。(4) 将收到的数据帧中的数据部分送交上层软件将收到的数据帧中的数据部分送交上层软件 （也就是数据链路层模型中的主机）。（也就是数据链路层模型中的主机）。(5) V(R)1 V(R)。可见只有接收成功才修改可见只有接收成功才修改V(R)(6) nV(R)； 发送确认帧发送确认帧 ACKn，转到，转到(2)。接收结点算法2022年2月 441)只有收到序号正确的确认帧只有收到序号正确的确认帧 ACKn 后，才更新发送后，才更新发送状态变量状态变量 V(S)一次，并发送新的数据帧。一次，并发送新的数据帧。2)接收端接收到数据帧时，要将收到的帧中的接收端接收到数据帧时，要将收到的帧中的N(S)与与本地的接收状态变量本地的接收状态变量 V(R) 比较。比较。l若二者相等表明是新的数据帧，收下并发送确认。l否则为重复帧，丢弃后仍须向发送端发送确认帧 ACKn，而接收状态变量 V(R) 和确认序号 n 都不变。(6) 3)连续出现相同发送序号的数据帧，表明发送端进行连续出现相同发送序号的数据帧，表明发送端进行了了超时重传超时重传(两种丢失两种丢失)。连续出现相同序号的确认帧，。连续出现相同序号的确认帧，表明接收端收到了表明接收端收到了重复帧重复帧。停止等待协议的要点2022年2月 454)发送端必须在其发送缓存中暂时保留已发数据帧的发送端必须在其发送缓存中暂时保留已发数据帧的副本副本。以便出差错时重传。只有收到该确认后才清。以便出差错时重传。只有收到该确认后才清除该副本。除该副本。5)实用的实用的 CRC 检验器都是用检验器都是用硬件硬件完成。完成。 CRC 检验器能够自动丢弃检测到的出错帧。对上检验器能够自动丢弃检测到的出错帧。对上层软件或用户来说层软件或用户来说感觉不到感觉不到。 发送端对出错的数据帧进行重传也是自动进行，发送端对出错的数据帧进行重传也是自动进行，因而这种差错控制体制常简称为因而这种差错控制体制常简称为 ARQ (Automatic Repeat reQuest)，直译是，直译是自动重传请求自动重传请求，但意思，但意思是是自动请求重传自动请求重传。停止等待协议的要点2022年2月 46l优点：优点：比较简单比较简单 。l缺点：通信信道的利用率不高，也就是说，缺点：通信信道的利用率不高，也就是说，信道还远远没有被数据比特填满。信道还远远没有被数据比特填满。l为了克服这一缺点，就产生了另外两种协议，为了克服这一缺点，就产生了另外两种协议，即即连续连续 ARQ 和和选择重传选择重传 ARQ。这将在后面。这将在后面进一步讨论。进一步讨论。停止等待协议 ARQ 的优缺点2022年2月 47l在发送完一个数据帧后，不停下来等待确认在发送完一个数据帧后，不停下来等待确认帧，而是可以连续再发送若干个数据帧。帧，而是可以连续再发送若干个数据帧。l如果这时收到了接收端发来的确认帧，那么如果这时收到了接收端发来的确认帧，那么还可以接着发送数据帧。还可以接着发送数据帧。l由于减少了等待时间，整个通信的吞吐量就由于减少了等待时间，整个通信的吞吐量就提高了。提高了。 连续 ARQ 协议1、连续、连续 ARQ 协议的工作原理协议的工作原理2022年2月 48DATA0DATA1DATA2DATA3DATA4DATA5重传 DATA2重传 DATA3ACK1ACK2ACK1 确认 DATA0ACK2 确认 DATA1DATA2 出错，丢弃DATA3 不按序，丢弃，重传 ACK2DATA4 不按序，丢弃，重传 ACK2DATA5 不按序，丢弃，重传 ACK2ACK3ACK3 确认 DATA2ACK4 确认 DATA3ACK4重传 DATA5重传 DATA4超时重传时间ABtout送交主机送交主机?ACK2ACK2ACK2连续 ARQ 协议2、连续 ARQ 协议示意图2022年2月 49 在实际网络中，需要双方向互传数据，为了提高信在实际网络中，需要双方向互传数据，为了提高信道的利用率，要允许一次连续发送多帧。道的利用率，要允许一次连续发送多帧。 在连续发送多帧时，并不是可以随意连续地发送，在连续发送多帧时，并不是可以随意连续地发送，必须对允许连续发送帧的数目加以限制。必须对允许连续发送帧的数目加以限制。滑动窗口协议规定滑动窗口协议规定:l发送端和接收端分别设定发送窗口和接收窗口发送端和接收端分别设定发送窗口和接收窗口 。l发送窗口用来对发送端进行流量控制。发送窗口用来对发送端进行流量控制。l发送窗口的大小发送窗口的大小 WT 代表在还没有收到对方确认信代表在还没有收到对方确认信息的情况下发送端最多可以发送多少个数据帧。息的情况下发送端最多可以发送多少个数据帧。 4.4 滑动窗口协议2022年2月 5001234567012发送窗口WT不允许发送这些帧允许发送 5 个帧(a)01234567012不允许发送这些帧还允许发送 4 个帧WT已发送(b)01234567012不允许发送这些帧WT已发送(c)01234567012不允许发送这些帧还允许发送 3 个帧WT已发送 已发送并已收到确认(d)2022年2月 51l在接收端只有当收到的数据帧的发送序号落在接收端只有当收到的数据帧的发送序号落入接收窗口内才允许将该数据帧收下。入接收窗口内才允许将该数据帧收下。 l若接收到的数据帧落在接收窗口之外，则一若接收到的数据帧落在接收窗口之外，则一律将其丢弃。律将其丢弃。 l在连续在连续 ARQ 协议中协议中,接收窗口的大小接收窗口的大小 WR = 1。l只有当收到的帧的序号与接收窗口一致时才能接收该帧。否则，就丢弃它。l每收到一个序号正确的帧，接收窗口就向前(即向右方)滑动一个帧的位置。同时发送对该帧的确认。 接收端设置接收窗口2022年2月 52不允许接收这些帧01234567012WR准备接收 0 号帧(a)不允许接收这些帧01234567012WR准备接收 1 号帧已收到(b)不允许接收这些帧01234567012WR准备接收 4 号帧已收到(c)2022年2月 53l只有在接收窗口向前滑动时（与此同时也发只有在接收窗口向前滑动时（与此同时也发送了确认），发送窗口才有可能向前滑动。送了确认），发送窗口才有可能向前滑动。l收发两端的窗口按照以上规律不断地向前滑收发两端的窗口按照以上规律不断地向前滑动，因此这种协议又称为滑动窗口协议。动，因此这种协议又称为滑动窗口协议。l当发送窗口和接收窗口的大小都等于当发送窗口和接收窗口的大小都等于 1时，时，就是停止等待协议。就是停止等待协议。 滑动窗口的重要特性2022年2月 54l当用当用 n 个比特进行编号时，若接收窗口的个比特进行编号时，若接收窗口的大小为大小为 1，则只有在发送窗口的大小，则只有在发送窗口的大小 WT 2n 1时，连续时，连续 ARQ 协议才能正确运行。协议才能正确运行。l例如，当采用例如，当采用 3 bit 编码时，发送窗口的最编码时，发送窗口的最大值是大值是 7 而不是而不是 8。否则在某些情况下协。否则在某些情况下协议不能正常工作。议不能正常工作。 发送窗口的最大值2022年2月 55(1)所有帧正确发送和接收导致序号循环所有帧正确发送和接收导致序号循环(2)所有确认帧丢失导致帧的判断问题所有确认帧丢失导致帧的判断问题如果是所有帧的确认帧丢失，超时后所有的帧都将重如果是所有帧的确认帧丢失，超时后所有的帧都将重发，这时接收方不能区分是新帧还是重发帧。发，这时接收方不能区分是新帧还是重发帧。发送窗口的取值问题2022年2月 56l不可能达到不可能达到 100 % 由于每个数据帧都必须包括一定的控制信息(如帧的序号、地址、同步信息以及其他的一些控制信息)，l当出现差错时当出现差错时(这是不可避免的这是不可避免的)，数据帧的，数据帧的不断重传将进一步使信道利用率降低。不断重传将进一步使信道利用率降低。 信道利用率2022年2月 57l若数据帧的帧长取得很短，那么控制信息若数据帧的帧长取得很短，那么控制信息在每一帧中所占的比例就增大，因而额外在每一帧中所占的比例就增大，因而额外开销增大，这就导致信道利用率的下降。开销增大，这就导致信道利用率的下降。l若帧长取得太长，则数据帧在传输过程中若帧长取得太长，则数据帧在传输过程中出错的概率就增大，于是重传次数将增大，出错的概率就增大，于是重传次数将增大，这也会使信道利用率下降。这也会使信道利用率下降。l由此可见，存在一个由此可见，存在一个最佳帧长最佳帧长，在此帧长，在此帧长下信道的利用率最高。下信道的利用率最高。 最佳帧长