计算机网络：第4章 数据链路层 (课件)

数据链路层数据链路层及其协议链路与数据链路

链路就是一条无源的点到点的物理线路段，中间没有任何其他的交换节点。数据链路则是另一个概念。这是因为当需要在一条线路上传输数据时，除了必须有一条物理线路外，还必须有一些必要的规程来控制这些数据的传输。把实现这些规程的硬件和软件加到链路上，就构成了数据链路。数据链路层要解决的问题如何在有差错的线路上，进行无差错传输。ISO关于数据链路层的定义数据链路层的目的是为了提供功能上和规程上的方法，以便建立、维护和释放网络实体间的数据链路。数据链路从数据发送点到数据接收点（点到点pointtopoint）所经过的传输途径。虚拟数据通路，实际数据通路数据链路层提供的服务

为网络层提供三种合理的服务无确认无连接服务，适用于误码率很低的线路，错误恢复留给高层；实时业务大部分局域网有确认无连接服务，适用于不可靠的信道，如无线网。有确认有连接服务数据链路层的功能数据链路层提供相邻设备间的无差错数据传输。它要完成如下功能：链路管理帧同步流量控制差错控制帧的透明传输寻址

数据链路层协议—为实现数据链路控制功能而制定的规程或协议。数据链路层协议的类型面向字符型数据链路层协议：BSC面向比特型数据链路层协议：HDLC面向字符型数据链路层协议：BSC以字符为控制传输信息的基本单元。常见的通信控制字符：格式字符：SOH（startofheading）STX（startoftext）ETB（endoftransmissionblock）ETX（endoftext）控制字符：ACK（acknowledge）NAK（negativeacknowledge）ENQ（enquire）EOT（endoftransmission）SYN（synchrous）DLE（datalinkescape）面向字符型BSC协议的帧格式面向比特型数据链路层协议：HDLC以比特作为传输控制信息的基本单元；数据帧与控制帧格式相同；传输透明性好；连续发送，传输效率高。面向比特型HDLC协议的帧格式将比特流分成离散的帧，并计算每个帧的校验和。物理层以比特为单位进行数据传输，数据链路层以帧为单位进行数据传输。帧是具有一定长度和格式的信息块，一般由一些字段和标志组成。不同网络其帧格式或长度可以不同，但将比特流分成帧的方法基本相同。四种常用的方法为：字符计数法；带填充字符的首尾界符法；带填充位的首尾标志法；物理层编码违例法。把比特流分成帧，标定帧的起始和结束，以利于进行差错控制。在数据链路层，数据的传送单位是帧。数据一帧一帧地传送，就可以在出现差错时，将有差错的帧重传一次，而避免将所有数据重传，从而实现差错控制。成帧（Framing）成帧方法：字符计数法（Fig.3-3）在帧头中用一个域来表示整个帧的字符个数缺点：若计数出错，对本帧和后面的帧有影响。带字符填充的首尾字符定界法（Fig.3-4）起始字符DLESTX，结束字符DLEETX字符填充 缺点：局限于8位字符和ASCII字符传送。带位填充的首尾标记定界法（Fig.3-5）帧的起始和结束都用一个特殊的位串“01111110”，称为标记(flag)“0”比特插入删除技术物理层编码违例法只适用于物理层编码有冗余的网络802LAN：ManchesterencodingorDifferentialManchesterencoding用high-lowpair/low-highpair表示1/0，high-high/low-low不表示数据，可以用来做定界符。采用0插入删除的方法来使得收发双发同步。零比特插入/删除工作过程流量控制

流量控制数据链路层必须控制链路上的数据流量，保证发送与接收速度匹配，防止出现发送速度超过接收能力的现象，以免丢失数据。大多数流量控制方法的基本原理都是相同的，都需要启用反馈机制，使发方直接或是间接地获得收方指示的发送时机。在未得到允许前，禁止发出帧。如单工停等协议、滑动窗口协议等。发方的发送速率必须小于等于收方的接收速率，否则会浪费网络资源，增加网络负担。流量控制就是对发方的发送速率进行控制。基本流量控制方法基于反馈的流控制接收方给发送方送回消息,告诉发送方它的状态基于速率的流控制限制了发送方传输数据的速率,无需利用接收方的反馈信息差错控制

差错控制一般方法：接收方给发送方一个反馈（响应）。比如自动重复请求（ARQ）出错情况帧（包括发送帧和响应帧）出错；帧（包括发送帧和响应帧）丢失通过计时器和序号保证每帧最终交给目的网络层仅一次是数据链路层的一个主要功能。差错出现的特点：随机，连续突发（burst）差错控制方法

