第4章 数据链路控制

《第4章 数据链路控制》由会员分享，可在线阅读，更多相关《第4章 数据链路控制（45页珍藏版）》请在金锄头文库上搜索。

1、第四章 数据链路控制,数据链路层定义和功能 差错控制 流量控制 常用的数据链路层协议,为什么要设计数据链路层？,在原始的物理传输线路上传输数据信号是有差错的，存在一定的误码率； 设计数据链路层的目的就是如何在有差错的线路上，进行无差错传输。向网络层提供高质量的服务。 从网络参考来看，物理层之上的各层都有改善数据传输质量的要求，数据链路层是重要的一层。,4.1 定义和功能,要解决的问题：如何在有差错的线路上，进行无差错传输。 ISO关于数据链路层的定义：数据链路层的目的是为了提供功能上和规程上的方法，以便建立、维护和释放网络实体间的数据链路。 数据链路：从数据发送点到数据接收点（点到点 poin

2、t to point）所经过的传输途径。,虚拟数据通路，实际数据通路,分组和帧的关系,二、数据链路层基本功能,数据链路控制规程 为使数据能迅速、正确、有效地从发送点到达接收点所采用的控制方式。 数据链路层协议应提供的最基本功能： 数据在数据链路上的正常传输（建立、维护和释放） 帧定界（帧同步） 差错控制 流量控制 寻址,数据链路层协议的位置,帧,分组,帧,分组,数据链路连接,数据链路层为网络层提供三种基本服务： 无确认无连接服务 由上层完成差错控制，适合于误码率低、实时性要求高的场合，如大部分有线局域网。 有确认无连接服务 进行简单的差错控制。适用于不可靠的信道，如无线网。 面向连接确认服务

3、在发送前需要建立连接，保证了帧的正确按序传输，适合于可靠性要求较高的场合。适合于大多数广域网。,应答方式,正向应答: 只对正确的信息应答。 负向应答: 只对错误的信息应答。 双向应答: 既对正确的信息应答，也对错误的信息应答。 问题1：在数据链路层，最常采用哪种应答方式？ 问题2：在数据传输过程中，数据会出现哪些情况？,正向应答工作方式,A0,D0,D1,A1,D0,D0,A0,D1,A1,D1,启动 计时器,计时器 超时,启动 计时器,计时器 超时,D0,A0,D1,A1,D1,A1,(1) 正常的数据传送 （2）数据帧丢失及出错 （3）应答帧丢失,4.2 成帧（Framing）,将比特流分

4、成离散的帧，并计算每个帧的校验和。 成帧方法： 1）字符计数法 在帧头中用一个域来表示整个帧的字符个数 缺点：若计数出错，对本帧和后面的帧有影响。 因此很少采用。,成帧（2）,2）带字符填充的首尾字符定界法 用DLE STX标示帧的开始 用DLE ETX标示帧的结束 用DLE DLE标示传送数据信息中的DLE 例如：信息DLE STX A DLE B DLE ETX在网络中传送时表示为：DLE STX DLE DLE STX A DLE DLE B DLE DLE ETX DLE ETX 缺点：局限于8位字符和ASCII字符传送，也不被普遍采用。,成帧（3）,3）带位填充的首尾标记定界法 帧的

5、起始和结束都用一个特殊的位串“01111110”，称为标记(flag) “0”比特插入删除技术，在传送的数据信息中每遇到5个连续的1在其后加0 例如：0110111111011111001在网络中传送时表示为： 0111111001101111101011111000101111110 4）物理层编码违例法 只适用于物理层编码有冗余的网络，如曼彻斯特编码 注意：在很多数据链路协议中，使用字符计数法和一种其它方法的组合。,4.3 差错控制,差错出现的特点：随机，连续突发（burst） 差错产生的原因 信道的电气特性引起信号幅度、频率、相位的畸变； 信号反射； 串扰； 闪电、大功率电机的启停等。

