第3章-数据链路层

1、计算机网络计算机网络第第3 3章章 数据链路层数据链路层 n数据链路层的服务与功能n成帧方法n差错控制与流量控制n差错检测和纠正n基本数据链路层协议-滑动窗口机制n数据链路层协议实例数据链路层的服务与功能（数据链路层的服务与功能（1 1） 使用物理层提供的服务在通信信道上发送和接收比特。完成功能包括：n向网络层提供一个定义良好的服务接口n处理传输错误n调节数据流，确保慢速的接收方不会被快速的发送方淹没 路由器的数据链路层示意数据链路层的服务与功能（数据链路层的服务与功能（2 2） n无确认无连接当错误率很低,恢复留给高层,对实时通信很适合.绝大多数局域网采用，以太网n有确认无连接每一帧都要独立

2、确认，超时重发,使用于不可靠信道,如无线系统，WiFin有确认有连接建立连接（初始化变量和计数器）、传输一个或多个帧、释放连接。为网络层进程提供了可靠的位流.3种可能的服务数据链路层的服务与功能（数据链路层的服务与功能（3 3） 成帧方法成帧方法 n字节计数法n字节填充的标志字节法n比特填充的标志比特法 n物理层编码违例法 成帧方法成帧方法- -字节计数法字节计数法 以特殊字符表征帧的起始和结束，并以一个专门字段来标明帧内的字节数。 典型实例是DEC公司的数字数据通信报协议DDCMP（Digital Data Communications Message Protocol）。成帧方法成帧方法-

3、标志字节填充法（标志字节填充法（1 1） 用特殊的字符作为帧头和帧尾，起始字符 DLE STX，结束字符DLE ETX，接收方一旦丢失了帧信息，只要查找DLE STX就可重新确定帧边界。字符填充局限于8位字符和ASCII字符传送。 透明传输策略：当数据中含有DLE时，在DLE前面加上DLE帧尾SYN SYN DLE STX A DLE DLE B DLE DLE C DLE ETX帧首同步字符数据传输帧填充字符字符填充成帧方法成帧方法- -标志字节填充法（标志字节填充法（2 2） 成帧方法成帧方法 -PPP协议采用字节填充方案成帧方法成帧方法-标志位填充法标志位填充法 帧 的 起 始 和 结

4、束 都 用 一 个 特 殊 的 位 串“01111110”，称为标记（flag）。在面向二进制位的同步串型通信中常使用带位填充的首尾标志格式，如HDLC 。 透明传输策略：“0”插入法 帧首帧首数据数据帧尾帧尾011111100111111001111101101111100填充位填充位 “0”比特插入删除技术比特插入删除技术成帧方法成帧方法- -物理层编码违例法n借用一些违法编码序列来定界帧的起始与终止，局域网IEEE 802标准中就采用了这种方法。违法编码法不需要任何填充技术，便能实现数据的透明性。 数据0：低高电平对数据1：高低电平对曼彻斯特编码差错控制和流量控制（1）n确保可靠传输 反

5、馈确认 超时重传 帧编号（区分原始帧和重传帧）n流量控制 基于反馈的流量控制 基于速率的流量控制（限制发送方传输数据的速率）流量控制流量控制 流量控制（Flow Control）规定了对帧进行发送和跟踪的方法，以及该站点如何进行错误控制。决定帧在什么时候可以或不可以被发送，什么时候这些帧可以被第二次发送。流量控制协议确保所有的相关帧能够精确和有序地到达目的地。 典型情况下，流量控制是发送方、接收方某些连续层次的多个实体交互作用的结果，例如OSI模型中数据链路层和网络层的交互关系。流量控制也存在于较高层协议如TCP，实际上流量控制存在于不同的模型以及不同的层之间。差错控制方法差错控制方法 从差错

