《计算机通信网 》第3章 数据链路层Part1

2014SPLENG第3章数据链路层3.1数据链路层概述3.2成帧与帧定界3.3差错检测与校正方法3.4差错与流量控制协议3.5协议描述与验证3.6数据链路层协议案例3.1数据链路层概述链路层模型本地连接传输系统G.703G.703远程连接物理层网络层链路层链路层网络层链路层链路层网络层传输系统提供透明的bit传输3.1数据链路层概述DL面临的环境网络层数据链路层物理层SAPSAPSAPSAP网络层数据链路层物理层分组帧装入分组取出1010…11011010…1101帧发送方接收方信道有噪声，bits可能出错可能装入太快取出跟不上★3.1数据链路层概述链路层模型链路层网络层物理层010101比特传输传输信号Packet物理层实现了把比特传输转换成信号传输、进入信道。网络层需要把一个个分组送到对方网络层链路层组织一个个分组，用比特传输实现逐个分组的传输和接收3.1数据链路层概述链路层的基本任务物理层AsynchronousBlockSynchronousDUFraming(帧同步)发送：转换成特定的bit传输形式，将Frame送出接收：界定每个frame的位置，取出frameDUErrorControl(差错控制)发送：组织DU(frame)，方便对方检查错误接收：检测DU是否出错，DU出错的处理LinkControl(链路控制)双方通过配合，实现：链路的使用规则，流量控制、汇聚分发等DUService(服务)为上面的实体提供分组传输服务3.1数据链路层概述链路层任务模型framingErrorControlDataLinkControlframingErrorControlDataLinkControlPhysicalLayerDataLinkLayerNetworkLayerDUDUFrame约定成帧方式约定出错处理手段约定控制方法可用的通信功能DU3.1数据链路层概述链路层效率定义链路层有效数据率r=∑ni/T（ni：第i帧bit数，T：测量总时间）物理层信道的速率Rb/s链路层效率：

η=r/R（η

≤1）链路层链路层LinkLayerServices三种服务的示意图有确认面向连接无确认无连接Frameack有确认无连接Frameack连接确认连接请求FrameFrameack拆除确认拆除请求B方A方LinkLayerServices三种可能的服务无确认的无连接服务无需对方许可，直接向对方发送Frame，对方不需要反馈确认信息优点：不受等待确认的拖累；缺点：frame传输可靠性不高信道效率：不等待确认，可提高信道效率，但传输出错降低信道效率协议考虑：PDU中含源/目的地址有确认的无连接服务无需对方许可，直接向对方发送Frame，需要对方反馈确认信息优点：通过重传增加了可靠性；缺点：受等待应答的拖累保持发送和确认间的正确对应关系所采取的措施会大大降低信道使用效率协议考虑：PDU编号，PDU中含源/目的地址、单帧确认，差错检测与重传有确认的面向连接服务需事先与对方沟通，双方建立起一套复杂的发送、确认机制来实现恢复差错、排除重复、维持顺序的可靠通信适合于有大量Frame传输的场合协议考虑：PDU编号、确认、差错控制（丢弃错帧和重复帧，请求重发错帧）3.2成帧Framing成帧(或帧同步)：就是确定帧的界限（起与止）通俗理解：发送方：在帧的前后各加入事先商定好的标记接收方：在bits中寻找标记来识别帧的起与止需要特别考虑：若数据与帧的起止标记相同时，发送方必须采取措施否则可能会引起接收方的误断成帧方法：字符计数法字符填充首尾界定法位填充首尾界定法物理层编码违例法110101101001011011001111011110010101011100010101001011010101011011010100100100…….如何分离出一个一个的帧？★成帧不同传输方式下的帧同步同步传输方式(Sync,连续bit流)连续的bit流传递离散的Frame每个Frame都成为连续bit流中的一段，接收方识别并取出Frame异步传输方式(Async,异步字节序列)每个Frame转换为异步字节序列传送，接收方收集字节序列，还原Frame数据块传输方式(Block)每个Frame形成一个数据块传送。Sync信道的帧同步技术连续的bit流由若干Frame和它们间的空闲bit组成注意：frame中或空闲的bit都只有两种取值：0或1关键问题：如何正确识别和提取bit流中的Frame部分？思路：假设空闲bit用某种特殊的bit模式(pattern)构成，而Frame中不会出现该pattern，则接收方就能够正确设别和提取Frame但:应该允许Frame包含任意数据，就肯定包含了这种Pattern。若能对Frame中出现的Pattern用某种变换方式消除，接收方提取出Frame后，再通过反变换，恢复原来的Frame，该假设成立Frame’FrameFrame’Frame反变换变换Frame连续bit流空闲空闲空闲特殊patternSync信道的帧同步技术发送开始扫描Frame发现PatternPattern变换扫描结束发送Frame’否是结束否是接收开始否检测pattern发现存储数据否检测pattern发现复原Frame是继续是结束是Frame开始Frame结束否Pattern选择--易于变换--易于检测--易于反变换Sync信道的帧同步技术位填充首尾定界法（‘0’比特插入/删除技术)Pattern=‘01111110’称为定界标志F(Flag)Frame内F的变换和反变换(利用F中连续6个‘1’的性质)变换：Frame中如果出现连续5个‘1’时，插入一个‘0’提取从第一次出现非F开始，到重新出现F时的所有bit反变换Frame中出现连续5个‘1’时，删除后面的1个‘0’采用01111110的特点：变换与发送合一：发送连续5个‘1’，加发一个‘0’接收与复原合一：连续接收5个‘1’，下一bit若是‘0’则直接去掉，否则，应该出现的就是‘01111110’结束该帧位填充首尾定界法

