计算机网络教程.ppt

1、第三章 数据链路层,数据链路层功能 差错检测和纠正 数据链路协议 协议描述与验证 链路通信协议举例, 3.1 数据链路层功能,基本功能：,将物理层提供的原始的传送比特流的可能出错的物理连接改造成为逻辑上无差错的数据链路。 最基本的服务就是将源机器网络层来的数据可靠地传输到相邻节点的目标机网络层 。, 3.1 数据链路层功能(续),要完成的特定功能： 主要有如何将比特组合成帧（frame） 处理传输中出现的差错 链路管理即管理数据链路层连接的建立、维持和释放，调节发送方的发送速率不至于使较慢的接收方不能承受,3.1.1 帧同步,字节计数法 字符填充法 比特填充法 违例编码法,3.1.1 帧同步(

2、续),1.字节计数法,一个字符流(a) 无差错(b)有一个差错,3.1.1 帧同步(续),2.字符填充的首尾定界符法,(a) 有标志字节作为分界的帧 (b) 4个字节填充前后的字节序列的例子,3.1.1 帧同步(续),3.比特填充的首尾标志法,(a) 原始的数据 (b) 线路上的数据 (c) 删除填充之后存储在接收方存储器中的数据,3.1.1 帧同步(续),4.违例编码法,在物理层采用特定的比特编码方法时采用。 如曼彻斯特编码方法中，将数据比特1编码成高-低电平对，而将数据比特0编码成低-高电平对。高-高电平或低-低电平对在这里是违例的，可以借用这些违例编码的序列来界定帧的开始和结束。,3.1

3、.2 差错控制,由差错控制码产生的校验和可以检查出一帧在传输中是否发生了错误。一旦检查出错误后，通常采用反馈重发的方法来纠正错误。 实现复杂一点的机制，要用： 保留己发的帧：以便出错后重发 计时器 (timer)：避免无限等待 帧编号 ：保证每帧最终都能正确地交付给接收方网络层一次,3.1.3 流量控制,流量控制处理的是发送方发送能力大于接收方接收能力的问题，其实际是要控制发送方的数据流量。 数据链路层控制的是相邻两节点间数据链路上的流量，以后再运输层中讲的是控制从源端到目标端间的端对端流量。,3.1.4 链路管理,无确认的无连接服务 有确认的无连接服务 正向应答 反向应答 双向应答 有确认的

4、面向连接服务,3.2差错检测和纠正,为什么需要差错检测？,有如下原因造成信号幅度、频率和相位的衰减或畸变（又称为失真）： 线路本身电气特性造成的随机噪声(热噪声)影响 电信号在线路上产生反射造成的回音效应 相邻线路间的串扰以及各种外界因素（如大气中闪电、开关的跳火、外界强电流磁场的变化和电源的波动等）,3.2 差错检测和纠正(续),差错： 数据通信中，前面的原因就会造成接收端收到的二进制数位（或称为码元）和发送端实际发送的二进制数位不一致 什么是差错检测与校正？ 在实用的通信系统中一定要能发现（检测）这种差错。 能采用措施纠正（校正），把差错控制在所能允许的尽可能小的范围内。,3.2 差错检测

5、和纠正(续),传输差错的特性 常用的检差码循环冗余码 海明码,3.2.1 传输差错的特性,噪声分类： 信道所固有的，持续存在的随机热噪声。 可引起随机性差错 由于外界特定的短暂原因所造成的冲击噪声。 可引起突发性差错 噪声比较： 随机错通常较少 冲击噪声的幅度可以相当大 ，它是传输中产生差错的重要原因,3.2.1 传输差错的特性(续),Pe误码率,衡量一个信道质量的重要参数是误码率， 通常用10的负若干次方来标志信道的误码率Pe。,3.2.1 传输差错的特性(续),差错控制编码的原理：,信息位：要发送的数据 冗余位：在向信道发送之前，先按照某种关系加上一定的冗余位 发送与接收的过程： 发送时：