6、控制的角度，对于传输的信号，利用检纠错基本原理进行编码来降低差错的发生，利用差错控制编码方法进行差错控制的常用方式主要有如下几种： n 自动请求重发（ARQ）方式n 前向纠错（FEC）方式n 混合纠错（HEC）方式自动请求重发（自动请求重发（ARQARQ）方式）方式 发送端发送出可以发现错误的码字，接收端译码若检测到错误，则主动向发送端发出请求，要求重发以便纠错。这种系统要求有反馈信道且发送端和接收端都有缓存器。前向纠错（FEC）方式 发送端发出的码字是具有一定纠错能力的码字。在接收端译码后不仅可以发现错码，而且能够判断错码所在的位置并自动纠正。这种方法不需反馈信道，实时性好，传输效率较高，但

7、纠错编码方法和设备较复杂。混合纠错（HEC）方式 实际应用中，可以结合使用ARQ方式和FEC方式。即在传输错码较少且接收端能纠正时，自动纠正错误；在错码较多、超出纠正能力但尚能检测时，采用自动请求重发方式，请求发送端重传，直到正确接收为止。该方式大大提高了通信的可靠性。差错检测和纠正n前向纠错（FEC）利用纠错码n反馈重传 利用检错码n纠错码的冗余量检错码的冗余量 对信道质量较好的有线链路一般都用检错码 对信道质量较差的无线链路采用纠错码纠错码出现在物理层、链路层和高层多个层次检错码更是经常应用于链路层、网络层和传输层检错纠错的基本原理检错纠错的基本原理 检纠错的基本思想就是，在被传送的信息中

8、附加一些冗余信息，使信息传输码元和冗余传输码元两者之间建立某种校验监督关系，当传输过程产生错误时，在接收端可利用监督关系进行检测并予以纠正。这种检纠错的能力是用信息量的冗余度来换取的。n码距和检纠错能力的关系n编码效率 码距和检纠错能力的关系n码重：指码字中非零码元的数目，即“1”的个数。码字（C表示）由许多码元组成，码字中码元的个数称为码长（n表示）。n码距：也称海明距离（Hamming distance），是一个码组中任意两码字之间对应位上码元取值不同的数目。用d表示，即10)(),(npjpipjiccccd意义任意两个码字的海明距离为d,则需要d个一位错误才能将一个码字变成另一个码字。

9、一种编码方案的检错和纠错能力与海明距的关系 n为了检测d个错误，需用距离为d+1的编码方案，因为d个1位错误不可能将一个有效码字变成另一个有效码字。接收到无效码字，就知道发生了传输错误。n为了纠正d个错误，需要一个距离为2d+1的编码方案，即使发生了d位错误，还是原来的码字离它最近。从而可以唯一的确定原来的码字。n若码组中用于纠t个错，同时检e个错，则距离de+t+1，其中et 纠错码4种不同的纠错编码n海明码n二进制卷积码n里德所罗门码n低密度奇偶效验码纠错码-海明码n设计一种编码方案 每个码字有m个报文位和r个校验位，n=m+r,可以纠正所有的单个错。 共有2n种符号表示。 其中合法报文（

10、2m个） 任意一个合法报文，发生单个错（n位中的任一位都有可能），可能造成n个与合法报文的距离是1的非法码字 因此编码方案中，n必须满足 （n+1）2m=2nn海明的方法（1950）：纠正单个差错.n码字中（1,2,4,8)为校验位;剩下的位是数据.每个校验位迫使某一组位的奇偶值为偶数或奇数.n当一个码字到来时,接收方将重新计算所收到的每个校验位,看是否有正确的奇偶性。 若有错，将有错的位置相加，就是错误位置.若检验出第1位和第4位校验位有误，则表示第5位出错7位ASCII码编成11位 满足27+ n* 27=2n校验位生成方法a1=a3+a5+a7+a9+a11a2=a3+a6+a7+a10

11、+a11a4=a5+a6+a7a8=a9+a10+a11若检验出第1位和第4位校验位有误，则表示第5位出错第1个校验位分别对3,5,7,9,11位做校验3=1+25=1+4 6=2+47=1+2+49=1+810=2+811=1+2+8纠错码-卷积码（convolution code）卷积码（n,k,m)不属于块码，主要用来纠随机错误 码元与前后码元有一定的约束关系，编码复杂度可用编码约束长度m*n来表示。 n个码元不仅与当前段的k个信息有关，而且与前面的（m1）段信息有关（m为编码的约束长度）。 已经成为GSM移动电话系统的一部分，在卫星通信和802.11中都得到应用。 例 NASA卷积码