从差错控制的角度，对于传输的信号，利用检纠错基本原理进行编码来降低差错的发生，利用差错控制编码方法进行差错控制的常用方式主要有如下几种：

自动请求重发（ARQ）方式

反馈校验方式

前向纠错（FEC）方式

混合纠错（HEC）方式自动请求重发（ARQ）方式

发送端发送出可以发现错误的码字，接收端译码若检测到错误，则主动向发送端发出请求，要求重发以便纠错。这种系统要求有反馈信道且发送端和接收端都有缓存器。反馈校验方式这种方式是发送端一边发送码字一边存贮发出的码字到缓冲区中。在接收端收到码字后，马上返回到发送端去与原发送码进行比较。如发现与发送码不同，就重发上一次的码字，直到发送端校验正确为止。这种方式进行差错控制的原理和设备都简单，但要求双向信道，且传输效率较低。前向纠错（FEC）方式发送端发出的码字是具有一定纠错能力的码字。在接收端译码后不仅可以发现错码，而且能够判断错码所在的位置并自动纠正。这种方法不需反馈信道，实时性好，传输效率较高，但纠错编码方法和设备较复杂。混合纠错（HEC）方式

实际应用中，可以结合使用ARQ方式和FEC方式。即在传输错码较少且接收端能纠正时，自动纠正错误；在错码较多、超出纠正能力但尚能检测时，采用自动请求重发方式，请求发送端重传，直到正确接收为止。该方式大大提高了通信的可靠性。差错控制方法处理差错的两种基本策略使用纠错码：发送方在每个数据块中加入足够的冗余信息，使得接收方能够判断接收到的数据是否有错，并能纠正错误。使用检错码：发送方在每个数据块中加入足够的冗余信息，使得接收方能够判断接收到的数据是否有错，但不能判断哪里有错奇偶校验码垂直奇（偶）校验水平奇（偶）校验水平垂直奇（偶）校验（方阵码）循环冗余编码CRC：目前应用最广的检错码编码方法之一海明码：是一种纠错码。纠错码码字（codeword）：一个帧包括m个数据位，r个校验位，n=m+r，则此n比特单元称为n位码字。海明距离（Hammingdistance）：两个码字之间不同的比特位数目。例：0000000000与0000011111的海明距离为5如果两个码字的海明距离为d，则需要d个单比特错就可以把一个码字转换成另一个码字；为了检查出d个错（单比特错），需要使用海明距离为d+1的编码；为了纠正d个错，需要使用海明距离为2d+1的编码；最简单的例子是奇偶校验，在数据后填加一个奇偶位（paritybit）例：使用偶校验（“1”的个数为偶数） 10110101 ——> 101101011 10110001 ——> 101100010奇偶校验可以用来检查单个错误。海明码设计纠错码要求：m个信息位，r个校验位，纠正单比特错； 利用n=m+r，得到(m+r+1)2r 给定m，利用该式可以得出校正单比特误码的校验位数目的下界海明码码位从左边开始编号，从“1”开始；位号为2的幂的位是校验位，其余是信息位；每个校验位使得包括自己在内的一些位的奇偶值为偶数（或奇数）。为看清数据位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）组成kn矩阵，按列发送，接收方恢复成kn矩阵kr个校验位，km个数据位，可纠正最多为k个的突发性连续比特错。12345678

910111111122222444888使用纠错码传数据，效率低，适用于不可能重传的场合；大多数情况采用检错码加重传。循环冗余码（CRC码，多项式编码）110001，表示成多项式x5+x4+1生成多项式G(x)发方、收方事前商定；生成多项式的高位和低位必须为1生成多项式必须比传输信息对应的多项式短。CRC码基本思想校验和（checksum）加在帧尾，使带校验和的帧的多项式能被G(x)除尽；收方接收时，用G(x)去除它，若有余数，则传输出错。检错码循环码的编码

第一步若生成多项式G(x)的阶是r,将信息位左移r位，得xrM(x)；第二步，作模2除法，求余数r(x)；余数由下式获得：第三步，根据T(x)=xrM(x)+r(x)，求出码字。

