计算机网络 第四章：数据链路层

第4章数据链路层计算机科学与技术学院1本章学习要求：了解：数据传输过程中差错产生的原因与性质掌握：误码率的定义与差错控制方法掌握：数据链路层的基本概念了解：面向字符型数据链路层协议实例—BSC掌握：面向比特型数据链路层协议实例—HDLC掌握：Internet中的数据链路层协议计算机科学与技术学院2本章知识点：差错产生与差错控制方法数据链路层的基本概念典型的数据链路层协议Internet中的数据链路层协议PPP协议面向字符型协议实例：BSC面向比特型协议实例：HDLC计算机科学与技术学院34.1差错产生与差错控制方法4.1.1为什么要设计数据链路层4.1.2差错产生的原因和差错类型4.1.3误码率的定义4.1.4检错码与纠错码4.1.5循环冗余编码工作原理4.1.6差错控制机制计算机科学与技术学院44.1.1为什么要设计数据链路层在原始物理传输线路上传输数据信号是有差错的；(语音、视频信号的失真)设计数据链路层的主要目的：在原始的、有差错的物理传输线路的基础上，将有差错的物理线路改进成无差错的数据链路；方法一差错检测差错控制流量控制作用：改善数据传输质量，向网络层提供高质量的服务。在OSI模型中，物理层以上的各层都有改善数据传输质量的责任，但数据链路层是最重要的一层。计算机科学与技术学院5数据链路层设计思想计算机科学与技术学院64.1.2差错产生的原因和差错类型传输差错（简称差错）通过通信信道后接收的数据与发送数据不一致的现象。差错控制：检查是否出现差错以及如何纠正差错；通信信道的噪声分为两类：热噪声和冲击噪声；由热噪声引起的差错是随机差错，或随机错；冲击噪声引起的差错是突发差错，或突发错；引起突发差错的位长称为突发长度；在通信过程中产生的传输差错，是由随机差错与突发差错共同构成的。计算机科学与技术学院7传输差错产生过程计算机科学与技术学院信源通信信道信宿数据噪声数据+噪声(a)001100111100011111000011000100010110011001010传输数据噪声数据信号与噪声信号叠加后的波形采样时间接收数据原始数据出错的位(b)84.1.3误码率的定义误码率定义：二进制比特在数据传输系统中被传错的概率，它在数值上近似等于：Pe=Ne/N其中，N为传输的二进制比特总数Ne为被传错的比特数计算机科学与技术学院9讨论误码率应该是衡量数据传输系统正常工作状态下传输可靠性的参数；对于一个实际的数据传输系统，IEEE802.3标准为千兆以太网制定的可接受的最高限度误码率为10-10。这个误码率标准是针对脉冲振幅调制(PAM-5)编码而设定的,是千兆以太网的编码方式；对于实际数据传输系统，如果传输的不是二进制比特，要折合成二进制比特来计算；差错的出现具有随机性，在实际测量一个数据传输系统时，只有被测量的传输二进制比特数越大，才会越接近于真正的误码率值。计算机科学与技术学院104.1.4检错码与纠错码纠错码：(海明码）它是利用在信息位为k位，增加r位冗余位，构成一个n=k+r位的码字每个传输的分组带上足够的冗余信息；接收端能发现并自动纠正传输差错。检错码:（奇偶校验码，CRC）分组仅包含足以使接收端发现差错的冗余信息；接收端能发现出错，但不能确定哪一比特是错的，并且自己不能纠正传输差错。计算机科学与技术学院11常用的检错码奇偶校检码垂直奇（偶）校验水平奇（偶）校验水平垂直奇（偶）校验（方阵码）循环冗余编码CRC目前应用最广的检错码编码方法之一奇偶校检码110011000001111110010011100100100101001001011水平偶校验00010100垂直偶校验计算机科学与技术学院124.1.5循环冗余编码工作原理计算机科学与技术学院发送数据f(x)生成多项式G(x)f(x)xk.G(x)=Q(x)+R(x)G(x)实际发送:f(x)xk.+R(x)f(x)xk.R(x)发送数据f'(x)生成多项式G(x)R'(x)=R(x)接收正确R'(x)≠R(x)接收错误发送f'(x)xk.G(x)=Q(x)+R'(x)G(x)+数据字段校验字段发送方接收方计算机网络13CRC校验码的编码方法是用待发送的二进制数据f(x)除以生成多项式g(x)，将最后的余数R(x)作为CRC校验码。计算机科学与技术学院举例：传送数据：110011110011发送数据比特序列CRC校验码比特序列1001带CRC校验码的发送数据比特序列1100111001110011100111001110010100001110011000011001G(x)1100110000110011001R(x)100001Q(x)f(x).xk14标准CRC生成多项式G（x）CRC-12CRC-16CRC-CCITTCRC-32G（x）=x12+x11+x3+x2+x+1G（x）=x16+x15+x2+1G（x）=x16+x12+x5+1G（x）=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1计算机科学与技术学院15CRC校验码的检错能力•CRC校验码能检查出全部单个错；•CRC校验码能检查出全部离散的二位错；•CRC校验码能检查出全部奇数个错；•CRC校验码能检查出全部长度小于或等于K位的突发错；•CRC校验码能以[1-(1/2)K-1]的概率检查出长度为（K+1）位的突发错；•如果K=16，则该CRC校验码能全部检查出小于或等于16位的所有的突发差错，并能以1-(1/2)16-1=99.997％的概率检查出长度为17位的突发错，漏检概率为0.003%；计算机科学与技术学院164.1.6差错控制机制反馈重发机制计算机科学与技术学院发送端信源校验码编码器存储器发送装置反馈信号控制器接收装置校验码译码器信宿反馈信号控制器接收端传输信道17反馈重发机制的分类停止等待方式和连续工作方式。1.停止等待方式计算机科学与技术学院接收端发送端ACKNAKACK12231223184.1.6差错控制机制停等协议(ARQ-自动重发请求)计算机科学与技术学院192.连续工作方式拉回方式(GBN，后退N)计算机科学与技术学院发送端接收端ACK0ACK1NAKACK2ACK3(a)ACK0ACK1NAKACK2ACK6(b)ACK3ACK4ACK5丢弃重传重传01234523456012345234560123452678901234526789发送端接收端丢弃选择重发方式20为什么提出滑动窗口协议在使用连续ARQ方法时，如果发送端一直没有收到对方的确认信息，那么发送端就不能无限制地向接收方发送其数据帧。因为：（1）接收端可能忙或者出现故障。（2）当未被确认的数据帧的数目太多时，只要有一帧出了差错，就要将很多的数据帧进行重传，这必然要白白花费很多时间。（3）为了对所发送出去的大量数据帧进行编号，每个数据帧的发送序号也要占用较多的比特数，这样又增加了一些不必要的开销。计算机科学与技术学院22滑动窗口协议所要解决的问题在发送端和接收端分别设发送窗口和接收窗口。发送窗口——用来对发送端进行流量控制，而发送窗口的大小WT代表在还没有收到对方确认的条件下发送端最多可以发送多少个数据帧。显然，停止等待协议的发送窗口大小是1。接收窗口——为了在接收端控制哪些数据帧可以接收而哪些帧不可以接收。在接收端只有当收到的数据帧的发送序号落入接收窗口WR内才允许将该数据帧收下。若接收到的数据帧落在接收窗口之外，则一律将其丢弃。计算机科学与技术学院23发送窗口的滑动过程接收窗口的滑动过程计算机科学与技术学院24发送窗口的最大值初看起来，这个问题好像很简单。例如，用3个比特可编出8个不同的序号，因而发送窗口的最大值似乎应当是8，其实不然。可以证明，当用n个比特进行编号时，只有在发送窗口的大小WT≤2n－1（WR＝1）时，连续ARQ协议才能正确运行。实际上，发送窗口和接收窗口的值需满足：WT＋WR≤2n。用3个比特可以编出8个不同的序号，这对一般的陆地链路已足够大了。但对于卫星链路，由于其传播时延很大，发送窗口也必须适当增大才能使信道利用率不致太低。这时常取编码n=7，因而发送窗口可达127。计算机科学与技术学院25举例：假设发送窗口尺寸为2，接收窗口尺寸为1计算机科学与技术学院264.2数据链路层的基本概念4.2.1物理线路与数据链路链路(link)：一个结点到相邻结点的一段物理线路，中间没有任何交换结点。在进行数据通信时，两个计算机之间的通路可能是由许多条链路串接而成的。数据链路(datalink)：除了必须有一条物理线路外，还必须有一些必要的规程来控制这些数据的传输。把实现这些规程的硬件和软件加到链路上，就构成了数据链路。计算机科学与技术学院电话交换网Modem计算机计算机物理线路数据链路Modem27数据链路层的简单模型计算机科学与技术学院28数据链路层传送的是帧计算机科学与技术学院29数据链路层像个数字管道常常在两个对等的数据链路层之间画出一个数字管道，而在这条数字管道上传输的数据单位是帧（Frame）。计算机科学与技术学院30早期的数据通信协议曾叫作通信规程(procedure)。因此在数据链路层，规程和协议是同义语。4.2.2数据链路层的主要功能链路管理帧同步流量控制差错控制帧的透明传输寻址数据链路层协议—为实现数据链路控制功能而制定的规程或协议。计算机科学与技术学院31（1）链路管理当网络中的两个结点要进行通信时，数据的发送方必须确知接收方是否已经处在准备接收的状态。为此，通信的双方必须先要交换一些必要的信息。也就是说有三个工作要做：1.建立一条数据链路2.维持这条数据链路3.释放这条数据链路数据链路的建立、维持和释放就叫做链路管理。计算机科学与技术学院324.2.2数据链路层的主要功能（2）组帧在用数据链路传送信息时，为了便于计算机进行处理，将从物理层来的原始位流进行分割，按照一定的格式组成若干个“帧”（Frame），以帧为单位进行传送。帧中应包括帧的内容：起始、结束标志;地址信息;控制信息;正文信息和差错控制信息;帧编号帧同步指的是接收端能从接到的比特流中正确地判断出一帧的起始位和结束标志。计算机科学与技术学院334.2.2数据链路层的主要功能封装成帧封装成帧(framing)就是在一段数据的前后分别添加首部和尾部，然后就构成了一个帧。确定帧的界限。首部和尾部的一个重要作用就是进行帧定界。计算机科学与技术学院34（3）差错控制在计算机通信中，要求有极低的比特差错率。为此，广泛地采用了编码技术。纠错技术有两大类：前向纠错FEC(ForwardErrorCorrection)方式，即接收方收到有差错的数据帧时，能够自动将差错改正过来。这种方法的编、译码开销太大，一般不适合于网络通信。反馈重传ARQ(AutomaticRequestforrepeat)方式，即接收方可以检测出收到的帧中有差错（但并不知道是哪几个比特错了），于是就让发送方重新发送这一帧，直到接收方正确收到这一帧为止。这种方法在计算机通信中是最常用的。计算机科学与技术学院354.2.2数据链路层的主要功能（续）（4）透明传输所谓透明传输就是不管所传数据是什么样的比特组合，都应当能够在链路上传送。当所传数据中的比特组合恰巧与某一个控制信息完全一样时，就必须采取适当的措施，使接收方不会将这样的数据误认为是某种控制信息。这样才能保证数据传输是透明的。例如：ETX(endoftext)正文结束字符，01111110比特组合。计算机科学与技术学院364.2.2数据链路层的主要功能（续）透明传输(文本)计算机科学与技术学院374.2.2数据链路层的主要功能（续）解决透明传输问题发送端的数据链路层在数据中出现控制字符“SOH”或“EOT”的前面插入一个转义字符“ESC”(其十六进制编码是1B)或“DEL”。这种方法称为字节填充(bytestuffing)或字符填充(characterstuffing)，接收端的数据链路层在将数据送往网络层之前删除插入的转义