12、第一个被用于1977年旅行者航天飞行任务中的编码卷积码的纠错能力不仅与约束长度有关，还与采用的译码方式有关。卷积码的性能至少不比分组码差纠错码-里德所罗门码（Reed-Solomon code）线性块码，与海明码不同，对m位符号进行操作，而不是针对单个位处理。类比方案描述：两个数据点代表一条线，选自同一条线上的额外两个点充当校验位，当有一个点出现错误，仍然可以通过拟合线恢复这个点。得到广泛应用，强大的纠错能力。用在DSL、线缆上的数据通信、卫星通信、CD、DVD。加入2t个冗余符号后，可以纠正传输符号中的任意t个错误。通常和其他编码结合一起用，如卷积码。纠错码-低密度奇偶校验码（LDPC）Ro

13、bert Gallagher 1962年博士论文中提出每个输出位由一小部分输入位形成，编码可以用一个1的密度很低的矩阵表示。接收码字通过一个近似算法解码获得，该算法通过迭代不断改进接收到的数据域合法码字的最佳匹配。适用于大块数据，纠错能力强。被新的协议所采纳，成为数字视频广播、万兆以太网、电力线网以及新版802.11标准的一部分。检错码检错码n纠错码广泛应用于无线链路,而有线链路,通常使用检错码.n例如:错误率为10-6,1000 位数据块,需要10位纠错码,能纠正1位错,而用检错码只需1个奇偶位,1M数据位需要的纠错和检错的开销?三种检错码线性块码n奇偶n校验和n循环冗余校验（CRC） 检错

14、码检错码-奇偶校验奇偶监督码是一种最基本的、最常用的、最简单的检错码。它可分为奇监督码和偶监督码两种，基本编码原理相同。奇偶监督码中，监督位仅有1位，设监督位为c0，奇偶监督码的编码规则是加入c0后，码字中“1”的个数满足奇数或偶数，用下式表示： 1200nnccc偶监督码：1201nnccc奇监督码：检错码检错码-二维奇偶监督码 二维奇偶监督码又称方阵码，是在奇偶校验码的基础上产生的。它把奇偶监督码的若干码字排列呈矩阵，每个码字一行，增加一位监督位，再按列的方向增加垂直监督位，构成水平垂直奇偶监督码。nInternet校验和 1.待校验的相邻字节成对组成16比特整数并计算其和的二进制反码(二

15、进制反码求和).二进制反码求和:从低位到高位逐列进行和计算,如果最高位(16位)进位,则得到的结果加1,一直循环到最高位没有进位为止.最后把得到的结果取反.2.检查校验和,将所有字节,包括校验和,进行相加并求二进制反码.如果结果为全1(即二进制反码算术中的0),检查通过.简单的求和，无法检测出0数据的增加和删除，保护很弱检错码检错码-校验和nFletcher校验和 Fletcher 1982年提出，将数据和位置的乘积添加到总和中，能对数据位置的变化提供更强大的检测作用。检错码检错码-循环冗余校验码（循环冗余校验码（CRCCRC） 循环码又称为多项式码，是一种线性分组码。它是在严格的代数学理论基