6、出错情况 帧（包括发送帧和响应帧）出错 帧（包括发送帧和响应帧）丢失,差错控制的目的 保证帧正确，按序送交上层。在接收方能够判断接收的数据是否正确，若错误还可能要恢复错误。 差错控制的方法 自动纠错机制 检错反馈重发机制,差错控制的方法,纠错码和检错码,码字codeword 一个帧包括m个数据位，r个校验位，称为n 位码字（n=m+r）。,纠错码 error-correcting code 加入了足够多的冗余位，使接收方不仅知道有差错发生，并知道哪些位发生差错。 检错码 error-detecting code 加入了冗余位，使接收方知道有差错发生，但不知道什么差错，然后请求重发。,海明定理,

7、海明距离 两个编码的海明距离：两个编码不相同位的个数。 编码方案的海明距离：编码方案中任两个编码海明距离的最小值。 例：0000000000 与0000011111的海明距离为5,海明定理 为检测d位错，编码方案的海明距离应至少为d+1； 当发生d位错时，不会由一种合法编码变为另一种合法编码。 为纠正d位错，编码方案的海明距离应至少为2d+1； 当发生d位错时，出错编码仍然最接近于原始的正确编码。,差错码举例,奇偶校验码 在数据后填加一个奇偶位（parity bit） 例：使用偶校验（“1”的个数为偶数） 10110101 101101011 10110001 101100010 若接收方收到

8、的字节奇偶结果不正确，就可以知道传输中发生了错误。 增加奇偶校验位后海明距离由1变为2，因此可以检查出一位二进制位的差错,循环冗余码 (CRC),循环冗余码（CRC码，多项式编码） 110001，表示成多项式 x5 + x4 + 1 生成多项式G(x) 发方、收方事前约定； 生成多项式的高位和低位必须为1 生成多项式必须比传输信息对应的多项式短。 CRC校验基本思想： CRC码（即校验和）加在帧尾，使带CRC码的帧的多项式能被G(x)除尽；接收方接收时，用G(x)去除它，若有余数，则传输出错。,设G(x)为 r 阶，在帧的末尾加 r 个0，使帧为 m + r位，相应多项式为xrM(x)； 按模