6、信息位+冗余位构成码字发送； 接收时：收到码字后查看信息位和冗余位，并检查它们之间的关系（校验过程），以发现传输过程中是否有差错发生。,3.2.1 传输差错的特性(续),差错控制编码分类：,检错码:能自动发现差错的编码 纠错码:不仅能发现差错而且能自动纠正差错的编码,3.2.1 传输差错的特性(续),衡量编码性能的参数 编码效率R :就是码字中信息位所占的比例。 若码字中信息位为k位，编码时外加冗余位为r位，则编码后得到的码字长为n = k + r位。,判定规律：编码效率越高，即R越大，则信道中用来传送信息码元的有效利用率就越高。,3.2.1 传输差错的特性(续),差错控制基本形式,(1)自动

7、请求重发ARQ （Automatic ReQuest for Repeat),只需少量冗余码就能获得很低的误码率，检错效果较好。但必须有反馈信道，信道干扰大时，效率会降低。,3.2.1 传输差错的特性(续),(2)前向纠错FEC (Forward Error Correction),无需反馈信道，能用于单向通信，但FEC差错控制码与信道的差错统计特性有关，传输效率不高。,3.2.1 传输差错的特性(续),除非在单向传输或实时要求特别高（FEC由于不需要重发，实时性较好）等场合外，数据通信中使用更多的还是ARQ差错控制方式。 也可以将上述两者混合使用，即当码字中的差错个数在纠正能力以内时，直接进

8、行纠正；当码字中的差错个数超出纠正能力时，则检出差错令其重发来纠正差错。,3.2.2 常用的检错码CRC,1.奇偶校验码,(1)偶校验,奇偶校验码是通过增加冗余位来使得码字中“1”的个数保持奇或偶数的编码方法。 如信息组中各码元为I1,I2,I3,I4, ,In， 则发送的信息组码元是I1,I2,I3,I4, ,Inr,(2)奇校验,3.2.2常用的检错码(续),只能检测出每个信息组中奇数个码元错，检测不出偶数个码元错。,编码效率为：,3.2.2常用的检错码(续),能边发送边产生冗余位，同时也能边接收边校验。能发现每列中的奇数位错，对突发错误的漏检率接近50%。,编码效率为：,发送顺序,(3)

9、垂直奇偶校验,3.2.2常用的检错码(续),发送顺序,能发现所有长度小于等于P的突发性错及水平方向的奇数个错，但发送和接收必须要等待整块信息到齐后才能进行。,编码效率为：,(4)水平奇偶校验,3.2.2常用的检错码(续),发送顺序,能发现所有3位及3位以下的错误、奇数位错和大部分偶数位错，能发现所有突发长度小于等于p+1的突发性错，并具有一位的纠错能力。,编码效率为：,(5)水平垂直奇偶校验,3.2.2常用的检错码(续),水平垂直奇偶校验不仅可检错，还可用来纠正部分差错。 垂直奇偶校验有时又称为纵向奇偶校验 水平奇偶校验有时又称为横向奇偶校验 水平垂直奇偶校验则又称为纵横奇偶校验,3.2.2常

10、用的检错码(续),2.循环冗余码(CRCCycle Redundancy Check) 又称为多项式码。这是因为任何一个由二进制数位串组成的代码都可以和一个只含有0和1两个系数的多项式建立一一对应的关系。,3.2.2常用的检错码(续),假设信息流长度为k位，冗余流长度为r位 ，则发送的信息是k位信息位后面再加上r位冗余位，即 ：T(x)=Xr*K(x)+R(x) 由于R(x)是Xr*K(x)除以G(x)的余数， 即：Xr*K(x)=G(x)*Q(x)+R(x) 接收方得：T(x)= G(x)*Q(x)+R(x)+R(x) 所以，T(x)= G(x)*Q(x),3.2.2常用的检错码(续),例：

11、K(x)= X6+X4+X0，G(x)= X4+X2+X1+X0，求R(x)。,X4* K(x)= X10+X8+X4，即比特流为10100010000,1,11010,0,0,1,11010,1,1,1,11010,11010,1101,余数为1101，所以R(x)= X3+X2+X0,1,11011,0,0,1,11001,1,1,1,11100,10111,0,3.2.2常用的检错码(续),G(x)有一些特征：,若G(x)含有(x+1)因子，可检测出所有奇数位错； 若G(x)不含有x因子，即G(x)中含有常数项1，就能检测出所有突发长度小于等于r的突发性错； 若G(x)不含有x因子，且对