16、础上建立起来的，检纠错能力非常强，且广泛应用在计算机网络和数据通信中。循环码除了具有线性分组码的一般性质外，还有一个显著的特点就是循环性，即循环码中任一码字循环左移（右移）一位或多位所形成的码字仍旧是循环码中的码字。 循环码的编码 n第一步 若生成多项式G(x)的阶是r, 将信息位左移r位，得xrM(x)；n第二步，作模2除法，求余数r(x)；余数由下式获得： n第三步，根据T(x)=xrM(x)+r(x)，求出码字。 )()()()(xrxQxGxMxrCRC的检错能力分析n接收方:T(x)+E(x)当E(x)/G(x)为0时,错误无法检出(1)1位错能够检出.E(x)=xi(2)两个独立的

17、一位错,E(x)=xi+xj=xj(x i-j+1) 除非i-j很大,要不然E(x)/G(x)!=0.如对于任何k1, rws=1n设窗口序列号分别是0、1、2.MAX-SEQ(2n-1)sws应小于N =2n ,最大未确认帧数是2n-1累计确认（cumulative acknowledgement） 若取sws=N,会导致某些情况下协议失败如当发送0-7号帧,成功，返回ACK=0 又发送0-7号帧，成功？全部丢失？无法区分Protocol Using Go-Back-N (3)A sliding window protocol using go-back-n. . .Protocol Usi

18、ng Go-Back-N (4). . .Protocol Using Go-Back-N (5). . .Protocol Using Go-Back-N (6). . .Protocol Using Go-Back-N (7)A sliding window protocol using go-back-n. . .Protocol Using Go-Back-N (8)A sliding window protocol using go-back-n. . .*累计确认的处理*重传Protocol Using Go-Back-N (9)用于流量控制，diable_network_laye

19、r()阻止网络层给予太多的工作Protocol Using Go-Back-N (10)Simulation of multiple timers in software. (a) The queuedtimeouts (b) The situation after the first timeout has expired.多个计时器的软件实现选择重传协议Pipelining and error recovery. Effect of an error when(b) receivers window size is large.选择重传协议非顺序接收带来的问题(a)Initial situ

20、ation with a window of size7(b)After 7 frames sent and received but not acknowledged.(c)Initial situation with a window size of 4.(d)After 4 frames sent and received but not acknowledged. sws1, rws1sws1, rws1举例说明选择性重传在发送窗口和接收窗口都取7时，在某些情况失效 设 2n = 8，设sws=7, rws = 7； 发方发帧 0 - 6，收方全部收到； 接收窗口前移（7 - 5）；

21、现在发生意外，确认帧全部丢失； 由于超时，发方重传帧0； 收方作为新帧接收，并对帧6确认（因为0-6都收 到） 发送方发出新帧 7-5， 收方已收过帧 0，丢弃新帧 0，协议出错。选择性拒绝ARQ中，显然接收窗口不应该大于发送窗口，当接收窗口尺寸取最大时，rws=sws，明显地， rws=sws 2n /2=2n-1，只有满足这个条件才能不发生混帧的问题。（前后两个接收窗口不能重叠）Protocol Using Selective Repeat (1)A sliding window protocol using selective repeat. . .Protocol Using Sele

22、ctive Repeat (2)A sliding window protocol using selective repeat. . .发送过程，可以发送数据、携带ack、或nakProtocol Using Selective Repeat (3)A sliding window protocol using selective repeat. . .Protocol Using Selective Repeat (4). . .Protocol Using Selective Repeat (5). . .Protocol Using Selective Repeat (6). . .P

23、rotocol Using Selective Repeat (7). . .将接收到的数据帧递交给网络层，接收窗口滑动Protocol Using Selective Repeat (8). . .检测到帧错误，发送nak重传Protocol Using Selective Repeat (9)数据链路协议实例数据链路协议实例 HDLC的帧格式，由标志、地址、控制、信息和帧检验序列（FCS）等段构成。 高级数据链路控制（HDLC- High-level Data Link Control）是由国际标准化组织ISO于1976年提出制定的面向位的有序链路级协议。 HDLC HDLC帧的类型帧的类

24、型 1 1、信息帧（、信息帧（InformationInformation）；）； 2 2、监控帧（、监控帧（SupervisorySupervisory）；）； 3 3、无编号帧（、无编号帧（U U帧）帧）数据链路协议实例数据链路协议实例 Internet两种常见情况下通过广域网中的SONET光纤链路发送数据包Internet边缘的电话网络本地回路上的ADSL链路数据链路协议都采用点到点协议（PPP）RFC1661，1662数据链路协议实例（数据链路协议实例（1)1) Packet over SONET. (a) A protocol stack. (b) Frame relationships数据链路协议实例（数据链路协议实例（2)2) PPP功能处理错误、检测链路配置、支持多种协议、允许身份认证三个主要部分 成帧方法成帧方法 明确地定界一个帧的结束 和下一个帧的开始，也允许进行错误检测。 链路控制协议（链路控制协议（LCPLC