第三讲-数据链路层

1第三讲数据链路层2本讲要求1理解数据链路层解决的基本问题2掌握数据帧的基本原理和方法3掌握出错处理的几种方式4掌握数据链路层的基本协议5掌握数据链路层的滑动窗口协议6了解典型的数据链路协议3基本问题如何利用物理层的0-1比特流传输能力在相邻机器间进行数据传输？问题分析◆信道问题广播信道点对点信道每对连接对应一对机器4问题分析（续1）◆地址问题—通信主机标识问题（*）◆面向连接还是非连接？□面向连接——是基于电话系统模型。也就是说，在数据传输前，有一个连接建立的过程，通信结束后，有一个连接断开的过程。（服务质量高）□面向非连接——是基于邮政系统模型。也就是说，任何时候数据都可以直接发送。（服务质量低）5问题分析（续2）◆数据封装问题—帧格式□开始、结束标志□通信地址：面向连接时，建立连接过程需要地址；面向非连接时，数据传输时需要地址。□数据及编码□递交对象——数据链路是数据传输服务层，到达目的机器后，数据必须递交给其他功能函数来处理。◆流量控制问题—发送者、接收者能力不对等问题◆出错处理—什么是错？纠错？检错？不管？结论：数据传输需要协调双方的行为——协议6数据链路层的地址问题◆随机分配—管理员分配配置◆固化设置—将地址固化到物理器械中如令牌环网等如以太网卡一般来说，通信主体都应该拥有一个标识——称为地址。小探索：查看以太网卡的物理地址，并修改它。7数据封装问题—帧格式（1）◆问题分析：什么是一个好的帧格式？（1）容易生成（2）重新实现帧同步的难度（3）普遍的适应性■将要传输的数据分成很多小段数据发送出去。8数据封装问题—帧格式（2）◆字符计数法□原理：在头部中的一个域指定该帧中的字符数。5个字符5个字符8个字符8个字符512345678901234568790123第一帧8第二帧第三帧第四帧8字符计数□问题：出错后的帧无法同步512347678901234568790123第一帧8第二帧8字符计数？9数据封装问题—帧格式（3）◆字节填充法□分析：字符计数法失去帧同步后，恢复很难。原因是很难区分计数的字符和数据字符。□原理：使用特殊的字符作为帧的开始和结束标志payloadFLAGFLAGheadertrailer□新的问题：如果负载重出现了FLAG了怎么办？AFLAGBFLAGFLAG10数据封装问题—帧格式（4）◆字节填充法□转义字节技术stuffing“ESC”ESCSamewithflagFLAGAFLAGBFLAGFLAGAFLAGBFLAG□新问题：数据中包含了ESC怎么办？11数据封装问题—帧格式（5）◆字节填充法□转义字节技术data“ESC”stuffing“ESC”ESCFLAGAESCBFLAGFLAGAESCBFLAG□其他问题？遇到第一个ESC，表示后面的是正常数据，不是特殊字符12数据封装问题—帧格式（6）◆字节填充法□字节填充法存在什么问题？◇必须紧紧依赖于8位字符模式◇不是所有的字符都是8位字符模式，如Unicode使用16位字符。结论：非8位字符模式，需要转换为8位字符模式才能顺利传输□字符填充法分析13数据封装问题—帧格式（7）◆位填充法□原理：帧开始和结束都有一个特殊的位模式01111110□问题：当传输数据中有01111110如何处理？□解决办法：碰到连续5连续的位“1”的时候，自动填充一位00111111001011111111011101111110123456123456781234560111111001011111011101110111111012345678□位填充法分析14数据封装问题—帧格式（8）◆物理层编码违例法□原理：使用非数据编码信号来表示帧的边界。如以太网（MAC子层中介绍）——曼彻斯特编码方式传输数据“1”的编码“0”的编码◇其他编码方式，可以用作帧的边界□物理层编码违例法分析15流控制问题◆问题描述发送方的速度超过了接受方能够接受这些帧的速度◆基本处理方法□基于反馈的流控制□基于速率的流控制定义规则，规范发送者什么时候可以发送帧。（具体协议中介绍）限制发送方的速率。（后面章节中详细介绍）16出错处理（1）◆定义—什么是错误？□严格意义：凡是接收到的数据和发送的数据不一致□不一致：错误数据*、丢失数据、数据乱序◆基本措施□纠错（错误纠正）：就是将不一致的数据恢复到一致□检错（错误发现）：检查数据中是否存在不一致□不作为先看看错误数据的基本措施，丢失和乱序问题在协议中介绍17出错处理（2）◆纠错—纠错码□原理：在发送的数据中包含冗余信息，以便接收者可以推断出数据中肯定有哪些内容。包含m个数据位和r个校验位的n-位单元，通常称为n位码字（n=m+r）。0111111001011111111011101111110mbitsDatabitsrbitsCheckbitsnbitscodeword（n=m+r）—有这么神奇的事情吗？18出错处理（3）◆纠错码□海明距离——两个码字不相同的位的个数10001001（码字1）10110001（码字2）XOR00111000海明距离d=3◇含义理解：如果码字1出错后，变为码字2，则至少要3位数据发生错误◇海明距离用来度量最少出错的位数19□海明距离用来度量最少出错的位数出错处理（4）◆纠错码□纠正d位错误的基本原理即假设传输过程中，最多d位出错。（1）对于传输数据m位，合法的报文有2m种情况；（2）对于传输的n位码字，可能的码字有2n种情况（n=m+r）；（3）从2n中选择2m个n位码字来表示合法的传输数据，并且保证每两个n位码间的距离至少为2d+1;（4）接收到数据A时，与所有的n位合法码字求解海明距离，海明距离小于d的，就是传输的数据。20出错处理（5）◆纠错码0000000000（码字1）0000011111（码字2）1111100000（码字3）1111111111（码字4）□例子编码距离为5，因此2d+1=5，可得d=2，该方案可以纠错2位以下的错误。接收到数据0000000111，与上面的码字计算海明距离，和码字2距离最小，为2，因此该数据有两位出错了，原始数据应该是000001111121出错处理（6）◆检错—检错码□原理：在发送的数据中包含冗余信息，以便接收者可以推断出数据中是否发生了错误。□奇偶检错方案——检测单个错误□检错原理：在数据后面加上一个奇偶位，如果码字中的“1”的位为偶数，则填0，如果是奇数，则填1。22出错处理（7）000001010011100101110111数据位校验位01101001000101数据位校验位00110010数据位校验位01senderreceivererror□奇偶校验例子□针对突发性长错误，可采用交错奇偶校验位来处理。23出错处理（8）□循环冗余校验（CyclicRedundancyCheck,CRC）也称多项式编码（PolynomialCode）◇基本思想○前提条件（1）将位串看成是系数为0或1的多项式。如10001011*x6+0*x5+0*x4+0*x3+1*x2+1*x1（2）发送方和接收在数据传输前商定一个生成多项式G(x).如G(x)=x4+x+1------10011（3）传输帧有m位，对应的多项式为M(x)。□校验和（Checksum）TCP/IP协议中使用的一种校验方法。24出错处理（9）○CRC校验和计算算法（1）假设G(x)的阶为r。在帧的低位端加上r个0，此时帧长为m+r，对应多项式为xrM(x)；（2）利用模2除法，用对应的G(x)的位串去除xrM(x)对应的位串，余数记为P(x)；（3）利用模2减法，xrM(x)-除法运算中的余数P(x)，结果记为T(x)就是带校验和的帧。25出错处理（10）○CRC校验和计算例子问题：发送数据帧1101011011m=10，M(x)为(m–1=9)阶多项式M(x)＝x9+x8+x6+x4+x3+x+1第一步：选择生成多项式G(x)=x4+x+1r=4，10011第二步：形成多项式xrM(x)n=m+r=10+4=14，xrM(x)为13阶多项式x4M(x)＝x13+x12+x10+x8+x7+x5+x41101011011000026出错处理（11）○CRC校验和计算例子第三步：用以2为模的除法求余数余数[11010110110000/10011]=1110第四步：用以2为模的减法计算校验和发送帧T(x)＝1101011011111027出错处理（12）○CRC检错能力说明（1）如果传输过程出错了，即有一些位的0或1发生了变化。把发生变化的位记录为1，其他位置为0，它对应一个多项式E(x)。（2）接收者的信息则为T(x)+E(x)；（3）校验时候计算为[T(x)+E(x)]/G(x)=E(x)/G(x)○CRC校验和验证接收者接收到T(X)后，用T(x)/G(x)，余数应该为0，否则就判定为有错误。T(X)=xrM(x)-P(x)如果E(x)不被G(x)除尽，则可以检测到传输过程中出错了，如果刚好被除尽了，则该错误没有被检测到。所以G(x)很重要。28基本数据链路协议（1）◆应用情况点到点信道，也就是只有一个发送者和接收者。◆几个重要功能函数□from_network_layer□to_network_layer□from_physical_layer□to_physical_layer29基本数据链路协议（2）◆无限制的单工协议□前提条件：◇单方向数据传输（即只有一个发送者和接收者）◇理想信道（信道不出错，传输速度极快）◇通信双方能力无穷（发送者不停发送，接收者不停接收）□发送者基本过程第一步：从网络层获得数据第二步：发送到物理层。□接收者基本过程第一步：等待数据到达第二步：从物理层提取数据第三步：把数据递交给网络层30基本数据链路协议（3）SENDER:from_network_layerframingto_physical_layerto_network_layerRECEIVER:wait_for_eventfrom_physical_layer31基本数据链路协议（4）◆什么是协议？通信双方关于如何进行通信的一种约定◆什么是服务？实体为它的用户提供的功能。如无限制单工协议规范双方的行为来完成数据的传输如数据链路层为网络层提供传输数据的功能如物理层为数据链路层提供0-1比特流传输功能◆什么是接口？定义调用服务的原语操作如from_physical_layer和to_physical_layer等□服务是用户的功能需求（该层要解决的问题）□协议是完成服务功能的实现过程（解决问题的程序）□接口是程序的交互界面（用户操作界面）32基本数据链路协议（5）◆无限制的单工协议分析现实问题：接收方的接收能力是有限制的。◆无限制的单工协议改进□问题分析：假设接收者处理一帧的时间是t，则希望发送者在t时间后，再发送下一帧。t如何确定？如何知道接收者的t？（很难估计）□解决办法：因为信道是理想信道，速度很快的，让接收者在处理完毕一帧后，反馈一个信息告诉发送继续发送数据（基于反馈的流控制机制）—单工停-等协议关键问题：如何避免大量数据淹没接收方？——流控制33基本数据链路协议（6）◆单工的停-等协议□前提条件：◇单方向数据传输（即只有一个发送者和接收者）◇理想信道（信道不出错，传输速度极快）◇接收者能力有限34ABf1ack□发送者基本过程第一步：从网络层获得数据第二步：发送到物理层第三步：等待对方的反馈第一步：等待数据到达第二步：从物理层提取数据第三步：把数据递交给网络层第四步：发送反馈帧□接收者基本过程基本数据链路协议（7）等待时间35基本数据链路协议（8）SENDER:from_network_layerframingto_physical_layerRECEIVER:wait_for_eventto_network_layerwait_for_eventfrom_physical_layerto_physical_layerWaitforacksendack36基本数据链路协议（9）◆