12、任何0en-1的e，除不尽xe+1，则能检测出所有的双错； 若G(x)不含有x因子，则对突发长度为r+1的突发错误的漏检率为2-(r-1)； 若G(x)不含有x因子，则对突发长度大于r+1的突发错误的漏检率为2-r。,3.2.2常用的检错码(续),CRC-12：G(x)=X12+X11+X3+X2+X+1 CRC-16：G(x)=X16+X15+X2+1（IBM公司） CRC-CCITT：G(x)=X16+X12+X5+1 CRC-32：G(x)=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7 +X5+X4+X2+X+1,若适当选取G(x)，使其含有（x+1）因子、

13、常数项不为0、且周期大于等于n，那末，由此G(x)作为生成多项式产生的CRC码可检测所有的双错、奇数个错和突发长度不大于r的突发性错及（1-2-(r-1)）的突发长度为r+1的突发错和（1-2-r）的突发长度大于r+1的突发性错。,几种常用的CRC生成多项式：,3.2.4 循环冗余码(续),G(x)=Xr+gr-1Xr-1+gr-2Xr-2+g1X+1,除以G（x）的运算用移位寄存器和半加器来实现的硬件编码图：,3.2.2常用的检错码(续),例：K(x)= X6+X4+X0，G(x)= X4+X2+X1+X0，要求画出硬件编码器图，并根据该编码器求出冗余信息R(x)。,输入 L R0 R1 R

14、2 R3 输出 初始化 0 0 0 0 1 1 1 1 1 0 1 0 0 0 1 1 1 0 1 0 0 0 1 1 1 0 1 1 1 1 1 0 0 1 1 0 0 1 0 0 1 1 0 1 0 0 1 1 1 0 1 1 1 0 0 1 0 1 1 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 1,3.2.3 常用的纠错码海明码,1.正反码,一种简单的能够纠正差错的编码，其中冗余位的个数与信息位个数相同。冗余位与信息位或者完全相同或者完全相反，由信息位中“1”的个数来决定。,如信息有K位，冗余位为R位，则 ：,3.2.3 常用的纠错码(续),接收方的校验过程：,

15、再根据检验码的情况来判断传输中是否有错：,全“0” 无错 只有一个“0” 信息位有一位错,位置对应于检验码中“0”位置 只有一个“1” 冗余位有一位错,位置对应于检验码中“1”位置 其它情况有两位以上差错,3.2.3 常用的纠错码(续),例：发送0101101011，在下列情况下判断接收方收到数据正确与否？,收到比特流,0101101011 1101101011 0101101010 1101111011 1101011010,其中信息位,合成码,校验码,结论,信息位中1个数,01011,00000,奇数,00000,传输正确,11011,10000,偶数,01111,第1信息位错,01011

16、,00001,奇数,00001,第5冗余位错,11011,00000,偶数,11111,两位以上出错,11010,00000,奇数,00000,传输正确,3.2.3 常用的纠错码(续),正反码能检测出全部2位差错和大部分2位以上的错，具有一位的纠错能力。 编码效率较低，只能用于信息位较短的场合。 编码效率为:50%,3.2.3 常用的纠错码(续),2.海明码(Hamming) 在偶校验中,信息位是n位(anan-1a1),加上一位偶校验a0 ,其中：,接收端，监督关系式为（S称为检验因子）:,如果数据位有n位，冗余位有r位，接收方会收到n+r位信息。要使得接收方能纠正一位差错，就必须能分辨出n

17、+r+1种情况。而r位冗余位能表达2r种情况，因此n和r一定要满足:,3.2.3 常用的纠错码(续),将码字每一位字左至右进行编号，最左边为第一位。 凡编号为2的乘幂的位（1、2、4、8等）都是冗余校验位，其余是数据位。 将每个数据位的编号展开成2的乘幂之和，该数据位只由展开式中的校验位校验。 每个校验位连同其所负责的所有数据位一起构成偶校验。,编码构成：,3.2.3 常用的纠错码(续),例：对a的ASCII码1100001构成海明码。,解：n=7，因此r要为4,构成海明码后一共为11位。 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 1+2 1+4 2+4 1+2+4

