单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,计算机网络,第三章 数据链路层,主要内容,组帧,差错检测,可靠交付,停,-,等协议,滑动窗口协议,数据链路层协议举例,HDLC,协议,PPP,协议,1.,组帧,使用字符填充的起止标记法,使用特殊的字符表示帧的开始与结束使用,字符填充,（在特殊字符前加转义字符）解决透明传输问题该方法依赖于特定的字符编码集，帧长必须是,8,比特的整倍数，灵活性差，处理开销大使用比特填充的起止标记法,使用一个特殊的比特模式（,01111110,）作为帧的起始与结束标志使用,比特填充,（连续,5,个,1,后插入一个,0,）解决透明传输问题该方法不依赖于特定的字符编码集，灵活性强，处理简单违法编码法,使用物理层编码中的无效编码表示帧的边界字符填充示例,比特填充示例,2.,差错检测,出错的类型,单个错：,由随机的信道热噪声引起，一次只影响,1,位突发错,：,由瞬间的脉冲噪声引起，一次影响许多位，用突发长度表示突发错影响的最大数据位数差错编码的类型,检错码：只能检测出传输错误，但无法自行纠正，通常与反馈重传结合起来进行差错恢复纠错码：能够检测出传输错误并纠正。
如何检测与纠正错误？,码字（,codeword,）：由,m,比特的数据（消息）加上,r,比特的冗余（校验位）构成有效编码集：由,2,m,个有效码字组成检错：当收到的码字为无效码字时检测出错误海明距离（,Hamming Distance,）：两个码字的对应位上取值不同的位数纠错：将收到的无效码字纠正到距其最近的有效码字检错码与纠错码的能力都是有限的编码集的检错与纠错能力,编码集的海明距离：编码集中任意两个有效码字的海明距离的最小值检错能力：为检测出,d,比特错误，编码集的海明距离至少应为,d+1,；,奇偶校验是能够检测出,1,比特错误的检错码纠错能力：为纠正,d,比特错误，编码集的海明距离至少应为,2d+1,结论：差错编码的检错,/,纠错能力与编码集的海明距离有关海明距离越大，检错纠错能力就越强；但所需的冗余信息也越多，编码效率就越低二维奇偶,校验,对一个,kn,比特的信息矩阵的每一行和每一列计算奇偶校验位循环冗余码（,CRC,）,CRC,是一种多项式编码，它将位串看成是某个一元多项式的系数，如,1011001,看成是一元多项式,X,6,+X,4,+X,3,+1,的系数信息多项式,M(x),：,由,m,个信息比特为系数构成的多项式。
冗余多项式,R(x),：,由,r,个冗余比特为系数构成的多项式码多项式,T(x),：,在,m,个信息比特后加上,r,个冗余比特构成的码字所对应的多项式，表达式为,T(x)=,x,r,M(x,)+R(x),生成多项式,G(x),：,双方预先确定用来计算,R(x),的一个多项式编码方法,：用对应于,G(x),的位串去除对应于,x,r,M(x,),的位串，所得的余式即为,R(x),，,将其,附加到信息比特串的后面一起发送校验方法,：用,对应于,G(x),的位串去除对应于,T(x),的位串，若余式为,0,则认为传输正确，否则认为传输错误CRC,码检错能力强，实现简单快捷，是应用最广泛的检错码CRC,的编码及校验,例,1,：,G(X)=X,4,+X+1,，,对,10110011,进行,CRC,编码例,2,：仍取,G(X)=X,4,+X+1,，判断收到的位串,100101111001,是否有错？,常见的,CRC,多项式,CRC,C(x,),CRC-8,X,8,+X,2,+X,1,+1,CRC-10,X,10,+X,9,+X,5,+X,4,+X,1,+1,CRC-12,X,12,+X,11,+X,3,+X,2,+1,CRC-16,X,16,+X,15,+X,2,+1,CRC-CCITT,X,16,+X,12,+X,5,+1,CRC-32,X,32,+X,26,+X,23,+X,22,+X,16,+X,12,+X,11,+X,10,+X,8,+X,7,+X,5,+X,4,+X,2,+X,1,+1,3.,可靠交付,差错恢复的两种办法：,使用纠错码，由接收端自动纠正错误。
使用检错码，采用自动重传请求（,ARQ,）保证可靠交付这是数据链路层（及传输层）上最常使用的可靠交付方式两种,ARQ,算法：,停,-,等,滑动窗口,3.1,停,-,等算法,基本思想：发送方发完一帧后即停下来等待确认；如果收到一个确认，接着发送下一个帧；如果定时器超时，重发刚才的帧停,-,等算法的四种情形,停,-,等算法的超时值对性能影响很大，必须仔细选择为区分新帧和重发帧，停,-,等算法使用一比特的帧序号停,-,等算法的四种情形,停,-,等算法的过,-,发送方,1,）帧序号初始化为,0,2,）从缓冲区中取出一个帧，加上当前帧序号发送3,）等待确认,i,）收到确认帧，且帧序号与当前维护的帧序号不同，将,帧序号加,1,，从缓冲区中取出一个新的帧，加上当前,帧序号发送ii,）收到确认帧，且帧序号与当前维护的帧序号相同，重,发当前序号的帧iii,）收到错误的确认帧，重发当前序号的帧iv,）定时器超时，重发当前序号的帧停,-,等算法的过程,-,接收方,1,）帧序号初始化为,0,（表示当前期望接收的帧序号）,2,）等待接收,3,）帧到达,i,）,帧,校验正确，且序号为当前期望接收的帧序号，将帧,放入接收缓冲区，帧序号加,1,，放入确认帧中发送。
ii,）帧校验正确，但序号与当前期望接收的帧序号不同，,丢弃帧，重发确认帧iii,）帧校验错误，丢弃帧，重发确认帧信道利用率与流水线技术,停,-,等算法在传输延迟较长的信道上传输效率很低假如将链路看成是一根管道，数据是管道中流动的水，那么停,-,等算法无法使数据充满管道，因而信道利用率很低管道的容量通常用延迟,-,带宽乘积表示，它表示发送端在收到第一个帧的确认前最多可以发送的数据量滑动窗口机制允许发送端连续发送多个帧来尽可能多地填充管道，从而提高信道的利用率3.2,滑动窗口,滑动窗口是计算机网络中最著名的算法，它可以应用在数据链路层及传输层，用来完成三个不同的任务：,在不可靠的链路（网络）上可靠地传输数据,保持数据的传输顺序,支持流量控制,在数据链路层上，以上三个功能组合在一个滑动窗口协议中发送窗口,发送窗口：发送端允许发送的帧序号表发送窗口大小：发送端最大允许的未确认帧数目发送窗口下沿：最早发送但尚未被确认的帧序号发送窗口上沿：（发送窗口下沿发送窗口大小,1,）,mod 2,n,当收到对发送窗口下沿帧的确认时，发送窗口整体向前滑动一个序号，将已被确认的帧移出发送窗口，并加入一个新的序号。
图,）,发送窗口中的帧都保留在缓冲区中以备重传，当某个帧被移出发送窗口时，同时从缓冲区中删除当发送窗口满时，停止从网络层接收数据，直到有一个缓冲区空出来为止发送窗口和接收窗口图示,接收,窗口,接收窗口：接收端允许接收的帧序号表接收窗口大小：接收端允许接收的最大帧数接收窗口下沿：接收端按顺序期待接收的帧序号当接收端收到窗口下沿帧且校验正确时，将帧交给网络层，向发送方发回一个确认，然后窗口整体向前滑动一个序号图,）,接收窗口的大小可以设为任意值，通常的设置有两种：,接收窗口大小,=1,：意味着接收方只能按顺序接收；,接收窗口大小,=,发送窗口大小：意味着接收方可以不按顺序接收，但接收方交给上层实体的数据总是有序的捎带确认,捎带确认（,piggybacking,）：将确认序号携带在数据帧中传输，提高线路的效率推迟确认：当需要发送确认但没有要发送的数据时，可以让确认信息推迟一小段时间再发送；这一小段时间后若数据仍未准备好，接收端必须立即发送一个单独的确认帧接收端对正确收到的若干个帧同时进行确认，通常用对某一个帧的确认来表示对该帧之前的所有帧进行确认Go Back n,Go back n,当接收端收到一个出错帧或乱序帧时，丢弃所有的后继帧，并且不为这些帧发送确认；发送端超时后，重传所有未被确认的帧。
该策略对应接收窗口为,1,的情况，即只能按顺序接收帧若信道的误码率较高，这种方法会浪费很多带宽，但对接收端内存的需求不大Go Back N,示,意图,选择重传,选择重传,当接收端收到一个出错帧或乱序帧时，后续到达的帧只要校验正确且落在接收窗口内，都放入接收缓冲区中；发送端超时后只重传最早发送但未被确认的帧该策略对应接收窗口大于,1,的情况选择重传通常使用一个否定的确认（,NAK,）,对校验出错或疑为丢失的帧进行确认，以便发送端尽快重传该帧当接收窗口很大时，这种方法要求接收端有较大的内存，但它不浪费带宽选择重传示意图,有限序号与窗口限制,使用,Go Back N,协议，发送窗口的大小不能超过,2,n,-1,使用选择重传协议，若发送窗口与接收窗口大小相同，则发送窗口的大小不能超过,2,n-1,4.,数据链路协议举例,高级数据链路控制（,HDLC,）,点到点协议（,PPP,）,4.1 HDLC,帧,结构,：,标志：,01111110,，标识一帧的开始与结束，以及作为帧间填充地址,：,在点到多点线路中用于指明通信的终端地址，在点到点线路中用于区分命令和响应控制,：,用于构成各种命令和响应，对链路进行监控。
信息,：,可以是任意的二进制比特串校验,：,CRC,码，对两个标志之间的帧内容进行校验帧,类型,信息帧：,以控制字段的第一比特为“,0”,标志用于传送数据，数据放在信息字段中采用滑动窗口协议，,N(S),为发送序号，,N(R),为捎带确认帧,类型（续）,监视帧：,以控制字段的第一、二比特为“,10”,标志用于差错控制和流量控制，没有信息字段S,1,S,2,：,决定监控帧的类型,类型,0,：接收准备好,类型,1,：否定确认,类型,2,：接收未准备好,类型,3,：选择拒绝,帧,类型（续）,无编号帧：,以控制字段的第一、二比特为“,11”,标志提供链路的建立、拆除及其它控制功能不包含,N(S),或,N(R),字段M,1,M,5,：,修正位，构成各种链路命令和响应,HDLC,的访问规程,链路层的,操作分为三个阶段：,建立链路：一方发送一个置模式命令，另一方发送,UA,帧进行响应，并初始化链路变量传输信息：,双方使用滑动窗口协议进行数据传输控制；,对收到的信息帧使用捎带确认或监视帧进行响应；,对检测到错误的帧使用否定确认或选择拒绝要求重发；,未准备好接收下一帧时，用接收未准备好暂停对方的发送断开链路：一方发送一个断连命令，另一方用一个,UA,帧进行响应。
4.2 PPP,协议,PPP,是因特网中广泛使用的点到点数据链路协议PPP,由以下三部分组成：,一种在串行通信线路上的组帧方式；,用于建立、配置、测试和拆除数据链路的链路控制协议,LCP,；,一组网络控制协议（,NCP,），,用以支持不同的网络层协议PPP,的组帧,PPP,采用与,HDLC,类似的帧结构，不同之处是：,PPP,采用字符填充而不是比特填充地址字段总是,oxFF,，控制字段总是,0 x03,增加的协议字段说明信息字段中携带的数据属于哪个上层协议CRC,字段的长度可以协商PPP,链路的,配置、维护和终止,。