链路+规程控制数据传输课件

计计 算算 机机 网网 络络 COMPUTER NETWORKS第第5章章 数据链路层数据链路层第5章 数据链路层5.1 5.1 基本概念基本概念n链路：一条无源的点到点的物理线路段。链路：一条无源的点到点的物理线路段。n数据链路：链路数据链路：链路+规程（控制数据传输）。规程（控制数据传输）。n数据链路层的作用：数据链路层的作用：通过一些数据链路层协议（即链路控制规程）通过一些数据链路层协议（即链路控制规程），在不太可靠的物理链路上实现可靠的数，在不太可靠的物理链路上实现可靠的数据传输。据传输。学习重点学习重点:两台机器之间实现可靠、有效的通两台机器之间实现可靠、有效的通信而涉及到的一些算法。信而涉及到的一些算法。5.1 基本概念n数据链路层的主要功能：数据链路层的主要功能：链路管理链路管理：数据链路的建立、维持和释放；：数据链路的建立、维持和释放；帧同步帧同步：收方能从收到的比特流中区分一帧开始和结束的：收方能从收到的比特流中区分一帧开始和结束的地方；地方；流量控制流量控制：发方发送数据的速率必须使收方来得及接收；：发方发送数据的速率必须使收方来得及接收；差错控制差错控制：收方收到有差错的数据帧时，能检错重传或纠：收方收到有差错的数据帧时，能检错重传或纠错；错；透明传输透明传输：不管所传数据是什么样的比特组合，收方都能：不管所传数据是什么样的比特组合，收方都能正确接收。并能正确接收。并能将数据与控制信息分开；将数据与控制信息分开；寻址寻址：保证每一帧都能发送到目的站。：保证每一帧都能发送到目的站。设计要点设计要点；1）向网络层提供一个定义良好的服务接口）向网络层提供一个定义良好的服务接口 2）处理传输错误）处理传输错误 3）调节数据流，确保慢速的接收方不会被除快）调节数据流，确保慢速的接收方不会被除快速的发送方淹没。速的发送方淹没。数据链路层的主要功能：5.1.2 5.1.2 为网络层提供的服务为网络层提供的服务最主要的服务是将数据从源机器的网络层传输到目最主要的服务是将数据从源机器的网络层传输到目标机器的网络层标机器的网络层.无确认的无连接的服务无确认的无连接的服务：(P56)(P56)适用于误码率很低的通信信道；或语音通信；适用于误码率很低的通信信道；或语音通信；有确认的无连接的服务有确认的无连接的服务：适用于误码率很高的通信信道；如无线通信；适用于误码率很高的通信信道；如无线通信；有确认的面向连接的服务有确认的面向连接的服务：适用于通信要求较高（可靠性、实时性）的情况适用于通信要求较高（可靠性、实时性）的情况5.1.2 为网络层提供的服务最主要的服务是将数据从源机器的5.1.35.1.3成帧方法成帧方法字符计数法字符计数法：在帧头部指明帧内字符数。在帧头部指明帧内字符数。问题：由于传输差错导致计数值被问题：由于传输差错导致计数值被“篡改篡改”；5.1.3成帧方法字符计数法：字符填充首尾界符法：字符填充首尾界符法：以以ASCII字符字符DLE和和STX作为帧的头部，作为帧的头部，DLE和和ETX作为帧的尾部（作为帧的尾部（DLE10H、STX02H、ETX 03H）技术：如何避免二进制数据可能与帧的头尾标志技术：如何避免二进制数据可能与帧的头尾标志相同？相同？发送方在数据中遇到发送方在数据中遇到DLE时，自动在其前后插入时，自动在其前后插入一个一个DLE;接收方在数据中遇到单个接收方在数据中遇到单个DLE时时,可确定帧界可确定帧界;遇遇到到2个个DLE时，自动删除一个时，自动删除一个DLE。字符填充首尾界符法：位填充首尾标志法：以一个特定的字节信息作为帧的头尾标志；如01111110；为了避免与原始数据比特组合相同，发送方在数据中遇到5个连续的1时，自动在其后插入一个0；接收方在数据中遇到5个连续的1后面跟着一个0，自动将此0删除。位填充首尾标志法：5.1.4 差错控制差错控制差错产生的原因主要由通信信道的噪声引起，差错产生的原因主要由通信信道的噪声引起，通信信道噪声分为二种：通信信道噪声分为二种：（1）热噪声：由传输介质导体的电子热运）热噪声：由传输介质导体的电子热运动产生。幅度较小，是产生随机差错的主动产生。幅度较小，是产生随机差错的主要根源；要根源；（2）冲击噪声：由外界电磁干扰产生，幅）冲击噪声：由外界电磁干扰产生，幅度较大，是产生突发差错的主要根源。度较大，是产生突发差错的主要根源。其中冲击噪声是引起差错的主要原因。其中冲击噪声是引起差错的主要原因。5.1.4 差错控制n差错评价指标如下：差错评价指标如下：n（1）误码率：）误码率：错传的码元数与所传输码元总数错传的码元数与所传输码元总数之比。之比。n PeNe/Nn其中，其中，N 传输的码元总数，传输的码元总数，Ne 错传的的码错传的的码元数。元数。n（2）误比特率：）误比特率：n错传的比特数与所传输总比特数之比。错传的比特数与所传输总比特数之比。n在二进制码元时，误比特率误码率。在二进制码元时，误比特率误码率。差错评价指标如下：n差错控制的基本方式如下：差错控制的基本方式如下：n（1）反馈纠错）反馈纠错n 在接收端能发现差错，但不能确定错码的位置，通过在接收端能发现差错，但不能确定错码的位置，通过反馈信息请求发送端重发，直到接收端肯定确认为止。反馈信息请求发送端重发，直到接收端肯定确认为止。n 适用于双工通信和非实时通信系统。适用于双工通信和非实时通信系统。n（2）前向纠错）前向纠错n在接收端不仅能发现错码，而且还能确定错码的位置，在接收端不仅能发现错码，而且还能确定错码的位置，并纠正错误。并纠正错误。n适用于单工通信和实时通信系统。适用于单工通信和实时通信系统。n（3）混合纠错）混合纠错n少量差错在接收端自动纠正，若超出自行纠正能力时，少量差错在接收端自动纠正，若超出自行纠正能力时，通过反馈信息请求发送端重发。通过反馈信息请求发送端重发。差错控制的基本方式如下：5.1.5流控制流控制n基于反馈的流控制基于反馈的流控制n基于速率的流控制基于速率的流控制5.1.5流控制5.2错误检测和纠正错误检测和纠正5.2 错误检测和纠正码字的检错与纠错能力码字的检错与纠错能力码字码字(n位位)数据码数据码(m位位)+冗余码冗余码(r位位)。海明距离：两个码字之间对应码元位的不同海明距离：两个码字之间对应码元位的不同码元的个数。码元的个数。码字的检错与纠错能力码字(n位)数据码(m位)+冗余码(r码字编码的海明距离码字编码的海明距离对于一种码字编码，在这个码字集合中，可得到对于一种码字编码，在这个码字集合中，可得到所有任意两个码字的海明距离，所有任意两个码字的海明距离，其中最小的海其中最小的海明距离称为该码字编码的海明距离明距离称为该码字编码的海明距离d。n定理定理1：如果：如果d2t+1,则该编码可则该编码可纠正纠正任何任何t个个(或或t个以下个以下)的错误。的错误。n定理定理2：如果：如果de+1,则该编码可则该编码可检测检测出任何出任何e个个(或或e个以下个以下)的错误。的错误。一般情况下，冗余位越多一般情况下，冗余位越多(即即r越大越大)，检错纠错，检错纠错能力越强，但相应的编码效率也随之降低了。能力越强，但相应的编码效率也随之降低了。码字编码的海明距离对于一种码字编码，在这个码字集合中，可得到示例：偶校验的检错与纠错能力示例：偶校验的检错与纠错能力例：例：对于偶校验（对于偶校验（使每个码字中都有偶数个使每个码字中都有偶数个1）数）数据码为据码为2位（有用数据为位（有用数据为00、01、10、11）冗余码）冗余码为为1位（偶校验位）位（偶校验位）有用数据经过偶校验编码，其码字集合：有用数据经过偶校验编码，其码字集合：000、011、101、110；该编码的海明距离该编码的海明距离d=2，根据根据定理定理1，该编码不能纠正任何错误该编码不能纠正任何错误(t0)。D=2t+1D=2t+1根据根据定理定理2，该编码可检测出任何该编码可检测出任何1个错误个错误(e1)。D=e+1D=e+1奇校验的检错能力与偶校验一样。奇校验的检错能力与偶校验一样。示例：偶校验的检错与纠错能力例：对于偶校验（使每个码字中都有误码控制编码的分类误码控制编码的分类按冗余码的控制功能分按冗余码的控制功能分:纠错码纠错码：在接收端能发现并自动纠正差错。：在接收端能发现并自动纠正差错。叫前向纠错叫前向纠错纠错检错的常用方法纠错检错的常用方法海明码海明码：可纠错和检错，实现复杂，效率：可纠错和检错，实现复杂，效率低。低。奇偶校验码奇偶校验码：方法简单，检错能力差。：方法简单，检错能力差。循环冗余编码循环冗余编码(CRC)：实现容易，检错：实现容易，检错能力强，广泛使用。能力强，广泛使用。误码控制编码的分类按冗余码的控制功能分:5.2.15.2.1纠错码：海明码纠错码：海明码海明在海明在1950年提出的可纠正年提出的可纠正一位错一位错的编码方法。的编码方法。用用r个校验位构造出个校验位构造出r个校验关系式来指示一位错码的个校验关系式来指示一位错码的n(=m+r)种可能位置及表示无差错。种可能位置及表示无差错。n码字排列：从最左边位开始依次编号码字排列：从最左边位开始依次编号(1、2、n);r个校验位：在个校验位：在2k的位置的位置(1、2、4、8、);m个数据位：在其余位个数据位：在其余位(3、5、6、7、9、)。r的确定：的确定：r2rm+1;（r2 n1=m+r+1）例如：例如：4个信息位个信息位D1D2D3D4，3个校验位个校验位P1P2P3。5.2.1纠错码：海明码海明在1950年提出的可纠正一位错的5.2.25.2.2检错码：循环冗余码检错码：循环冗余码CRC码码n特点：特点：实现容易，检错能力强，广泛使用。实现容易，检错能力强，广泛使用。常结合常结合反馈重传法反馈重传法来保证信息的可靠传输。来保证信息的可靠传输。n码字组成：码字组成：5.2.2检错码：循环冗余码CRC码特点：实现容易，检错能例：若数据码例：若数据码110011，可表示为：可表示为：M(x)=1x5+1x4+0 x3+0 x2+1x+1即：即：M(x)=x5+x4+x+1。生成多项式生成多项式G(x)：G(x)=grxr+.+gixi+.+g1x+g0其中其中,gi=0或或1,ri0,gr 0,g0 0,共共r+1位位G(x)被通信双方事先共同选定使用：被通信双方事先共同选定使用：发送端：通过发送端：通过G(x)生成校验码；生成校验码；接收端：通过接收端：通过G(x)校验接收的码字。校验接收的码字。对于多项式的运算：采用模对于多项式的运算：采用模2计算（加法不进位，减法不借位）；计算（加法不进位，减法不借位）；加减法是一样的。加减法是一样的。模模2计算即是异或运算。计算即是异或运算。例：若数据码110011，循环冗余检验的原理循环冗余检验的原理 n在数据链路层传送的帧中，广泛使用了循在数据链路层传送的帧中，广泛使用了循环冗余检验环冗余检验 CRC 的检错技术。的检错技术。n在发送端，先把数据划分为组。假定每组在发送端，先把数据划分为组。假定每组 k 个比特。个比特。n假设待传送的一组数据假设待传送的一组数据 M=101001（现在（现在 k=6）。我们在）。我们在 M 的后面再添加的后面再添加供差错检测用的供差错检测用的 n 位冗余码一起发送。位冗余码一起发送。循环冗余检验的原理 在数据链路层传送的帧中，广泛使用了循环冗冗余码的计算冗余码的计算 n用二进制的模用二进制的模 2 运算进行运算进行 2n 乘乘 M 的运算，的运算，这相当于在这相当于在 M 后面添加后面添加 n 个个 0。n得到的得到的(k+n)位的数除以位的数除以事先选定好事先选定好的长度为的长度为(n+1)位的除数位的除数 P，得出商，得出商是是 Q 而余数是而余数是 R，余数，余数 R 比除数比除数 P 少少1 位，即位，即 R 是是 n 位。位。冗余码的计算 用二进制的模 2 运算进行 2n 乘 M 的运冗余码的计算举例冗余码的计算举例 n现在现在 k=6,M=101001。n除数除数 P=1101，则，则 n=3,n被除数是被除数是 2nM=101001000。冗余码的计算举例 现在 k=6,M=101001。110101 Q(商)P(除数)1101 101001000 2nM(被除数)1101 1110 1101 0111 0000 1110 1101 0110 0000 1100 1101 001 R(余数)，作为 FCS 循环冗余检验的原理说明循环冗余检验的原理说明 n模模 2 运算的结果是：商运算的结果是：商 Q=110101，余数余数 R=001。n把余数把余数 R 作为冗余码添加在数据作为冗余码添加在数据 M 的后的后面发送出去。发送的数据是：面发送出去。发送的数据是：2nM+R 即：即：101001001，共，共(k+n)位。位。模 2 运算的结果是：商 Q=110101，检测出差错检测出差错n接接收收方方对对接接收收到到的的数数据据除除以以同同样样的的除除数数,只只要要得得出出的余数的余数 R 不为不为 0，就表示检测到了差错。，就表示检测到了差错。n但但这这种种检检测测方方法法并并不不能能确确定定究究竟竟是是哪哪一一个个或或哪哪几几个比特出现了差错。个比特出现了差错。n一旦检测出差错，就丢弃这个出现差错的帧。一旦检测出差错，就丢弃这个出现差错的帧。n只只要要经经过过严严格格的的挑挑选选，并并使使用用位位数数足足够够多多的的除除数数 P，那么出现检测不到的差错的概率就很小很小。，那么出现检测不到的差错的概率就很小很小。检测出差错接收方对接收到的数据除以同样的除数,只要得出的余数链路+规程控制数据传输课件考研复习指导练习题：考研复习指导练习题：1)要发送的数据是要发送的数据是1101 0110 11,采用采用CRC校验，生成多项式是校验，生成多项式是10011,那么最那么最终要发送的数据是：终要发送的数据是：A.1101 0110 111010B.1101 0110 110110C.1101 0110 111110D.1101 0110 111100考研复习指导练习题：2 在数据的传输过程中，若接收方收到的二进在数据的传输过程中，若接收方收到的二进制比特序列是：制比特序列是：1011 0011 010,接收双方接收双方采用的生成多项式是：采用的生成多项式是：G(x)=x4+x3+1,则该二进制比特序列在传输中是否出错？如果则该二进制比特序列在传输中是否出错？如果未出现差错，发送数据的比特序列和未出现差错，发送数据的比特序列和CRC检检验码序列分别是什么？验码序列分别是什么？2 在数据的传输过程中，若接收方收到的二进制比特序列是：101 数据链路(即逻辑链路)与链路(即物理链路)有何区别?“电路接通了”与”数据链路接通了”的区别何在?n答：数据链路与链路的区别在于数据链路出链路外，还必须答：数据链路与链路的区别在于数据链路出链路外，还必须有一些必要的规程来控制数据的传输，因此，数据链路比链有一些必要的规程来控制数据的传输，因此，数据链路比链路多了实现通信规程所需要的硬件和软件。路多了实现通信规程所需要的硬件和软件。n“电路接通了电路接通了”表示链路两端的结点交换机已经开机，物理表示链路两端的结点交换机已经开机，物理连接已经能够传送比特流了，但是，数据传输并不可靠，在连接已经能够传送比特流了，但是，数据传输并不可靠，在物理连接基础上，再建立数据链路连接，才是物理连接基础上，再建立数据链路连接，才是“数据链路接数据链路接通了通了”，此后，由于数据链路连接具有检测、确认和重传功，此后，由于数据链路连接具有检测、确认和重传功能，才使不太可靠的物理链路变成可靠的数据链路，进行可能，才使不太可靠的物理链路变成可靠的数据链路，进行可靠的数据传输当数据链路断开连接时，物理电路连接不一定靠的数据传输当数据链路断开连接时，物理电路连接不一定跟着断开连接。跟着断开连接。1 数据链路(即逻辑链路)与链路(即物理链路)有何区别?“2 为了进行差错控制为了进行差错控制,必须对传送的数据进行校验必须对传送的数据进行校验.在局域在局域网中广泛使用的校验方法是网中广泛使用的校验方法是_(1)_,CRC-16标准规标准规定生成多项式为定生成多项式为G(x)=x16+X15+x2+1,它产生的校它产生的校验码是验码是_(2)_位位,接收端发现错误后采取的措施是接收端发现错误后采取的措施是_(3)_.如果如果CRC的生成多项式是的生成多项式是G(x)=x4+x+1,信息码字是信息码字是10110,由计算出来的由计算出来的CRC校验码是校验码是_(4)_.(1)A 奇偶检验奇偶检验 B 海明码海明码 C格雷码格雷码 D 循环冗余校验循环冗余校验(2)A 2 B 4 C 16 D 32(3)A 自动纠错自动纠错 B 报告上层协议报告上层协议 C 自动请求重发自动请求重发 D 重重新生成原始数据新生成原始数据(4)A 0100 B1010 C 0111 D 11112 为了进行差错控制,必须对传送的数据进行校验.在局域网中书上作业练习书上作业练习:P845-41 要发送的数据为1101011011。采用CRC的生成多项式是P（X）=X4+X+1。试求应添加在数据后面的余数。数据在传输过程中最后一个1变成了0，问接收端能否发现？若数据在传输过程中最后两个1都变成了0，问接收端能否发现？采用CRC检验后，数据链路层的传输是否就变成了可靠的传输？书上作业练习:P845-41 要发送的数据为1101011n答：作二进制除法，答：作二进制除法，1101011011 0000 10011 得余数得余数1110，添加的，添加的检验序列是检验序列是1110.n 作二进制除法，两种错误均可发现作二进制除法，两种错误均可发现n仅仅采用了仅仅采用了CRC检验，缺重传机制，数据检验，缺重传机制，数据链路层的传输还不是可靠的传输。链路层的传输还不是可靠的传输。答：作二进制除法，1101011011 0000 1本课重点本课重点n掌握掌握CRC冗余校验码的计算冗余校验码的计算.本课重点掌握CRC冗余校验码的计算.5.3 5.3 基本数据链路协议基本数据链路协议数据链路协议主要考虑的问题：数据链路协议主要考虑的问题：避免所传送的数据可能出现差错和丢失；避免所传送的数据可能出现差错和丢失；使发方发送数据的速率适应收方的接收能力。使发方发送数据的速率适应收方的接收能力。5.3 基本数据链路协议数据链路协议主要考虑的问题：流量控制、可靠传输与滑动窗口机制流量控制、可靠传输与滑动窗口机制n流量控制的基本方法是由接收方控制发送方的速率。流量控制的基本方法是由接收方控制发送方的速率。n常见方式有二种：常见方式有二种：1）停止）停止等待协议等待协议2）滑动窗口协议）滑动窗口协议停止等待协议每发送一帧，都要等待接收方应答，传输停止等待协议每发送一帧，都要等待接收方应答，传输效率低。效率低。滑动窗口是发送方维持一组连续的允许发送的帧序号，滑动窗口是发送方维持一组连续的允许发送的帧序号，称为发送窗口，接收方也维持一组连续的接收帧序号，称为发送窗口，接收方也维持一组连续的接收帧序号，称为接收窗口。在发送端，每收到一个确认帧，发送称为接收窗口。在发送端，每收到一个确认帧，发送窗口就向前滑动一个帧的位置。当发送窗口全是已发窗口就向前滑动一个帧的位置。当发送窗口全是已发送未收到确认的帧，则停止发送。送未收到确认的帧，则停止发送。流量控制、可靠传输与滑动窗口机制流量控制的基本方法是由接收方理想化的数据传输理想化的数据传输假设假设1：所传送的数据即不会出现差错和也：所传送的数据即不会出现差错和也不会丢失；不考虑差错控制问题）不会丢失；不考虑差错控制问题）假设假设2：接收端的数据接收速率足够快，有：接收端的数据接收速率足够快，有能力接收发送端的数据发送率。能力接收发送端的数据发送率。（不考虑流量控制问题）（不考虑流量控制问题）在理想化的条件下，数据链路在理想化的条件下，数据链路层不需要：层不需要：差错控制协议；差错控制协议；流量控制协议；流量控制协议；就可保证数据的正确传输。就可保证数据的正确传输。理想化的数据传输假设1：所传送的数据即不会出现差错和也不会丢实用的停止等待协议（实用的停止等待协议（ARQ）去掉假设去掉假设1 1；去掉假设；去掉假设2 2。考虑差错控制问题考虑差错控制问题差错控制协议；差错控制协议；考虑流量控制问题考虑流量控制问题流量控制协议；流量控制协议；n初步协议：初步协议：发送端发送数据帧后，等待接收端的应答帧；发送端发送数据帧后，等待接收端的应答帧；接收端收到数据帧后，通过接收端收到数据帧后，通过CRC校验校验(一般用硬一般用硬件检验件检验)，如果无差错，回送一个，如果无差错，回送一个确认帧确认帧ACKACK，否，否则，回送一个则，回送一个否认帧否认帧NAKNAK。发送端收到应答帧，发送端收到应答帧，n如果是如果是ACKACK，发送下一数据帧，发送下一数据帧，n如果是如果是NAKNAK，重发数据帧。，重发数据帧。实用的停止等待协议（ARQ）去掉假设1；去掉假设2。链路+规程控制数据传输课件死锁现象死锁现象：当出现帧丢失时，发送端永当出现帧丢失时，发送端永远等待下去。远等待下去。如何解决？如何解决？解决方法：解决方法：发送端设立一个超时计时器，发送端设立一个超时计时器，发送完一个数据帧时，就启动它；发送完一个数据帧时，就启动它；如果在规定时间如果在规定时间tout内得不到应答内得不到应答帧，就判定为超时，重传数据帧。帧，就判定为超时，重传数据帧。Tout也称重传时间也称重传时间死锁现象：当出现帧丢失时，发送端永重复帧差错：重复帧差错：若应答帧丢失，按照超若应答帧丢失，按照超时重发方法，接收端将收到时重发方法，接收端将收到重复帧，如何解决？重复帧，如何解决？解决方法：解决方法：给每个数据帧附加不同的发送序给每个数据帧附加不同的发送序号号Ns，如果接收端收到相同序，如果接收端收到相同序号的数据帧号的数据帧,则丢弃则丢弃,并回送一并回送一个个ACKACK。重复帧差错：若应答帧丢失，按照超发送序号需要多少位发送序号需要多少位?n 对于对于ARQ协议，发送序号有协议，发送序号有0和和1即可即可(只需只需1个个bit);n每发一个新的数据帧，发送序号就和上次发送的每发一个新的数据帧，发送序号就和上次发送的不一样，不一样，n重发的数据帧发送序号不变。重发的数据帧发送序号不变。发送序号需要多少位?对于ARQ协议，发送序号有0和1ARQ协议：协议：ARQ协议：重传时间重传时间tout的选择的选择n若若Tout 太长，浪费时间，太长，浪费时间，n若若Tout 太短，过早重传数据，产生太短，过早重传数据，产生“额外额外”应应答帧。答帧。n如何解决？如何解决？n提示：在确认帧提示：在确认帧ACK和否认帧和否认帧NAK中附加序号。中附加序号。重传时间tout的选择若Tout 太长，浪费时间，停止等待协议的信道利用率停止等待协议的信道利用率停止等待协议的信道利用率链路+规程控制数据传输课件连续连续ARQ协议协议n目的：目的：提高信道利用率。提高信道利用率。n方法：方法：n发送端发送完一个数据帧后，不停下来等待应答发送端发送完一个数据帧后，不停下来等待应答n帧，而是连续再发送数据帧。当收到否认帧帧，而是连续再发送数据帧。当收到否认帧NAK时，时，n再控制重发。再控制重发。n实现要求：实现要求：n数据帧需附加发送序号信息。否认帧附加出错的数据帧需附加发送序号信息。否认帧附加出错的n数据帧发送序号。数据帧发送序号。n常用协议：常用协议：n回退回退N帧帧ARQ协议（协议（go back n）n选择重发选择重发ARQ协议（协议（selective repeat）连续ARQ协议目的：提高信道利用率。回退回退N帧帧ARQ协议（协议（go back n）n方式方式1：n反馈否认帧反馈否认帧NAK（含出错的数据帧发送序号）。（含出错的数据帧发送序号）。再从出错的数据帧开始重传。再从出错的数据帧开始重传。n要求：发送端要求有一个能存储要求：发送端要求有一个能存储N个数据帧的缓个数据帧的缓冲区。冲区。n接收端只需能存储一个数据帧的缓冲。接收端只需能存储一个数据帧的缓冲。回退N帧ARQ协议（go back n）方式1：n 方式方式2：n不反馈否认帧不反馈否认帧NAK。发送端采用超时机制。发送端采用超时机制。n发送端每发送一个数据帧就启动该帧计时器，发送端每发送一个数据帧就启动该帧计时器，当收到确认帧后，计时器复位；如果直到超当收到确认帧后，计时器复位；如果直到超时还没有收到确认帧，则重发该数据帧及后时还没有收到确认帧，则重发该数据帧及后继的帧。继的帧。方式2：选择重发选择重发ARQ协议协议（selective repeat）n目的：目的：进一步提高信道利用率。进一步提高信道利用率。n方法：只重传出现差错的数据帧或者超时的数据方法：只重传出现差错的数据帧或者超时的数据帧。帧。n要求：在接收端要设置具有相当容量的缓存空间。要求：在接收端要设置具有相当容量的缓存空间。选择重发ARQ协议（selective repeat）目的：选择重发选择重发ARQ协议工作原理示协议工作原理示意图意图选择重发ARQ协议工作原理示意图5.4 5.4 滑动窗口协议滑动窗口协议（Sliding Windows protocol）n当未被确认的数据帧数目太多时；只要有一帧出错，当未被确认的数据帧数目太多时；只要有一帧出错，就有很多数据帧需要重传，因而增大开销。就有很多数据帧需要重传，因而增大开销。n为了对发送出去的大量未被确认的数据帧进行编号，每为了对发送出去的大量未被确认的数据帧进行编号，每个数据帧的发送序号也要占用较多的比特数，因而又增大个数据帧的发送序号也要占用较多的比特数，因而又增大了开销。了开销。n对于连续对于连续ARQ协议，采用了发送端不等待确认帧返回就协议，采用了发送端不等待确认帧返回就可连续发送帧，存在问题：可连续发送帧，存在问题：n滑动窗口协议滑动窗口协议：n对发送端已发送出去但未被确认的帧的数目加以限制。对发送端已发送出去但未被确认的帧的数目加以限制。n在发送端和接收端分别设置在发送端和接收端分别设置发送窗口发送窗口和和接收窗口接收窗口。5.4 滑动窗口协议（Sliding Windows pro发送窗口发送窗口（在发送端（在发送端）n目的：用来对发送端进行流量控制。目的：用来对发送端进行流量控制。n发送窗口尺寸发送窗口尺寸Ws：在还没有收到应答帧的情况下，：在还没有收到应答帧的情况下，n发送端最多可以连续发送数据帧的个数。发送端最多可以连续发送数据帧的个数。n发送序号：发送序号：n一般采用一般采用n位位bit进行编号（进行编号（02n-1）。）。n若若n=3；则用；则用3位位bit进行编号（进行编号（07）。）。发送窗口（在发送端）目的：用来对发送端进行流量控制。n发送端只能连续发送窗口内的数据帧；发送端只能连续发送窗口内的数据帧；n每收到一个确认帧后，发送窗口的前、后沿顺每收到一个确认帧后，发送窗口的前、后沿顺时针旋转一个号，并可以一个发送新的数据帧。时针旋转一个号，并可以一个发送新的数据帧。n若未应答帧的数目等于发送窗口尺寸时，便停若未应答帧的数目等于发送窗口尺寸时，便停止发送新的数据帧。止发送新的数据帧。发送端只能连续发送窗口内的数据帧；接收窗口接收窗口（在接收端）（在接收端）n目的：用来控制可以接收哪些数据帧而不可以接目的：用来控制可以接收哪些数据帧而不可以接收哪些帧。收哪些帧。n接收窗口接收窗口Wr：只有当收到的数据帧的发送序号落：只有当收到的数据帧的发送序号落入接收窗口内，才允许将该数据帧收下；否则，入接收窗口内，才允许将该数据帧收下；否则，丢弃。丢弃。接收窗口（在接收端）目的：用来控制可以接收哪些数据帧而不可以n如果如果Wr=1，意味着只能按顺序接收数据帧。，意味着只能按顺序接收数据帧。n如果如果Wr较大，有可能会出现数据帧的失序。较大，有可能会出现数据帧的失序。n差错情况差错情况：设：设Wr=1；n 若收到若收到0号数据帧，接收窗口顺时针旋转一号数据帧，接收窗口顺时针旋转一个号，个号，n并发出并发出0号确认帧；准备接收号确认帧；准备接收1号数据帧。号数据帧。n此时，如果收到的不是此时，如果收到的不是1号数据帧，而是号数据帧，而是0号数号数据帧，表明发出据帧，表明发出0号确认帧发送端没有收到，因号确认帧发送端没有收到，因此再发送一次此再发送一次0号确认帧，此时收到的号确认帧，此时收到的0号数据号数据帧必须丢弃，否则发生重复。帧必须丢弃，否则发生重复。n 若是若是2号数据帧，表明发送端发出的号数据帧，表明发送端发出的1号数据号数据帧丢失，因此发送帧丢失，因此发送1号否认帧，让对方重新发送号否认帧，让对方重新发送1号数据帧。号数据帧。如果Wr=1，意味着只能按顺序接收数据帧。应答帧丢失情况应答帧丢失情况应答帧丢失情况应答帧被应答帧被“篡改篡改”情况情况:ACKNAK应答帧被“篡改”情况:ACKNAK链路+规程控制数据传输课件重叠问题重叠问题n在接收前后，接收窗口范围内的有效序号出现重在接收前后，接收窗口范围内的有效序号出现重叠。叠。重叠问题在接收前后，接收窗口范围内的有效序号出现重叠。避免重叠问题避免重叠问题n为了避免重叠问题，接收窗口尺寸为了避免重叠问题，接收窗口尺寸Wr2n/2。避免重叠问题为了避免重叠问题，接收窗口尺寸Wr2n/2。发送窗口的最大尺寸值发送窗口的最大尺寸值发送窗口的最大尺寸值累积确认方法累积确认方法n 接收端在连续接收若干个正确的数据帧以接收端在连续接收若干个正确的数据帧以后，对最后一个数据帧发回确认帧。后，对最后一个数据帧发回确认帧。累积确认方法 接收端在连续接收若干个正确的数据帧以窗口控制协议的信道利用率窗口控制协议的信道利用率窗口控制协议的信道利用率窗口控制协议的信道利用率n设：单程传输时延Td，数据帧发送时间Tf，n数据传输率C，数据帧长度L，窗口尺寸Wsn在正常传输情况下，忽略应答帧长度和处理时间：窗口控制协议的信道利用率设：单程传输时延Td，数据帧发送时依据信道利用率进行窗口尺寸的选择依据信道利用率进行窗口尺寸的选择n优化原则：优化原则：n 发送端收到窗口中第一个已发数据帧的确发送端收到窗口中第一个已发数据帧的确认时，正好发完窗口中的最后一个数据帧。认时，正好发完窗口中的最后一个数据帧。nWs大于上述选择，则大于上述选择，则Cr=100%，但浪费缓，但浪费缓冲区；冲区；nWs小于上述选择，则小于上述选择，则Cr=2a+1,N近近似等于似等于2a+1,则则n当当W=2a+1,由上面知由上面知a=2.35n故故w=2X2.35+1=5.7n取取w=6例1:已知数据帧长为1000bit,帧头为64bit,数据n3)nP一般比较小一般比较小,在分母看作为在分母看作为0,故得故得:n由于由于w=4,2a+1=5.7,为小窗口为小窗口,nW=w(1-p)/2a+1=4X(1-0.01)/5.7=0.693)练习练习1 一个使用选择重传协议的数据链路层协议，一个使用选择重传协议的数据链路层协议，如果采用了如果采用了5位的帧序列号，那么可以选位的帧序列号，那么可以选用的最大接收窗口是用的最大接收窗口是_.练习1 一个使用选择重传协议的数据链路层协议，如果采用了5位答：答：选用选用n个比特对帧进行编号，为了避免接收个比特对帧进行编号，为了避免接收端向前移动窗口与旧的窗口重合，接收窗端向前移动窗口与旧的窗口重合，接收窗口的最大尺寸不超过该序列号一半：口的最大尺寸不超过该序列号一半：Wr=2n-1=25-1=16答：2）在选择重传）在选择重传ARQ协议中，设编号用协议中，设编号用3位，发送窗口位，发送窗口Wt=6,而接收窗口而接收窗口Wr=3,试找出一种情况，使得在试找出一种情况，使得在此情况下协议不能正确工作。此情况下协议不能正确工作。答：对于选择重传答：对于选择重传ARQ协议，接收窗口加发送协议，接收窗口加发送窗口尺寸大小应该少于等于窗口尺寸大小应该少于等于2n,但该题发送窗口但该题发送窗口+接收窗口接收窗口=9(=)23,所以无所以无法正常工作。法正常工作。例发送方：例发送方：0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 接收方：接收方：0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0当发送方发送当发送方发送0-5共共6个帧后，发送窗口已满暂停等待个帧后，发送窗口已满暂停等待接收方确认，并期待收到后续的接收方确认，并期待收到后续的6 7 0,如果所有确如果所有确认帧均没收到，发送超时后重发认帧均没收到，发送超时后重发0 1 2 3 4 5,但接但接收方不知道这个收方不知道这个0是前面的重发还是后面的是前面的重发还是后面的02）在选择重传ARQ协议中，设编号用3位，发送窗口Wt=6,5.5协议协议n1.协议开发过程5.5 协议1.协议开发过程协议的形式描述协议的形式描述n描述方法：n有限状态机n 采用状态流程图进行描述。n事件状态表n 采用表格进行描述。n结构化程序n 采用程序代码进行描述。nPetri网模型n 采用状态流程图进行描述。协议的形式描述描述方法：有限状态机模型有限状态机模型FSMnFSM协议描述方法也称状态转移图。n特点：易懂、易理解和易于实现。n组成：状态圆和有向弧。有限状态机模型FSMFSM协议描述方法也称状态转移图。Petri网模型网模型n德国德国C.A.Petrit提出提出(1962,博士论文博士论文)。n4个基本元素：个基本元素：n位置：系统可能处于的状态；用圆圈表示。位置：系统可能处于的状态；用圆圈表示。n转换：改变状态；用线段表示。转换：改变状态；用线段表示。n有向弧：位置与转换之间的相互依赖关系；有向弧：位置与转换之间的相互依赖关系；用弧线表示。用弧线表示。n标记：系统当前处于的状态；在圆圈中用标记：系统当前处于的状态；在圆圈中用黑点表示。黑点表示。Petri网模型德国C.A.Petrit提出(1962,博士链路+规程控制数据传输课件数据链路层示例数据链路层示例n分类：数据链路层示例分类：高级数据链路控制高级数据链路控制HDLCn1976年，年，ISO提出提出HDLC（High-level Data Link Control）n适用范围：适用范围：n计算机计算机计算机、计算机计算机、计算机终端、终端终端、终端终端终端n三种类型的站：三种类型的站：n 主站：主要功能是发送命令（包括数据），接收主站：主要功能是发送命令（包括数据），接收响应，负责整个链路的控制（如系统的初始、流控、响应，负责整个链路的控制（如系统的初始、流控、n 差错恢复等）；差错恢复等）；n 次站：主要功能是接收命令，发送响应，配合主次站：主要功能是接收命令，发送响应，配合主站完成链路的控制；站完成链路的控制；n复合站：同时具有主、次站功能，既发送又接收命复合站：同时具有主、次站功能，既发送又接收命令和响应，并负责整个链路的控制。令和响应，并负责整个链路的控制。高级数据链路控制HDLC1976年，ISO提出HDLC（HiHDLC的链路构型n非平衡配置非平衡配置n 主站控制整个链路工作。主站控制整个链路工作。主站主站发出的帧叫命发出的帧叫命令；令；次站次站发出的帧叫响应。发出的帧叫响应。n 适合把智能和半智能的终端连接到计算机。适合把智能和半智能的终端连接到计算机。HDLC的链路构型非平衡配置HDLC的链路构型的链路构型n平衡配置平衡配置n 复合站复合站具有主站和次站的功能。地位具有主站和次站的功能。地位平等。平等。n 适合于计算机和计算机之间的连接适合于计算机和计算机之间的连接HDLC的链路构型平衡配置HDLC的基本操作模式的基本操作模式n正规响应模式正规响应模式NRMNRM：n 适用于点适用于点点式和多点式两种非平衡构型。点式和多点式两种非平衡构型。只有当主站向次站发出探询后，次站才能获得只有当主站向次站发出探询后，次站才能获得传输帧的许可。传输帧的许可。n异步响应模式异步响应模式ARMARM：n 适用于点适用于点点式非平衡构型和主站点式非平衡构型和主站次站式次站式平衡构型。次站可以随时传输帧，不必等待主平衡构型。次站可以随时传输帧，不必等待主站的探询。站的探询。n异步平衡模式异步平衡模式ABMABM：n 适用于通信双方都是复合站的平衡构型，也适用于通信双方都是复合站的平衡构型，也采用异步响应，双方具有同等能力。采用异步响应，双方具有同等能力。HDLC的基本操作模式正规响应模式NRM：HDLC的帧结构的帧结构n帧标志（帧标志（FlagFlag）n定界符为定界符为011111107EH（零比特填充法）。（零比特填充法）。n地址域（地址域（AddressAddress）n多终端线路，用来区分终端；多终端线路，用来区分终端；n点到点线路，有时用来区分命令和响应。点到点线路，有时用来区分命令和响应。n 若是接收该帧的站的地址，则该帧是命令帧；若是接收该帧的站的地址，则该帧是命令帧；n 若是发送该帧的站的地址，则该帧是响应帧。若是发送该帧的站的地址，则该帧是响应帧。HDLC的帧结构帧标志（Flag）HDLC的帧结构的帧结构n有效地址为有效地址为254个（通常为个（通常为8位，可扩展到位，可扩展到16位）位）n 全全1的的8位地址表示广播（所有次站接收）；位地址表示广播（所有次站接收）；n 全全0的的8位地址是无效地址。位地址是无效地址。n控制域（控制域（Control）n标识帧的类型和功能，使对方站执行特定的操作。标识帧的类型和功能，使对方站执行特定的操作。n 信息帧（信息帧（Information帧）；帧）；n 管理帧（管理帧（Supervisory帧）；帧）；n 无序号帧（无序号帧（Unnumbered帧）。帧）。HDLC的帧结构有效地址为254个（通常为8位，可扩展到16HDLC的帧结构的帧结构n数据域（数据域（Data）n任意比特串或字符串（有上限）任意比特串或字符串（有上限）n校验和（校验和（Checksum）n循环冗余校验（循环冗余校验（CRC）n生成多项式：生成多项式：HDLC的帧结构数据域（Data）控制域的格式控制域的格式nSeq发送序号发送序号n 使用滑动窗口技术，使用滑动窗口技术，3位序号，发送窗口位序号，发送窗口Ws=7；nNext捎带确认捎带确认n 接收站期望收到的帧序号，而不是最后一个已接收站期望收到的帧序号，而不是最后一个已收到的帧序号；收到的帧序号；控制域的格式Seq发送序号控制域的格式控制域的格式nP/F询问询问/终止终止n 命令帧置命令帧置P位，表示要求对方立即发送响应；位，表示要求对方立即发送响应；n 响应帧置响应帧置F位，表示要发送的数据已经发送完毕。位，表示要发送的数据已经发送完毕。n 注：最后一个帧注：最后一个帧P/F位置为位置为“F”，其它置为，其它置为“P”。n 有些协议，有些协议，P/F位用来强迫对方机器立刻发控制帧；位用来强迫对方机器立刻发控制帧；nType类型类型n“Type0”表示确认帧；表示确认帧；“Type1”表示否定帧。表示否定帧。n“Type2”表示接收未准备好；表示接收未准备好；“Type3”表示选择拒绝。表示选择拒绝。n无序号帧无序号帧n 可以用来传控制信息，也可在不可靠无连接服务可以用来传控制信息，也可在不可靠无连接服务n中传数据。中传数据。n尽管尽管HDLC被广泛地被使用了被广泛地被使用了,但它还不够完美但它还不够完美,这就是这就是网络网络.控制域的格式P/F询问/终止因特网的点对点协议因特网的点对点协议PPPn1992年，年，PPP:Point-to-Point Protocoln应用：应用：拨号方式入网拨号方式入网n 专线方式入网专线方式入网因特网的点对点协议PPP1992年，PPP:Point-PPP的组成的组成nInternet 需要一个点到点协议需要一个点到点协议,它有多种用途它有多种用途,其中包括传送从路由器到路由器之间的流量其中包括传送从路由器到路由器之间的流量,以及以及从家庭用户到从家庭用户到ISP之间的流量之间的流量.nPPP处理错误检测处理错误检测,支持多个协议支持多个协议,允许在连接时允许在连接时刻协商刻协商IP地址地址,允许身份认证允许身份认证.nPPP提供了三类功能提供了三类功能:(P201)n成帧方法（面向比特和面向字符）成帧方法（面向比特和面向字符）n链路控制协议链路控制协议LCPn网络控制协议网络控制协议NCPPPP的组成Internet 需要一个点到点协议,它有多种用PPP的帧结构的字段描述的帧结构的字段描述n帧标志（帧标志（FlagFlag）n定界符为定界符为011111107EH。n 在同步链路传输时：采用零比特填充法；在同步链路传输时：采用零比特填充法；n 在异步链路传输时：采用字符填充法。在异步链路传输时：采用字符填充法。n 若数据字段出现一个若数据字段出现一个7EH，变为，变为7DH和和5EH；n 若数据字段出现一个若数据字段出现一个7DH，变为，变为7DH和和5DH；n 若数据字段出现若数据字段出现ASCII码的控制字符码的控制字符(小于小于20Hn 的字符的字符)，则在该字符前插入一个，则在该字符前插入一个7DH。n地址域（地址域（AddressAddress）n 始终为始终为FFH。实际上，不需要地址。实际上，不需要地址。PPP的帧结构的字段描述帧标志（Flag）PPP的帧结构的字段描述的帧结构的字段描述n控制域控制域（Control）n 一般为一般为03H，表示是无序号帧。，表示是无序号帧。n协议域协议域（Protocol）n 若为若为C021H，则数据字段是，则数据字段是PPP链路控制链路控制数据；数据；n 若为若为8021H，则数据字段是，则数据字段是PPP网络控制网络控制数据。数据。n净荷域净荷域:最大不超过最大不超过15001500字节字节PPP的帧结构的字段描述控制域（Control）PPP的通信过程的通信过程n当用户拨号接入当用户拨号接入ISP，n 路由器的路由器的modem对拨号做出确认，对拨号做出确认，n 建立一条物理连接；建立一条物理连接；n PC机发送机发送LCP分组（分组（PPP参数）参数）n 路由器进行网络层配置，路由器进行网络层配置，n NCP给给PC机一个临时机一个临时IP地址；地址；n当用户挂机时，当用户挂机时，n NCP释放网络层连接，释放网络层连接，n 收回原来分配出去的收回原来分配出去的IP地址；地址；n LCP释放数据链路层连接，释放数据链路层连接，n 最后，释放物理层连接。最后，释放物理层连接。PPP的通信过程当用户拨号接入ISP，本章小结本章小结u数据链路层的任务数据链路层的任务u 检错与纠错检错与纠错u滑动窗口协议滑动窗口协议uHDLC与与PPP协议协议u相应协议的软件程序实现相应协议的软件程序实现本章小结数据链路层的任务作业作业n5-41n5-42作业5-41