18、 1+8 2+8 1+2+8,监督关系式为：,冗余位为：,3.2.3 常用的纠错码(续),对接收方来说，利用监督关系式对收到的数据进行运算，得到校验因子S0S1S2S3，再根据下表进行判断。,3.2.3 常用的纠错码(续),信息位越长，编码效率就越高，但不能适用于数据传输中突发性差错的控制。,编码效率为：R=n/(n+r),为了能让海明码用于检测数据传输中突发性差错，可以采用和水平奇偶校验码相类似的水平海明码。,特点：, 3.3数据链路协议,停等协议 顺序接收管道协议 选择重传协议 流量控制和滑动窗口机制,3.3.1 停等协议(Stop and Wait),3.3.1 停等协议(续),ACK,

19、ACK,1.正常情况：,3.3.1 停等协议(续),超时,ACK,2.数据帧丢失：,3.3.1 停等协议(续),NAK,ACK,3.数据帧出错：,3.3.1 停等协议(续),ACK,4.应答帧丢失 ：,3.3.1 停等协议(续),5.停等协议的信道利用率,假设信道容量为B(bps)，帧长为L(bits)，所以一帧的实际发送时间为L/B，如果信号的传播时间为R(s)，则其信道利用率为：,(L/B)/(L/B+2R)=L/(2RB+L),3.3.1 停等协议(续),设帧内有效数据长度为D(bits)，帧头和帧尾长度为H(bits)，等待ACK超时间隔为T(s)，数据帧和ACK帧出错以及丢失的概率分

20、别为P1和P2。,则每个数据帧不能正确发送和收到ACK的概率为： P=1-(1-P1)(1-P2) 最终发送成功所需的平均发送次数为:,所以平均重传次数为:,3.3.1 停等协议(续),总的时间为：,信道的有效利用率为：,超时间隔必须满足TH/B+2R,为使U最大,可取T= H/B+2R,得:,3.3.1 停等协议(续),若进一步假定信道的比特误码率是E，且各比特间相互独立，则1-P1=(1-E)L，1-P2=(1-E)H ，代入,令UD=0，可求到最佳帧长度Dopt：,由于通常E-0，所以可得 ：,3.3.1 停等协议(续),6. 停等协议的捎带确认,3.3.2 顺序接收管道协议,使用管道协

21、议： 可以提高信道的有效利用率，就要允许发送方不等确认帧返回就再连续发送若干帧 。 由于允许连续发出多个未被确认的帧，帧号就不能仅采用一位（只有0和1两种帧号），而要采用多位帧号才能区分 。 凡是被发送出去尚未被确认的帧都可能出错或丢失而要求重发，因而都要保留下来。这就要求发送方有较大的发送缓冲区保留准备重发的帧。,3.3.2 顺序接收管道协议(续),出错,被数据链路层丢弃的帧,又称“回退n”（go back n）,帧号字段的位数m要满足：,3.3.2 顺序接收管道协议(续),回退n的缺陷：允许已发送未被确认的帧越多，可能要退回来重发的帧也越多 改进：发送窗口 为了控制发送方的发送速度以及受发

22、送缓冲区大小的制约等因素都要求对发送方已发出但尚未经确认的帧的数目加以限制，这个数目就是“发送窗口”。 落在这个窗口内的帧号就是等待接收返回的Ack信息的帧号。由于帧号只有有限的位数，到一定时间后就又反复循环了。,3.3.3 选择重传(selective repeat)协议,出错,暂存不送主机,将2-6送主机,针对回退n法的缺点作出改进，若某一帧出错后，接收方对后面送来的正确的帧先收下，放在一个缓冲区，同时要求发送方重传出错的帧，一旦收到后把原先暂存在缓冲区的其余帧一起按正确顺序送往主机。,3.3.3 选择重传协议 (续),选择重传协议的优点： 在某帧出错时减少了后面所有帧都要重传的浪费 但接

