1、第三章 数据链路层协议及技术成帧成帧 差错检测与差错控制差错检测与差错控制 链路层协议链路层协议3.1 数据链路层基本概念 链路：一条无源的点到点的物理线路段 数据链路：链路规程（控制数据传输）。一条物理连接加上为实现数据可靠传输所配置的硬件和相关的通信协议） 数据链路层的作用：通过一些数据链路层协议（链路控制规程），在不太可靠的物理链路上实现可靠的数据传输数据链路层功能和提供的服务 数据链路层的协议数据单元PDU:帧帧 任务是将网络层的数据组合成帧，加上一定的校验，然后交物理层用某种信号表示二进制数据位送到目的计算机，并通过目的计算机的物理层和数据链路层送到网络层，为网络层提供了一条可靠可靠
2、的数据链路提供服务（通过有无连接，有无确认区分）： 无确认无连接服务例如：局域网1）共享信道无需连接2）传输出错或丢失由上层恢复3）信道比较好，数据传输的误码率比较低无确认并非不可靠，其可靠性由上层负责 有确认无连接：使用前不建立连接，但每帧传输必须得到确认适合信号传播时延比较大，线路状态不一定很可靠的情况例如：无线通信：建立连接降低了利用率(540ms)；误码率相对高，需确认）：用于不可靠的通道传输； 有确认有连接（电话，大多数广域网的通信子网的DLL）数据链路层可靠传输保证直接相连的两台主机的可靠性传输1）将传输的数据组合成同一的格式：帧2）数据校验和反馈重发机制3）流量控制3.2 成帧（
3、framing)帧的组成必须保证能识别一个完整的帧，并保证一旦出现传输差错导致前一个帧丢失，也必须能识别下一个帧(错误发生之后重新同步)。成帧方法：字符计数法带字符填充的首尾字符定界法带位填充的首尾标记定界法物理层编码违例法3.2.1 字符计数法 帧头中用一个字节来表示整个帧的字符个数 若计数出错，对本帧和后面的帧有影响。（错误没有办法恢复）3.2.2 带字符填充的首尾字符定界法 比如以ASCII字符DLE和STX作为帧的头部，DLE和ETX作为帧的尾部（DLE=10H,STX=02H,ETX=03H）（DLE:data link escape表转义字符，STX:start of text,E
4、TX:end of text) 技术：如何避免字符数据可能与帧的头尾标志相同？ 发送方在数据中遇到DLE时，自动在其前后插入一个DLE 接收方在数据中遇到单个DLE时，可确定帧界，遇到2个 DLE时，自动删除一个DLE3.2.2 带字符填充的首尾字符定界法 用途：帧同步用于面向字符型协议，比如PPP，IBM的二进制同步通信协议BSC 不足：依靠字节模式，但不是所有的字符编码都是采用8位模式，unicode采用16位编码，如何允许任意长度的字符编码的帧同步技术呢？3.2.3 带位填充的首尾字符定界法 帧的起始和结束都用一个特殊的位串“01111110”，称为标记（flag）如果由于干扰，一个帧标
5、志没有正确接收，则继续扫描接收串，一旦扫描到，表示新的一帧的开始，具有再同步能力 “0”比特插入删除技术（透明传输）：发送方5个“1”后插入“0”,接收方删除第5个“1”后的“0”3.2.4 物理层编码违例法 Manchester encoding or Differential Manchester encoding 用high-low pair/low-high pair 表示1/0，high-high/low-low不表示数据，可以用来做定界符。 令牌环网中使用编码违例格式3.3 差错产生与差错控制方法3.3.1 为什么要设计数据链路层 在原始物理传输线路上传输数据信号是有差错的； 设计
6、数据链路层的主要目的： 将有差错的物理线路改进成无差错的数据链路； 方法 差错检测 差错控制（重发和编序号） 流量控制（滑动窗口协议） 作用：改善数据传输质量，向网络层提供高质量的服务。差错产生的原因和差错类型 传输差错 通过通信信道后接收的数据与发送数据 不一致的现象; 差错控制 检查是否出现差错以及如何纠正差错； 通信信道的噪声分为两类：热噪声热噪声（传输介质导体的电子热运动形成）和冲击噪声冲击噪声（外界电磁干扰形成）； 由热噪声引起的差错是随机差错随机差错，或随机错，一般出错数据位不相邻 ； 冲击噪声引起的差错是突发差错突发差错，或突发错，一般会引起相邻多个数据位出错 ； 引起突发差错的
7、位长称为突发长度； 在通信过程中产生的传输差错，是由随机差错与突发差错共同构成的。差错评价指标及差错控制方法评价指标： 误码率：错传的码元数与所传输码元总数之比 误比特率：错传的比特数与所传输总比特数之比。在二进制码元时，误比特流误码率差错控制基本方式： 反馈纠错：在接收端能发现差错，但不能确定错码的位置，通过反馈信息请求发送端重发，直到接收端肯定确认为止。适合双工通信和非实时通信系统 前向纠错：在接收端不但能发现错码，还能确定错码位置，并纠正错码。适合单工通信和实时通信系统 混合纠错：少量差错在接收端自动纠正，超出自纠正能力，通过反馈请求重发误码控制基本原理 为了能判断传送的信息数据是否有误
8、，在传送时增加必要的附加判断数据，在不发生误码的情况之下，附加判断数据是完全多余的，但如果发生误码，即可利用信息数据与附加数据之间的特定关系来实现检错和纠错 为了使数据码有一定的检错和纠错能力，应当按一定的规则在数据码的基础上增加一些冗余码码字的检错与纠错能力 码字（n位）数据码（m位）冗余码（r位） 海明距离：两个码字之间对应码元位的不同码元的个数。 比如：与，有3位不同，海明距离3 码字编码的海明距离码字编码的海明距离：对于一种码字编码，在这个码字集合中，可得到所有任意两个码字的海明距离，其中最小的海明距离称为该码字编码的海明距离d检错编码和纠错编码使用3位二进制来对8个码字进行编码不能检
9、测出错使用4位二进制来对8个码字进行编码能检测奇数位出错，但不能纠错海明距离（码距）为海明距离（码距）为3 3及以上，才能够进行纠错及以上，才能够进行纠错码距与纠错检错位的关系一般情况下，冗余位越多，检错纠错能力越强，但相应编码效率也随之降低了L-1=C+D L为码距，D为可以检测出的错误位数，C为可以纠正的错误位数，并且有DC。常用检错码和纠错码检错码：校验和奇偶校验码循环冗余编码CRC 目前应用最广的检错码编码方法之一纠错码：海明码3.3.1 校验和 算法简单，容易实现，但检错率不高 将发送的数据看成是二进制整数序列，并划分成一段段规定的长度（8bbit,16bit,32bit）计算他们的
10、和，若校验和大于规定的长度，则将进位加到最后的校验和中。将校验和和数据一起发送。在接收端，重新计算校验和与原校验和比较。比如传输“HELLO WORLD.”以16bit为例4865H+6C6CH+6F20H+776FH+726CH+642EH+进位71FCH3.3.2 奇偶检验 通过增加冗余位使得码字中“1”的个数恒为奇数或偶数的编码方法.例：发送端发送ASCII码，在传输的过程中由于干扰，接收端接收的是。那么系统能不能知道出现出错了呢？如果发送端发送的是ASCII码数据奇校验位，即，那么接收端接收的是，那么系统能不能知道出错了呢？若接收到的数据是，那么系统如何判断？3.3.3 循环冗余码CR
11、C码 特点：实现容易，检错能力强，广泛使用。常结合反馈重发法来保证信息的可靠传输。 码字组成： 编码和解码的计算采用二进制比特序列多项式 二进制比特序列多项式 例：若数据码110011，可以表示为：M(X)=X5+X4+X+1 生成多项式G(X): G(X)被通信双方事先共同选定使用：发送端：通过G(X)生成校验码接收端：通过G(X)校验接收的码字 对于多项式的运算：采用模2计算（加法不进，减法不借位）；加减法是一样的模2计算即是异或运算 发送端：1、生成校验码R(X):把要发送的数据码去除G(X)，所得的余数值T(X)就是循环冗余码2、发送 ：实际上，把CRC校验码R(X)附加到数据码M(X
12、)的后面，然后发送传输 接收端：CRC举例 数据码M(X)=110011,利用生成多项式G(X)=X4+X3+1,求CRC校验码为多少？ 流行的生成多项式有：CRC-12 G（x）= x12+x11+x3+x2+x+1CRC-16 G（x）= x16+x15+x2+1CRC-CCITT G（x）= x16+x12+x5+1CRC-32 G（x）= x32+x26+x23+x22+x16+x12+x11+ x10 +x8+x7+x5+x4 + x2+x+1 检测能力： 所有单个错、奇数个错和离散的二位错 所有长度r位的突发差错 CRC实现：硬件：采用多段移位寄存器或异或门组成CRC校验电路来实现
13、软件：通过快速的CRC检验软件来实现3.4 差错控制和流量控制 数据链路协议主要考虑的问题：1、避免所传送的数据可能出现差错和丢失2、使发方发送数据的速率适应收方的接收能力理想化的数据传输 假设1：所传送的数据既不会出现差错和也不会丢失（不考虑差错控制问题） 假设2：接收端的数据接收速率足够快，有能力接收发送端的数据发送率（不考虑流量控制问题） 在理想化的条件下，数据链路层不需要：1、差错控制协议2、流量控制协议 就可保证数据的正确传输3.4.1 最简单流量控制的停止等待协议 保留假设1，去掉假设2。考虑流量控制问题流量控制协议 使发送端发送数据的速率适应接收端的接收能力 最简单流量控制协议（
14、发送方和接收方各有一个帧的缓冲空间）发送节点：1、从数据链路层的发送缓存中取一个数据帧2、发送这个数据帧3、等待4、若收到由接收端的应答信息，转1接收节点：1、等待2、接收由发送端发来的数据帧3、将其存入数据链路层的接收缓存4、发送应答信息，表示数据帧已接收，转到13.4.2实用的停止等待协议ARQ 去掉假设1，去掉假设2考虑差错控制问题差错控制协议考虑流量控制问题流量控制协议初步协议：1、发送端发送数据帧后，等待接收端的应答帧2、接收端收到数据帧后，通过CRC校验，如果无差错，回送一个确认帧ACK，否则，回送一个否认帧NAK3、发送端收到应答帧，如果是ACK，发送下一数据帧，如果是NAK，重
15、发数据帧 协议有什么缺陷呢？协议有什么缺陷呢？死锁现象缺陷1：数据帧丢失 当出现帧丢失时，发送端永远等待下去，如何解决？ 解决方法：发送端设立一个超时计时器，发送完一个数据帧时，就启动它，如果在规定时间内得不到应答帧，判定为超时，重传数据 tout称为重传时间重复帧差错缺陷2：应答帧丢失，产生重复帧 若应答帧丢失，按照超时重发方法，接收端将接收到重复帧，如何解决？ 解决方法：给每个数据帧附加不同的发送序号Ns,如果接收端收到相同序号的数据帧，则丢弃，并回送一个ACK 发送序号需要多少位？对于ARQ协议，发送序号有1和0即可（只需1bit)，每发一个新的数据帧，发送序号和上次发送不一样停止等待协
16、议的信道利用率 单程传输时延Td,数据帧发送时间Tf,数据传输率C，数据帧长度L，信道利用率Cr(总时间等待时间)/传输一帧的总时间 忽略应答帧长度和处理时间： Cr=Tf/(Tf+2Td)=1/(1+2TdC/L) 卫星信道传输速率50kbps,往返传输延迟500ms，若传1000bit的帧，使用停止等待协议，则传输一个帧所需时间为： 发送时间信息信道延迟确认信道延迟1000bit/50kbps+250ms+250ms=520ms 信道利用率20/520约为4% 一般情况：信道速率b比特/秒，帧长度L比特，往返传输延迟R秒，则信道利用率为 （L/b）/（L/b+R）=l/(l+Rb/L) 结
17、论：传输延迟大（R)、信道带宽高、帧短时 信道利用率低3.4.3 连续ARQ 目的：提高信道利用率 方法：发送端发送完一个数据帧后，不停下来等待应答帧，而是连续再发送数据帧，当收到否认帧NAK时，再控制重发 实现要求： 数据帧需附加发送序号信息。否认帧附加出错的数据帧发送序号 常用协议 回退N帧ARQ协议 选择重发ARQ协议回退N帧ARQ协议 方式1：反馈否认帧NAK（含出错的数据帧发送序号）。再从出错的数据帧开始重传 要求：发送端要求有一个能存储N个数据帧的缓冲区，接收端只需能存储一个数据帧的缓冲（接收端的数据链路层协议要求将分组按次序递交给网络层）方式2： 不反馈否认帧NAK。发送端采用超
18、时机制。 发送端每发送一个数据帧就启动该帧计时器，当收到确认帧后，计时器复位；如果知道超时还没有收到确认帧，则重发该数据帧及后续的帧选择重传ARQ协议 回退N帧协议，当信道误码率较高时，对损坏帧和非损坏帧的重传非常的多，浪费带宽 目的：进一步提高信道利用率 方法：只重传出现差错的数据帧或者超时的数据帧 要求：在接收端要设置具有相当容量的缓存空间选择重发ARQ协议工作原理示意图 多个数据帧出错情况3.5 滑动窗口协议对于连续ARQ协议，采用了发送端不等待确认帧返回就可以连续发送帧，存在问题：1、当未被确认的数据帧数目太多时，只要有一帧出错，就有很多数据帧需要重传，增大了开销2、为了对发送出去的大
19、量未被确认的数据帧进行编号，每个数据帧的发送需要也要占用较多的比特数，又增大了开销滑动窗口协议：对发送端已发送出去但未被确认的帧的数目加以限制，在发送端和接收端分别设置发送窗口和接收窗口3.5.1发送窗口（发送端） 目的：对发送端进行流量控制 发送窗口大小Ws：在还没有收到应答帧的情况下，发送端最多可以连续发送数据帧的个数 发送序号：一般采用n位bit进行编号，若n=3，则编号为（07） 发送端只能连续发送窗口内的数据帧 每收到一个确认帧后，发送窗口的前后沿顺时针旋转一个号，并可以发送一个新的数据帧 若未应答帧的数目等于发送窗口大小时，便停止发送新的数据帧3.5.2 接收窗口（接收端） 目的：
20、用来控制可以接收哪些数据帧而不可以接收哪些帧 接收窗口Wr:只有当收到的数据帧的发送序号落入接收窗口内，才允许将该数据帧收下，否则，丢弃 若Wr1，意味着只能按顺序接收数据帧 若Wr较大，有可能会出现数据帧的失序应答帧丢失情况 应答帧被“篡改”情况：ACK-NAK 应答帧被“篡改”情况：NAK-ACK 3.5.3 重叠问题 在接收前后，接收窗口范围内的有效序号出现重叠避免重叠问题 为了避免重叠问题，接收窗口大小Wr=2n/2发送窗口的最大尺寸值 发送窗口大小Wr=2Td+Tf时：Cr约为100 当Ws*Tf1,接收窗口Wr=1 2、选择重发连续ARQ协议 发送窗口Ws1,接收窗口Wr1,且Wr
21、=Ws3.6 数据链路层协议(广域网) 按所传输信息的基本单位分：面向字符(BSC,ARPA,DLC，PPP， DDCMP)面向比特（HDLC,SDLC,ADCCP,LAPB,) 发展IBM：最早数据链路层协议SDLC（synchronous data link control同步数据链路控制）协议美国国家标准协会ANSI对其作了修改成为高级数据通信控制规程ADCCPISO将其修改成高级数据链路控制HDLCCCITT在HDLC基础上修改，作为链路访问规程LAP，后来又修改为LAPB作为X.25网的第二层协议IEEE将SDLC修改成LAN的LLC子层标准称为IEEE802.2 所有面向位的协议基
22、本原理相同，相互之间只所有面向位的协议基本原理相同，相互之间只是实现方法不同是实现方法不同高级数据链路控制HDLC 协议的目的是提供一种通信准则，满足计算机、终端之间数据通信以及计算机通信子网节点间的数据通信。 适用范围：计算机计算机、计算机终端、终端终端 三种类型的通信站：主站：主要功能是发送命令（包括数据），接收响应，负责整个链路的控制（如系统的初始、流控、差错恢复等）次站：主要功能是接收命令，发送响应，配合主站完成链路的控制复合站：同时具有主、次站功能，既发送又接收命令和响应，并负责整个链路的控制3.6.1 HDLC的链路构型 非平衡配置（主从配置）主站控制整个链路工作，主站发出的帧叫命
23、令；从站发出的帧叫响应。适合把智能和半智能的终端连接到计算机HDLC的链路构型 平衡配置复合站具有主站和从站的功能。地位平等。适合于计算机和计算机之间的连接 不支持多点平衡配置3.6.2 HDLC的基本操作模式 正常响应模式NRM适合于非平衡构型。只有当从站得到主站的许可（主站向从站发出探询）后，从站才能发起一次一帧或多帧数据的传输响应 异步响应模式ARM适用于点点式非平衡构型。从站不必等待主站的许可，就可发起一次传输。但主站和从站的地位不变 异步平衡模式ABM适合于复合站的平衡构型。双方具有同等能力，任何一个复合站可随时传输帧3.6.3 HDLC的帧的类型 信息帧（I帧）用来传输用户数据 监
24、控帧（S帧）用来传输控制信息（如流量和差错控制信息） 无序号帧（U帧）用来传输网络管理信息HDLC的帧结构 帧标志（flag） 定界符为7EH（零比特填充法） 地址域（address）1)使用不平衡方式传送数据时（采用NRM和ARM），地址字段总是写入从站的地址；2)使用平衡方式时（采用ABM），地址字段总是写入应答站的地址。3)有效地址为254个（通常为8位，可扩展到16位） 全1的8位地址表示广播（所有次站接收） 全0的8位地址是无效地址 数据域：任意比特串或字符串（有上限）I帧和U帧HDLC的帧结构 校验和（checksum） 循环冗余校验CRC，生成多项式，为透明传输插入的“0”不在校
25、验范围内HDLC帧的控制域 控制域：标识帧的类型和功能，使对方站执行特定的操作，是HDLC的关键字段，许多重要功能由此字段实现HDLC帧的控制域(信息帧) N(s)-发送序号 表示当前发送的信息帧的序号，使用滑动窗口技术，3位序号 N（r）-接收序号（确认序号） 约定：表示本站期望收到的帧的发送序号，而不是最后一个已收到的帧序号 它具有捎带确认功能 HDLC帧的控制域监控帧(48bit) HDLC进行询问示例：从站数据主站 HDLC进行询问示例：主站数据从站 HDLC帧的控制域无序号帧 3.7 因特网的数据链路层 因特网模型1：因特网中的网络互联（路由器之间是通过点到点来进行连接的） 因特网模
26、型2：因特网中家庭用户入网：用户通过拨号与ISP连接后，采用点到点方式连接因特网的点对点协议PPP 1992年，PPP：point-to-point protocol，RFC1661、RFC1662、RFC1663 1）PPP协议可以在同一条链路上同时支持多种网络层协议（IP,IPX)2）PPP协议能够在多种不同类型的链路上传输,并且对每中类型的点对点链路设置了最大传输单元MTU)支持远程分配地址)支持验证3）PPP协议不提供纠错，只进行检错，无序号，无流量控制，所以是不可靠的传输协议4）不支持多点传输，只支持全双工链路3.7.1 PPP3.7.1 PPP协议的三个组成部分协议的三个组成部分P
27、PP提供了串行点对点链路上传输数据报的方法，包含了以下几个部分：1、封装方法一个将IP数据报封到串行链路的方法。PPP既支持异步链路（无奇偶校验的8比特数据），也支持面向比特的同步链路 2、链路控制协议LCP(建立链路连接)负责建立、维护、配置及测试数据链路的连接。支持面向字节的和面向位的编码方法3、网络控制协议NCP(建立网络连接)PPP协议提供了一种机制使得通信双方的网络层实体能够通过协商知道或能够配置彼此的网络层地址。（在链路建立后，可以通过NCP分组来协商网络层选项的方法，协商的方法与所使用的网络层协议都是独立的）。3.7.2 PPP帧结构的字段描述 PPP帧结构类似与HDLC，长度为
28、整数个字节 帧标志flag，定界符为7EH1）在同步链路传输时：采用零比特填充法（路由器和路由器）2）在异步链路传输时：采用特殊的字符填充法（主机通过RS232和调制解调器连接到路由器） 若数据字段出现一个7EH，变成7DH和5EH 若数据字段出现一个7DH,变为7DH和5DH 若信息字段中出现ASCII码的控制字符（小于20H），则在该字符前面要加入一个0 x7D字节 地址域：始终为FFH，实际上，由于是点到点链路，通信两端无须知道对方的数据链路层地址PPP的帧结构的字段描述 控制域： PPP数据帧的控制域没有实际意义，按照协议的规定，通信双方将该字节的内容填充为0X03，PPP不提供流量控
29、制和差错控制，不提供确认 协议域：指明数据承载的是哪一种的分组 C021H,表明该帧是链路控制协议LCP信息帧 8021H，表明该帧是网络控制协议NCP信息帧 0020H，表明该帧是IP数据报信息帧 数据的部分最多可达一个商定的最大值。默认的最大长度为1500字节 帧校验：CRC3.7.3点对点PPP协议变迁状态图1、链路不可用阶段通信双方的两端检测到物理线路激活时，线路就进入建立状态2、链路建立阶段通过LCP开始协商一些选项，进行链路参数的配置3、验证阶段(可选） 缺省无需认证，多数情况需要两端设备经过认证才进入网络层协议阶段4、网络层协议阶段NCP配置网络层，分配IP地址，然后就进入可进行数据通信的打开状态5、网络终止阶段点对点PPP协议变迁状态图
