计算机网络数据链路层剖析

第三章数据链路层Q:为什么要设计数据链路层？设计“数据链路层”的主要目的就是在原始的、有差错的物理传输线路的基础上，采取差错检测、差错控制与流量控制等方法，将有差错的物理线路改进成逻辑上无差错的数据链路，以便向它的上一层—“网络层”提供高质量的服务。数据链路层可以屏蔽物理层中的不同。2Q：物理链路与逻辑链路（或称数据链路）的不同？物理链路是指在物理层设备和相应物理层通信规程作用下形成的；逻辑链路是指在数据链路层设备和相应的通信规程作用下建立的；是在“物理链路”基础上建立的。把实现数据传输规程(即通信协议)加到链路上，就构成了逻辑链路。二者的本质作用都是一样的，就是用来构建进行网络通信、访问的通道，只不过“物理层”构建的是一条物理通道，而“数据链路层”构建的是真正用于数据传输的逻辑通道。3它们之间的关系如下图所示。4电话交换网调制解调器计算机计算机物理线路数据链路调制解调器5•链路(link)是从一个结点到相邻结点的一段物理线路，中间没有任何其他的交换结点。（物理链路）–一条链路只是数据传输通路的一个组成部分。3.1数据链路层的功能物理层只负责比特流的接收和发送，而不考虑信息本身的意义，同时物理层也不能解决数据传输的控制，而这就是数据链路层所要解决的。因此，数据链路层的功能是实现系统实体之间二进制数据单元的正确传输，通过必要的同步控制、差错控制、流量控制，为其上层（网络层）提供可靠、无差错的数据信息。7数据链路层的主要功能（总结）(1)封装成帧：帧头和帧尾就是作为帧的起始和结束标志，也就是帧边界。(2)透明传输：其目的就是要实现“帧同步”，就是接收端能从收到的比特流中准确地识别“帧”的边界。(3)差错控制：在通信过程中能够自动检测出错误并进行纠正的方法；(4)流量控制：控制帧在物理信道上的传输；(5)数据链路管理：链路的建立、维持和释放管理。1.帧的封装2.透明传输--帧同步•在数据链路层中，数据的传输单位是帧。帧是具有一定长度的格式，每个帧除了要传送的数据外，还包括校验码，以使接收方能发现传输中的差错。•帧同步即接收端应当能从收到的比特流中准确地识别一个帧的开始和结束。•数据链路层常见的几种帧同步方法包括：字节计数法、字符填充的首尾定界符法、比特填充的首、尾定界符法、违例编码法。3.差错控制•为了将比特流在传输中的差错率控制在一定的范围之内，广泛地采用了各种编码技术。•编码技术可分为两类：–一类是向前纠错，当接收方收到出错的数据帧后，能够自动将错误修正过来。这种方法的系统开销大，不适合于计算机网络；–另一类是检错重传，即接收方检错到错误的帧后，就通知发送方重新发送该帧，直到收到正确的帧为止。这种方法的系统开销较小，通常应用于计算机网络中。•常用的差错控制技术有反馈检测、自动请求重发（ARQ）和前向纠错（FEC）。•1）反馈检测•反馈检测方法又称回送校验法。双方在进行数据传输时，接收方将接收到的数据重新发回发送方，由发送方检查是否与原始数据完全相符。如不相符，则发送方发送一个控制信息通知接收方删去出错的数据。并重新发送该数据；如相符，则发送下一个数据。•2）自动请求重发•自动请求重发（AutomaticRepeatrequest，ARQ），是计算机网络中较常采用的差错控制方法。•ARQ的原理：P52•特点：•3）前向纠错•前向纠错简称FEC（ForwardErrorCorrection）。•其原理是：发送方将要发送的数据附加上一定的冗余纠错码一并发送，接收方则根据纠错码对数据进行差错检测，如发现差错，由接收方进行纠正。4.流量控制•为防止接收端缓存能力不足而造成的阻塞和数据丢失，将数据高速、可靠地传输到接收方，发送端发送数据的速率必须使接收端来得及接收，当接收方来不及接收时，接收方必须及时控制发送方发送数据的速率，这就是流量控制功能。•概括地讲，流量控制就是使发送方和接收方的数据处理速率保持一致。•数据链路层常用的流量控制方法有：停等协议和滑动窗口机制，将在介绍ARQ协议时再重点介绍。•5.数据链路管理•当网络中的两个节点间要进行通信时，数据的发送方必须知道接收方是否处于准备接收状态。为此，在传输数据之前通信双方必须事先交换一些必要的信息，让通信双方做好数据发送和接收的准备。同样，在传输数据时要维持数据链路，而在通信完毕时要释放数据。•数据链路的建立、维持和释放就叫做链路管理。3.2差错控制3.2.1传输差错的特性当数据从信源出发，经过通信信道时，由于通信信道总是有一定的噪声存在，因此在到达信宿时，接收信号是信号与噪声的叠加。在接收端，接收电路在取样时判断信号电平。如果噪声对信号叠加的结果判断出现错误，就会引起传输数据的错误。我们把通过通信信道后接收数据与发送数据不一致的现象称为传输差错。比特在传输过程中可能会产生差错，1可能会变成0而0也可能变成1--比特差错。差错的类型：•通信信道的噪声分为热噪声和冲击噪声两种。由这两种噪声分别产生两种——随机差错和突发差错。•热噪声是由传输介质导体的电子热运动产生的，它的特点是时刻存在，幅度较小且强度与频率无关，但频谱很宽，是一类随机噪声。由热噪声引起的差错称为随机差错。此类差错的特点是差错是孤立的，在计算机网络应用中是极个别的。•与热噪声相比，冲击噪声幅度较大，是引起传输差错的主要原因。冲击噪声的持续时间要比数据传输中的每比特发送时间要长，因而冲击噪声会引起相邻多个数据位出错。冲击噪声引起的传输差错称为突发差错。•计算机网络中的差错主要是突发差错。18•差错产生的原因？P47误码率是衡量一个信道质量的重要参数。是在一段时间内，传输错误的比特占所传输比特总数的比率。在数值上近似等于：Pe=Ne/N；其中：N为传输的二进制比特总数，Ne为被传错的比特数。3.2.2常用的简单差错控制编码为了保证数据传输的可靠性，在计算机网络传输数据时，必须采用各种差错检测措施来减少误码率。差错控制编码的原理是：发送方对准备传输的数据进行抗干扰编码，即按某种算法附加上一定的冗余位，构成一个码字后再发送。接收方收到数据后进行校验，即检查信息位和附加的冗余位之间的关系，以检查传输过程中是否有差错发生。差错控制编码分检错码和纠错码两种，检错码是能自动发现差错的编码，纠错码是不仅能发现差错而且能自动纠正差错的编码。常用的差错控制编码方法主要有奇偶校验、海明码、循环冗余检错。3.2.3海明码自主学习•1950年，海明发明了从待发送的数据位中生成一定数量的特殊码字，并发明了通过此特殊码字来检测和纠正差错代码的理论和方法。按照海明的方法，要求在比特串发送前插入多个奇偶校验位，奇偶校验位校验在关键位置上的奇偶性的思想是如果比特位改变了，它们的位置将决定一个特定的奇偶校验错误组合。比特串被发送后，接收方就可以将这些在传输中出现错误的比特位纠正到正确的值。海明码在内存寻址及RAM与寄存器之间传送比特时非常有用。3.2.4循环冗余码重点掌握•目前在数据链路层广泛使用循环冗余检验码（即CRC码）的检错码编码方法之一，简称循环码。•CRC是一种被广泛采用的多项式编码，具有良好的数学结构，易于实现，具有较强的检错能力，特别适合于检测突发性的错误。•CRC的工作方法是在发送端产生一个冗余码，附加在信息位后面一起发送到接收端，接收端收到的信息按发送端形成循环冗余码同样的算法进行校验，如果发现错误，则通知发送端重发。任何一个由二进制数位串组成的代码，都可以唯一的与一个只含有0和1两个系数的多项式建立一一对应的关系。22•CRC码字由两部分组成，前一部分是k个比特的待发送信息码，固定不变的，后一部分是n个比特的冗余码。•Q：如何得出n个比特的冗余码？冗余码的计算方法是，先将信息码后面补0，补0的个数是生成多项式的最高次幂n；将补零之后的信息码除以G(X），注意除法过程中所用的减法是模2减法，即没有借位的减法，也就是异或运算。当被除数逐位除完时，得到比除数少一位的余数。此余数即为冗余位（冗余码），将其添加在信息位后便构成CRC码字。23循环冗余检验CRC的原理•在发送端，先把数据划分为组。假定每组k个比特。•假设待传送的一组数据M=101001（现在k=6）。那么在M的后面再添加供差错检测用的n位冗余码一起发送。•计算n位的冗余码。24冗余码的计算•实际的CRC校验码生成是采用二进制模2运算，是一种异或运算（相同为0，不同为1）；•将发送数据比特序列左移n位以放入余数，这相当于在M后面添加n个0。•得到的(k+n)位的CRC码字除以事先选定好的长度为(n+1)位的除数P，得出商是Q而余数是R，即R为n位的冗余码。（余数R比除数P少1位，所以R是n位。）•实例：见下页25冗余码的计算实例•现在k=6,M=101001。•设n=3,除数P=1101，•被除数是101001000—左移3位，用0填充。•模2运算的结果是：商Q=110101，余数R=001。•把余数R作为冗余码添加在数据M的后面发送出去。发送的数据是：2nM+R即：101001001，共(k+n)位。26循环冗余检验的原理说明110101←Q(商)P(除数)→1101101001000←2nM(被除数)11011110110101110000111011010110000011001101001←R(余数)，作为FCS说明：做题过程中要有此计算过程。27接收端对收到的每一帧进行CRC检验•(1)若得出的余数R=0，则判定这个帧没有差错，就接受(accept)。•(2)若余数R0，则判定这个帧有差错，就丢弃。•CRC的特点：P50•但这种差错校验方法并不能确定究竟是哪一个或哪几个比特出现了差错。数据链路层用于实现差错控制和流量控制的协议有：停等协议、连续ARQ协议和选择重传协议。3.3.1停等协议停等协议是最基本也是最简单的差错控制和流量控制协议。采用了有效的检错重传机制。它只允许每次传一帧的信息，然后就停止等待对方回应，当接收到确认帧ACK后，再发送下一帧。如果收到否认帧或是没有收到任何确认帧，就采取超时重发的措施。3.3数据链路协议停止等待协议（单帧）(b)超时重传(a)无差错情况A发送M1确认M1B发送M2发送M3确认M2确认M3tt超时重传M1丢弃有差错的报文A发送M1B发送M2确认M1tt确认丢失和确认迟到A发送M1B超时重传M1发送M2丢弃重复的M1重传确认M1(a)确认丢失确认M1A发送M1B超时重传M1发送M2丢弃重复的M1重传确认M1(b)确认迟到确认M1收下迟到的确认但什么也不做tttt请注意•保留副本：在发送完一个分组后，必须暂时保留已发送的分组的副本。•编号：分组和确认分组都必须进行编号。•设置超时计时器，它的重传时间设置应当比数据在分组传输的平均往返时间更长一些。3.3.2连续ARQ协议（多帧）指发送端可以连续发送一系列数据帧（具体可以连续发送多少个帧，要视双方的缓存空间大小（也即“窗口大小”）而定），效率大大提高。当然，在这个连续发送的过程中也可以接收来自接收端的响应消息（可以是确认帧，也可能是否认帧），发送端同样可以对传输出错的数据帧（如接收端返回了否认帧的帧，或者响应计时器超时的帧）进行重发。3.3.2连续ARQ协议（多帧）自动请求重传ARQ的原理：P54应注意的四点：连续ARQ协议的工作原理连续ARQ协议(窗口机制)123456789101112(a)发送方维持发送窗口（发送窗口是5）发送窗口(b)收到一个确认后发送窗口向前滑动向前123456789101112发送窗口•发送窗口•发送窗口用来对发送端进行流量控制。流量控制是通过窗口的大小WT来限制的，表示在还没有收到对方确认信息的情况下发送端最多可以发送多少个数据帧。显然，停等协议的发送窗口大小为1。•接收窗口•接收端设置接收窗口，在接收端只有当收到的数据帧的发送序号落入接收窗口内才允许将该数据帧收下。若接收到的数据帧落在接收窗口之外，则一律将其丢弃。在连续ARQ协议中，接收窗口的大小WR＝1。只有当收到的帧的序号与接收窗口一致时才能接收该帧。否则，就丢弃。每收到一个序号正确