23、收方要有一个足够大的缓冲区来暂存未按顺序正确接收到的帧,3.3.4 流量控制的滑动窗口机制,把顺序接收的管道协议看成一种滑动窗口协议(sliding window),发送窗口WT： 指发送端已发送但未被确认的数据帧的数目 接收窗口WR： 指接收端允许接收的帧的数目 由于要求顺序接收，所以接收窗口始终为1,3.3.4 流量控制的滑动窗口机制(续),例:取帧号3位,发送窗口数为2,接收窗口数为1的滑动窗口图。,3.3.4 流量控制的滑动窗口机制(续),可以用滑动窗口的观点来统一看待停等、回退n和选择重传这三种协议，其差别仅在其窗口的大小,3.3.4 流量控制的滑动窗口机制(续),为何回退n的发送窗

24、口要小于等于2m-1 ？ 假设发送过程发送帧0到7；帧7的捎带确认回到发送过程；发送过程发送另外8帧，序号再次为0到7；现在帧7的另一个捎带确认到达。那么，是第二次发送的8帧都成功了还是全部丢失了？,3.3.4 流量控制的滑动窗口机制(续),为何选择重传的发送窗口要小于等于2m-1 ？,3.4 协议描述与验证,由于协议的复杂性,因此要用一些形式化的、数字的确技术来描述和验证,有限状态机FSM(Finite State Machine)模型 Petri网模型,3.4.1 有限状态机模型,一种用来描述系统的常用方法,系统被描述成有限的状态，在一定的前提条件下会发生一系列的输入事件，这些事件使得系统