CRC的检错能力发送：T(x)；接收：T(x)+E(x)；余数((T(x)+E(x))/G(x))=0+余数(E(x)/G(x))若余数(E(x)/G(x))=0，则差错不能发现；否则，可以发现。如果只有单比特错，即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)整除(ki-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。 错误检测和纠正（8）四个多项式已成为国际标准CRC-12 =x12+x11+x3+x2+x+1CRC-16 =x16+x15+x2+1CRC-CCITT =x16+x12+x5+1CRC-32硬件实现CRC校验。CRC校验码的检错能力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%；

基本的数据链路层协议无约束单工协议（AnUnrestrictedSimplexProtocol）工作在理想情况，几个前提：单工传输发送方无休止工作（要发送的信息无限多）接收方无休止工作（缓冲区无限大）通信线路（信道）不损坏或丢失信息帧工作过程发送程序:取数据，构成帧，发送帧；接收程序：等待，接收帧，送数据给高层Fig.3-9单工停等协议（ASimplexStop-and-WaitProtocol）增加约束条件：接收方不能无休止接收。解决办法：接收方每收到一个帧后，给发送方回送一个响应。工作过程发送程序：取数据，成帧，发送帧，等待响应帧；接收程序：等待，接收帧，送数据给高层，回送响应帧。Fig.3-10有噪声信道的单工协议（ASimplexProtocolforaNoisyChannel）增加约束条件：信道（线路）有差错，信息帧可能损坏或丢失。解决办法：出错重传。带来的问题：什么时候重传——定时响应帧损坏怎么办（重复帧）——发送帧头中放入序号为了使帧头精简，序号取多少位——1位发方在发下一个帧之前等待一个肯定确认的协议叫做PAR（PositiveAcknowledgementwithRetransmission）或ARQ（AutomaticRepeatreQuest）自动重复请求（ARQ）

自动重复请求（ARQ）是应用最广泛的一种差错控制技术，包括:无错接收的PDU的肯定确认、对未确认PDU的自动重传和丢弃。接收方监测到数据中存在差错：发否认帧，立即启动重发；不理会，发送方超时重发停止—等待式ARQA方B方DATA(0，0)时间DATA(0，1)DATA(1，1)DATA(1，0)停等式ARQ捎带确认协议简单效率低效率是多少？滑动窗口大小发送窗口大小SWS

=1

接收窗口大小RWS=1

注意协议的漏洞由于确认帧中没有序号，超时时间不能太短，否则协议失败。因此假设协议的发送和接收严格交替进行。Fig.3-11的实现是正确的，确认帧有序号发送接收001ACKACK

滑动窗口协议单工——>全双工捎带/载答（piggybacking）：暂时延迟待发确认，以便附加在下一个待发数据帧的技术。优点：充分利用信道带宽，减少帧的数目意味着减少“帧到达”中断；带来的问题：复杂。本节的三个协议统称滑动窗口协议，都能在实际（非理想）环境下正常工作，区别仅在于效率、复杂性和对缓冲区的要求。滑动窗口协议（2）滑动窗口协议（SlidingWindowProtocol）工作原理：发送的信息帧都有一个序号，从0到某个最大值，0~2n-1，一般用n个二进制位表示；发送端始终保持一个已发送但尚未确认的帧的序号表，称为发送窗口。发送窗口的上界表示要发送的下一个帧的序号，下界表示未得到确认的帧的最小编号。发送窗口大小=上界（前指针）-下界（后指针），大小可变；发送端每发送一个帧，序号取上界值，上界加1；每接收到一个正确响应帧，下界加1；接收端有一个接收窗口，大小固定，但不一定与发送窗口相同。接收窗口的上界表示允许接收的序号最大的帧，下界表示希望接收的帧；接收窗口容纳允许接收的信息帧，落在窗口外的帧均被丢弃。序号等于下界的帧被正确接收，并产生一个响应帧，上界、下界都加1。接收窗口大小不变。前指针前指针后指针后指针发送窗口接收窗口窗口尺寸>1时的滑动窗口协议运行一比特滑动窗口协议（AOneBitSlidingWindowProtocol）协议特点窗口大小：N=1，发送序号和接收序号的取值范围：0，1；可进行数据双向传输，信息帧中可含有确认信息（piggybacking技术）；信息帧中包括两个序号域：发送序号和接收序号（已经正确收到的帧的序号）工作过程：Fig.3-13存在问题能保证无差错传输，但是基于停等方式；若双方同时开始发送，则会有一半重复帧；Fig.3-14效率低，传输时间长。退后n帧协议（AProtocolUsingGoBackn）为提高传输效率而设计例：卫星信道传输速率50kbps，往返传输延迟500ms，若传1000bit的帧，使用上面的协议，则传输一个帧所需时间为：发送时间+信息信道延迟+确认信道延迟（确认帧很短，忽略发送时间）=1000bit/50kbps+250ms+250ms=520ms信道利用率=20/5204%一般情况信道带宽b比特/秒，帧长度L比特，往返传输延迟R秒，则信道利用率为(L/b)/(L/b+R)=L/(L+Rb)结论传输延迟大，信道带宽高，帧短时，信道利用率低。解决办法连续发送多帧后再等待确认，称为流水线技术（pipelining）。带来的问题信道误码率高时，对损坏帧和非损坏帧的重传非常多两种基本方法退后n帧（gobackn）接收方从出错帧起丢弃所有后继帧；接收窗口为1；对于出错率较高的信道，浪费带宽。Fig.3-15(a)

选择重传（selectiverepeat）接收窗口大于1，先暂存出错帧的后继帧；只重传坏帧；对最高序号的帧进行确认；接收窗口较大时，需较大缓冲区。Fig.3-15(b)滑动窗口协议退后n帧协议发送方有流量控制，为重传设缓冲；发送窗口未满，EnableNetworkLayer发送窗口满，DisableNetworkLayer发送窗口大小<序号个数（MaxSeq+1）；考虑MaxSeq=7的情况1发送方发送帧0~7；2序号为7的帧的确认被捎带回发送方；3发送方发送另外8个帧，序号为0~7；4另一个对帧7的捎带确认返回。问题：第二次发送的8个帧成功了还是丢失了？退后n帧重发；由于有多个未确认帧，设多个计时器。 滑动窗口协议工作过程 Fig.3-16计时器实现 Fig.3-17滑动窗口协议协议实现分析事件驱动Network_layer_ready（内部事件）发送帧（帧序号，确认序号，数据）Frame_arrival（外部事件）检查帧序号，落在接收窗口内则接收，否则丢弃；检查确认序号，落在发送窗口内则移动发送窗口，否则不做处理。Cksum_err（外部事件）丢弃timeout（内部事件）退后n帧重传计时器处理启动，发送帧时启动停止，收到正确确认时停止超时则产生timeout事件滑动窗口协议选择重传协议（AProtocolUsingSelectiveRepeat）目的在不可靠信道上有效传输时，不会因重传而浪费信道资源，采用选择重传技术。基本原理发送窗口大小：MaxSeq，接收窗口大小：(MaxSeq+1)/2保证接收窗口前移后与原窗口没有重叠；设MaxSeq=7,若接收窗口=7，发方发帧0~6，收方全部收到，接收窗口前移（7~5），确认帧丢失，发方重传帧0，收方作为新帧接收，并对帧6确认，发方发新帧7~5，收方已收过帧0，丢弃新帧0，协议出错。Fig.3-19滑动窗口协议发送窗口下界：AckExpected，上界：NextFrameToSend接收窗口下界：FrameExpected，上界：TooFar缓冲区设置发送方和接收方的缓冲区大小应等于各自窗口大小；增加确认计时器，解决两个方向负载不平衡带来的阻塞问题；可随时发送否定性确认帧NAK。工作过程Fig.3-18滑动窗口协议协议实现分析事件驱动Network_layer_ready（内部事件）发送帧（帧类型，帧序号，确认序号，数据）Frame_arrival（外部事件）若是数据帧，则检查帧序号，落在接收窗口内则接收，否则丢弃；不等于接收窗口下界还要发NAK若是NAK，则选择重传；检查确认序号，落在发送窗口内则移动发送窗口，否则不做处理。Cksum_err（外部事件）发送NAKtimeout（内部事件）选择重传Ack_timeout（内部事件）发送确认帧ACK滑动窗口协议计时器处理启动，发送数据帧时启动停止，收到正确确认时停止超时则产生timeout事件Ack计时器处理启动，收到帧的序号等于接收窗口下界或已经发过NAK时启动停止，发送帧时停止超时则产生ack_timeout事件常用的数据链路层协议ISO和CCITT在数据链路层协议的标准制定方面做了大量工作，各大公司也形成了自己的标准。数据链路层协议分类面向字符的链路层协议ISO的IS1745，基本型传输控制规程及其扩充部分（BM和XBM）IBM的二进制同步通信规程（BSC）DEC的数字数据通信报文协议（DDCMP）PPP面向比特的链路层协议IBM的SNA使用的数据链路协议SDLC（SynchronousDataLinkControlprotocol）；ANSI修改SDLC，提出ADCCP（AdvancedDataCommunicationControlProcedure）；ISO修改SDLC，提出HDLC（High-levelDataLinkControl）；CCITT修改HDLC，提出LAP（LinkAccessProcedure）作为X.25网络接口标准的一部分，后来改为LAPB。高级数据链路控制规程HDLC1976年，ISO提出HDLC（High-levelDataLinkControl）HDLC的组成帧结构规程元素规程类型 使用HDLC的语法可以定义多种具有不同操作特点的链路层协议。HDLC的适用范围计算机——计算机计算机——终端终端——终端数据站（简称站station），由计算机和终端组成，负责发送和接收帧。HDLC涉及三种类型的站：主站（primarystation）：主要功能是发送命令（包括数据），接收响应，负责整个链路的控制（如系统的初始、流控、差错恢复等）；次站（secondarystation）：主要功能是接收命令，发送响应，配合主站完成链路的控制；组合站（combinedstation）：同时具有主、次站功能，既发送又接收命令和响应，并负责整个链路的控制。HDLC适用的链路构型非平衡型点—点式主站次站多点式适合把智能和半智能的终端连接到计算机。平衡型主站—次站式组合式适合于计算机和计算机之间的连接主站次站次站次站...主站主站次站次站逻辑通道组合站组合站HDLC的基本操作模式正规响应模式NRM（NormalResponseMode）适用于点—点式和多点式两种非平衡构型。只有当主站向次站发出探询后，次站才能获得传输帧的许可。异步响应模式ARM（AsynchronousResponseMode）适用于点—点式非平衡构型和主站—次站式平衡构型。次站可以随时传输帧，不必等待主站的探询。异步平衡模式ABM（AsynchronousBalancedMode）适用于通信双方都是组合站的平衡构型，也采用异步响应，双方具有同等能力。HDLC的帧结构

F（flag）：固定格式—01111110

作用—帧同步传输数据的透明性（零比特插入与删除）A（address）：地址多终端线路，用来区分终端；点到点线路，有时用来区分命令和响应。若帧中的地址是接收该帧的站的地址，则该帧是命令帧；若帧中的地址是发送该帧的站的地址，则该帧是响应帧。C（control）：帧的类型、帧的编号、命令与控制信息I（information）：网络层数据CRC（checksum）：校验A、C、I字段的数据G(X)=X16+X12+X5+1帧类型及控制字段的意义帧类型I帧：N（S）和N（S）为帧的序号：使用滑动窗口技术，3位序号，发送窗口大小为7N（S）—发送帧的顺序号

N（R）—接收帧的顺序号：捎带确认，捎带第一个未收到的帧序号，而不是最后一个已收到的帧序号探询/结束P/F位（Poll/Final）命令帧置“P”，响应帧置“F”。有些协议，P/F位用来强迫对方机器立刻发控制帧；多终端系统中，计算机置“P”，允许终端发送数据；终端发向计算机的帧中，最后一个帧置为“F”，其它置为“P”。

S帧：监控功能位

S=00，RR（receiveready）S=01，RNR（receivenotready）S=10，RJE（reject）S=11，SREJ（selectreject）U帧：用于实现数据链路控制功能U帧的格式与链路控制功能数据链路层的工作过程

简化的信息帧结构的表示方法一个信息帧的表示

无编号帧的表示方法

SNRM帧与UA帧结构的表示方法

正常响应模式数据链路工作X.25的链路层协议LAPB“X.25协议规程使用HDLC规程的原理和术语”X.25LAP：HDLC非平衡模式，也可组成主站—次站式平衡模式。X.25LAPB：HDLC组合站平衡模式。因此，X.25LAP、LAPB是HDLC的子集。X.25的帧格式与HDLC完全相同X.25链路级的命令和响应X.25LAPB的各种检错和纠错措施a帧格式上采用CRC校验，只检错，不纠错，丢弃出错帧；b设立超时机制，计时器超时重传，重传N次，则向上层协议报告。超时机制用来检错，重传用来纠错。c帧序号若接收方发现帧序号错，就发拒绝帧给发送方，发送方重传，既检错也纠错。d采用P/F位来进行校验指示发送置为P的命令帧，等待置为F的响应帧，能及时发现远程数据站是否收到命令帧。规程规定：a必须使用；b,c,d组合使用。Internet的数据链路层协议点到点通信的两种主要情形路由器到路由器（router-routerleasedlineconnection）通过modem拨号上网，连到路由器或接入服务器（AccessServer）（dial-uphost-routerconnection）Internet中主要的数据链路层协议SLIP（SerialLineIP）—串行线路的Internet数据链路层协议PPP（Point-to-PointProtocol）—点-点协议SLIP与PPP用于串行通信的拨号线路上，是目前家庭计算机或公司用户通过ISP接到Internet主要的协议。SLIP协议SLIP出现于20世纪80年代初，最早是在BSDUNIX4.2版操作系统上实现的;SLIP协议支持TCP/IP协议;对数据报进行了简单的封装，然后来用RS-232接口串行线路进行传输;SLIP通常也用来将远程终端连接到UNIX主机，也可通过租用或拨号串行线路进行主机到路由器，以及路由器到路由器的通信