清华大学计算机网络ch5

主要内容5.1定义和功能5.1.1定义5.1.2为网络层提供服务5.1.3成帧5.1.4差错控制5.1.5流量控制5.2错误检测和纠正5.2.1纠错码5.2.2检错码5.3基本的数据链路层协议5.3.1无约束单工协议5.3.2单工停等协议5.3.3有噪声信道的单工协议5.4滑动窗口协议5.4.1一比特滑动窗口协议5.4.2退后n帧协议5.4.3选择重传协议5.5协议说明与验证5.5.1通信协议中的形式化描述技术5.5.2有限状态机模型5.5.3Petri网模型5.6常用的数据链路层协议5.6.1高级数据链路控制规程HDLC5.6.2X.25的链路层协议LAPB5.6.3Internet数据链路层协议5.6.4ATM数据链路层协议5.1定义和功能（1）5.1.1定义要解决的问题：如何在有差错的线路上，进行无差错传输。ISO关于数据链路层的定义：数据链路层的目的是为了提供功能上和规程上的方法，以便建立、维护和释放网络实体间的数据链路。数据链路：从数据发送点到数据接收点（点到点pointtopoint）所经过的传输途径。虚拟数据通路，实际数据通路。Fig.3-15.1定义和功能（2）数据链路控制规程：为使数据能迅速、正确、有效地从发送点到达接收点所采用的控制方式。数据链路层协议应提供的最基本功能数据在数据链路上的正常传输（建立、维护和释放）定界与同步，也处理透明性问题差错控制顺序控制流量控制5.1定义和功能（3）5.1.2为网络层提供服务为网络层提供三种合理的服务无确认无连接服务适用于误码率很低的线路，错误恢复留给高层；实时业务大部分局域网有确认无连接服务适用于不可靠的信道，如无线网。有确认有连接服务5.1定义和功能（4）5.1.3成帧（Framing）将比特流分成离散的帧，并计算每个帧的校验和。成帧方法：字符计数法在帧头中用一个域来表示整个帧的字符个数缺点：若计数出错，对本帧和后面的帧有影响。Fig.3-3带字符填充的首尾字符定界法起始字符DLESTX，结束字符DLEETX字符填充Fig.3-4缺点：局限于8位字符和ASCII字符传送。5.1定义和功能（5）带位填充的首尾标记定界法帧的起始和结束都用一个特殊的位串“01111110”，称为标记(flag)“0”比特插入删除技术Fig.3-5物理层编码违例法只适用于物理层编码有冗余的网络802LAN：ManchesterencodingorDifferentialManchesterencoding用high-lowpair/low-highpair表示1/0，high-high/low-low不表示数据，可以用来做定界符。注意：在很多数据链路协议中，使用字符计数法和一种其它方法的组合。5.1定义和功能（6）5.1.4差错控制一般方法：接收方给发送方一个反馈（响应）。出错情况帧（包括发送帧和响应帧）出错；帧（包括发送帧和响应帧）丢失通过计时器和序号保证每帧最终交给目的网络层仅一次是数据链路层的一个主要功能。5.1.5流量控制基于反馈机制流量控制主要在传输层实现。5.2错误检测和纠正（1）差错出现的特点：随机，连续突发（burst）处理差错的两种基本策略使用纠错码：发送方在每个数据块中加入足够的冗余信息，使得接收方能够判断接收到的数据是否有错，并能纠正错误。使用检错码：发送方在每个数据块中加入足够的冗余信息，使得接收方能够判断接收到的数据是否有错，但不能判断哪里有错。5.2.1纠错码码字（codeword）：一个帧包括m个数据位，r个校验位，n=m+r，则此n比特单元称为n位码字。海明距离（Hammingdistance）：两个码字之间不同的比特位数目。5.2错误检测和纠正（2）例：0000000000与0000011111的海明距离为5如果两个码字的海明距离为d，则需要d个单比特错就可以把一个码字转换成另一个码字；为了检查出d个错（单比特错），需要使用海明距离为d+1的编码；为了纠正d个错，需要使用海明距离为2d+1的编码；最简单的例子是奇偶校验，在数据后填加一个奇偶位（paritybit）。例：使用偶校验（“1”的个数为偶数）10110101——10110101110110001——101100010奇偶校验可以用来检查单个错误。5.2错误检测和纠正（3）设计纠错码要求：m个信息位，r个校验位，纠正单比特错；对2m个有效信息中任何一个，有n个与其距离为1的无效码字，因此有：(n+1)2m2n利用n=m+r，得到(m+r+1)2r给定m，利用该式可以得出校正单比特误码的校验位数目的下界。海明码码位从左边开始编号；位号为2的幂的位是校验位，其余是信息位；每个校验位使得包括自己在内的一些位的奇偶值为偶数（或奇数）。5.2错误检测和纠正（4）为看清数据位k对哪些校验位有影响，将k写成2的幂的和。例：11=1+2+8海明码工作过程每个码字到来前，接收方计数器清零；接收方检查每个校验位k(k=1,2,4…)的奇偶值是否正确；若第k位奇偶值不对，计数器加k；所有校验位检查完后，若计数器值为0，则码字有效；若计数器值为m，则第m位出错。若校验位1、2、8出错，则第11位变反。Fig.3-6使用海明码纠正突发错误可采用k个码字（n=m+r）组成kn矩阵，按列发送，接收方恢复成kn矩阵kr个校验位，km个数据位，可纠正最多为k个的突发性连续比特错。123456789101111111222224448885.2错误检测和纠正（5）5.2.2检错码使用纠错码传数据，效率低，适用于不可能重传的场合；大多数情况采用检错码加重传。循环冗余码（CRC码，多项式编码）110001，表示成多项式x5+x4+1生成多项式G(x)发方、收方事前商定；生成多项式的高位和低位必须为1生成多项式必须比传输信息对应的多项式短。CRC码基本思想：校验和（checksum）加在帧尾，使带校验和的帧的多项式能被G(x)除尽；收方接收时，用G(x)去除它，若有余数，则传输出错。5.2错误检测和纠正（6）校验和计算算法设G(x)为r阶，在帧的末尾加r个0，使帧为m+r位，相应多项式为xrM(x)；按模2除法用对应于G(x)的位串去除对应于xrM(x)的位串；按模2减法从对应于xrM(x)的位串中减去余数（等于或小于r位），结果就是要传送的带校验和的多项式T(x)。Fig.3-7CRC的检错能力发送：T(x)接收：T(x)+E(x)余数((T(x)+E(x))/G(x))=0+余数(E(x)/G(x))若余数(E(x)/G(x))=0，则差错不能发现；否则，可以发现。5.2错误检测和纠正（7）如果只有单比特错，即E(x)=xi，而G(x)中至少有两项，余数(E(x)/G(x))0，所以可以查出单比特错；如果发生两个孤立单比特错，即E(x)=xi+xj=xj(xi-j+1)，假定G(x)不能被x整除，那么能够发现两个比特错的充分条件是：xk+1不能被G(x)整除(ki-j)；如果有奇数个比特错，即E(x)包括奇数个项，G(x)选(x+1)的倍数就能查出奇数个比特错；具有r个校验位的多项式能检查出所有长度r的差错。长度为k的突发性连续差错（并不表示有k个单比特错）可表示为xi(xk-1+…+1)，若G(x)包括x0项，且k-1小于G(x)的阶，则E(x)/G(x)0;如果突发差错长度为r+1，当且仅当突发差错和G(x)一样时，E(x)/G(x)=0，概率为1/2r-1;长度大于r+1的突发差错或几个较短的突发差错发生后，坏帧被接收的概率为1/2r。5.2错误检测和纠正（8）三个多项式已成为国际标准CRC-12=x12+x11+x3+x2+x+1CRC-16=x16+x15+x2+1CRC-CCITT=x16+x12+x5+1CRC-32硬件实现CRC校验。5.3基本的数据链路层协议（1）5.3.1无约束单工协议（AnUnrestrictedSimplexProtocol）工作在理想情况，几个前提：单工传输发送方无休止工作（要发送的信息无限多）接收方无休止工作（缓冲区无限大）通信线路（信道）不损坏或丢失信息帧工作过程发送程序:取数据，构成帧，发送帧；接收程序：等待，接收帧，送数据给高层Fig.3-95.3基本的数据链路层协议（2）5.3.2单工停等协议（ASimplexStop-and-WaitProtocol）增加约束条件：接收方不能无休止接收。解决办法：接收方每收到一个帧后，给发送方回送一个响应。工作过程发送程序：取数据，成帧，发送帧，等待响应帧；接收程序：等待，接收帧，送数据给高层，回送响应帧。Fig.3-105.3基本的数据链路层协议（3）5.3.3有噪声信道的单工协议（ASimplexProtocolforaNoisyChannel）增加约束条件：信道（线路）有差错，信息帧可能损坏或丢失。解决办法：出错重传。带来的问题：什么时候重传——定时响应帧损坏怎么办（重复帧）——发送帧头中放入序号为了使帧头精简，序号取多少位——1位发方在发下一个帧之前等待一个肯定确认的协议叫做PAR（PositiveAcknowledgementwithRetransmission）或ARQ（AutomaticRepeatreQuest）5.3基本的数据链路层协议（4）工作过程Fig.3-11注意协议3的漏洞由于确认帧中没有序号，超时时间不能太短，否则协议失败。因此假设协议3的发送和接收严格交替进行。Fig.3-11（与教材不同）的实现是正确的，确认帧有序号发送接收001ACKACK5.4滑动窗口协议（1）单工——全双工捎带/载答（piggybacking）：暂时延迟待发确认，以便附加在下一个待发数据帧的技术。优点：充分利用信道带宽，减少帧的数目意味着减少“帧到达”中断；带来的问题：复杂。本节的三个协议统称滑动窗口协议，都能在实际（非理想）环境下正常工作，区别仅在于效率、复杂性和对缓冲区的要求。5.4滑动窗口协议（2）滑动窗口协议（SlidingWindowProtocol）工作原理：发送的信息帧都有一个序号，从0到某个最大值，0~2n-1，一般用n个二进制位表示；发送端始终保持一个已发送但尚未确认的帧的序号表，称为发送窗口。发送窗口的上界表示要发送的下一个帧的序号，下界表示未得到确认的帧的最小编号。发送窗口=上界-下界，大小可变；发送端每发送一个帧，序号取上界值，上界加1；每接收到一个正确响应帧，下界加1；接收端有一个接收窗口，大小固定，但不一定与发送窗口相同。接收窗口的上界表示允许接收的序号最大的帧，下界表示希望接收的帧；接收窗口表示允许接收的信息帧，落在窗口外的帧均被丢弃。序号等于下界的帧被正确接收，并产生一个响应帧，上界、下界都加1。接收窗口大小不变。Fig.3-125.4滑动窗口协议（2）5.4.1一比特滑动窗口协议（AOneBitSlidingWindowProtocol）协议特点窗口大小：N=1，发送序号和接收序号的取值范围：0，1；可进行数据双向传输，信息帧中可含有确认信息（piggybacking技术）；信息帧中包括两个序号域：发送序号和接收序号（已经正确收到的帧的序号）工作过程Fig.3-135.4滑动窗口协议（3）存在问题能保证无差错传输，但是基于停等方式；若双方同时开始发送，则会有一半重复帧；Fig.3-14效率低，传输时间长。5.4滑动窗口协议（4）5.4.2退后n帧协议（AProtocolUsingGoBackn）为提高传输效率而设计例：卫星信道传输速率50kbps，往返传输延迟500ms，若传1000bit的帧，使用协议4，则传输一个帧所需时间为：发送时间+信息信道延迟+确认信道延迟（确认帧很短，忽略发送时间）=1000bit/50kbps+250ms+250ms=520ms信道利用率=20/5204%一般情况信道带宽b比特/秒，帧长度l比特，往返传输延迟R秒，则信道利用率为(l/b)/(l/b+R)=l/(l+Rb)结论传输延迟大，信道带宽高，帧短时，信道利用率低。5.4滑动窗口协议（