25、采取相应的动作，并从一个状态转换成另一个状态，我们称为状态的变迁或转换（transition）,3.4.1 有限状态机模型(续),发送方状态：,0 发送了0号帧 1 发送了1号帧,接收方状态：,0期待接收0号帧 1期待接收1号帧,信道状态：,0信道上有0号帧 1信道上有1号帧 A信道上有ACK帧 S信道处于空帧,以最简单的数据链路层停等协议为例,系统状态:(发送方状态、接收方状态、信道状态),3.4.1 有限状态机模型(续),(000),(01A),(111),(10A),(00S),(01S),(010),(11S),(101),(10S),3.4.1 有限状态机模型(续),系统状态:(发送

26、方状态，接收方状态，正向数据信道状态，反向Ack信道状态）,正向信道状态：,0信道上有0号帧 1信道上有1号帧 S信道处于空帧,反向信道状态：,A信道上有ACK帧 S信道处于空帧,前面图中Ack帧是不带确认帧号的，将状态进一步细化，如：若将传送数据帧的正向信道和传送Ack帧的反向信道分开。,3.4.1 有限状态机模型(续),正反向信道分开的状态变迁图,3.4.2 Petri网模型,由德国学者C. A. Petri首先提出的一种描述方法 本质上也是一种有限状态机模型，但是它允许多种状态变迁同时交叉发生，对于异步并发过程的描述更为方便 Petri网的描述中有四种基本元素：位置（place）、标记（

27、token）、变迁（transition）和带箭头的孤线（arc）。,3.4.2 Petri网模型(续),具有2个位置和2个转换的Petri网,圆圈，表示可能进入的状态 位置中的小圆黑点，某个位置中有标记就表示已处于该状态 变迁用一根直线段来表示 在状态变迁过程中，由于每个变迁的输入弧线数并不一定与输出弧线数相等，因而整个图中的标记数是不守恒的，可能增多或减少,3.4.2 Petri网模型(续),ACK帧不带帧号停等协议的Petri图,3.4.2 Petri网模型(续),ACG1ADF 表示触发了变迁1 Petri网的任何所处状态都可表示成无序的位置组合，且位置可重复出现。如变迁7：AAC，所

28、以ACG7ACCG。,3.5 链路通信协议举例,起止式异步规程 面向字符的同步协议BSC 面向比特的同步规程HDLC 点对点协议PPP,3.5 链路通信协议举例(续),异步协议 把每个字符看作一个独立的信息，在每个字符起始处同步，但各个字符之间的间隔时间是可以变化的； 由于发送器和接收器近似于同一频率的两个时钟（要两个时钟频率严格完全相同是不可能的）能够在一段短时间内保持同步，就可以用字符起始处同步的时钟来采样该字符中的各位，而不需要每位都严格地同步了。,3.5 链路通信协议举例(续),同步协议 把许多字符组织成一个数据块（即帧），除在该数据块的起始处同步外，还要在后面维持固定的时钟，实际上是

29、发送端通过某种技术将时钟混合到数据中一起发送出来，而接收端又从输入数据中分离出时钟来 。,3.5 链路通信协议举例(续),同步与异步的主要区别在字符之间,同步是指连续传送的字符之间是同步的 实现起来较复杂 ； 由于同步协议是许多字符组成一个数据块发送的，它能更有效地利用信道，也便于实现差错控制和其它更强的控制功能 。 异步则指字符之间不是同步的 典型的异步数据链路层协议是起止式异步规程。,3.5.1 起止异步规程,传输过程中效率较低，但实现较容易，发送端时钟漂移不会积累,它是一个字符一个字符传输的，字符与字符间没有固定的时间间隔要求。,3.5.1 起止异步规程(续),上图示出了一个频率为位频率

30、16倍的接收端时钟。利用这个时钟，接收端能在一个位周期1/16时间内决定字符的开始，并按如下步骤进行后面各位采样：,3.5.1 起止异步规程(续), 当检测到起始位下降前沿时将某个计数器清零。 16倍频时钟的每个脉冲使计数器加1。 当计数器第一次到达值8时，表示已到达起始位的中间。此时采样值应为0，并把计数器清零。若采样值不为0，那末表示一开始检测到的下降沿不是真正起始位的前沿，而可能只是一次干扰，此次检测应作废。 以后，计数器每次到达值16时，就采样输入波形，将采样到的数值暂存起来，并将计数器清零。采样重复直至最后的终止位被采样。 如果终止位采样正确（为1），那么字符被接收，由暂存处装入寄存

31、器。若应该为终止位处采样到逻辑值0，说明同步或者传输有问题，该次采样的字符作废，不被接收。,3.5.2 面向字符的同步规程,通信控制字符 :序始(SOH),文始(STX),组终(ETB),文终(ETX),同步(SYN),送毕(EOT),询问(ENQ),确认(ACK),否认(NAK),转义(DLE),最早出现的是IBM公司的二进制同步通信规程BSC(Binary Synchronous Communication)协议,ISO的标准称为数据通信系统的基本型控制规程(Basic mode control procedure for data communication system),3.5.2

32、面向字符的同步规程(续),帧格式,规程将特定模式字符作为普通数据字符处理 可以使用转义字符DLE（Data Link Escape）来完成所需的“透明”,3.5.2 面向字符的同步规程(续),采用字符填充来实现数据透明传输的能力。,将每个独立的控制字符都作为普通的数据字符对待，因而它可以出现在数据正文段中，而不具有通信控制的含义 。 而只有在这些字符紧随着一个DLE转义字符后面时才具有通信控制的含义 。,3.5.2 面向字符的同步规程(续),同步比异步的优点：,避免了异步方式中许多起始和终止信号，信道的有效利用率提高了（特别是在传输较长的数据时）。 由于有标题字段，可以具备更为复杂的通信控制能

33、力，校验的功能也增强了。 面向字符的缺点： 它和特定的字符编码集的关系过于密切，不利于兼容 。 为了实现“数据透明”而采用的字符填充方法，无论用硬件或软件实现起来都较麻烦，而且它也要依赖于所采用的字符编码集。,3.5.3 面向比特的同步规程,帧格式,典型代表是IBM公司的面向比特的同步数据链路控制规程SDLC (Synchronous Data Link Control)。 ANSI修改了该协议，变成了高级数据通信控制过程ADCCP (Advance Data Communication Control Procedure)。 ISO修改此协议变成了高级数据链路控制规程HDLC (High Level Data Link Control)。,3.5.3 面向比特的同步规程(续),比特位的填充,原始数据 011011111111111111100000011111000010 线上数据 011011111011111011111000000011111