数据链路层协议及差错控制.ppt

计算机网络与INTERNET原理及技术,计算机科学与技术专业 Major of Computer Science and Technology,主讲：郭银章 教授,第一讲：计算机网络概述,第二讲：计算机网络通信与数据交换技术,第三讲：数据链路层协议及差错控制技术,第四讲：局域网协议体系及以太网技术,目录提纲,第五讲：网络层网络互连协议IP/ICMP,第六讲：路由协议与路由算法,第七讲：传输层传输控制协议TCP/UDP,计算机网络与INTERNET原理及技术,第三讲：数据链路层协议及差错控制技术,3.1点到点通信的数据链路层概述,3.2数据链路层的帧同步技术,3.3数据链路层的差错检测技术,3.4数据链路层的差错控制技术,3.5数据链路层的流量控制技术,计算机网络与INTERNET原理及技术,3.6数据链路层协议HDLC和PPP,1、数据链路层概述 数据链路层位于物理层和网络层之间，物理层屏蔽了底层物理设备、传输介质以及通信技术的差异，向数据链路层提供数据传输服务。数据链路层将原始的、有差错的物理线路改造成逻辑上无差错的数据链路，向网络层提供无差错的数据服务。其提供的主要功能包括：差错控制、流量控制、帧的封装同步、透明传输、链路管理以及MAC寻址等。 数据链路层使用的通信信道有两种： 点到点信道和广播信道。点到点信道是收发双方一对一的通信方式。 广播信道则采用广播方式进行信息传递，需要专门协议来管理信道使用。 本章主要介绍比较简单的点到点信道数据链路层的问题。,3.1、数据链路层的概念,第三讲：数据链路层协议及差错控制技术,1、数据链路层概述,3.1、数据链路层的概念,第三讲：数据链路层协议及差错控制技术,我们可以把各种连接看作是一个节点到另一个节点的点到点通信,1、数据链路层概述,3.1、数据链路层的概念,第三讲：数据链路层协议及差错控制技术,2、数据链路层的功能 帧同步：数据链路层传输的数据格式为帧，在发送端进行封装成帧的时候，为了保证接收端能够同步接收数据，需要设置帧的起始定界符和结束定界符。 差错控制：采用奇偶校验、循环冗余码、校验和等进行差错检测；采用自动请求重传ARQ机制进行差错控制。 流量控制：流量控制一般采用滑动窗口机制防止数据溢出。 链路管理： 数据链路层的链路管理功能主要有链路的建立、维持和释放 透明传输：对于传输的数据内容、格式及编码没有限制、不负责信息结构意义的解释。,3.1、数据链路层的概念,第三讲：数据链路层协议及差错控制技术,2、数据链路层的功能 MAC寻址：不同于IP寻址，寻找的是计算机的物理地址，在以太网中采用媒体访问控制地址进行网络主机的定位。 数据与控制信息的区分:数据和控制信息都是在同一信道传输，打包在同一数据帧中，如何有效地区分数据信息和控制信息，是DH层必须解决的问题。,3.1、数据链路层的概念,第三讲：数据链路层协议及差错控制技术,3、数据链路层的服务 无确认无连接服务 源主机向目标主机发送独立的帧，目标主机不需要对这些帧进行确认。源端发送前，也不需要事先进行连接请求。对于数据完整性要求不高的网络服务，可使用该服务，以提高数据的传输效率。 有确认无连接服务：源主机在发送帧的时候，不需要事先建立连接。但是要对每一个发送的帧进行编号，目标主机要对接收的数据帧进行确认，源主机在规定的时间周期内没有收到ACK确认信息，则要重传已发送的数据帧。 有确认面向连接服务：发送数据前既要建立可靠的链接，又要对数据帧进行确认重传。保证每一帧数据只按正常顺序接收一次,3.1、数据链路层的概念,第三讲：数据链路层协议及差错控制技术,1、字符计数法 是一种面向字节的同步规程，它利用帧头部中的一个域来指定该帧中的字符数，以一个特殊的字符表示一帧开始，以一个专门的字段标注帧内的字符数。其同步原理是：接收方可以通过对该特殊字符的识别从比特流中区分出帧的开始，并从专门字段中获知该帧中随后跟随的数据字符数，从而确定帧的终止位置。其最大缺点是：标识帧大小的字段出错，将无法确定帧的长度，也不能进行重传。这种同步技术使用已经很少。,3.2、数据链路层的帧同步技术 帧同步要解决的核心问题：对物理层提供的比特流中进行数据帧的开始位和结束位进行识别。,第三讲：数据链路层协议及差错控制技术,2、字符填充的首尾定界符法 是一种使用特定的字符来定界一帧的起始与终止，以解决错误后的重新同步问题。控制字符SOH为帧的起始定界符，表示一幅帧的开始，控制字符EOT表示一幅帧的结束。,3.2、数据链路层的帧同步技术,第三讲：数据链路层协议及差错控制技术,2、字符填充的首尾定界符法 当帧的数据部分包含了控制字符EOT或者SOH的时候，就会发生帧同步传输错误。例如当数据部分出现EOT字符的时候，接收端就会认为帧的传输结束，将后边的数据丢弃，无法保证透明传输。解决策略：在数据部分出现的定界符前插入转义字符ESC,接收端删除ESC,并把其后的定界符当做数据处理,3.2、数据链路层的帧同步技术,第三讲：数据链路层协议及差错控制技术,2、字符填充的首尾定界符法,3.2、数据链路层的帧同步技术,第三讲：数据链路层协议及差错控制技术,3、比特填充的首尾定界符法 是以一组特定的比特模式来标识一帧的起始与终止。例如HDCL中的01111110.允许任意长度的位码，允许任意字符有任意长度的位。对于数据中包含连续的五个“1”的情况，采用“0位插入法”进行解决。例如：一个数据为“0110111111011111001”，在传输时就可以表示为： 0111111001101111101011111000101111110 比特填充帧同步方式很容易通过硬件实现，性能优于字符填充方式，所有面向比特的同步控制协议均采用比特填充同步方式，如：ISO、HDLC协议等,3.2、数据链路层的帧同步技术,第三讲：数据链路层协议及差错控制技术,1、数据链路层差错检测的原理 在数据通信系统中产生传输差错主要有随机差错和突发差错共同够成。 热噪声：传输媒体的电子热运动产生，是随机噪声引起随机差错。特点是随机存在、幅度小、与频率无关、单码元出错。 冲击噪声：由外界电磁干扰引起，主要有脉冲干扰、信号衰落、瞬时中断造成突发性错误。特点是幅度大、持续时间长、成批码元出错。 常用误码率来衡量信道的传输质量。,3.3、数据链路层的差错检测技术,第三讲：数据链路层协议及差错控制技术,1、数据链路层差错检测的原理 为了减少传输差错，一般采用两种策略：改善线路质量和差错检测与纠正。 改善线路质量：光纤的误码率是10-9 差错检测与控制：主动式差错控制策略。纠错有两种：请求重传机制（反馈重发纠错）、纠错码机制（向前纠错FEC）。 在发送端，通过对数据单元进行计算得到一个校验码作为发送数据的冗余码，然后将由数据单元和冗余码组成的发送数据进行传输。接收端收到数据后，采用相同的校验码计算方法求的标准的冗余吗，与数据帧携带的冗余码进行比较，如果不正确就表明数据出错了。,3.3、数据链路层的差错检测技术,第三讲：数据链路层协议及差错控制技术,1、数据链路层差错检测的原理,3.3、数据链路层的差错检测技术,第三讲：数据链路层协议及差错控制技术,E=f(数据),E=f(数据),比较,数据,发送器,接收器,接收信号是数据信号和噪声信号的叠加。热噪声、冲击噪声。数据传输的差错是随机差错和突发差错共同构成。,差错产生的原因：物理线路本身的电气特性产生的畸变和衰减、信号反射噪声回波效应、相邻串扰、外界因素。,2、奇偶校验检错码： 奇偶校验码是在所发送的每个字符后面添加一个校验位，称为奇偶位奇校验是指若字符中有奇数个1则添校验位0，若偶数个1，则添校验位1，最终保证字符中有奇数个1偶校验是指若字符中有奇数个1则添校验位1，若偶数个1，则添校验位0，最终保证字符中有偶数个1例如：发送1110010时，采用奇校验为11100101，偶校验为11100100 奇偶校验可以检测奇数位错误，而不能检测偶数位错误奇偶校验也无法判断是哪些位发生错误偶校验一般用于同步传输、奇校验一般用于异步传输。,3.3、数据链路层的差错检测技术,第三讲：数据链路层协议及差错控制技术,4、循环冗余CRC检错码： 在网络协议中最常用的差错检测技术是循环冗余码校验技术CRC，它能检测出更多的错误，常用在数据链路层，在网络传输的数据帧的后面有一个帧校验序列FCS就是CRC。其原理是： 假定：M表示被传输的数据字符位串，有K位P是位的标准位串，与M无关，r=k-1.rM用P除时，得商Q和余数R，则2rM=QP+R.注意：这里的运算是以2为模的运算，即加不进位，减不借位，所以余数R至少比P少一位，R的位数可以看作是不大于r位的比特位串。R就是M对P的循环冗余码CRC，记为F。被传输的数据帧M与帧校验序列F组成帧T，即： T=2rM+F=2rM+R=(QP+R)+R,3.3、数据链路层的差错检测技术,第三讲：数据链路层协议及差错控制技术,4、循环冗余CRC检错码： 对于任何二进制数X，XX，所以，RR0，这说明T应该能够被P整除。即如果收到的T不能被P整除，则一定发生差错，这就是循环冗余码校验。当然如果收到的T能构被P整除，则不一定说明传输中没有错误。下面举例说明： 例：给定M1101011101 P101101 求F和T。 解：由于P101101为6位，则r+1=6,r=5,F为位。rM=110101110100000,作除法,3.3、数据链路层的差错检测技术,第三讲：数据链路层协议及差错控制技术,4、循环冗余CRC检错码：,3.3、数据链路层的差错检测技术,第三讲：数据链路层协议及差错控制技术,101101,110101110100000,101101,110001,101101,111001,101101,101000,101101,101100,101101,1000,余数R,1111001000商Q,4、循环冗余CRC检错码： 解：F=R=01000,T=25M+F=110101110101000 若收到的T110101010101000，则不能被P除尽，检测到错误，若收到的 T111111111111000，出错4位，但能够被P除尽 CRC一般用多项式表示，目前广泛使用的16次多项式P(X)标准有： CRC-16:X16+X15+X2+1 CRC-CCITT:X16+X12+X5+1 CRC计算过程的实现电路采用异或门电路和移位寄存器实现,3.3、数据链路层的差错检测技术,第三讲：数据链路层协议及差错控制技术,1、自动重传请求ARQ机制 当接收端检测出数据帧中的错误后，就将有错误的帧丢弃，那么出错的数据帧如何恢复呢？这就是差错控制技术，其基本技术就是自动重传请求ARQ技术，其核心是通过收发双方的确认和重传方式实现确认技术有： 正确认超时重传：接收方在成功接收无差错的数据帧后，返回给发送方一个正确认消息ACK若发送方在超过一定时间间隔后，没有收到ACK，则重新发送该数据帧。 负确认重传：接收方在检测到数据帧有差错时，返回一个负确认NAK，发送方重发该数据帧,3.4、数据链路层的差错控制技术,第三讲：数据链路层协议及差错控制技术,2、停等ARQ协议 停等差错控制技术采用的是正确认超时重传机制。就是发送方每发送一个数据帧就等待一个正确认，在收到接收方发送的ACK后才发送下一个数据帧 帧的差错可能有： 数据帧丢失和出错：接收方没有收到或检测到错误的数据帧时，丢弃该错误的数据帧，发送方通过超时重传方式，重发数据该数据帧 ACK消息出错：帧正确到达目的地，接收端也正确接收，但是返回的ACK丢失或出错，发送方仍收不到正确认，超时后，发送方仍然重发该帧，这样，接收端收到两个一样的数据帧如何处理？ 解决上述问题的方法是给每个数据帧编上序号，比如F0、F1、F2、F3，若接收方连续收到两个序号相同的帧，则为重复的数据帧，丢弃！,3.4、数据链路层的差错控制技术,第三讲：数据链路层协议及差错控制技术,2、停等ARQ协议,3.4、数据链路层的差错控制技术,第三讲：数据链路层协议及差错控制技术,2、停等ARQ协议 ACK要指明下一个准备接收的数据帧的序号，比如ACK2，表示准备接收的是F2，且F2以前的帧已全部正确接收停等ARQ最大优点就是简单，但是缺点是效率低下，每发一个数据帧，发送方都要停下来等待浪费了大量的网络时间 任何一个编号系统的序号所占用的比特数一定是有限的，所以发送序号总是循环出现。序号占用的比特越少，数据传输的额外开销就越小。,3.4、数据链路层的差错控制技术,第三讲：数据链路层协议及差错控制技术,3、后退N-ARQ协议 后退N-ARQ技术，就是在发送方收到ACK之前可以连续发送多个数据帧，而不必等待正确认ACK（n）的到来但是，如果在这期间接收到一个错误的NCK（n），则n以后的所有已发送的帧都需重发.这就是后退N机制 比如发送方最多可发送8个数据帧而无需确认，即窗口大小为8，如果第4个帧出错，即收到NCK（4），则表明03的数据帧正确接收，而帧4及以后的数据帧F5-F7全部被接收端丢弃和忽略，发送方从F7后退到F4，再重新发送F4-F7如图所示. 后退N机制，采取累计确认的方式，可以应用ACK和NCK结合的方式实现,3.4、数据链路层的差错控制技术,第三讲：数据链路层协议及差错控制技术,3、后退N-ARQ协议,3.4、数据链路层的差错控制技术,第三讲：数据链路层协议及差错控制技术,发送方,接收方,F0,F1,F6,F3,F2,F4,F5,F7,ACK2,ACK4,NCK4,重发F4,重发F5,重发F6,重发F7,ACK5,ACK7,4、选择重发ARQ协议 后退N机制解决了停等ARQ的网络利用率低的问题，但是后退N在重发的时侯，不管N后面的数据帧是否有错，都要重新发送，这样浪费了系统资源，于是提出了选择重发ARQ技术选择重发ARQ只是发送出错的数据帧，这样提高了信道的利用率，但是要求接收方维持较大的缓冲区间，以便存储已到达、无差错、但序号不连续的帧，等到发送方重发的帧到齐后，再将其插入到适当位置进行按序接收。,3.4、数据链路层的差错控制技术,第三讲：数据链路层协议及差错控制技术,4、选择重发ARQ协议,3.4、数据链路层的差错控制技术,第三讲：数据链路层协议及差错控制技术,选择重发ARQ要求一次发送窗口的大小应不大于帧编号数的1/2. 例如：编号为3，则一次发送窗口的大小为23X1/2=23-1=4,1、滑动窗口流量控制协议原理 在数据链路层，由于收发双方各自工作速率和缓冲存储空间的差异，当发送发发送的数据速率大于接收方接收的能力时，就会发生数据的溢出和丢失。这时，就需要对收发双方的数据流量进行控制，使发送方的速率不致超过接收方所能承受的能力。这就是数据链路层的流量控制。 流量控制的过程需要通过某种反馈机制使发送方知道接收方是否能跟的上发送速率，需要有一些规则控制发送方的发送和等待时机。 最简单的流控机制就是停等流控，但是这种流控技术效率太低，所以现在普遍采用的是滑动窗口流控机制其工作原理是,3.5、数据链路层的流量控制技术,第三讲：数据链路层协议及差错控制技术,1、滑动窗口流量控制协议原理 （1） 通信双方在数据交换前，准备好各自的接收缓存区，并通告对方，作为对方的发送窗口 （2）发送方在收到确认前，可以发送的最大数据量是由发送窗口大小决定，在没有收到ACK时，窗口在不断缩小，只有收到ACK，窗口才能向右滑动相应空间。 （3）接收端可以接收的最大数据量是接收窗口的大小每接收一个数据帧，窗口就收缩一个空位，当通过帧的差错检测后，并向发送端发送ACK后，接收窗口就向右滑动并扩展空位 （4）帧的顺序号占据帧的一个域，域的位数决定了顺序号的大小，比如域的大小是三位，则帧的编号为0(-)。,3.5、数据链路层的流量控制技术,第三讲：数据链路层协议及差错控制技术,2、滑动窗口流量控制举例,3.5、数据链路层的流量控制技术,第三讲：数据链路层协议及差错控制技术,0,1,2,3,4,5,6,7,0,0,1,2,3,4,5,6,7,0,0,1,2,3,4,5,6,7,0,0,1,2,3,4,5,6,7,0,0,1,2,3,4,5,6,7,0,0,1,2,3,4,5,6,7,0,0,1,2,3,4,5,6,7,0,0,1,2,3,4,5,6,7,0,F0,F1,F2,ACK3,滑动窗口流控机制图示,2、滑动窗口流量控制举例 滑动窗口流量控制机制的特点是：发送方根据接收方的接收窗口大小界定发送数据量，滑动窗口左边为已发送并确认的数据，窗口内为可以一次发送的数据，窗口右边为待发送的数据,3.5、数据链路层的流量控制技术,第三讲：数据链路层协议及差错控制技术,1、HDLC简介： 1974年美国IBM公司推出了著名的系统网络体系结构SNA,SNA中数据链路层协议采用了面向比特的SDLC协议，后来国际标准化组织将其改为HDLC. HDLC协议是一个面向比特流的通用数据链路协议，他描述了数据链路层帧的结构和收发双方对数据链路的控制规程。可实现完全可靠的数据帧的传输控制。包括帧的确认重传、差错控制、流量控制等。当有多个节点时，HDLC对链路的使用权轮询控制机制。由主站发起、从站发起和混合发起三种模式。,3.6、高级数据链路控制HDLC协议,第三讲：数据链路层协议及差错控制技术,2、HDLC的操作方式： 主节点方式操作、从节点方式操作、混合节点操作。 主节点负责对数据流的组织和数据差错控制的实施。主节点到从节点发送的是命令帧，反之为响应帧。HDLC常用的操作方式有三种： 正常响应方式NRM：非平衡数据链路操作方式。适用于面向终端的点到点或点到多点的链路。主节点启动，进行管理整个链路、超时重传、轮询、选择从节点等管理功能。 异步响应方式ARM：非平衡数据链路操作方式。从节点启动，从节点向主节点发送帧，从节点控制超时重传和轮询。 异步平衡方式ABM：允许任何节点来启动数据传输。,3.6、高级数据链路控制HDLC协议,第三讲：数据链路层协议及差错控制技术,3、HDLC的帧格式：,3.6、高级数据链路控制HDLC协议,第三讲：数据链路层协议及差错控制技术,比特 8 8 8 可变 16 8,标志字段：01111110，作为帧的开始与结束标志。当处于连接状态时，可连续发送标志位，直到出现数据为止。数据透明传输采用“0比特插入法”处理。 地址字段：取决于所采用的操作方式，全1为广播地址，全0为无节点地址。从节点与组合节点都被分配一个唯一的地址。,3、HDLC的帧格式：,3.6、高级数据链路控制HDLC协议,第三讲：数据链路层协议及差错控制技术,控制字段：用于构成各种命令及响应，以实现对链路层的监视与控制。发送方主节点或组合节点利用控制字段来通知被寻址的从节点执行约定操作。从节点用该字段作为对命令的响应，报告已经完成的操作或状态变化。控制字段的前两位是帧类型：信息帧、监控帧和无编号帧。第五位是P/F：轮询/终止位。 信息字段：长度不限，上限由FCS字段和通信节点的缓冲容量决定。国际上一般采用1000-2000bit FCS帧校验序列：16 位CRC，生成多项式为16、12、5、1,4、HDLC的帧类型：,3.6、高级数据链路控制HDLC协议,第三讲：数据链路层协议及差错控制技术,信息帧（I帧）：控制字段第一位为0表示，用于传送有效信息和数据。用控制字段N(S)存放发送帧序列，N(R)存放接收方下一个预期接收的帧序号。 监控帧（S帧）：控制字段10表示。用于差错控制和流量控制。INFO由6个字节48位表示。控制字段的3、4位是帧的类型编码，共有4种组合：,4、HDLC的帧类型：,3.6、高级数据链路控制HDLC协议,第三讲：数据链路层协议及差错控制技术,00-接收就绪RR：主节点使用RR型的S帧轮询从节点，希望从节点传输编号为N(R)的信息帧。从节点使用RR型的S帧响应，表示希望从主节点那里接收的下一个信息帧的编号为N(R) 01-拒绝REJ：用以要求发送方从编号为N(R)开始及其以后的帧重新发送，同时，N(R)以前的信息帧已正确接收 10-接收未就绪RNR：表示编号为N(R)以前的帧已经收到，但是正在进行接收处理，但是编号为N（R）的信息帧接收尚未准备好，主要是用来进行流量控制。 11-选择拒绝SREJ：要求重新发送编号为N(R)的帧，并表示其他编号的帧已正确接收。,4、HDLC的帧类型：,3.6、高级数据链路控制HDLC协议,第三讲：数据链路层协议及差错控制技术,无编号帧（U帧）：无编号帧因其控制字段不包含字段N(S)和字段N(R)而得名。用于提供对链路的建立、拆除和多种控制功能。这些控制功能用5个M位表示32种附加命令功能或32中应答功能。 5、HDLC的应用特点： 应用场合：HDLC适用于点到点和点到多点式的系统结构。从工作方式而言，适用于半双工或全双工结构。从传输方式而言，适用于同步传输和中高速传输。,3.6、高级数据链路控制HDLC协议,第三讲：数据链路层协议及差错控制技术,传输效率：HDLC开始发送一帧后，就可以连续不断地发送所有的帧。可同时确认多幅帧。HDLC的每幅帧都含有地址字段，在多点结构中，每个从节点只接收含有本节点地址的帧，主节点在选中一个从节点并与之通信的同时，不用拆除链路，就可以选择其他节点通信，所以具有很高的传输效率。 传输可靠性：HDCL所有帧都包含FCS,按照窗口序号顺序传输。 数据透明性：HDCL采用“0比特插入法”对数据进行透明传输，传输信息的组合方式无任何限制。 信息传输格式：HDCL采用统一的帧格式实现数据、命令、响应的传输。 链路控制：HDCL利用改变帧中的控制字段编码格式完成各种规定的链路操作功能，提供面向比特的传输功能。,3.7、点对点协议PPP,第三讲：数据链路层协议及差错控制技术,现在全世界使用得最多的数据链路层协议是点对点协议 PPP (Point-to-Point Protocol)。用户使用拨号电话线接入ISP,获取临时IP地址，结束后释放IP地址。用户连接到ISP使用的协议标准就是 PPP 协议。,1、PPP协议简介,3.7、点对点协议PPP,第三讲：数据链路层协议及差错控制技术,协议简单：接收方每收到一个帧，就进行CRC校验，正确接受，错误丢弃 采用特殊字符作为帧的定界符封装成帧 ，可实现透明传输 可在同一条物理链路上支持多种网络层协议以及能够在多种链路上运行 PPP协议具有快速检测数据链路的连接状态，具有及时检查的特点 PPP协议对每一种类型的点到点链路设置一个最大传输单元默认值MTU，MTU不是帧的总长度，是指帧数据部分的长度。若超过MTU就丢弃。 PPP协议具有网络层地址协商功能,2、PPP协议的特点,3.7、点对点协议PPP,第三讲：数据链路层协议及差错控制技术,PPP协议由三部分组成：一个将IP数据封装到串行链路的策略，一个用来建立、配置和测试数据链路连接的链路控制协议LCP,一套网络控制协议NCP PPP的帧格式：,3、PPP协议的帧格式,3.7、点对点协议PPP,第三讲：数据链路层协议及差错控制技术,（1）帧的首尾定界符 F = 0x7E （符号“0x”表示后面的字符是用十六进制表示。十六进制的 7E 的二进制表示是 01111110），PPP收尾均出现，作为帧的定界符使用。 （2）地址字段 A 只置为 0xFF，控制字段 C 通常置为 0x03。地址和控制字段实际上并不起作用。 （3）PPP 有一个 2 个字节的协议字段。 若为 0x0021，PPP 帧的信息字段就是IP数据报。 若为 0xC021, 则信息字段是 PPP 链路控制数据。 若为 0x8021，则表示这是网络控制数据。,3、PPP协议的帧格式,3.7、点对点协议PPP,第三讲