计算机通信网之数据链路层

[e-mail]1数据链路层第三章[e-mail]2主要内容3.1数据链路层设计要点3.2错误检测和纠正3.3基本数据链路层协议3.4滑窗协议3.5协议验证3.6数据链路层协议示例[e-mail]33.1数据链路层的设计要点为网络层提供的服务成帧差错控制流量控制[e-mail]4链路层基本功能向网络层提供一个服务接口处理传输错误调节数据流（流控）[e-mail]5分组与帧之间的关系[e-mail]6虚拟通信和实际通信(a)虚拟通信.(b)实际通信[e-mail]7数据链路层提供的服务无确认的无连接服务用于低误码率链路或对误码不敏感的业务.(fiber,utp,real-time)有确认的无连接服务用于高误码率链路(Wireless)有确认的面向连接的服务保证每个帧真正接收到且只接收一次。为网络层进程提供一个可靠的位流。[e-mail]8例子数据链路协议的位置[e-mail]9DLL将原始码流分解为离散的单元，该单元称为帧。那么接收端如何检测帧的边界呢？或者说接收端如何界定帧的开始和结束呢？讨论4种方法：•字符计数法•含字节填充的分界符法•含位填充的分界标志法•编码违例成帧[e-mail]10字符计数法一个字符流(a)无差错.(b)有一个差错[e-mail]11字符填充(a)有标志字节作为分界的帧.(b)字节填充前后的4个字节序列例子[e-mail]12比特填充Bit填充，标记01111110(a)原始数据.(b)线路上的数据.(c)删除填充后存储在接收方存储器中的数据[e-mail]13编码违例适用于“物理介质上的编码方法中包含冗余信息”的网络。例如有些LAN用2个物理位来编码1位数据。“1”位是“高-低”电平对，“0”位是“低-高”电平对。而“高高”“低低”电平对不用于数据，则可用于帧定界。优点是没有额外带宽开销[e-mail]14•为了保证所有的帧最终传送到（有可能顺序的）目的端，需要三个部件。Acknowledgments,Timers,SequenceNumbersAcknowledgments:•当接收端正确接收一个帧，它会向发送端返回一个ACK帧用于指示发端该帧已正确接收。•在某些系统，如果接收的帧不正确，接收端会发端返回一个NACK（NegativeACK）用于指示该帧没有正确接收.•提示发端不用等待定时器超时就立即发送（重传）一个帧.错误控制[e-mail]15Timers:•如果没有定时器，当帧丢失或者ACK/NACK丢失，会出现什么情况？•定时器怎么工作呢？当发送一个帧的时候，发端开启一个定时器，当在约定的时间内，发端接收到ACK/NACK，则立即发送（重发）一个帧，且重置定时器，否则当定时超时时，重发该帧。SequenceNumbers:•主要解决接收端接收到重复帧的问题.•为了避免接收重复帧的问题，给发送的帧分配序列号，这样接收端就能够区分原始帧和重传帧。[e-mail]16流控流控主要是处理发端与接收端之间速率匹配的问题。通常，流控是个动态的过程，取决于负载强度、接收端缓存大小等，常用的方法：基于反馈的流控制基于速率的流控制（从来没有用于DDL）[e-mail]173.2错误检测和纠正纠错码检错码[e-mail]18错误•数据通信中，链路噪声无处不在，并且研究发现，链路噪声引起的比特错误通常是突发性的，而不是独立的，单比特错误，例如：闪电会引起短暂的突发比特错误。[e-mail]19纠错码检测和纠正数据中的错误冗余（redundancy）-在数据中加入附加的信息。两种策略：检错码:包含足够的冗余比特检错，然后使用NACK告知发端重传。纠错码:包含足够的冗余比特检测和纠正错误。[e-mail]20海明距离给定两个码子，对其进行异或运算，然后计算出异或结果中1的个数，两个码子中不相同的位的个数称为海明距离.它的意义在于：如果两个码子的海明距离为d，则需要d个1位错误才能将一个码子转变成另一个码子。[e-mail]21海明距离通常，所有2m种可能的数据报文都是合法的，但是并非所有的2n（n=m+r；m为数据位，r为冗余位）种码子都被用到。给定计算校验位的算法后，可以构造合法码子列表，并且可以从该表中找到海明距离最小的两个码子，此距离是整个编码方案的海明距离。为了检测d个错误，需要一个距离为d+1的编码方案为了纠正t个错误，需要一个距离为2t+1的编码方案[e-mail]22奇偶位保证码子中“1”位的数目是偶数（或者奇数）。.1000000(1)1111101(0)奇偶位的海明距离为2，因此它可以检测单比特错误，但是不能纠错考虑以下的例子，4个有效码子的编码：0000000000,0000011111,1111100000,and1111111111.编码距离为5,可以纠正2个错误。[e-mail]23纠错设计一种编码方案，每个码子有m个报文位和r个校验位，并且能够纠正所有的单个错误。对于2m合法报文，任一个报文都对应有n个非法的码子，它们与该报文的距离为1。因此每个合法的报文都要求n+1个位模式供他使用。由于总共有2n个位模式，所以有(n+1)*2m2n,利用n=m+r,有：(m+r+1)2r，给定m的情况下，这个条件给出了用于纠正单个错误所需要的校验位数目的下界例如m=10，[e-mail]24检错码纠错码代价很大（计算量和带宽），因此用在无线通信较为合适，但是在铜线或者光缆，错误检测和重传机制往往更加有效。例如，若误码是独立的，误码率为10-6。则对于1000bit的数据块，需要10个校验位纠正1个单bit错误，1Mbit的需要10Kbit，显然如果仅仅检测错误，每个数据块1个奇偶位就足够了，每一千个数据块额外传输一个块，因此开销小，利用检错/重传机制，则1Mbit只需2001位，相比之下，海明码需要10000位。最广泛使用的检错码是多项式编码，也称CRC。[e-mail]25CyclicRedundancyCheck基本思想：将位串看成系数为0或1的多项式。多项式的算术运算以2为模完成，加减法等同于异或，除法为长除运算。生成多项式G(x)：事先约定的，最低位，最高位必须是1。校验和：添加到帧序列多项式中，用于检测传输是否有错误。[e-mail]26CyclicRedundancyCheck校验和的计算方法：(1)假设G(x)的阶为r。在帧的低位端加上r个0位，所以该帧现在包含m+r位。对应的多项式为xrM(x)。(2)利用模2除法，用对应于G(x)的位串去除xrM(x)的位串。(3)利用模2减法，从对应于xrM(x)的位串中减去余数，结果就是将被传输的带校验和的帧，记为：T(x)。[e-mail]27CyclicRedundancyCheck校验和的计算过程[e-mail]28CyclicRedundancyCheck分析：1.所有的错误都能检测出吗？错误多项式E(x)能被G(x)除尽，则这类错误无法被检测。2.所有的一位错误都将被检测到。低阶的多项式可以保护长的帧（K=i–j,两个独立的一位错误）奇数项多项式不可能被x+1除尽(奇数个位发生错误)。带r个校验位的多项式编码可以检测到所有长度小于等于r的突发性错误。[e-mail]29CyclicRedundancyCheck通常用到的3种CRC生成多项式：CRC-16=x16+x15+x2+1(usedinHDLC)CRC-CCITT=x16+x12+x5+1CRC-32=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x1+1(usedinEthernet)尽管复杂，可以用硬件构造出来[e-mail]303.3基本数据链路协议一个无限制的单工协议一个单工的停—等协议有噪声信道的单工协议[e-mail]31基本数据链路协议几个假设：•物理层、数据链路层和网络层都是独立的进程，它们通过报文来相互通信。•可靠的、面向连接的服务•机器不会崩溃[e-mail]32协议定义Continued协议中需要用到的一些定义。这些定义包含在头文件protocol.h中[e-mail]33协议定义(ctd.)协议中需要用到的一些定义。这些定义包含在头文件protocol.h中[e-mail]34无限制的单工协议假设条件:数据单向传输物理信道无误码，即无帧损坏或丢失发/接收端缓存无限大发端/收端的网络层总是处于准备就绪状态[e-mail]35无限制的单工协议[e-mail]36一个单工的停/等协议假设:不再假设收端能够无限快速的处理到来的数据.基本思想和特点发端发送一个帧，然后等待确认(stopandwait.)确认帧的内容并不重要数据传输是单向的，但是必须是双向链路，因此用一个半双工的物理信道就足够了[e-mail]37单工的等/停协议[e-mail]38有噪声信道的单工协议假设:信道有噪声，因此可能会丢/损坏帧简单的方法:发端设置一个定时器，如果在规定的时间内没有接收到ACK，则重发该帧.这种方法有没有问题？[e-mail]39有噪声信道的单工协议考虑下面的场景：A传输一个帧B接收到A传来的帧A1B产生ACKACK丢失A定时器超时,重传B得到A1的副本(将会把副本送到网络层.)(另外一种出现副本的情况是长的时延)使用序列号在这个例子里，1bit就够了。在协议中，发送方在准备下一个数据项目之前先等待一个肯定的确认，则这样的协议称为（PositiveAcknowledgmentwithRetransmission(PAR)/AutomaticRepeatreQuest(ARQ)）[e-mail]40有噪声信道的单工协议一个支持重传的肯定确认协议Continued[e-mail]41有噪声信道的单工协议一个支持重传的肯定确认协议[e-mail]423.4滑窗协议用于双向通信使用同一条线路来传输两个方向上的数据反向信道与前向信道有相同的容量.有两种类型的帧(kindfield):数据（Data）ACK(含有最新接收帧的序号)[e-mail]43捎带确认（Piggybacking）Piggybacking–确认信息附在往外（反向链路）发送的数据帧上的行为。优点:更好的利用信道带宽。问题:为了更好的利用带宽，数据链路层应该等待下一个分组多长时间?[e-mail]44滑窗协议每个外发的帧都包含一个序列号，其范围为0~MaxSeq(2n–1).这样的序列号正好可以填到一个n位的域中。等-停滑动窗口协议使用n=1。滑窗协议的本质：在任何时刻，发送方总是维持着一组序列号，分别对应于允许它发送的帧。称这些帧落在发送窗口内，接受方也维持一个接收窗口，对应一组允许他接收的帧。窗口大小可以固定或者不固定。[e-mail]45滑窗协议(2)滑窗大小为1，有3个序列号的滑动窗口(a)初始化(b)第1帧发送以后(c)第1帧接