3.1基本概念 第3章 连路:一条无源的点到点的物理线路段 数据链路层 数据链路:链路+规程(控制数据传输) 数据链路层的作用 通过一些数据链路层协议(即链路控制规程) 在不太可靠的物理链路上实现可靠的数据传输 数据链路层的主要功能 为网络层提供的服务 ①链路管理:数据链路的建立、維持和释放; ②帧同步:收方能从收到的比特流中区分一帧开始和 ①无确认的无连接的服务 结束的地方 适用于误码率很低的通信信道;或语音通信; ③差错控制:收方收到有差错的数据帧时,能检错重 传或纠错; ②有确认的无连接的服务 ④流量控制:发方发送數据的速率必须使收方来得及 用于误码率很高的通信信道;如无线通信 ⑤透明传输:不管所传数据是什么样的比特组合,收 方都能正确接收。并能将数据与控制信息分开; ③有确认的面向连接的服务 ⑥寻址:保诬每一帧都能发送到目的站 适用于通信要求较高(可靠性、实时性)的情况 差错检测和纠正 差错评价指标 差错:接收的与发送的数据不一致 误码率:错传的码元数与所传输码元总数之比 随机差错:具有独立性,与前后码元无关 Pe= Ne/N 突发差错:相邻多个数据位出错 其中,N一传输的码元总数,Ne-错传的的码元数 差错产生的原因 误比特率: 通信信道的噪声 错传的比特数与所传输总比特数之比 ①热噪声:由传输介质导体的电子热运动产生。幅 在二进制码元时,误比特率=误码率 度较小,是产生随机差错的主要根源 ②冲击噪声:由外界电磁干扰产生,幅度较大 是产生突发差错的主要根源 普通电话线路:Pe=104~-1 冲击噪声是引起差错的主要原因 大多数通信系统:Pe=105~10°
1
差错控制的基本方式 误码控制基本原理 ①反馈纠错 为了能判断传送的信息数据是否有误,在传送 时增加必要的附加判断数据;在不发生误码的情况 在接收端能发现差镨,但不能确定错爲的位置,通过反 之下,附加判断数据是完全多余的,但如果发生 馈信息请求发送端重发,直到接收端肯定确认为止 适用于双工通信和非实时通信系统 来实现检错和纠错 ②前向纠错 即,为了使数据码具有检错和纠错能力,应当 在接收端不仅能发现错码,而且还能够确定错鸸的位 按一定的规则在数据码的基础上增加一些冗余码(又 置,并纠正错码。 称监督码) 适用于单工通信和实时通信系 ③混合纠错 码}编码 据码 少量差错在接收端自动纠正,若超出自行纠正能力 生成蔹醬码冗余码 通过反馈信息请求发送端重发 信息帻 码字的检错与纠错能力 码字编码的海明距离 对于一种码字編码,在这个码字集合中,可得到 码字(n位)-数据码(m位)冗余码(r位 所有任意两个码字的海明距离,其中最小的海明距离 海明距离:两个码字之间对应码元位的不同码元 称为该码字编码的海明距离d 的个数 定理1:如果d>2t+1,则該编码可纠正任何t个(或t个以 0001001 定理2: 1,则该编码可检测出任何e个(或e个 10100011 00101010 有3位不同。所以,海明距离 一般情况下,冗余位越多(即r越大),检错纠错 能力越强,但相应的编码效率也随之降低了 示例:偶校验的检错与纠错能力 误码控制编码的分类 例:对于偶校验(使每个码字中都有偶数个1) 按冗余码的控制功能分: 数据码为2位(有用数据为00、01、10、11) ①纠错码:在接收端能发现并自动纠正差错 冗余码为1位(偶校验位) ②检错码:在接收端能发现差错 有用数据经过偶校验編码,其码字集合 0、0ll、10l、110; 该编码的海明距离d=2, 纠错检错的常用方法 海明码:可纠错和检错,实现复杂,效率低 根据定理1,该编码不能纠正任何错误 艮据定理2,该編码可检测出任何1个错 ②奇偶校验码:方法简单,检错能力差 循环冗余编码(CRC):实现容易,检错能力强,广 寄校验的检错能力与偊校验一样
2
纠错码:海明码 确定校验关系 明在1950年提出的可纠正一位错的编码方法 用r个校验位构造出r个校验关系式来指示一位错 凸"豐 码的n(m+r)种可能位置及表示无差错 码字排列:从最左边位开始依次编号(1、2、…n); XXi r个校验位:在2的位置(1、2、4、8、…) m个数据位:在其余位(3、5、6、7、9、…) r的确定:r2-r>m+1;(∵r2>n+1-m+r+1) 发送1P2b3eb6b7 例如:4个信息位D1D2D3D4,3个校验位P1P2P3. P]=b5 6 b6 e b7 采用偶校验 段BB的的 -SIa ebe b56 b7 $2=b26 6 b66 b7 s4=b⊕bs⊕b6⊕b7 校验位 海明示例:接收端 海明示例:发送端 收到的发送码一[010011差错位 增 S2=b2eb3⊕b⊕b7 发送 LOLLLOTOLL CP3-bsab⊕b7 s4=b4ebs⊕b6b7=1 S4S2 SIll≠000, 有差错!差错位是b7(D4) 获取数据:去掉校验位,数据=1011, 海明编码解码一简便法 海明示例:数据=1100001(m=7,r=4) 例:数据 将码字中为1的各 时,, 位码字位号表示为二进制码,再口 按模2求和,所得结果就是校 1_P■P1 P3P2P1= 发送的码字:一龆 即p3p11 收到的码字:一[o00 差错位 解码简便法:将码字中为1的各 接收:口11@oo 位码字位号表示为二进制码 b3=011 按模2求和,若和为0,则无 b6=110 错。若和不为0,则指明差错的S4
3
检错码:循环冗余码一CRC码 例:若数据码=110011 可表示为:M(x)=1x5+1x+0x3+0x2+1x+1 特点:实现容易,检错能力强,广泛使用 即;M(x)=x3+x4+x+1. 常结合反馈重传法来保证信息的可靠传输 生成多项式G(x) 码字组成 G(x)=gx+…+x2+…+gx+ge 发送的码宇【bbb1br;nn1rn 其中,g=0或lr>}>0,g,≠0,gn≠共r+1位 G(x)被通信双方事先共同选定使用 編码与解码的计算采用二进制比特序列多项式。 发送端:通过GAx)生成校验码 二进制比特序列多项式: 接收端:通过G(x)校验接收的码字, M(x)=bmp1+…+bx+…+bx+be 对于多项式的运算:采用模2计算(加法不进 位,减法不借位);加减法是一样的 其中,b=0或1,m-1>>0,共m位 模2计算即是异或运算 在发送端 在接收端 1.生成校验码R(x 把要发送的数据码M(去除G(x,所得的余 接收到(x)-x+R(x)后,按如下操作进行校 数值R(x)就是循环冗余码(简称CRC校验码) H(x)-x Msb2x日 E(x为余数 G(x)R(x为余数(CRC校验码) =0无错 G(x共r+1个bit位, ≠0有错 x)x一R(x) 2.发送M(x)x+R(x 数据码十编 码」数据码 际上,把CRC校验码R(x附加到数据码 的后面,就构成编码多项式M(x)x+R(x),然 CRC示例1:发送端 CRC示例1:接收端一无差错 例:设数据码M(x=110011 接收端:采用生成多项式G()=x+x3+l(即11001) 采用生成多项式G(x)=x2+x3+l(即11001),r=4 发送端:求CRC校验码 M(x)x'+R(xL=o(x) G(x)→11001/1100 若E(Ax 多项式运算采用 1101011 发送码M(x)x"+R(x 发送码:M(x)-x+Rx=1100111001 数据位校验位 0←余数E(x)无差错!
4
CRC示例1:接收端一有差错 CRC示例2:发送端 例:设数据Mx)=1110110,G(x=11001,r=4 发送端发出的码字=1100111001 求CRC校验码R(x 接收端收到的码字=110010001 突发差错 Gay→11017111 ←MAxx 01←收到的码字M(x)-x2+R(x) 11001 发送码 00←余数E(x M(xx+R/x) =111001100110 E(x)≠0,检测到差错 数搪位校验位 0110←余数Rx 流行的生成多项式有: 32停止等待协议 CRC-8 G(x)=xtx +r+ 数据链路协议主要考虑的问题 CRC-12 G/x)=x2+x+x+x2+x+ ①避免所传送的数据可能出现差错和丢 G(x)=x16+x15+x2+l ②使发方发送数据的速率适应收方的接收能力 CRC-CCITT: G(x)=x+x2+x'+I 检测能力: 发送端 接收端 所有单个错、奇数个错和离散的二位错。 所有长度≤r位的突发差错 CRC的实现: 数据链路 ①硬件:采用多段移位寄存器及异或门组成CR 校验电路来实现 ②软件:通过快速CRC校验软件来实现 物理链路 理想化的数据传输 最简单流量控制的停止等待协议 假设1:所传送的数据即不会出现差错和也不会丢 保留假设1:去掉假设2。考虑流量控制问题→流量控制协议 失;(不考虑差错控制问 使发送端发送数据的速率适应接收端的接收能力 假设2:接收端的数据接收速率足够快,有能力 最简单流量控制协议 在发送节点 发送螭接收端 收发送端的数据发送率 (不考虑流量控制问题) 发送端接收端 ①从数裾链路层的发送缓存中取一个数据桢 ②发送这个数据桢 在理想化的条件下,数据链路 ③等待 ④若收到由接收端的应答信息,转到① 在接收节点 ①差错控制协议; ①等待; ②流量控制协议; ②接收由发送端发来的数据桢 就可保证数据的正确传输 ①将其存入数据链路层的接收缓存 ④发送应答信息,表示数据桢已接收;转到①
5
实用的停止等待协议(ARQ) 去掉假设1;去掉假设2 发送端接收端发送端接收端 考虑差错控制问题→差错控制协议 考虑流量控制问题→流量控制协议; D上X出错 的应答帧 ②接收端收到数据桢后 校验(一般用硬件检验) 如果无差错,回送一个 否则,回送一个否认帧NAK 时 ①发送端收到应答帧 如果是AcK,发送下一数据帧 (a)正常情况 b)数据顿出错 如果是NAK,重发数据帧 死锁现象: 重复帧差 发送端接收端 当出现桢丢失时,发送端永 应答帧丢失,按照超时 远等待下去。如何解决? 重发方法,接收端将收到重复 发送端接收端 帧,如何解决 发送端设立一个超时计时器, 丢失 送完一个数据帧时,就启动 每个数据帧附加不同的 ACK 发送序号Ns,如果接收端收到 相同序号的数据帧,则丢弃,并 械,就定为超时,重传数据 回送一个ACK (d)应答帧丢失 数据帧头出N数据CRC尾」 )数据帧丢失 T。也称重传时间 其它附加控制信息 发送序号需要多少位? 对于ARQ协议,发送序号有0和1即可(只需1个bi ARQ协议: 每发一个送新的数据帧,发送序号就和上次发送的不一样, 重发的数据帧发送序号不变 接收端□R 状态序号 发送端 等待 校>发送NAK 规时到←重传 RA重复倾丢弃 丢弃重复D2 NAK←重传 i(N==R)接收de丢弃 S-发送端本地状态序号(1bit 匮囧x,s R-接收端本地状态序号(bin) ←1-S←变序号 Ns-发送端附加到数据帧上的序号(1
6
重传时间tm的选择 停止等待协议的信道利用率 若T。m太长,浪费时间, 设:单程传输时延Td 数据帧发送时间Tf 传检时间 若Tm太短,过早重传数据,产生“额外”应答幀 额外”应答梳 数据传输率C,数据帧长度L 状态序号 信道利用率C 总时间-等待时间 传送一桢的总时间 帧序号 忽略应答幀长度和处理时间 丢弃差错丢弃丢弃mDs 如何解决? 提示:在确认桢ACK和否认帧NAK中附加序号 数据帧L越短,信道利用率越低 示例 33连续ARQ协议 星信道 目的:提高信道利用率 单程传输时延Td=250m 数据传输率C=50kb/s 发送端发送完一个数据帧后,不停下来等待应答 数据帧长度L=1kbit, 而是连续再发送数据帧,当收到否认桢NAK时 信道利用率Cr= =3.8% 数据帧需附加发送序号信息。否认帧附加出错的 例:若,Td=20ms,C=4kb/s, 数据帧发送序号 要使信道利用率达到50%,L=? 常用协议 27dC.Cr2×20×10-×4×10×50°=160(bit ①回退N帧ARQ协议( go back n) 1-Cr ②选择重发ARQ协议( selective repeat 回退N帧ARQ协议( go back n) ②方式 ①方式1 不反馈否认帧NAK。发送端采用超时机制 反馈否认帧NAK(含出错的数据帧发送序号)。再 发送端每发送一个数据帧就启动该帧计时器, 从出错的数据帧开始重传 当收到确认幀后,计时器复位;如果直到超时 还没有收到确认帧,則重发该数据帧及后继的 往返时间 使重 发送端 4s6789 发送端□ ■2■3「45國3■「5789 345■673 67 要求:发送端要求有一个能存儲N个数据桢的缓冲区 接收端只需能存储一个数据帧的缓冲
7
3.4选择重发ARQ协议( selective 选择重发ARQ协议一工作原理示意图 目的:进一步提高信道利用率。 方法:只重传出现差错的数据帧或者超时的数据 回四 要求:在接收端要设置具有相当容量的缓存空间 123_4 78910 暂存于缓存中 多个数据帧出错情况 滑动窗口协议( Sliding Windows) 发送窗口(在发送端) 对于连续ARQ协议,采用了发送端不等待确认 目的:用来对发送端进行流量控制 帧返回就可连续发送帧,存在问题: 发送窗口尺寸s:在还没有收到应答帧的情况下 ①当未被确认的数据幀数目太多时;只要有一桢出 送端最多可以连续发送数据帧的个数 错,就有很多数据帧需要重传,因而增大开销 ②为了对发送出 量未被确认的数据帧进行编 发送序号 号,每个数据帧的发送序号也要占用较多的比特 一般采用n位b进行编号(0-2-1) 数,因而又增大了开销 3;则用3位bi进行编号(0-7) 滑动窗口协 对发送端已发送出去但未被确认的幀的数目加以限 在发送端和接收端分别设置发送窗口和接收窗口 ·发送端只能连续发送窗口内的数据帧; 接收窗口(在接收端) 每收到一个确认幀后,发送窗口 沿顺时针 目的:用来控制可以接收哪些数据帧而不可以接收哪 旋转一个号,并可以一个发送新的数据帧 些桢 ·若未应答帧的数目等于发送窗口尺寸时,便停止发 接收窗口r:只有当收到的数据帧的发送序号落入接 新的数据帧 收窗口内,才允许将该数据幀收下;否则,丢 Ns-5 Hsas 等待换收0号数据候并发出静号确 收到1-3号数据帻后 确认,则停止发送,等待 等持接收1号数 待接收4号数据
8
应答帧丢失情况 如果W~1,意味着只能按顺序接收数据帧 Hs-2发送端 接收端H=2送 如果W较大,有可能会出现数据帧的失序 0234567 0234567D0 差错情况:设Wr=1 n34567D1 若收到0号数据帧,接收窗口順时针旋转一个号, 并发出θ号确认帧;准备接收1号数据帧 ck201234567D2 此时,如果收到的不是1号数据 4567 而是0号数据帧,表明发出0号确认帧发送端没有 改到,因此再发送一次0号确认帧,此时收到的0号数 01234567 01234567 若是2号数据帧,表明发送端发出的1号数据帧丢 失,因此发送1号否认幀,让对方重新发送1号数据 Y01234567 应答帧被“篡改”情况:NAK→ACK 应答帧被“篡改”情况:ACK→NAK s=2 u=2发送端 接收端H=2 ]234567 m23456 0234567 o234567b NAn234567 k234567|D0 0234567tb2 疑ACk0234567D1 :o0234567 ipz 2345 K201234567D2 :", xn234567 01234567 D1丢弃 o2345 0I23456 01区3456 吨012s67iD4D5 重叠问题 避免重叠问题 在接收前后,接收窗口范围内的有效序号出现重 为了避免重叠问题,接收窗口尺寸Wr≤2"12 叠 01234567dag0D3 01234567 01234567 01234567 重发 01234567 回1234567 01234567cm 01234567 01234567 重复D1-3丢弃 01234567 应答帧全部丢失 应答帧全部丢失
9
发送窗口的最大尺寸值 累积确认方法 Js=8发送端接收端H=4 接收端在连续接收若干个正确的数据帧以 后,对最后一个数据幀发回确认桢 1234567 0123456 接收端Wr=4 CkH30123H567 01234567 回1234567 01234567aD 01234567 0123456 AcKn-3 01234567 0123456 01234567 重复帧D小~7 ACK 123456 答帧全部丢失 所以,Ws274+T时:Cr=100% 当Ws·Tf<27d+T时 发送端[u3 Tf 显然,越大,信道利用率越高 依据信道利用率进行窗口尺寸的选择 例 例:卫星信道 优化原则 单程传输时延Td=250 发送端收到窗口中第一个已发数据帧的确认时,正 数据传输率C=50kb/s, 好发完窗口中的最后一个数据帧 数据帧长度L=1000bit, 口人寸mm+30m2 1+21d 例:若,Td=20ms,C=56kb/s,Ws=8,L 数据帧长度L 2Td.C2×0.02 320(bit) 大于上述选择,则Cr=100%,但浪费缓冲区 卩s小于上述选择,则Cr<100%,发送瑞需要等待应 在已知条件不变的情况下,设置L=160bt,信道 答而使发送停顿 利用率如何?
10