9、2除法用对应于G(x)的位串去除对应于xrM(x)的位串； 按模2减法从对应于xrM(x)的位串中减去余数（等于或小于r位），结果就是要传送的带校验和的多项式T(x)。,CRC码计算算法,CRC的检错能力 发送：T(x)；接收：T(x) + E(x)； 余数(T(x) + E(x) / G(x) = 0 + 余数(E(x) / G(x) 若 余数(E(x) / G(x) = 0，则差错不能发现；否则，可以发现。 四个多项式已成为国际标准 CRC-12 = x12 + x11 + x3 + x2 + x + 1 CRC-16 = x16 + x15 + x2 + 1 CRC-CCITT = x1

10、6 + x12 + x5 + 1 CRC-32= X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X+1 硬件实现CRC校验。,循环冗余校验法CRC码计算算法,检验和(checksum)算法,检验字段初值置0； 数据拆分成与检验字段等长的分片，不足部分补0； 将所有分片逐位取反，并连续累加，丢弃最高进位； 计算结果置入检验字段； 接收段执行相同的过程，并将计算结果和传输过来的检验和进行比较以决定数据是否出现差错； 适用于高层协议，如IP、TCP、UDP等；,检验和算法举例,待传输数据为：10010100,01110110,1100 计算过程 (10

11、010100)+(01110110)=11110100 11110100+(11000000)=00110011 带检验和的传输数据是 10010100,01110110,1100 00110011,4.4 流量控制,假设 单工传输 发送方无休止工作（要发送的信息无限多）； 接收方无休止工作（缓冲区无限大）； 发送数据的速率低于接收数据的速率； 通信线路（信道）不损坏或丢失信息帧（无错）。 工作过程 发送程序 取数据，构成帧，发送帧； 接收程序 等待，接收帧，送数据给高层。,单工停等协议（理想情况）,（a）简单停等协议；（b）带流量控制停等协议,增加约束条件：接收方不能无休止接收。 例如：缓冲

12、区数量有限，接收速率比发送速率低等。 解决办法： 接收方每收到一个帧，给发送方回送应答。发送方收到应答前不发送后续帧。 工作过程 发送程序 取数据，成帧，发送帧，等待应答帧； 接收程序 等待，接收帧，数据送高层，发送应答帧。,单工停等协议（无错情况）,数据帧在链路上传输的可能情况,增加约束条件：信道有差错，信息帧可能损坏或丢失。 解决方法 常使用正向应答+重发机制来解决差错控制。 数据序号采用循环序号机制。 应答帧的两种方式： 单帧应答：应答序号为某一个正确帧的序号 成批应答：应答序号为下一个期望接收的序号 通常采用附载应答方式：将数据帧携带应答信息的通信方式称为附载应答。可以把应答帧的序号加

13、在信息帧中一并发送，以提高效率。,单工停等协议（有错情况）,有噪声信道的单工停等协议示意图,停等协议效率,连续ARQ协议,工作原理 连续停等协议是指不需要收到应答帧就可连续不断的发下面的帧 出错后处理 全部重发流水线协议 当一帧出错时，需重发出错帧之后的所有帧； 接收方的缓冲区数量只需要一个。 选择重发流水线协议 当一帧出错时，只重发出错帧； 接收方的缓冲区数量足够多。,连续ARQ协议的工作原理,滑动窗口协议,滑动窗口协议是对连续停等协议的改进，它能够控制已发送但未确认的数据帧的个数（滑动窗口的大小）。 发送窗口 窗口尺寸：允许连续发送未应答帧的个数 数据允许发送条件：上界下界 窗口尺寸 窗口

14、滑动的条件 窗口上界移动：发送数据帧； 窗口下界移动：收到应答帧,滑动窗口协议（接收窗口）,接收窗口 窗口尺寸：允许连续接收未处理帧的个数 数据允许接收的条件：数据序号落在接收窗口中 窗口滑动的条件 发送应答帧后上下界同时移动,窗口大小与序号关系,出错全部重传 WT WR ，WR =1 WT 2n-1 选择性重传 WT = WR WT 2n-1,Internet中的数据链路层,点到点通信的两种主要情形： 路由器到路由器（router-router leased line connection） 通过modem拨号上网，连到路由器或接入服务器（dial-up host-router connec

15、tion）,SLIP协议,SLIP Serial Line IP 1984年，Rick Adams提出，RFC1055，发送原始IP包，用一个标记字节（0xC0）来定界，采用字符填充技术； 新版本提供TCP和IP头压缩技术，RFC 1144 存在的问题 不提供差错校验 只支持IP IP地址不能动态分配 不提供身份认证 多种版本并存，互连困难,PPP（Point-to-Point Protocol）协议,RFC 1661，RFC 1662，RFC 1663 提供差错校验、支持多种协议、允许动态分配IP地址、支持认证等。 以帧为单位发送，而不是原始IP包； 包括两部分 链路控制协议LCP（Link

16、 Control Protocol） 建立、配置和测试多种物理层服务：modem，HDLC串线，SDH/SONET，以太网等 网络控制协议NCP（Network Control Protocol） 建立、配置不同网络层协议,标记域：01111110，字符填充； 地址域：11111111 控制域：缺省值为00000011，表示无序号帧，缺省情况下，PPP不提供使用序号和确认的可靠传输；但是在不可靠线路上，也可使用有序号的可靠传输。 协议域：指示净负荷中是何种包，比如IP，IPX等。缺省大小为2个字节。 净负荷域：变长，缺省为1500字节； 校验和域：2或4个字节,PPP的帧格式,PPP工作过程（简单状态图）,