发送：在帧体部分出现连续5个1，无条件地插入一个0

接收：在帧体中扫描连续5个1，无条件去掉后面的0011111100010101111011111011111101010111111111001000成帧00101011110111111010111111111001000位填充首尾定界法位填充(实现示意图)…01111110011111101001111010110101010111111010101110101110111111001111110…帧提取…01101010…移位寄存器F检测结果帧体帧体“0”bit删除01111110‘0’bit插入控制接收发送控制数据位填充首尾定界法软件模拟intSend(char*pF,intLen){inti,j,c,msk,sn;sn=0;for(i=0;i<Len;i++){//循环帧的字节长度

msk=1;for(j=0;j<8;j++){//8bitc=pF[i]&msk?1:0;测试第jbitmsk<<=1;准备测试下一bitXmitb(c);sn++;if(c)cnt++;elsecnt=0;//计算连续1的个数

if(cnt==5){Xmitb(0);cnt=0;sn++;}}}returnsn;//回送发送总bit数}假定函数Xmitb(c)：向信道发送c(1bit)Async信道的帧同步技术描述以字节(8bit)为单位的传输方式逐字节传输实现Frame传输帧同步讨论Frame间留有足够的时间间隔，以区分各个Frame对Frame传输能力有较大的影响Frame间的时间间隔不够大，帧与帧区分易出错两种典型帧同步技术字节计数法字符填充首尾定界法PSTN成帧——字符计数法也可称为字节计数法假设一个字符由8位二进制数表示基本思想在帧头的第1个字节指明帧内的字节数问题字节计数值可能在传输中出错（被篡改）简单、不可靠1110101000101110

0101010101011101010101011发送DATA11101010001011100101010101011101010101011错00000010接收11101010001011100101010101011101010101011000001100000001100000110★字符填充首尾定界法思想与同步方式的位填充类似，不同的是以字节为单位方法：“定界字符”在帧体的前后都用某个特定的字节加以“定界”帧体中也可能出现该定界字符，通过变换消除接收时提取Frame后，通过反变换复原局限性：数据的长度总是以字符或其倍数为单位定界字符:F(Flag)=01111110F14768x31452F684314F第1帧第2帧68431414768F31452字符填充首尾定界法将F变换为某个其它字节(x)存在问题：帧体中其它字节也可能出现x，反变换xF时就出错Frame体中定界字符的变换方法一字节到两字节的变换,变换后帧体中不出现F帧体中的F和x都需要变换：Fxy;xxzy和z是另外选取的两个字符，对y、z不再需要变换分析若帧体中出现xy变换：xy(xz)y；反变换：xzyxy,正确复原可以验证：对帧体中出现F,x,y,z的任意顺序的组合，只对其中的所有F和x进行变换，反变换时都能正确复原字符填充首尾定界法处理帧体内的特殊字符(RFC1662，异步PPP)F=01111110(7e),定界字符x=01111101(7d),称为转义字符y=01011110(5e)z=01011101(5d)帧体1476F43x5d52F1476x5e43x5d5d52F帧体填充后发送XmitB(F)B=F？结束否是B=Frame[i++]XmitB(B)B=x？XmitB(x)XmitB(y)XmitB(x)XmitB(z)否是i<Len是XmitB(F)否XmitB：发送字节XrcvB：接收字节练习分两组：一组成帧，一组提取帧分别用位填充法、计数法、字符填充法进行练习F=01111110，x、y、z可自行定义可自定义若干帧来完成该练习思考字符填充法中，仅用F和x是否能够实现，如能实现，给出实现方法，如不能实现，请说明不能实现的理由帧1：1001111111100000010111010100001001100011帧2：110110110000000001100111帧3：11000101111111111101001011011111

字符填充首尾定界法教材PP.159块传输信道的帧同步技术当用电缆或无线直接通信(不经过传输系统)时，最简洁的通信方式是块传输方式，每个块就是一个Frame块传输方式每个Frame都带有前导bit序列(preamble)和后续bit序列(postamble),以确保Frame的头和尾能正确检测和接收因此需要确定：Preamble结束和Frame开始的比特位置Frame结束和postamble开始的bit位置同步技术违例编码法：利用信息bit的码型特性，用非正常码型来进行界定位置preamblepostamble块传输信道的帧同步技术例1：曼切斯特编码(1b/2b,10M以太网)Block=010101JKFramebodyKJ010101例2：4b/5b编码(100M以太网)4bit数据映射成5bit码组000011110,000101001,…,111111101空闲11111,定界符111000,定界符210001Block=010101定界符1FrameBody定界符2010101例3：8b/10b编码(1000M以太网)8bit数据映射成10bit码组从1024个码组中只需选取256个来代表8bit的各个值剩余1024-256个码组可作为控制、定界等多种功能‘0’=‘1’=违例和J=K=块传输信道的帧同步技术

校验和法利用ATM信元固定、且长度较短(53字节)的特性信元前4字节是头部，第5字节是校验和，使用循环冗余校验设40位寄存器，计算校验和正确则可能发现了一个信元不正确则移一位，再次计算，直到得到一个信元成帧1001101000101011111101000110110001111011100信元头信元体信元头信元体……3.2成帧——讨论与理解帧定界正确，请问帧一定无错吗？一个帧定界出错，请问用字符计数法，后续的帧也不能正确识别吗？为什么？用字符填充法和位填充法，情况又如何？位填充法比字符填充法有哪些优越性？Framing小结不同的成帧技术以适应信道的不同传输体制需求：接收方易于提取、出错时对后续帧的提取影响小较高的信道利用率、较简单的实现位填充、字符计数、字符填充、违例编码、校验和与其它功能的关系实现的是信道上传输和接收帧的功能，不涉及帧的内容链路层其它功能直接对帧的处理，不受传输体制影响framingframing差错处理、链路功能差错处理、链路功能3.3差错检测与纠正信道传输过程中(误码：10;01)随机干扰：随机错(均匀性)突发干扰：突发错(一定的突发长度)出错处理检错：验证是否出现了误码纠错：找到误码的位置，纠正之…01111110011111101001111010110101010111111010101110101110111111001111110……01111110011011101001111110110101010110111010101110101111111111001111110…Bit错可能造成：

帧体错——帧错误定界错——帧错误、帧丢失、多余帧信道异常(多于6个1)——信道失序原码出错后3.3差错检测与纠正如何理解数据传输中的差错？一位错就等于全帧错关于误码率Pb与误帧率Pe假设帧长度为N比特，误码率为Pb（设每比特出错独立）则比特正确率为：1-PbN比特正确率为（1-Pb）N帧出错率（误帧率）（一帧中至少一位错）为

Pe=

1-（1-Pb）N≈NPb

（帧出错的概率与帧成近似成正比）★3.3差错检测与纠正差错控制，意味着：首先检测出差错然后是纠正差错检测差错采用冗余编码技术进行差错检验编码纠错码：不仅能检测差错，且能知道错在哪儿检错码：只能检测差错，但不知错在哪纠正差错前向纠错FEC（ForwardErrorCorrection）用纠错码，收方检错并自动纠错自动请求重发ARQ（AutomaticRequestforRepeat）用检错码，收方检错通知发方重发恢复差错计算机网络中常采用★3.3差错检测与纠正假设待传数据为m位为检测差错，所需要的冗余位（校验位）为r位则传输码长度n=m+r通常采用纠错码或检错码，即：按某种算法计算出校验位然后将m位数据和r位校验码形成传输码接收方根据相同的算法重新计算校验位，判断是否出错★3.3差错检测与纠正一种直观简单的纠错方法每个bit重传三次：1111;0000如果3bit中有1bit错,我们可以纠正过来101、110、0111111001、010、1000000如果3bit中有2bit或3bit全错，则无法纠正了101111?000?无法知道是1bit还是2bit错将每个bit重传2n+1次，n越大，纠错能力越强(传输效率越低)不管n如何取，我们仍不知道是否真的纠正了错误，只能认为增大了纠正错误的概率3.3.1纠错码——海明码海明距离（HammingDistance）教材P162～163两个等长码对应位不同的个数，称作这两个码的海明距离例：0001111和0001100的海明距离为2某种编码的任意两个有效编码之间的距离称为该编码的海明距离结论1：检出d个错误的检错码，海明距离至少为d＋1结论2：纠正d个错误的纠错码，海明距离至少为2d＋1

海明码是一种能纠正一位错的纠错码3.3.1纠错码——海明码假设数据为m位则纠正一位错的校验码r满足

m+r+1≤2r（证明：P163）例如：m=3，3+r+1≤2r→r=3则海明码码长=m+r=6位海明码的编码为r与m的混排方式，规则为：检验位r的序号为2的整次幂1，2，4，8，……信息位m的序号为2的非整次幂，3，5，6，7…..r1r2m3r4m5m63.3.1纠错码——海明码假设数据为011，该如何确定海明编码？编码应为：r1r2m3r4m5m6现已知：m3m5m6=011关键是确定r1、r2和r4r的计算方法首先找出哪些与r1、r2和r4相关的数据位将数据位数拆成2的整次幂相加如3=1+2→m3与r1和r2相关然后将与某r相关的数据位模2加(异或），结果为该r值与r1相关的数据位：m3、m5则r1=0⊕1=1与r2相关的数据位：m3、m6则r2=0⊕1=1与r4相关的数据位：m5、m6则r4=1⊕1=0得出：011的海明编码为1100113.3.1纠错码——海明码已知：011的海明编码为110011（r1r2m3r4m5m6）假设：编码在传输中出了一位错

110011错成110010

接收方的纠错规则首先：对于每个ri，将ri和与之相关的数据位进行依次异或结果为1，则记录Ai=i（i为r的序号）结果为0，则记录Ai=0然后累加，计算∑Ai的值，结果等于几就是该对应位出错最后，将出错位取反进行纠错计算过程r1⊕m3⊕m5=1⊕0⊕1=0则A1=0r2⊕m3⊕m6=1⊕0⊕0=1则A2=2r4⊕m5⊕m6=0⊕1⊕0=1则A4=4出错位：∑Ai=A1+A2+A4=6纠错：110010

→110011

（差错位取反）3.3.2差错检测采用冗余编码技术进行差错检验编码基本思想发送方：将待发数据按照某种规则加上一定的冗余位后，进行传输，接收方：对收到的数据进行判断，是否符合原规则，若符合则无错，不符合则出错。C(x)=R(x)

无错C(x)≠R(x)

出错★3.3.2差错检测——检错码奇偶校验码循环冗余码CRC校验和编码3.3.2差错检测——奇偶校验码增加冗余位使信息码中的“1”的个数为奇数或偶数的编码奇校验：“1”的个数为奇数偶校验：“1”的个数为偶数具体实现：信息位逐位进行模2加（异或运算）a1⊕a2⊕a3⊕a4⊕a5……

结果为0，偶校验时校验位为0，奇校验时，校验位为1结果为1，偶校验时校验位为1，奇校验时，校验位为0例信息字段奇校验码偶校验码

01100101100100110011

出错为：00100100010011重新计算校验和：10不同则出错★纠正突发错数据组织成矩阵，按行编写奇偶效验码发送时按列发送出现突发错误时，可按行纠正1001011110101000101101001001101001000010100100100100001011101011010101101010010000100001010111110000101113.3.2差错检测——循环冗余码循环冗余码（CRC:CyclicRedundancyCode）教材p165~167对任意m位二进制流，补充r个0用规定的r+1位除数进行求余计算，得到r位效验码数据与r位效验码组成传输码组发送出去1011010110001010000000101101011000101

1110001011000101

01001110110110000000000

1001110011000101

1011001011000101

1110111011000101

01010110m位数据r位CRC101011000000000

1010110模2加3.3.2差错检测——循环冗余码CRC校验对收到的完整的数据帧用发送方相同的r+1位除数进行求余计算余数为0则无错101101010101101100010111100000110001010100101100000000

1001011011000101

1010011111000101

1100010111000101

0000000000000000000000011000101101101010101103.3.2差错检测——循环冗余码基于任何一个二进制位串组成的代码，都可以与系数只为0和1的多项式建立一一对应的关系。一个K位的数据可以看成是从xK-1～x0次系数为0和1的多项式

x4x3x2x1x0

数据：11011多项式x4+x3+x+13.3.2差错检测——循环冗余码1）基本思想：设：数据m位，对应多项式M（x），校验码为r位，对应多项式R(x)

给定：生成多项式G（x），阶数为r，r+1位，高位和低位系数为1发送方：将M（x）通过G（x）计算出带校验和的传输多项式T（x）接收方：将收到的带校验和的多项式T’（x）除以G（x），如有余数，出错，能除尽，无错2）校验码与传输多项式的计算STEP1在m位数据之后加上r个0，数据位变成m+r位，对应多项式xrM（x）STEP2计算校验码多项式：xrM（x）/G（x）(对应二进制位串模2除)，余数为校验码，对应多项式为R（x）STEP3计算传输多项式：T（x）=xrM（x）+R（x），对应系数位串为传输数据★3.3.2差错检测——循环冗余码示例：数据：110110G（x）=x4+x+1对应位串10011（除数）在数据后加4个0形成1101100000被除数，求余数3.3.2差错检测——冗余循环码值得注意：多项式变为码字时，首位对应最高次，中间的“0”不能丢掉在计算中涉及的“+”和