《计算机网络原理与技术(第二版)》第3章数据链路层

《《计算机网络原理与技术(第二版)》第3章数据链路层》由会员分享，可在线阅读，更多相关《《计算机网络原理与技术(第二版)》第3章数据链路层（37页珍藏版）》请在装配图网上搜索。

1、单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,计算机网络,第三章 数据链路层,主要内容,组帧,差错检测,可靠交付,停,-,等协议,滑动窗口协议,数据链路层协议举例,HDLC,协议,PPP,协议,1.,组帧,使用字符填充的起止标记法,使用特殊的字符表示帧的开始与结束。,使用,字符填充,（在特殊字符前加转义字符）解决透明传输问题。,该方法依赖于特定的字符编码集，帧长必须是,8,比特的整倍数，灵活性差，处理开销大。,使用比特填充的起止标记法,使用一个特殊的比特模式（,01111110,）作为帧的起始与结束标志。,使用,比特填充,（连续,5,个,1,后插入一个

2、,0,）解决透明传输问题。,该方法不依赖于特定的字符编码集，灵活性强，处理简单。,违法编码法,使用物理层编码中的无效编码表示帧的边界。,字符填充示例,比特填充示例,2.,差错检测,出错的类型,单个错：,由随机的信道热噪声引起，一次只影响,1,位。,突发错,：,由瞬间的脉冲噪声引起，一次影响许多位，用突发长度表示突发错影响的最大数据位数。,差错编码的类型,检错码：只能检测出传输错误，但无法自行纠正，通常与反馈重传结合起来进行差错恢复。,纠错码：能够检测出传输错误并纠正。,如何检测与纠正错误？,码字（,codeword,）：由,m,比特的数据（消息）加上,r,比特的冗余（校验位）构成。,有效编码集

3、：由,2,m,个有效码字组成。,检错：当收到的码字为无效码字时检测出错误。,海明距离（,Hamming Distance,）：两个码字的对应位上取值不同的位数。,纠错：将收到的无效码字纠正到距其最近的有效码字。,检错码与纠错码的能力都是有限的。,编码集的检错与纠错能力,编码集的海明距离：编码集中任意两个有效码字的海明距离的最小值。,检错能力：为检测出,d,比特错误，编码集的海明距离至少应为,d+1,；,奇偶校验是能够检测出,1,比特错误的检错码。,纠错能力：为纠正,d,比特错误，编码集的海明距离至少应为,2d+1,。,结论：差错编码的检错,/,纠错能力与编码集的海明距离有关。海明距离越大，检错

