1、计算机网络（计算机网络（四四）关于数据链路层（关于数据链路层（1.基本原理）基本原理）信息科学与技术学院 学习目标!w 了解：数据链路层的设计问题w 掌握：数据链路层差错控制方法、循环冗余码编码原理w 掌握：数据链路层的功能w 掌握：基本数据链路协议w 掌握：停等协议、滑动窗口协议的工作原理w 掌握：面向比特型数据链路层协议实例 HDLC。w 了解：Internet中的数据链路层协议。前言：数据链路层的设计问题w 为什么需要数据链路层？w 物理层未解决的问题：n位流传输过程中不可避免会出现差错 （电磁干扰，线路问题）n数据收发之间的速率匹配问题（不同设备处理速度不同）最主要的作用是通过一最主要
2、的作用是通过一些数据链路层协议些数据链路层协议(即即链路控制规程链路控制规程),),在不太在不太可靠的物理链路可靠的物理链路上实现上实现可靠可靠的数据传输的数据传输.前言：数据链路层的设计问题前言：数据链路层的设计问题1.向网络层提供的服务向网络层提供的服务主机主机A主机主机BALTLNLDLPLALTLNLDLPL帧帧帧帧 帧帧 帧帧 帧帧 帧帧 帧帧 帧帧 帧帧 帧帧 帧帧 帧帧 帧帧 帧帧 帧帧 帧帧 帧帧 帧帧无确认的无连接服务无确认的无连接服务有确认的无连接服务有确认的无连接服务面向连接的服务面向连接的服务前言：数据链路层的设计问题前言：数据链路层的设计问题 2.成帧成帧w 涉及的问
3、题涉及的问题w 协议协议数据单元数据单元将上层将上层(网络层网络层)交下来的数据包按照所采用协议决交下来的数据包按照所采用协议决定的格式，封装成一定形式的帧；定的格式，封装成一定形式的帧；考虑接收双方的同步问题（即定界）；考虑接收双方的同步问题（即定界）；计算帧的校验和并放入帧中一起传送给接收方；计算帧的校验和并放入帧中一起传送给接收方；帧：在数据链路上交换数据的单位。帧：在数据链路上交换数据的单位。标标 志志字字 段段指明帧指明帧的开始的开始和结束和结束地址字段地址字段控制字段控制字段正文字段正文字段校验字段校验字段前言：数据链路层的设计问题前言：数据链路层的设计问题 2.成帧成帧w 字符计
4、数法字符计数法w 字符填充的首尾定界法字符填充的首尾定界法w 位填充的首尾定界法位填充的首尾定界法5 1 2 3 4 5 6 7 8 9 8 0 1 2 3 4 5 6 8 7 8 9 0 1 2 35 1 2 3 4 7 6 7 8 9 8 0 1 2 3 4 5 6 8 7 8 9 0 1 2 3计数值传输出错时导致收发双方不同步计数值传输出错时导致收发双方不同步.同步字同步字符法符法标志法标志法填充技术填充技术前言：前言：数据链路层的设计问题数据链路层的设计问题2.成帧成帧w 物理层编码违例法物理层编码违例法w 综合法综合法“0”“1”违例违例或或用用计数值确定帧尾计数值确定帧尾检查检查
5、帧定界符是否出现在应该出现的地方帧定界符是否出现在应该出现的地方计算校验和计算校验和前言：前言：数据链路层的设计问题数据链路层的设计问题 3.流量控制流量控制w 流量控制流量控制w 流量控制的特点流量控制的特点网络层实体控制从数据链路层接收数据的速率，据此，网络层实体控制从数据链路层接收数据的速率，据此，数据链路层要控制从同等实体接收数据链路层要控制从同等实体接收PDU的速率。的速率。限制发送方发限制发送方发送速度的一种送速度的一种机制。使发送机制。使发送速率不能超过速率不能超过接收方能处理接收方能处理的速率。的速率。流量控制必须是动态的流量控制必须是动态的必须有某种反馈机制必须有某种反馈机制
6、流量速度不仅与发方流量速度不仅与发方速度相关而且与网络速度相关而且与网络的当前拥挤程度有关的当前拥挤程度有关使发方了解收方使发方了解收方的当前处理能力的当前处理能力前言：前言：数据链路层的设计问题数据链路层的设计问题 4.差错控制差错控制w 顺序到达顺序到达指保证所有的帧最终都按正确的发送次序到达目的。指保证所有的帧最终都按正确的发送次序到达目的。检错和纠错检错和纠错检出传输中出现的差错；可能的话确定出错位置从检出传输中出现的差错；可能的话确定出错位置从而纠正错误。而纠正错误。确认方式确认方式计时器法计时器法计时器值的设定要保证一帧计时器值的设定要保证一帧到达对方并作处理后，相应到达对方并作处
7、理后，相应的确认帧返回。的确认帧返回。ACK肯定确认肯定确认NAK否定确认否定确认计时结合序号才能保证每一帧的正确次序。计时结合序号才能保证每一帧的正确次序。前言：前言：数据链路层的设计问题数据链路层的设计问题5.数据链路层协议的作用数据链路层协议的作用数据链数据链路协议路协议23数据链路进程数据链路进程路由选择进程路由选择进程路由器路由器A帧帧分组分组/包包2322 232路由器路由器B传输线传输线2322 223DL协议的作用就是使不可靠的协议的作用就是使不可靠的通信线路变得一定程度的好。通信线路变得一定程度的好。物理层:-物理链路 -比特流传输 -有差错的物理链路数据链路层:-数据链路
8、-帧传输 -无差错的数据链路 -数据链路层数据服务单元 -帧一、数据链路层概述w 数据链路层于物理层之上,属于低层。物理层传输的是比特流，单位是比特。w 数据链路层传输单位是帧，一帧一帧地处理。其工作是从物理层获取比特流，进行封装成帧、并对帧进行如透明传输、差错控制等处理，从而递交给上一层（网络层），同时也对网络层下传的数据进行处理，进而传给物理层。数据链路层传送的是帧数据链路层传送的是帧IP 数据报数据报1010 0110帧帧取出取出数据数据链路层链路层网络层网络层链路链路结点结点 A结点结点 B物理层物理层数据数据链路层链路层结点结点 A结点结点 B帧帧(a)(b)发送发送帧帧接收接收链路
9、链路IP 数据报数据报1010 0110帧帧装入装入一、数据链路层概述一、数据链路层概述 分组分组与帧的关系图示与帧的关系图示Relationship between packets and frames一、数据链路层概述一、数据链路层概述 数据链路层的简单模型数据链路层的简单模型局域网局域网广域网广域网主机主机 H1主机主机 H2路由器路由器 R1路由器路由器 R2路由器路由器 R3电话网电话网局域网局域网主机主机 H1 向向 H2 发送数据发送数据链路层链路层应用层应用层运输层运输层网络网络层层物理物理层层链路链路层层应用层应用层运输层运输层网络网络层层物理物理层层链路层链路层网络网络层层
10、物理物理层层链路层链路层网络网络层层物理物理层层链路层链路层网络网络层层物理物理层层R1R2R3H1H2从层次上来看数据的流动从层次上来看数据的流动一、数据链路层概述一、数据链路层概述数据链路层数据链路层的简单模型的简单模型局域网局域网广域网广域网主机主机 H1主机主机 H2路由器路由器 R1路由器路由器 R2路由器路由器 R3电话网电话网局域网局域网主机主机 H1 向向 H2 发送数据发送数据链路层链路层应用层应用层运输层运输层网络网络层层物理物理层层链路层链路层应用层应用层运输层运输层网络网络层层物理物理层层链路层链路层网络网络层层物理物理层层链路层链路层网络网络层层物理物理层层链路层链路
11、层网络网络层层物理物理层层R1R2R3H1H2仅从数据链路层观察帧的流动仅从数据链路层观察帧的流动一、数据链路层概述一、数据链路层概述数据链路层数据链路层协议在路由器中的位置协议在路由器中的位置Placement of the data link protocol一、数据链路层概述一、数据链路层概述数据链路层协议在路由器中的位置数据链路层协议在路由器中的位置数据链数据链路协议路协议23数据链路进程数据链路进程路由选择进程路由选择进程路由器路由器A帧帧分组分组/包包2322 232路由器路由器B传输线传输线2322 223DL协议的作用就是使不可靠的协议的作用就是使不可靠的通信线路变得一定程度的
12、好。通信线路变得一定程度的好。一、数据链路层概述一、数据链路层概述1.常用概念常用概念w 链路(link)：是一条无源的点到点的物理线路段，中间没有任何其他的交换结点。n一条链路只是一条通路的一个组成部分。w 数据链路(data link)：除了物理线路外，还必须有通信协议来控制这些数据的传输。若把实现这些协议的硬件和软件加到链路上，就构成了数据链路。n现在最常用的方法是使用适配器（即网卡）来实现这些协议的硬件和软件。n一般的适配器都包括了数据链路层和物理层这两层的功能。w结点（node）：网络中的主机（host）和路由器（router）称为结点。一、数据链路层概述一、数据链路层概述1.常用概
13、念常用概念w链路（link）：通信路径上连接相邻结点的通信信道称为链路。w数据链路（data link)：链路+实现通信协议的硬件和软件。w数据链路层协议：定义了一条链路的两个结点间交换的数据单元格式，以及结点发送和接收数据单元的动作。w端到端（end to end）与点到点（point to point）：n从源结点（source node）到目的结点（destination node）的通信称为端到端通信，通信路径（path）可能由多个链路组成。n在相邻结点间的一条链路上的通信称为点到点通信。w数据链路控制规程：为使数据能迅速、正确、有效地从发送点到达接收点所采用的控制方式。w早期的数据通
14、信协议曾叫作通信规程(procedure)。因此在数据链路层，规程和协议是同义语。w 虚拟数据通路，实际数据通路 一、数据链路层概述一、数据链路层概述1.常用概念常用概念 一、数据链路层概述一、数据链路层概述1.常用概念常用概念w 数据链路层像个数字管道 w 常常在两个对等的数据链路层之间画出一个数字管道，而在这条数字管道上传输的数据单位是帧。结点结点结点结点帧帧帧帧 一、数据链路层概述一、数据链路层概述2.数据链路层使用的信道类型数据链路层使用的信道类型w 数据链路层使用的信道主要有以下两种类型：n点对点信道点对点信道:这种信道使用一对一的点对点通信方式。（例如PPP、SLIP）n广播信道广
15、播信道:这种信道使用一对多的广播通信方式，因此过程比较复杂。广播信道上连接的主机很多，因此必须使用专用的共享信道协议来协调这些主机的数据发送。（例如以太网）一、数据链路层概述一、数据链路层概述3.数据链路层协议基本功能数据链路层协议基本功能w 链路管理数据在数据链路上的正常传输（建立、维护和释放）。w 帧同步：数据传输的单位为帧，定界与同步。也处理透明性问题。w 流量控制与顺序控制。w 差错控制：前向纠错、差错检测，检错重发。w 将数据和控制信息分开。w 透明传输。w 寻址。二、差错检测与校正二、差错检测与校正1.基本概念基本概念w 什么是差错？n在通信中接收端收到的二进制数位（码元）和发送端
16、实际发送的数据不一致。w 差错检测与校正：把差错控制在允许的范围内。w 差错控制的主要内容：n差错编码、反馈重传、超时重传、重复帧丢弃、定时器管理等。二、差错检测与校正二、差错检测与校正1.基本概念基本概念w 误码率：衡量物理信道的质量.w 差错控制编码：信息位(k)冗余位(r)w 检错码：自动发现差错w 纠错码：不仅能发现差错而且能够自动纠正w 编码效率R：码字中信息位所占的比例 R=k/(k+r)w 漏检率：信息位出错但是接收者无法了解到的概率的负若干次方来表示常常用接收的总码元数发生差错的码元数10 eP 二、差错检测与校正二、差错检测与校正2.差错与校正概念差错与校正概念w 出错的类型
17、n单个错：由随机的信道热噪声引起，一次只影响1位；n突发错：由瞬间的脉冲噪声引起，一次影响许多位，用突发长度表示突发错影响的最大数据位数。w 编码的类型n检错码：只能检测到数据传输发生了错误，但无法自行纠正，通常与反馈重传结合起来使用以便进行差错恢复；n纠错码：不权能够检测到数据传输发生了错误，而且能够自行纠正错误。二、差错检测与校正二、差错检测与校正2.差错与校正概念差错与校正概念w 码字（codeword）：由m比特的数据（消息）加上r比特的冗余（校验位）构成；w 有效编码集：由2m个有效码字组成；w 检错：当收到的码字为无效码字时检测出错误；w 海明距离（Hamming Distance
18、）：两个码字的对应位上取值不同的位数；w 纠错：将收到的无效码字纠正到距其最近的有效码字；w 检错码与纠错码的能力都是有限的。二、差错检测与校正二、差错检测与校正2.差错与校正概念差错与校正概念w 编码集的海明距离：编码集中任意两个有效码字的海明距离的最小值。w 检错能力：为检测出d比特错误，编码集的海明距离至少应为d+1；奇偶校验是能够检测出1比特错误的检错码。w 纠错能力：为纠正d比特错误，编码集的海明距离至少应为2d+1；海明码是能够纠正1比特错误的纠错码。二、差错检测与校正二、差错检测与校正2.差错控制与校正方法差错控制与校正方法w 差错控制：ARQ和FECnARQ（自动重传请求）lA
19、utomatic Request for Repeatl接收方检测错误，通知发送方重传l双向信道，发送方缓存发送的数据nFEC（前向纠错）lForward Error Correctionl接收方不仅可以检测错误，而且知道错误的位置，从而改正错误l采用纠错码，无需反向信道，无需重发，但编码效率低,纠错设备复杂 二、差错检测与校正！二、差错检测与校正！3.差错检测与校正和流量控制差错检测与校正和流量控制由于系统性能的不同，如硬件能力（包括由于系统性能的不同，如硬件能力（包括CPU，存储器等）和软件存储器等）和软件功能的差异，会导致发送方与接收方处理数据的能力有所不同。功能的差异，会导致发送方与接
20、收方处理数据的能力有所不同。流量控制的作用是使发送方所发出的数据流量，使其发送速率不要流量控制的作用是使发送方所发出的数据流量，使其发送速率不要超过接收方所能接收的速率。超过接收方所能接收的速率。流量控制的关键是需要有一种信息反馈机制，使发送方能了解接收流量控制的关键是需要有一种信息反馈机制，使发送方能了解接收方是否能接收到方是否能接收到存在各种不同的流量控制机制。如简单的停等协议，而滑动窗口协存在各种不同的流量控制机制。如简单的停等协议，而滑动窗口协议则将关于帧的确认与流量控制巧妙地结合在了一起。议则将关于帧的确认与流量控制巧妙地结合在了一起。w 流量控制的主要机制：n基于反馈的流量控制（）
21、n基于速率的流量控制二、差错检测与校正二、差错检测与校正4.常用的简单差错控制编码（奇偶校验码）常用的简单差错控制编码（奇偶校验码）w 奇偶校验码：增加冗余位使得码字中1的个数为奇数或者偶数，检错码n垂直奇偶校验n水平奇偶校验n水平垂直奇偶校验w 垂直奇偶校验：n发送的信息块分成定长为p位的若干段（一列）。n每段增加一个（奇偶校验）冗余位ri：I11 I12 贩 I1q I21 I22 贩 I2q2 Ip1 Ip2 贩 Ipq 贩 贩 贩 r1 r2 贩 rq 冗冗余余位位 信息位 发发送送顺顺序序 垂直奇偶校验 q1,2,.,i 21piiiiIIIr偶校验：q1,2,.,i 121piii
22、iIIIr奇校验：二、差错检测与校正二、差错检测与校正4.常用的简单差错控制编码（垂直奇偶校验）常用的简单差错控制编码（垂直奇偶校验）w 垂直奇偶校验n编码效率：n能力：l检测出每列（段）中所有奇数（1、3）个错l突发错误的漏检率为50%!l在发送和接收的过程中进行编解码w 水平奇偶校验：降低突发错误的漏检率n对各个信息段的相应位横向进行编码1ppR二、差错检测与校正二、差错检测与校正4.常用的简单差错控制编码（水平奇偶校验）常用的简单差错控制编码（水平奇偶校验）w 水平奇偶校验n编码效率：n能力：l各段同一位上的奇数个错l长度小于等于p的突发差错l编码和检测相比垂直校验而言实现要复杂一些p1
23、,2,.,i 21iqiiiIIIr偶校验：p1,2,.,i 121iqiiiIIIr奇校验：I11 I12 贩 I1q I21 I22 贩 I2q2 Ip1 Ip2 贩 Ipq 贩 贩 贩 r1 r2 rp 冗冗余余位位 信息位 发发送送顺顺序序 水平奇偶校验 贩 1qqR二、差错检测与校正二、差错检测与校正4.常用的简单差错控制编码（水平垂直奇偶校验）常用的简单差错控制编码（水平垂直奇偶校验）w 水平垂直奇偶校验1,1,21,1,12,11,11,121,1211,q1,2,.,j p1,2,.,i qpqqqpppqppjjjjpiqiiqirrrrrrrIIIrIIIr偶校验：I11
24、I12 贩 I1q I21 I22 贩 I2q2 Ip1 Ip2 贩 Ipq 贩 贩 贩 r1,q+1 r2 q+1 rp q+1 冗冗余余位位 信息位 发发送送顺顺序序 水平奇偶校验 贩 rp+1,1 rp+1,2 贩 rp+1,q rp+1,q+1 编码效率)1)(1(qppqR二、差错检测与校正二、差错检测与校正4.常用的简单差错控制编码（水平垂直奇偶校验）常用的简单差错控制编码（水平垂直奇偶校验）w 水平垂直奇偶校验能力n检测出：l所有3位或3位以下的错误、奇数位错l突发长度小于等于p+1的突发差错l很大一部分偶数位错：差错分布以致于某一行或者某一列有奇数个差错n部分纠错功能：l可以纠
25、正1比特错w信息块中恰好只有某一行和某一列有奇数位错时，可确定为该行和该列的交叉处二、差错检测与校正二、差错检测与校正4.常用的简单差错控制编码（水平垂直奇偶校验）常用的简单差错控制编码（水平垂直奇偶校验）10001010字符字符1b1b2b3b4b5b6b7check11001011字符字符211011010字符字符310101011字符字符410001010字符字符510001010字符字符611101010字符字符700100001校验校验字符字符w 水平垂直奇校验的例子二、差错检测与校正二、差错检测与校正4.常用的简单差错控制编码（海明码）常用的简单差错控制编码（海明码）1.海明码(1
26、)海明距离及意义两个码字中不同的位数的个数称为海明距离,简称H距离 1 0 0 0 1 0 0 1 1 0 1 1 0 0 0 1求H距离的方法主要有:异或运算海明距离的意义是:假如两个码字具有海明距离d,则需要d 个位差错才能将其中一个码字转换成另一个.H=3二、差错检测与校正二、差错检测与校正4.常用的简单差错控制编码（海明码）常用的简单差错控制编码（海明码）(2)海明码算法将码字数内的位从最左边开始按顺序依次编号,第1位是1号,第2位是2号,第n位是n号.编号为2的幂的位(1号位,2号位,4号位,8号位等)是校验位,其余的位填入m 位数据(2 r n+1).每个校验位的取值应使得包括自己
27、在内的一些位的集合符合规定的奇偶性.(主要用于奇偶性校验)1 2 3 4 5 6 7 8 9 10 11 12校验位校验位二、差错检测与校正二、差错检测与校正4.常用的简单差错控制编码（海明码）常用的简单差错控制编码（海明码）为了知道编号为K的数据位对哪些检测位有影响,将编号K 改写成2的幂的和(如:11=1+2+8,29=1+4+8+16),1个位只由扩展式中所示编号的位检测(编号为11的位,只能由1,2,8 检测位检测)由于在每个校验位的形成表达式中,除自身编号外,其余都是信息位的编号,因此只要信息位是确定的,校验位也可以唯一地确定.二、差错检测与校正二、差错检测与校正4.常用的简单差错控
28、制编码（海明码）常用的简单差错控制编码（海明码）w 由上图可看出,海明码的信息余量很大,因而编号效率低.w 例:根据海明编码方法,对ASCII字符Z(二进制编码是1011010),w 形成11位码字,要求简单地写出编码过程.并说明在传输过程中,w 有一位错的情况下,如何能够检查出是哪一位是错的?w 解:m=7,n=11,r=4w 编号:1=1,2=2,3=1+2,4=4,5=1+4,6=2+4,7=1+2+4,8=8,9=1+8,w 10=2+8,11=1+2+8w 于是有:(1)(3)+(5)+(7)+(9)+(11)w (2)(3)+(6)+(7)+(10)+(11)w (4)(5)+(6
29、)+(7)w (8)(9)+(10)+(11)被检测位：被检测位：数据位数据位检测位检测位二、差错检测与校正二、差错检测与校正4.常用的简单差错控制编码（海明码）常用的简单差错控制编码（海明码）1 2 3 4 5 6 7 8 9 10 11 0 0 1 0 0 1 1 1 0 1 0 编码编码码字码字最终的最终的海明码海明码为什么此为什么此处是处是1?1,2,4,8是校验位是校验位!其余位是信息位其余位是信息位.(8)(9)(10)(11)(1)(3)(5)(7)(9)(11)1 0 1 0 0 1 0 1 0 0奇数个奇数个1偶数个偶数个1采用偶采用偶检验哦检验哦!二、差错检测与校正二、差错
30、检测与校正4.常用的简单差错控制编码（常用的简单差错控制编码（CRC循环冗余码）循环冗余码）w 纠错码的编码效率较低，差错控制经常采用检错码ARQ。循环冗余码CRC（Cyclic Redundancy Code）是计算机网络中使用最为广泛的检错码，又称为多项式码。二、差错检测与校正二、差错检测与校正4.常用的简单差错控制编码（常用的简单差错控制编码（CRC循环冗余码）循环冗余码）w CRC的工作原理（1）w 将要发送的二进制数序列看成是只有0和1两个系数的一个多项式。n位的数据序列对应n-1次多项式。如：二进制数序列为“1010001”，7位的数据序列对应6次多项式：K(x)=x6+x4+1
31、w 选定除式G(x)，被选作除式的多项式称为生成多项式，以下三个多项式已成为国际标准nCRC-12：G(x)=x12+x11+x3+x2+x+1nCRC-16：G(x)=x16+x15+x2+1nCRC-CCITT：G(x)=x16+x12+x5+1 nCRC-32 G（x）=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1二、差错检测与校正二、差错检测与校正4.常用的简单差错控制编码（常用的简单差错控制编码（CRC循环冗余码）循环冗余码）w CRC的工作原理（2）w 将K(x)乘以 G(x)的最高幂次作为被除式，G(x)作多项式除式XrK(
32、x)=G(x)*商+R(x)（相应系数相除）。除法采用“加法不进位，减法不借位”的规则，即相当于异或操作R(x)作为冗余码，加在原传送数据后面:T(x)=XrK(x)+R(x)=G(x)*商+R(x)+R(x)=G(x)*商构成发送序列。接收方收到后，将接收序列用同样的生成多项式去除 T(x)/G(x)。若余式为零，则表示无差错；否则，说明传输过程中出现了错误。01100001 1101001010110011 01100001 1101001010110011 二、差错检测与校正二、差错检测与校正4.常用的简单差错控制编码（常用的简单差错控制编码（CRC循环冗余码）循环冗余码）CRC的例子（
33、1）要发送的二进制数序列为“1010001”，7位的数据序列对应6次多项式：K(x)=x6+x4+1 选定的生成多项式为：G(x)=x4+x2+x+1（最高次数为4，相当于10111）被除多项式为：K(x)x4 x10+x8+x4（相当于10100010000）二、差错检测与校正二、差错检测与校正4.常用的简单差错控制编码（常用的简单差错控制编码（CRC循环冗余码）循环冗余码）w CRC的例子（2）w 多项式除法后得到冗余码为1101，所以相应的数据发送序列为1010001 1101101000100000000101111011111011111010 0 00111 11101010111
34、10111110101011110111101111011111010101111011111011101二、差错检测与校正二、差错检测与校正4.常用的简单差错控制编码（常用的简单差错控制编码（CRC循环冗余码）循环冗余码）R0R1Rr-1信息输入端g1g2gr-11.)(12211xgxgxgxxGrrrCRC校验可以由软件或硬件来实现，现多采用超大规模集成电路芯片以硬件方式实现。校验可以由软件或硬件来实现，现多采用超大规模集成电路芯片以硬件方式实现。CRC硬件实现1)(24xxxxG111101R0R1R3信息输入端R21000101R0R1R2R3输入输出:110100001GG1110
35、1001110101100011111011001010101101010100100001000100000111101二、差错检测与校正二、差错检测与校正4.常用的简单差错控制编码（常用的简单差错控制编码（CRC循环冗余码）循环冗余码）二、差错检测与校正二、差错检测与校正4.常用的简单差错控制编码（常用的简单差错控制编码（CRC循环冗余码）循环冗余码）w CRC的检错能力（1）w 如果传输过程中出现差错：差错模式E(x)发送码字和接收码字的半加，其中1的位置对应变化了信息位的位置。w 若E(x)能被G(x)整除，则不能检测这样的错误E(x)/G(x)E(x)/G(x)T(x)/G(x)E(
36、x)/G(x)(T(x)0)(/)()()()()()()()()()(:)()(/)()()()()(有错时：，即无错时，记为xGxTxQxGxRxRxQxGxRxKxxTxRxGxKxxRxQxGxKxrrr二、差错检测与校正二、差错检测与校正4.常用的简单差错控制编码（常用的简单差错控制编码（CRC循环冗余码）循环冗余码）w CRC的检错能力（2）w 全部单个错 w 全部离散的二位错 w 全部奇数个错w 全部长度小于或等于r的突发错（r为生成多项式的最高幂次）w 以1-（1/2）r-1的概率检出长度为r+1位的突发错 w 以1-2-r的概率检出长度大于r+1位的突发错三、关于数据帧w 数
37、据链路层所传送的不再是原始的比特流，而应具备相应的语法和语义，以达到可靠传输的功能。w 数据链路层将从网络层接收的分组（Packet)组成帧后传送给物理层，通过物理层传送到对方的数据链路层。w 帧：数据链路层规定最小的数据传送逻辑单位w 数据链路层协议要规定帧的类型与格式类型包括控制信息帧与数据信息帧等，格式则规定帧所包含的域）。3.1 帧的基本组成w 帧定界（开始与结束）w 地址字段（用于寻址）w 帧类型（或长度/控制）字段w 数据w 帧校验字段（差错控制）帧的开始帧的开始地址地址帧类型或长度帧类型或长度数据数据帧校验帧校验帧的结束帧的结束上图只是帧的一般组成，不同的数据链路层协议所规定的帧
38、格式可能会与其存在微小的区别。3.2 帧的同步同步就是标识帧的开始与结束同步就是标识帧的开始与结束常用的帧同步方法：常用的帧同步方法：字符计数法字符计数法带字符填充的首尾界符法带字符填充的首尾界符法带位填充的首尾标志法带位填充的首尾标志法违例编码法违例编码法字符计数法5 1 2 3 4 5 6 7 8 9 8 0 1 2 3 4 5 65 1 2 3 4 7 6 7 8 9 8 0 1 2 3 4 5 6计数计数计数第第1帧帧5个字符个字符第第2 2帧帧5个字符个字符第第3 3帧帧8个字符个字符发送发送:接收接收:第第1 帧正确帧正确!第第2 帧不正确帧不正确!问题:出错之后,接收方与发送方不
39、同步!无法确定下一帧的开始位置.请求重传也没有用处,因为目的机器不知道应该回跳多少字符开始重传.7出错!11个字符计数?在帧头中使用一个字段来标明帧内的字符数，通常该字段称为帧长字段。首尾界符法w 每一帧以ASCII字符序列DLE STX开始，以DLE ETX结束。w DLE为Data Link Escape 的缩写，STX意味着Start of Text，ETX代表 End of Text。w 其缺点是成帧完全依赖于8位字符STX,A,B,GOOD,BYE,ETX A,B,GOOD,BYE 数据数据组帧组帧字符填充w 在首尾界符法中，由于数据中可能会出现DLE STX或DLE ETX，从而干
40、扰帧的正常定界w 字符填充法可用于解决上述问题。即发送端在数据中所遇到的DLE前再插入一个附加的DLE，而接收端则忽略两个连续DLE的前一个。DLE,STX,A,DLE,B,DLE,ETXDLE,STX,A,DLE,DLE,B,DLE,ETX网络层发出的数据网络层发出的数据经数据链路层填充后的数据经数据链路层填充后的数据字节填充图例(a)A frame delimited by flag bytes(b)Four examples of byte sequences before and after stuffing.首尾标记法w 每一帧使用一个特殊的位模式“01111110”作为开始和结束标
41、记。w 该位模式又称为flagw 位模式允许数据帧包含任意个数的比特，也允许每个字符采用任意比特的编码。Data 0111111001111110位填充w 在首尾标记法中，由于数据中可能会出现与标记相同的位串，从而干扰帧的正常定界w 位填充法可用于解决上述问题。即发送端在数据中若遇到5个连续的“1”时，则在其后自动插队入一个“0”。该技术简称“逢五1插0”；接收端则忽略5个连续的“1”后面的“0”，简称“逢五1删0”。(a)0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0(b)0 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1
42、1 1 1 0 1 0 0 1 0(c)0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 填充的位填充的位比特填充图例(a)The original data.(b)The data as they appear on the line.(c)The data as they are stored in receivers memory after destuffing.违例编码法n采用不可能出现在信息位中的比特编码作为帧的起始边界。l在物理层采用特定的比特编码方法时使用l曼彻斯特编码中电平的跳变表示1（低-高）和0（高-低）l高高和低低电平是违例
43、编码四、数据链路层协议 数据链路通信的简单模型AP1缓存AP2缓存帧帧数据链路发送方接收方主机A主机B完全理想化的数据传输完全理想化的数据传输基于以下两个假定w 假定1：链路是理想的传输信道，所传送的任何数据既不会出差错也不会丢失。w 假定2：不管发送方以多快的速率发送数据，接收方总来得及收下，并及时上交主机。(接收端向主机交付的数据速率永远不会低于发送端发送数据的速率)4.1 停等协议w 停止等待(stop-and-wait)协议是最简单但也是最基本的数据链路层协议。l具有最简单流量控制的数据链路层协议l仍保留假定1，但去掉假定2 w链路是理想的传输信道，即所传送的任何数据既不会出差错也不会
44、丢失w由接收方控制发送方的数据流(计算机网络中流量控制的一个基本方法)。停等协议算法w在发送结点：在发送结点：（1）从主机取一个数据帧；（2）将数据帧送到数据链路层的发送缓存；（3）将发送缓存中的数据帧发送出去；（4）等待；（5）若收到由接收结点发过来的信息(此信息的格式与内容可由双方事先商定好)，则从主机取一个新的数据帧，然后转到（2）。w在接收结点：在接收结点：（1）等待；（2）若收到由发送结点发过来的数据帧，则将其放入数据链路层的接收缓存；（3）将接收缓存中的数据帧上交主机；（4）向发送结点发一信息，表示数据帧已经上交给主机；（5）转到(1)。停等协议w 两种数据传输比较从从主主机机取取
45、数数据据上上交交主主机机DATA1DATA4DATA3DATA2结点结点A结点结点B 理想信道理想信道从从主主机机取取数数据据上上交交主主机机DATA1DATA2结点结点A结点结点BACKACK 具有简单流量控制具有简单流量控制的数据链路层协议的数据链路层协议从从主主机机取取数数据据上上交交主主机机DATA1DATAnDATA2结点结点A结点结点BDATAn+3DATAn+2DATAn+1NAKn+1 ACK 流水线协议流水线协议实用的停止等待协议w 前提：去掉两个假定，即传输数据的信道不能保证使所传的数据不产生差错，而且还需对数据的发送端进行流量控制。w 流量控制方法：等待发送w 差错控制：
46、发送方数据帧中加入校验码（CRC），由接收方检查；若正确，返回ACK，若出错，返回NAK；发送方根据收到的返回帧，决定发送新帧和重发。w 帧丢失处理：超时定时器；以序号标识数据帧 w 优点：简单w 缺点：信道利用率低，信道还远远没有被数据比特填滿数据帧在链路上传输的几种情况Data0Data1ACKACKAB时时间间送送主主机机送送主主机机Data0Data0ACKToutACK丢失丢失AB重传重传送送主主机机放放弃弃 (a)正常情况正常情况 (b)数据帧出错数据帧出错 (C)数据帧丢失数据帧丢失 (d)确认帧丢失确认帧丢失Data0Data0NAKACKAB出错出错重重传传送送主主机机重传重
47、传Data0Data0ACK丢失丢失ABTout送送主主机机实用停止等待协议的算法w在发送结点：在发送结点：(1)从主机取一个数据帧，送交发送缓存。(2)v(S)0。(发送状态变量v(S)初始化)(3)N(S)v(S)。(将发送状态变量值写入数据帧中的发送序号N(S)(4)将发送缓存中的数据帧发送出去。(这个数据帧的副本仍保留在发送缓存中)(5)设置超时计时器。(选择适当的超时重传时间tout)(6)等待。(等待以下(7)和(8)这两个事件中最先出现的一个)(7)收到确认帧ACKn，(这里隐含地表示已经通过了CRC的硬件差错检测)若n=1-v(S)，则：(已发送的数据帧被接收方确认)从主机取一
48、个新的数据帧，放入发送缓存：v(S)1-v(S)：（更新发送状态变量，使用下一个序号）转到(3)。否则，丢弃这个确认帧，转到(6)。（这表明已发送的数据帧没有被接收方确认）(8)若超时计时器时间到，则转到(4)。(重传已发送的数据帧)停止等待协议的算法w 在接收结点在接收结点：(1)v(R)0。(接收状态变量初始化，其数值等于欲接收的数据帧的发送序号(2)等待。(3)收到一个数据帧：(这里隐含地表示已经通过了CRC的硬件差错检测)若N(s)=v(R)，则执行(4)；(收到正确序号的数据帧)否则丢弃此数据帧，然后转到(6)。(丢弃的帧就是重复帧)(4)将收到的数据帧中的数据部分送交上层软件。(5
49、)v(R)1-v(R)。(更新接收状态变量，准备接收下一个数据帧)(6)nV(R)；发送确认帧ACKn，转到(2)。(期望接收n号数据帧，在它之前的帧收到了)停止等待协议的算法停止等待协议的算法V(S)=0从主机取一帧N(S)=V(S)将帧送缓冲区从发送缓冲区取出帧并发送设置超时记时器tout应答到？ACK/NAK？V(S)=(1-V(S)超时？ACKNAKNNYY发送方V(R)=0帧收到？接收帧并作差错校验结果正确？N(S)=V(R)?将收到的帧中的数据部分送主机V(R)=(1-V(R)发NAK发ACK丢弃此帧N（重复帧）YYYNN接收方停止等待协议中数据帧和确认帧的发送时间关系 ABDAT
50、ADATAACK传播时延 tp处理时间 tpr确认帧发送时间 ta传播时延 tp处理时间 tprtT时间两个成功发送的数据帧之间的最小时间间隔数据帧的发送时间tf设置的重传时间tout停等协议的信道利用率发送方接收方Ack帧数据帧2RL/B时间T(sec)B为信道容量(b/s)R为单程传播延迟时间(s)L为数据帧长度(bits)U为信道利用率RBLLRBLBLU22/停等协议在开始传输一个数据帧到确认回来这一段时间里必须等待，传播时间远大于传输时间的时候会带来很大的浪费。4.2 Go-back-N连续ARQ协议w 工作原理：发送方发完一帧后，不必停下来等待对方的应答，可以连续发送若干帧；如果在
