计算机网络_CH03_数据链路层

第3章数据链路层,计算机网络ComputerNetworks,南京邮电大学计算机学院“计算机通信与网络”国家精品课程组,内容纲要,数据链路层的基本概念数据的可靠传输和流量控制差错控制点对点信道的数据链路层协议,内容纲要,数据链路层的基本概念数据的可靠传输和流量控制差错控制点对点信道的数据链路层协议,3.1数据链路层的基本概念,数据链路层在物理连接提供的比特流传输服务基础上，构成透明的、相对无差错的数据链路，实现可靠、有效的数据传送。数据链路层协议负责在物理网络与计算机的协议组之间提供一个接口。,数据电路,数据链路,数据电路：在传输信道两端加上信号变换设备（如Modem）之后所形成的二进制比特流通路。即数据电路由传输信道加DCE组成。,数据链路：在数据电路建立的基础上，在链路协议控制下，使通信双方正确传输数据的终端设备与传输线路的组合体。,3.1数据链路层的基本概念,数据链路与数据电路数据电路又可称为物理链路或链路数据链路又称为逻辑链路数据链路是在数据电路上增加传输控制功能实现的。只有建立了数据链路，才能真正地实现数据通信。,3.1数据链路层的基本概念,数据链路的基本结构（线路拓扑）点到点链路多点链路数据链路层的传送方式：单工通信半双工通信(HalfDuplex)全双工通信(FullDuplex),3.1数据链路层的基本概念,在链路中，所连接的节点称为“站”。发送命令或信息的站称为“主站”，在通信过程中一般起控制作用；接收数据或命令，并做出响应的站称为“从站”，在通信过程中处于受控地位。同时具有主站和从站功能的，能够发出命令和响应信息的站称为复合站。,3.1数据链路层的基本概念,3.1数据链路层的基本概念,在点到点链路中，两端的站可能是主站、从站或复合站。链路可以是不平衡的，或平衡结构。,3.1数据链路层的基本概念,DTE,DTE,DTE,DTE,DTE,DTE,DTE,主从式点到多点链路,对等式点到多点链路,在主从式点到多点链路中，常常是不平衡的；在对等式点到多点链路中，常使用平衡型链路。,物理层的任务是实现比特流的传送，但不能保证没有错误，需要数据链路层进行差错检测和纠正。为了便于实现流量控制和差错控制，数据链路层将比特流分割成离散的帧，独立地计算校验和，发送和接收。数据链路层的协议数据服务单元PDU，即传输和处理的数据单位：帧。,3.1数据链路层的基本概念,数据链路层帧的结构，包括需要传输的数据、相应的控制信息、校验信息、帧之间的分隔标志等。帧的形成方法：字符计数法含字节填充的分界符法含位填充的分界标志法物理层编码违例法,3.1数据链路层的基本概念,数据链路层的目标：在数据链路上提供可靠的信息传输数据链路层的功能：,链路管理帧同步（帧定界）流量控制数据和控制信息的识别,差错控制透明传输寻址,3.1数据链路层的基本概念,内容纲要,数据链路层的基本概念数据的可靠传输和流量控制差错控制点对点信道的数据链路层协议,所谓数据的可靠传输，主要是指数据从发送方经过传输到达接收方后，没有出现差错和数据丢失。数据的可靠传输必须包括数据在链路上的流量控制过程和差错控制过程，这两个过程的有机结合，实现了可靠的数据传输控制。,3.2数据的可靠传输与流量控制,在数据通信中，要求发送方的发送数据速率必须不能超过接收方的接收和处理数据的速率。由于双方数据收发设备处理能力的差异，在传输中必须协调收发双方的数据传输，保证数据正确、有序的接收。当接收方来不及接收和处理数据时，就必须采取相应的措施来控制发送方发送数据的速率。流量控制一般由接收方主动控制实现的。,3.2数据的可靠传输与流量控制,流量控制的作用：现代数据通信的交换方式，采用了存储转发的分组交换技术，当接收方的处理能力小于发送方的发送量时，必须采用流量控制。,处理单元,没有缓冲空间了！后面分组丢弃,3.2数据的可靠传输与流量控制,1、完全理想化的数据传输2、最简单流量控制的数据链路层协议3、实用的停止等待协议4、连续ARQ协议5、选择ARQ协议,流量控制的基本原理,3.2数据的可靠传输与流量控制,1、完全理想化的数据传输,数据链路层,主机A,缓存,主机B,数据链路,AP2,AP1,缓存,发送方,接收方,帧,高层,帧,3.2数据的可靠传输与流量控制,完全理想化的数据传输所基于的两个假定:假定1：链路是理想的传输信道，所传送的任何数据既不会出差错也不会丢失。假定2：不管发送方以多快的速率发送数据，接收方总是来得及收下，并及时上交主机。,1、完全理想化的数据传输,3.2数据的可靠传输与流量控制,保留上述的第一个假定，即主机A向主机B传输数据的信道仍然是无差错的理想信道。但现在不能保证接收端向主机交付数据的速率永远不低于发送端发送数据的速率，需要流量控制。由收方控制发方的数据流，是计算机网络中流量控制的一个基本方法。,2、最简单流量控制的数据链路层协议,3.2数据的可靠传输与流量控制,开关式流量控制:XON/XOFF,硬件协议式流量控制:ARQ自动重发请求停止等待协议（Stop-and-WaitProtocol）滑动窗口协议（SlideWindowProtocol）（1）连续ARQ协议（2）选择ARQ协议,流量控制方法,3.2数据的可靠传输与流量控制,(1)从主机取一个数据帧；(2)将数据帧送到数据链路层的发送缓存；(3)将发送缓存中的数据帧发送出去；(4)等待；(5)若收到由接收结点发过来的确认应答信息，则从主机取一个新的数据帧，然后转到(2)。,2、最简单流量控制的数据链路层协议,在发送结点,3.2数据的可靠传输与流量控制,(1)等待；(2)若收到由发送结点发过来的数据帧，则将其放入数据链路层的接收缓存；(3)将接收缓存中的数据帧上交主机；(4)向发送结点发送一个确认信息，表示数据帧已经上交给主机；(5)转到(1)。,2、最简单流量控制的数据链路层协议,在接收结点,3.2数据的可靠传输与流量控制,2、最简单流量控制的数据链路层协议,两种情况的对比（传输均无差错）,A,B,DATA,DATA,DATA,DATA,送主机B,送主机B,送主机B,送主机B,A,B,DATA,送主机B,DATA,送主机B,时间,不需要流量控制,需要流量控制,3.2数据的可靠传输与流量控制,在实际的数据传输过程中，由于传输信道特性的不理想和外界干扰的存在，出现传输差错是不可避免的。传输差错导致接收的数据帧错误，接收方要求发送方重发数据帧。严重的传输差错还导致数据帧或应答帧丢失，使发送操作不能继续进行，或接收方重复接收数据。,3、实用的停止等待协议,3.2数据的可靠传输与流量控制,3、实用的停止等待协议,时间,A,B,送主机,ACK,送主机,ACK,(a)正常情况,A,B,DATA0,送主机,ACK,(c)数据帧丢失,重传,丢失！,A,B,送主机,ACK,丢弃,ACK,(d)确认帧丢失,重传,丢失！,A,B,NAK,送主机,ACK,(b)数据帧出错,重传,3.2数据的可靠传输与流量控制,接收方检测出传输差错，则要求发送方重新发送此帧。传输差错还导致的问题：数据帧丢失，接收方未接收数据帧而不发送应答帧，使发送方操作不能继续进行（继续发送下一帧或重发）。应答帧丢失，发送方超时重发，接收方重复接收相同的帧。,3、实用的停止等待协议,3.2数据的可靠传输与流量控制,结点A发送完一个数据帧时，就启动一个超时计时器。此计时器又称为定时器。若到了超时计时器所设置的重传时间tout而仍收不到结点B的任何确认帧，则结点A就重传前面所发送的这一数据帧。一般可将重传时间选为略大于“从发完数据帧到收到确认帧所需的平均时间”。重传若干次后仍不能成功，则报告差错。,3、实用的停止等待协议,超时重发技术,3.2数据的可靠传输与流量控制,如果是接收方的应答帧丢失，会导致发送方重复发送，出现重复帧。每个数据帧带上不同的发送序号。每发送一个新的数据帧就把它的发送序号加1。若结点B收到发送序号相同的数据帧，就表明出现了重复帧。这时应丢弃重复帧，因为已经收到过同样的数据帧。但此时结点B还必须向A发送确认帧ACK，以保证协议正常执行。,3、实用的停止等待协议,重复帧问题,3.2数据的可靠传输与流量控制,任何一个编号系统的序号所占用的比特数一定是有限的。因此，经过一段时间后，发送序号就会重复。序号占用的比特数越少，数据传输的额外开销就越小。对于停止等待协议，由于每发送一个数据帧就停止等待应答，因此用一个比特来编号就够了。,3、实用的停止等待协议,帧的编号问题,3.2数据的可靠传输与流量控制,一个比特可表示0和1两种不同的序号。数据帧中的发送序号N(S)以0和1交替的方式出现在数据帧中。每发一个新的数据帧，发送序号就和上次发送的不一样。用这样的方法就可以使收方能够区分开新的数据帧和重传的数据帧了。,3、实用的停止等待协议,帧的发送序号,3.2数据的可靠传输与流量控制,停止等待方式的性能分析,由于发送端口或传输信道的速率限制，发送一帧需要一定的时间：“发送时延”。接收一帧的时间和发送一帧的时间相同。发送应答帧，也有“发送时延”。由于电磁波传输速率的存在，帧在信道中的传送，具有“传播时延”。接收方收到帧后，差错检验、转交处理，发送方收到应答后，准备发送下一帧，都需要“处理时延”。,3.2数据的可靠传输与流量控制,停止等待方式的性能分析,3.2数据的可靠传输与流量控制,tP=t2t0=t3t1=L/v传播时延tF=t1t0=t3-t2=F/C发送时延tA=t5t4=A/C应答帧发送时延tproc=t4-t3处理时延L节点A与B之间的距离v信号传播速率（3108m/s）F数据帧长度=H+D（帧头数据）A应答帧长度C数据发送速率bits/s,停止等待方式的性能分析,3.2数据的可靠传输与流量控制,停止等待方式的性能分析,正常情况信道利用率U=tD/(tF+tA+2tP+2tproc)tD=D/C，tF=F/C，tA=A/CU=D/（FA2C（tP+tproc）不考虑处理时延和传播时延，及应答帧的开销，则U仅与帧结构相关；当传播时延较大时，信道利用率很低。,3.2数据的可靠传输与流量控制,优点：比较简单。缺点：通信信道的利用率不高，信道还远远没有被所传输的数据比特填满。虽然物理层在传输比特时会出现差错，但由于数据链路层的停止等待协议采用了有效的检错重传机制，数据链路层对上面的网络层可以提供可靠传输服务。,停止等待协议的优缺点,3.2数据的可靠传输与流量控制,为了克服停止等待协议信道利用率低的问题，可以采用滑动窗口控制方法。当发送完一个数据帧后，不是停下来等待确认帧，而是继续发送若干数据帧。由于在等待确认时可以继续发送数据，减少了信道空闲时间，因而提高了整个通信过程的吞吐量。,4、连续ARQ协议,滑动窗口流量控制方法,3.2数据的可靠传输与流量控制,“滑动窗口”机制是实现数据帧传输控制的逻辑过程，它要求通信两端节点设置发送存储单元，用于保存已发送但尚未被确认的帧，这些帧对应着一张连续序号列表，即发送窗口。接收方则有一张接收序号列表，即接收窗口。,4、连续ARQ协议,滑动窗口流量控制方法,3.2数据的可靠传输与流量控制,后沿L（W）前沿H（W）窗口尺寸W6H(W)=L(W)+W1mod2n发送窗口：发送端允许连续发送的帧的序号表接收窗口：接收端允许连续接收的帧的序号表,4、连续ARQ协议,滑动窗口图形表示方法,3.2数据的可靠传输与流量控制,发送窗口尺寸WT：发送端可以不等待应答而连续发送的最大帧数；发送窗口后沿L(W)：发端最先发出而尚未收到应答的帧序号；发送窗口前沿H(W)：发端最后发出而尚未收到应答的帧序号；考虑出现差错的可能，WT不能过大。,4、连续ARQ协议,发送窗口,3.2数据的可靠传输与流量控制,接收窗口尺寸：接收端允许接收的帧数；在接收端只有当收到的数据帧的发送序号落入接收窗口内才允许将该数据帧收下。若接收到的数据帧落在接收窗口之外，则一律将其丢弃。,4、连续ARQ协议,接收窗口,3.2数据的可靠传输与流量控制,发送窗口：每发送一帧数据，窗口后沿移动一格；每接收一帧应答，窗口前沿移动一格；接收窗口：每接收一帧数据，窗口后沿移动一格；每发送一帧应答，窗口前沿移动一格；,4、连续ARQ协议,窗口滑动规则,3.2数据的可靠传输与流量控制,只有接收窗口向前滑动时（与此同时也发送了确认），发送窗口才有可能向前滑动。收发两端的窗口按照以上规律不断地向前滑动，因此这种协议又称为滑动窗口协议。当发送窗口和接收窗口的大小都等于1时，就是停止等待协议。,4、连续ARQ协议,滑动窗口流量控制方法,3.2数据的可靠传输与流量控制,当发送完一个数据帧后，不是停下来等待确认帧，而是继续发送若干数据帧；如果收到了接收方发来的确认帧，则发送方可以继续发送数据帧；如果出现差错，则从出现差错的数据帧开始全部重发。,4、连续ARQ协议,3.2数据的可靠传输与流量控制,4、连续ARQ协议,连续ARQ工作原理,3.2数据的可靠传输与流量控制,(1)接收端只按序接收数据帧。虽然在有差错的2号帧之后接着又收到了正确的4个数据帧，但接收端都必须将这些帧丢弃，因为在这些帧前面有一个2号帧还没有收到。虽然丢弃了这些不按序的无差错帧，但应重复发送已发送过的最后一个确认帧（防止确认帧丢失）。,4、连续ARQ协议,3.2数据的可靠传输与流量控制,(2)ACK0表示确认DATA0帧，并期望下次收到DATA1帧；ACK1表示确认DATA1帧，期望下次收到DATA2帧；依次类推。在协议式流量控制方式中，确认序号N(R)一般表示接收方希望接收的下一帧的序号，实际上也表示对N(R)1帧及其以前各帧的确认。因此在实际应用中常常使用ACK1确认DATA0帧。,4、连续ARQ协议,3.2数据的可靠传输与流量控制,(3)结点A在每发送完一个数据帧时都要设置该帧的超时计时器。如果在超时时间内收到确认帧，就立即将超时计时器清零，继续发送后续的数据帧。但若在所设置的超时时间到了而未收到确认帧，就要重传相应的数据帧（仍需重新设置超时计时器）。,4、连续ARQ协议,3.2数据的可靠传输与流量控制,(4)在重传2号数据帧时，虽然结点A已经发完了6号帧，但仍必须将2号帧及其以后的各帧全部进行重传。连续ARQ又称为Go-back-NARQ，即“返回N帧的ARQ”，意思是当出现差错必须重传时，要向回走N个帧，然后再开始重传。,4、连续ARQ协议,3.2数据的可靠传输与流量控制,发送端和接收端分别设定发送窗口和接收窗口。发送窗口用来对发送端进行流量控制。发送窗口的大小WT代表在还没有收到对方确认信息的情况下发送端最多可以发送多少个数据帧。,4、连续ARQ协议,发送端设置发送窗口,3.2数据的可靠传输与流量控制,0,1,2,3,4,5,6,7,0,1,2,发送窗口,WT,不允许发送这些帧,允许发送5个帧,(a),0,1,2,3,4,5,6,7,0,1,2,不允许发送这些帧,还允许发送4个帧,WT,已发送,(b),0,1,2,3,4,5,6,7,0,1,2,不允许发送这些帧,WT,已发送,(c),0,1,2,3,4,5,6,7,0,1,2,不允许发送这些帧,还允许发送3个帧,WT,已发送,已发送并已收到确认,(d),连续ARQ协议,在连续ARQ协议中，接收窗口的大小WR=1。只有当收到的帧的序号与接收窗口一致时才能接收该帧。否则，就丢弃它。每收到一个序号正确的帧，接收窗口就向前（即向右方）滑动一个帧的位置。同时发送对该帧的确认。,4、连续ARQ协议,接收端设置接收窗口,3.2数据的可靠传输与流量控制,不允许接收这些帧,0,1,2,3,4,5,6,7,0,1,2,WR,准备接收0号帧,(a),不允许接收这些帧,0,1,2,3,4,5,6,7,0,1,2,WR,准备接收1号帧,已收到,(b),不允许接收这些帧,0,1,2,3,4,5,6,7,0,1,2,WR,准备接收4号帧,已收到,(c),连续ARQ协议,接收窗口,只有接收窗口向前滑动时（正确接收并发送了确认），发送窗口才可能向前滑动，流量控制主要由接收方实施。发送窗口尺寸一般大于1，需要多位编码表示已发送但未被确认的帧序号。发送窗口大小的理想值：即将发送完窗口中最后一帧时，收到了窗口中第一帧的确认。接收窗口尺寸等于1。,4、连续ARQ协议,3.2数据的可靠传输与流量控制,当用n个比特进行编号时，则只有在发送窗口的大小WT2n1时，连续ARQ协议才能正确运行。例如，当采用3bit编码时，发送窗口的最大值是7而不是8。在实际应用中，有模8和模128两种编码方式。模8采用3位编码，一般用于地面链路通信；模128采用7位编码，一般用于卫星链路通信。,4、连续ARQ协议,3.2数据的可靠传输与流量控制,在连续ARQ协议中，如果某个数据帧发生差错，后续的数据帧即使被正确地接收到，也要被丢弃，造成网络资源浪费；为进一步提高信道的利用率，可设法只重传出错的数据帧或计时器超时的数据帧。,5、选择ARQ协议,3.2数据的可靠传输与流量控制,可加大接收窗口，先收下发送序号不连续但仍处在接收窗口中的那些数据帧。等到所缺序号的数据帧收到后再一并送交主机。选择ARQ协议可避免重复传送那些本来已经正确到达接收端的数据帧。我们付出的代价是在接收端要设置具有相当容量的缓存空间且控制复杂。,5、选择ARQ协议,3.2数据的可靠传输与流量控制,4、选择ARQ协议,选择ARQ工作原理,3.2数据的可靠传输与流量控制,选择ARQ方式，若用n比特进行编号，则接收窗口的最大值受下式的约束WR2n/2当接收窗口为最大值WR2n/2时，选择ARQ方式发送窗口WT2n/2,5、选择ARQ方式,3.2数据的可靠传输与流量控制,内容纲要,数据链路层的基本概念数据的可靠传输和流量控制差错控制点对点信道的数据链路层协议,由于数据通信系统传输特性的不理想和外部干扰的存在，传输中出现差错是不可避免的。由于数据序列的独立性和随机性，物理层无法有效地发现和纠正差错。差错控制的目的：确保所有的帧按顺序正确递交到数据链路层用户（网络层实体）。,3.3差错控制,随机差错原因：信道热噪声特点：随机的、单个的突发差错原因：脉冲噪声（如闪电）特点：成片的、连续的,3.3差错控制,1、差错产生原因,3.3差错控制,在发送的数据码元序列中加入监督位，并进行某种变换，使它们和原来相互独立的数据码元之间具有某种约束关系。在接收端检测接收的数据码元和监督码元的约束关系，如果这种约束关系被破坏，则接收端就可以发现传输中的错误，甚至纠正错误。,2、差错控制原理,变换的方法不同，就构成了不同的编码，因而产生不同的差错控制方法。检错码可以发现传输错误，但不能自动纠正差错。纠错码可以自动纠正传输错误。差错控制是以降低效率为代价的。,3.3差错控制,2、差错控制原理,检错重发法：接收端在收到的信码中检测出错码时，即设法通知发送端重发。前向纠错法：接收端不仅能在收到的信码中发现有错码，而且能够纠正错码。反馈校验法：接收端将收到的信码原封不动地转发会发送端，并与原发送信码相比较。,3.3差错控制,3、差错控制方法,3.3差错控制,在二进制编码中，设：信息长度k比特，可以表示信息2k种；监督信息r比特，实现对传输差错监督；2k种信息比特组合，能够按照一定的编码规则产生相应的监督位。实际传输长度为n比特，n=k+r；n比特编码可以表示比特组合2n种，2kt），则编码集的汉明距离至少为e+t+1；,3.3差错控制,汉明距离与纠错检错能力例1数据编码是000000否111111汉明距离d=1d=2d=3,例2000000000111111000111111,收到010111,4152,恢复000111,3.3差错控制,3.3差错控制,检错码恒比码正反码奇偶校验码循环冗余码（CRC）纠错码汉明码（Hamming),4、差错控制编码,3.3差错控制,线性分组码线性码：信息位和监督位为线性关系。分组码：监督位仅与本组信息位有关。系统码：前半部为未变化的信息位，后半部为生成的监督位。线性分组码的性质封闭性：任意两个有效码组之和（模2加）仍为一个有效码组。码的最小距离等于非零码最小重量。,4、差错控制编码,常用的简单编码奇偶校验码，恒比码，正反码线性分组码汉明码，循环码（包括CRC）非分组码卷积码,3.3差错控制,差错控制编码分类,4、差错控制编码,奇偶校验码是在数据码后附加一个校验位，使构成的码组中“1”的个数为奇数（奇校验）或偶数（偶校验）。01001010奇校验01001011偶校验奇偶校验码的汉明距离？,3.3差错控制,奇偶校验码,4、差错控制编码,奇偶校验码只能检测出奇数个错码，而不能检测出偶数个错码。奇偶校验码检错能力不高，但易于实现。使用水平奇偶校验码和二维奇偶校验码可以得到更强的检错能力。,3.3差错控制,奇偶校验码,4、差错控制编码,纠正一比特差错的编码；n=k+r，其中，每个校验位和某几个特定信息位构成偶校验，形成r个监督关系式；使用r个校验位构造r个监督关系式来指示一位错码可能的n个位置，则n2r1,3.3差错控制,汉明码,4、差错控制编码,3.3差错控制,接收端按照特定的对应关系，将每个校验位和相关联的信息位进行异或运算，得到r个校正子S；不同位的差错，影响的校正子组合不同。判断r个校正子S，如全为0，则无差错；若有一位错，则可根据r个校正子的不同取值组合，确定出错位。,4、差错控制编码,汉明码,3.3差错控制,（7，4）汉明码的构成：k=4，r=3，n=7数据位：a6，a5，a4，a3校验位：a2，a1，a0校正子组合与错码位置：S2S1S0出错位置S2S1S0出错位置001a0101a4010a1110a5100a2111a6011a3000无,汉明码,发送端按下式生成校验位：a2=a6a5a4a1=a6a5a3a0=a6a4a3,校正子与校验位关系（偶校验）：S2=a6a5a4a2=0S1=a6a5a3a1=0S0=a6a4a3a0=0,3.3差错控制,汉明码,3.3差错控制,接收端按下式校验：S2=a6+a5+a4+a2S1=a6+a5+a3+a1S0=a6+a4+a3+a0,得到校正子S2S1S0,S2=0,S1=0,S0=0,无差错,若S0,出错码位置由S2S1S0组合表示,汉明码,3.3差错控制,n=1010111a6a5a4a3=1010a2a1a0=111计算校正子S2S1S0,校正子S2S1S0=101a4错n=1010111,例：（7，4）汉明码，若接收端收到1010111，是否有错？在哪一位？,0,汉明码的编码效率R,若k=4，r=3，汉明码（7，4）的编码效率R=57%,若k=7，r=4，汉明码（11，7）的编码效率R=63.6%,3.3差错控制,循环冗余码（CRC）是一种特殊的线性分组码。循环冗余码各码组中的码元循环左移(或右移)，所形成的码组仍然是一个许用码组(全零码组除外)，称为循环性。循环冗余码具有较高的检错能力。,3.3差错控制,4、差错控制编码,循环冗余码（CRC）,3.3差错控制,例如A4=0111001，对应的码多项式为：,码多项式,(n，k)循环码中，为了便于描述与计算，经常使用n-1次码多项式来表示码字，码字A=an-1an-2a1a0，它对应的码多项式为：,3.3差错控制,在(n，k)循环码中，存在惟一的最高幂次为(n-k)，最多k-1个连续的0项，且常数项必须为1的码多项式g(x)，此码多项式的幂次最低（0元除外）；其它所有的码多项式都能被g(x)整除；并且g(x)是xn+1的一个因式。g(x)称为该编码集的生成多项式。,生成多项式g(x),CRC-16,CRC-CCITT,CRC-32,3.3差错控制,标准生成多项式,4、差错控制编码,选择r阶生成多项式G(x)，rnk在数据帧末尾加r个0，形成多项式xrM(x)xrM(x)R(x)G(x)G(x)移项得：xrM(x)R(x)Q(x)G(x)发送循环码多项式T(x)=xrM(x)R(x)检错标准：接收端检测T(x)/G(x)是否为零,Q(x),3.3差错控制,循环冗余码CRC的编码和检错,4、差错控制编码,例1：设信息流为10110011，G（X）=X4+X+1，即10011,101100110000,10011,10101100,10011,01010,00000,10101,10011,0100余数,10110011,0100,发送信息流为：,3.3差错控制,4、差错控制编码,例2：CRC检错数据帧1101011011（M(x)，m=10）生成多项式G(x)=x4+x+1（r=4）生成多项式也可表示为10011以2为模的除法：11010110110000/10011=1110发送帧11010110111110（以2为模的减法）接收端检测：11010110111110/10011=0,3.3差错控制,4、差错控制编码,以2为模的除法和减法（加法）110000101010011）110101101100001001110011110101101100001001111101011011010110111110100111010010011余数1110,G(x),发送序列T(x)=xrM(x)余数,xrM(x),3.3差错控制,4、差错控制编码,在数据后面添加上的冗余码称为帧检验序列FCS(FrameCheckSequence)。循环冗余检验CRC和帧检验序列FCS并不等同。CRC是一种常用的检错方法，而FCS是添加在数据后面的冗余码。FCS可以用CRC这种方法得出，但CRC并非用来获得FCS的惟一方法。,3.3差错控制,4、差错控制编码,循环冗余码（CRC）,得出的余数R不为0，就表示检测到差错。但这种检测方法并不能确定究竟是哪一个或哪几个比特出现了差错。一旦检测出差错，就丢弃这个差错的帧。只要经过严格的挑选，并使用位数足够多的除数P，那么出现检测不到的差错的概率就很小很小。,3.3差错控制,4、差错控制编码,循环冗余码（CRC）,仅用循环冗余检验CRC差错检测技术只能做到无差错接受(accept)。“无差错接受”是指：“凡是接受的帧(即不包括丢弃的帧)，我们都能以非常接近1的概率认为这些帧在传输过程中没有产生差错”。要做到“可靠传输”（即发送什么就收到什么）就必须再加上确认和重传机制。,3.3差错控制,4、差错控制编码,循环冗余码（CRC）,内容纲要,数据链路层的基本概念数据的可靠传输和流量控制差错控制点对点信道的数据链路层协议,数据链路控制协议的作用数据链路层控制功能的具体体现，使通信变得比较可靠。数据链路控制规程的作用：,3.4点对点信道的数据链路层协议,帧控制透明传送流量控制,差错控制链路管理异常状态的恢复,面向字符的数据链路控制规程基本型（如BSC，二进制同步通信）高级（DDCMP，数字数据通信报文规程）SLIP和PPP面向比特的数据链路控制规程IBMSDLCISOHDLCCCITT（ITU-T）LAPB,3.4点对点信道的数据链路层协议,站的定义：主站：允许发送控制报文从站：在主站控制下操作，回复响应复合站：具有主、从站双重功能链路配置：不平衡：用于点点或点多点链路平衡：用于点点链路,1、面向比特的链路控制规程高级数据链路控制规程HDLC,3.4点对点信道的数据链路层协议,NRM正常响应模式只有主站才能发起向从站的数据传输，从站只能响应主站的询问。ARM异步响应模式允许从站发起向主站的数据传输，但主站仍然负责全程的初始化。ABM异步平衡模式任一复合站均可发送、接收命令/响应,1、面向比特的链路控制规程HDLC,3.4点对点信道的数据链路层协议,HDLC的帧结构,F帧标志01111110A地址字段C控制字段I信息字段FCS帧校验序列,F,F,A,C,FCS,短帧,长帧,1、面向比特的链路控制规程HDLC,3.4点对点信道的数据链路层协议,信息Info,标志F,标志F,地址A,控制C,帧检验序列FCS,帧Frame,1、面向比特的链路控制规程HDLC,HDLC的帧结构,物理层,帧层,网络层,同步比特流,头部,数据部分,分组,3.4点对点信道的数据链路层协议,标志字段F(Flag)为6个连续“1”加上两边各一个“0”共8bit。在接收端只要找到标志字段就可确定一个帧的位置。,比特,8,8,8,可变,16,8,信息Info,标志F,标志F,地址A,控制C,帧检验序列FCS,透明传输区间,FCS检验区间,1、面向比特的链路控制规程HDLC,标志字段F,3.4点对点信道的数据链路层协议,HDLC采用零比特插入法使一帧中两个F字段之间不会出现6个连续1。在发送端，当一串比特流数据中有5个连续1时，就立即插入一个0。在接收帧时，先找到F字段以确定帧的边界。接着再对比特流进行扫描。每当发现5个连续1时，就将其后的一个0删除，以还原成原来的比特流。,1、面向比特的链路控制规程HDLC,零比特插入法,3.4点对点信道的数据链路层协议,1、面向比特的链路控制规程HDLC,零比特的插入与删除,数据中某一段比特组合恰好出现和F字段一样的情况,01001111110001010,会被误认为是F字段,发送端在5个连1之后插入0比特再发送出去,填入0比特,010011111010001010,在接收端将5个连1之后的0比特删除，恢复原样,在此位置删除填入的0比特,010011111010001010,3.4点对点信道的数据链路层协议,1、面向比特的链路控制规程HDLC,HDLC透明传输,采用零比特插入/删除法可传送任意组合的比特流，或者说，可以实现数据链路层的透明传输。当连续传输两个帧时，前一个帧的结束标志字段F可以兼作后一帧的起始标志字段。当暂时没有信息传送时，可以连续发送标志字段，使收端可以一直和发端保持同步。,3.4点对点信道的数据链路层协议,1、面向比特的链路控制规程HDLC,HDLC帧结构,地址字段A不平衡配置：从站地址平衡配置：应答站地址控制字段C说明帧的类型、功能信息帧I：数据传送，包含信息字段监督帧S：监视和控制数据传送无编号帧U：数据链路的控制和管理信息字段I高层信息，长度可变帧校验序列FCS差错控制，CRC校验,3.4点对点信道的数据链路层协议,1、面向比特的链路控制规程HDLC,信息帧,LSB为0表明该帧是信息帧。N(S)号表明该帧的发送一个帧号。N(R)号表明该帧的发送者期望接收的下一个帧号。（对N(R)1及以前各帧的确认）3比特编码表示为模8方式。利用信息帧携带确认信息可提高传送效率。,P/F,0,N(R),N(S),3.4点对点信道的数据链路层协议,1、面向比特的链路控制规程HDLC,监视帧S,N(R)用于向发送方确认接收端所收到帧的序号。N(R)表示该帧的发送者期望接收的下一个帧的序号，同时对N(R)1及以前各帧确认。,3.4点对点信道的数据链路层协议,监视帧用于数据传送阶段，实现流量控制和差错控制，保证数据传输的正常进行。RRReceiverReady接收端准备好RNRReceiverNotReady接收端未准备好REJReject帧拒绝（连续ARQ）SREJSelectReject选择拒绝（选择ARQ）,1、面向比特的链路控制规程HDLC,监视帧S,3.4点对点信道的数据链路层协议,RR帧是一种标准应答，表示接收端已作好接收准备，发送方可发送信息帧。RNR帧用来通知对方停止发送任何帧，直到发送RR帧为止，同时确认前面发送的帧。REJ帧是用于拒绝收到出错的帧。SREJ用于要求选择重发出错的帧。,1、面向比特的链路控制规程HDLC,HDLC监视帧的作用,3.4点对点信道的数据链路层协议,LSB为11表明该帧是无编号帧（U帧）,1、面向比特的链路控制规程HDLC,无编号帧,3.4点对点信道的数据链路层协议,无编号帧的控制字段中没有N(S)、N(R)序号。无编号帧的控制字段中有5位，可以实现32种编码，用来表示帧的功能，实际只使用了十几种。无编号帧一般用于链路建立、拆除控制和异常情况处理。,1、面向比特的链路控制规程HDLC,无编号帧,3.4点对点信道的数据链路层协议,在TCP/IP协议族中，串行线路网际协议（SLIP）和点到点协议（PPP）是专门用于调制解调器和其它直接连接的，它不需要进行介质访问控制，提供完整的数据链路层功能。用户使用拨号电话线接入因特网时，一般都是使用SLIP或PPP协议。,2、因特网的点对点协议PPP,SLIP和PPP,3.4点对点信道的数据链路层协议,由于SLIP在协议识别和差错控制等方面的不足，现在使用得最多的是点到点协议PPP(Point-to-PointProtocol)。1992年制订了PPP协议。经过1993年和1994年的修订，现在的PPP协议已成为因特网的正式标准RFC1661。,2、因特网的点对点协议PPP,SLIP和PPP,3.4点对点信道的数据链路层协议,2、因特网的点对点协议PPP,PPP协议有