4、纠错能力就越强；但所需的冗余信息也越多，编码效率就越低。,二维奇偶,校验,对一个,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(

5、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,是否有错？,常见

6、的,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.,可靠交付,差错恢复的两种办法：,使用纠错码，由接收端自动纠正错误。,使用检错码，采用自动重传

7、请求（,ARQ,）保证可靠交付。这是数据链路层（及传输层）上最常使用的可靠交付方式。,两种,ARQ,算法：,停,-,等,滑动窗口,3.1,停,-,等算法,基本思想：发送方发完一帧后即停下来等待确认；如果收到一个确认，接着发送下一个帧；如果定时器超时，重发刚才的帧。,停,-,等算法的四种情形,。,停,-,等算法的超时值对性能影响很大，必须仔细选择。,为区分新帧和重发帧，停,-,等算法使用一比特的帧序号。,停,-,等算法的四种情形,停,-,等算法的过,-,发送方,1,）帧序号初始化为,0,2,）从缓冲区中取出一个帧，加上当前帧序号发送。,3,）等待确认,i,）收到确认帧，且帧序号与当前维护的帧序号

8、不同，将,帧序号加,1,，从缓冲区中取出一个新的帧，加上当前,帧序号发送。,ii,）收到确认帧，且帧序号与当前维护的帧序号相同，重,发当前序号的帧。,iii,）收到错误的确认帧，重发当前序号的帧。,iv,）定时器超时，重发当前序号的帧。,停,-,等算法的过程,-,接收方,1,）帧序号初始化为,0,（表示当前期望接收的帧序号）,2,）等待接收,3,）帧到达,i,）,帧,校验正确，且序号为当前期望接收的帧序号，将帧,放入接收缓冲区，帧序号加,1,，放入确认帧中发送。,ii,）帧校验正确，但序号与当前期望接收的帧序号不同，,丢弃帧，重发确认帧。,iii,）帧校验错误，丢弃帧，重发确认帧。,信道利用率

9、与流水线技术,停,-,等算法在传输延迟较长的信道上传输效率很低。,假如将链路看成是一根管道，数据是管道中流动的水，那么停,-,等算法无法使数据充满管道，因而信道利用率很低。,管道的容量通常用延迟,-,带宽乘积表示，它表示发送端在收到第一个帧的确认前最多可以发送的数据量。,滑动窗口机制允许发送端连续发送多个帧来尽可能多地填充管道，从而提高信道的利用率。,3.2,滑动窗口,滑动窗口是计算机网络中最著名的算法，它可以应用在数据链路层及传输层，用来完成三个不同的任务：,在不可靠的链路（网络）上可靠地传输数据,保持数据的传输顺序,支持流量控制,在数据链路层上，以上三个功能组合在一个滑动窗口协议中。,发送

10、窗口,发送窗口：发送端允许发送的帧序号表。,发送窗口大小：发送端最大允许的未确认帧数目。,发送窗口下沿：最早发送但尚未被确认的帧序号。,发送窗口上沿：（发送窗口下沿发送窗口大小,1,）,mod 2,n,。,当收到对发送窗口下沿帧的确认时，发送窗口整体向前滑动一个序号，将已被确认的帧移出发送窗口，并加入一个新的序号。（,图,）,发送窗口中的帧都保留在缓冲区中以备重传，当某个帧被移出发送窗口时，同时从缓冲区中删除。,当发送窗口满时，停止从网络层接收数据，直到有一个缓冲区空出来为止。,发送窗口和接收窗口图示,接收,窗口,接收窗口：接收端允许接收的帧序号表。,接收窗口大小：接收端允许接收的最大帧数。,

11、接收窗口下沿：接收端按顺序期待接收的帧序号。,当接收端收到窗口下沿帧且校验正确时，将帧交给网络层，向发送方发回一个确认，然后窗口整体向前滑动一个序号。（,图,）,接收窗口的大小可以设为任意值，通常的设置有两种：,接收窗口大小,=1,：意味着接收方只能按顺序接收；,接收窗口大小,=,发送窗口大小：意味着接收方可以不按顺序接收，但接收方交给上层实体的数据总是有序的。,捎带确认,捎带确认（,piggybacking,）：将确认序号携带在数据帧中传输，提高线路的效率。,推迟确认：当需要发送确认但没有要发送的数据时，可以让确认信息推迟一小段时间再发送；这一小段时间后若数据仍未准备好，接收端必须立即发送一

12、个单独的确认帧。,接收端对正确收到的若干个帧同时进行确认，通常用对某一个帧的确认来表示对该帧之前的所有帧进行确认。,Go Back n,Go back n,当接收端收到一个出错帧或乱序帧时，丢弃所有的后继帧，并且不为这些帧发送确认；发送端超时后，重传所有未被确认的帧。,该策略对应接收窗口为,1,的情况，即只能按顺序接收帧。,若信道的误码率较高，这种方法会浪费很多带宽，但对接收端内存的需求不大。,Go Back N,示,意图,选择重传,选择重传,当接收端收到一个出错帧或乱序帧时，后续到达的帧只要校验正确且落在接收窗口内，都放入接收缓冲区中；发送端超时后只重传最早发送但未被确认的帧。,该策略对应接

13、收窗口大于,1,的情况。,选择重传通常使用一个否定的确认（,NAK,）,对校验出错或疑为丢失的帧进行确认，以便发送端尽快重传该帧。,当接收窗口很大时，这种方法要求接收端有较大的内存，但它不浪费带宽。,选择重传示意图,有限序号与窗口限制,使用,Go Back N,协议，发送窗口的大小不能超过,2,n,-1,。,使用选择重传协议，若发送窗口与接收窗口大小相同，则发送窗口的大小不能超过,2,n-1,。,4.,数据链路协议举例,高级数据链路控制（,HDLC,）,点到点协议（,PPP,）,4.1 HDLC,帧,结构,：,标志：,01111110,，标识一帧的开始与结束，以及作为帧间填充。,地址,：,在点

14、到多点线路中用于指明通信的终端地址，在点到点线路中用于区分命令和响应。,控制,：,用于构成各种命令和响应，对链路进行监控。,信息,：,可以是任意的二进制比特串。,校验,：,CRC,码，对两个标志之间的帧内容进行校验。,帧,类型,信息帧：,以控制字段的第一比特为“,0”,标志。,用于传送数据，数据放在信息字段中。,采用滑动窗口协议，,N(S),为发送序号，,N(R),为捎带确认。,帧,类型（续）,监视帧：,以控制字段的第一、二比特为“,10”,标志。,用于差错控制和流量控制，没有信息字段。,S,1,S,2,：,决定监控帧的类型,类型,0,：接收准备好,类型,1,：否定确认,类型,2,：接收未准备

15、好,类型,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,链路的,配置、维护和终止,