第四章数据链路层

1、1计算机与信息学院计算机与信息学院课前思考课前思考 为什么建立数据链路连接？为什么建立数据链路连接？ 数据链路连接与物理连接的联系和区别？数据链路连接与物理连接的联系和区别？ 数据链路层主要功能有哪些？数据链路层主要功能有哪些？ 数据链路层上常用的差错控制码有哪些？数据链路层上常用的差错控制码有哪些？ 数据链路层上常用的流量控制策略有哪些？数据链路层上常用的流量控制策略有哪些？ 常用的数据链路层协议有哪些？常用的数据链路层协议有哪些？第四章第四章 数据链路层数据链路层2计算机与信息学院计算机与信息学院本章内容本章内容4.1 概述概述4.2 差错控制差错控制4.3 流量控制流量控制 4.4 数据

2、链路层协议举例数据链路层协议举例3计算机与信息学院计算机与信息学院4.1 概述概述 数据链路层主要功能数据链路层主要功能 在相邻节点之间保证数据帧的在相邻节点之间保证数据帧的“透明透明”传输。传输。 数据帧数据帧 数据帧数据帧是数据链路层的最小数据传输单元，即是数据链路层的最小数据传输单元，即DPDU。 数据帧数据帧的一般格式：的一般格式：帧同步帧同步目的地址目的地址源地址源地址控制控制数据数据帧校验帧校验数据链路层协议涉及的主要内容数据链路层协议涉及的主要内容l 数据链路的建立与拆除数据链路的建立与拆除l 帧同步帧同步l 差错控制差错控制l 流量控制流量控制4计算机与信息学院计算机与信息学院

3、4.2 差错控制差错控制4.2.1 传输差错的特征传输差错的特征 热噪声热噪声: 传输介质内的分子热运动。冲击噪冲击噪声声：外界干扰。热噪热噪声声: 干扰幅度小，持续性，对模拟通信影响大。 冲击噪冲击噪声声：干扰幅度大，突发性，对数字通信影响大。 特征特征 如数据率为9600bps，一次闪电持续时间约为10ms，则连续破坏96位。 差错产生的主要原因差错产生的主要原因 计算机网络中，差错控制主要针对冲击噪声。计算机网络中，差错控制主要针对冲击噪声。5计算机与信息学院计算机与信息学院4.2 差错控制差错控制4.2.2 差错控制方法差错控制方法 通过特殊的编码（差错控制码），使接收端能够发现甚至自

4、动纠正错误。差错控制编码差错控制编码l检错码：检错码：能够发现差错，但无法自动纠正差错，通过发送方重传来 获得正确的数据。l纠错码：纠错码：不但能过发现差错，而且知道哪些位出错，从而能够自动 纠正差错。4.2.3 编码的检错和纠错能力、编码效率编码的检错和纠错能力、编码效率 定义定义l码字：码字：码字由信息位串和校验位串（冗余位串）组成。设信息位 为m位，校验位为r位，则码字长度为n=m+r。6计算机与信息学院计算机与信息学院4.2 差错控制差错控制l两个码字的距离两个码字的距离 两个等长码字的不同位数称为这两个码字的距离，简称码距。两个等长码字的不同位数称为这两个码字的距离，简称码距。 如：

5、如：10001001 10110001 则这两个码字的距离为则这两个码字的距离为3。l海明距离海明距离 给定某种编码规则，就能够造出包含全部合法码字的码字给定某种编码规则，就能够造出包含全部合法码字的码字表（编码系统）；该码字表中必存在着两个码字，使得这两个表（编码系统）；该码字表中必存在着两个码字，使得这两个码字的距离最小；该最小距离称为该码字表（编码系统）的码字的距离最小；该最小距离称为该码字表（编码系统）的海海明距离明距离。海明距离海明距离决定了编码系统的检错和纠错能力决定了编码系统的检错和纠错能力 编码的检错和纠错能力编码的检错和纠错能力l若要检测若要检测d位出错，则海明距离至少为位出

6、错，则海明距离至少为d+1。l若要纠正若要纠正d位出错，则海明距离至少为位出错，则海明距离至少为2d+1。7计算机与信息学院计算机与信息学院 例：设有一编码系统的码字表有例：设有一编码系统的码字表有4 4个码字组成：个码字组成： 0000000000 0000011111 1111100000 1111111111 因为海明距离为因为海明距离为5，可检测出，可检测出4位出错，自动纠正位出错，自动纠正2位出错。位出错。 如果出错位不超过如果出错位不超过4位，则收到的码子必定是非法的码子位，则收到的码子必定是非法的码子,即不属即不属于码子表于码子表; 如果出错位为如果出错位为5位，则出错的码子可能

7、是合法的码子。位，则出错的码子可能是合法的码子。例：例： 发送的码子为发送的码子为1111100000，而收到的码子，而收到的码子1111111111。 设收到的码字为设收到的码字为0000000111，如果出错位不超过两位，则可以，如果出错位不超过两位，则可以断定其正确码字为断定其正确码字为0000011111; 如果出错位可能超过两位（如如果出错位可能超过两位（如3位），则无法断定其正确码字是位），则无法断定其正确码字是 0000011111，还是，还是0000000000。 编码效率编码效率 R=m/n=m/(m+r) 其中，m为信息位串长度， r为校验位串（冗余位串）长度。4.2 差错

8、控制差错控制8计算机与信息学院计算机与信息学院a5= a1 +a2+ a3a6= a2 +a3+ a4a7= a1 +a3+ a4 0000000 0100110 1000101 1100001 0001011 0101101 1001110 1101000 0010111 0110001 1010010 1110100 0011100 0111010 1011001 1111111显然，编码表的海明距离为3，能够自动纠正一位出错。其中，+：异或， 由式（4-1）构造的编码表如下：(4-1) 设信息位有4位，记为a1a2a3a4；校验位为3位，记为a5a6a7。 编码系统中任何一个合法的码字满

9、足如下线性独立的方程： 4.2 差错控制差错控制4.2.4 海明码海明码(纠错码纠错码) 构造海明码构造海明码9计算机与信息学院计算机与信息学院设发送方发出的码字为： a1a2a3a4 a5a6a7 接受方收到的码字为：b1b2b3b4 b5b6b7 令：br= ar+er r=1,2,.7 (4-2)若第r位出错，则er=1；否则er=0。s1 s2 s3称为校验因子；接受方将根据校验因子来判断哪位出错。 再令：s1= b1 +b2+b3+ b5 s2= b2 +b3+ b4+b6 s3= b1 +b3+b4+ b7(4-3)将（4-1）,（4-2）代入（4-3）得： s1= e1 +e2+

10、 e3+ e5 s2= e2 +e3+ e4+ e6s3= e1 +e3+ e4+ e7(4-4) 纠错原理纠错原理10计算机与信息学院计算机与信息学院4.2 差错控制差错控制根据式（4-4）:s1= e1 +e2+ e3 + e5 s2= e2 +e3+ e4 + e6s3= e1 +e3+ e4+ e7得到下表:出错位 s1 s2 s3 1 0 11 1 0无无 0 001 1 10 1 11 0 00 1 00 0 1123456711计算机与信息学院计算机与信息学院4.2 差错控制差错控制l上述上述海明海明码码只能纠正一位出错，而实际通信中经常发生的是突只能纠正一位出错，而实际通信中经

11、常发生的是突发性错误（一连串位出错）。发性错误（一连串位出错）。l要纠正突发性出错，则必须加大海明距离；但加大海明距离势要纠正突发性出错，则必须加大海明距离；但加大海明距离势必会增加校验位串长度，从而降低了编码效率必会增加校验位串长度，从而降低了编码效率，同时也会使编同时也会使编码系统过于复杂。码系统过于复杂。l只要将发送方式稍做改变，就能利用纠正一位出错的海明码来只要将发送方式稍做改变，就能利用纠正一位出错的海明码来纠正多位突发错：纠正多位突发错： 讨论讨论 将k个码字排列成一个矩阵，每行一个码字。按列发送，一次传输k个码字。 数据到达接收端后，再重新组成矩阵。如果突发长度K,则每个码字最多

12、出现一位错误，而前述的海明码恰好能够纠正这样的一位错。 12计算机与信息学院计算机与信息学院4.2 差错控制差错控制 循环冗余码循环冗余码（CRC码码） 是目前计算机网络中使用最广泛的一种检错码。是目前计算机网络中使用最广泛的一种检错码。CRC码又称多项式码，每个码字对应于一个多项式。码又称多项式码，每个码字对应于一个多项式。 设码字为a1a2a3.an，则对应的多项式为：A(x)=a1xn-1+ a2xn-2+ a3xn-3+. +an 如： 110001 x5+x4+1 4.2.5 循环冗余码循环冗余码( (检错码检错码) ) l设信息位串为a1a2a3.am ，则对应的多项式为： M(x

13、)=a1xm-1+ a2xm-2+ a3xm-3+. +aml选择一个r次多项式G(x)作为生成多项式，按下面步骤生成校验串：在信息位串后补r个0，对应的多项式为xrM(x)用模2不借位除法，计算余数R(x)： R(x)= MOD(xrM(x)/G(x)要发送的码字多项式：T(x)=xrM(x)+ R(x) 编码原理（发送端）编码原理（发送端） 13计算机与信息学院计算机与信息学院4.2 差错控制差错控制例：信息位串为例：信息位串为1010001，若若G(x)= x4+x2+x+1，求，求CRC码。码。 解：M（x）= x6+x4+ 1 r=4 xrM(x)= x10+x8+ x4101000

14、10000 计算 ：R(x)= MOD(xrM(x)/G(x)14计算机与信息学院计算机与信息学院= x10+x8+ x4+x3+x2+ 110111 10100010000 10111T(x) = xrM(x)+ R(x)信息位串信息位串 11010 10111 1001111 11010 10111 11010 10111 11010 10111 1101R(x)= x3+x2+ 1 1010001 1101商商除数除数G(XG(X) )余数余数被除数被除数校验位串校验位串 4.2 差错控制差错控制15计算机与信息学院计算机与信息学院4.2 差错控制差错控制G (x) = x4+x2+x+

15、1的编码电路R01000101输入10111000101输出 编码电路编码电路R1R2R3 译码原理译码原理( (接受端）接受端） 接受方收到一个码字后，用同一生成多项式接受方收到一个码字后，用同一生成多项式G(x)G(x)除该码字多项式除该码字多项式T T (x)(x)， 若若MOD(TMOD(T(x)/G(x)(x)/G(x)0,0,则正确则正确 若若MOD(TMOD(T (x)/G(x)(x)/G(x)0,0,则出错则出错思考：思考： 若若MOD(T(x)/ /G(x)0, 是否一定正确是否一定正确? 若若MOD(T(x)/ /G(x) 0，是否一定出错，是否一定出错?16计算机与信息学

16、院计算机与信息学院4.2 差错控制差错控制l若若G(x)含有含有x+1因子，则能检测出所有的奇数位错。因子，则能检测出所有的奇数位错。l若若G(x)含有常数项含有常数项1，那么能检测出所有突发长度，那么能检测出所有突发长度r的突发错。的突发错。l若若G(x)含有常数项含有常数项1，且对任何，且对任何01， 接收窗口尺寸接收窗口尺寸WR=1。发送方连续发送发送方连续发送n帧而无需对方应答，但需要将已发出但尚帧而无需对方应答，但需要将已发出但尚未得到确认的帧保存在发送窗口中，以备重发。未得到确认的帧保存在发送窗口中，以备重发。接收方将正确的且帧序号落入当前接收窗口的帧存入接收窗接收方将正确的且帧序

17、号落入当前接收窗口的帧存入接收窗口，同时按序将接收窗口的帧送交给主机（网络层）。出错口，同时按序将接收窗口的帧送交给主机（网络层）。出错或帧序号未落入当前窗口的帧予以丢弃。或帧序号未落入当前窗口的帧予以丢弃。当某帧丢失或出错时，则其后到达的帧均丢弃，并返回否认当某帧丢失或出错时，则其后到达的帧均丢弃，并返回否认信息，请求对方从出错帧开始重发。信息，请求对方从出错帧开始重发。发送方设置一个超时计时器，当连续发送发送方设置一个超时计时器，当连续发送n帧后，立即启动帧后，立即启动超时计时器；若超时且未收到应答，则重发这超时计时器；若超时且未收到应答，则重发这n帧。帧。 顺序接收管道协议顺序接收管道协

18、议 （回退（回退n协议）协议）l 协议描述协议描述23计算机与信息学院计算机与信息学院4.3 流量控制流量控制l 优点：仅需一个接收缓冲区。优点：仅需一个接收缓冲区。l 缺点：当信道误码率较高时，会产生大量重发帧。缺点：当信道误码率较高时，会产生大量重发帧。 选择重传协议选择重传协议l 发送窗口尺寸发送窗口尺寸WT= n 1， 接收窗口尺寸接收窗口尺寸WR=m 1 。l若某一帧出错，后面正确到达的帧虽然不能立即送网络层，但可若某一帧出错，后面正确到达的帧虽然不能立即送网络层，但可将其保存在接收窗口；因此，仅需重传出错帧。将其保存在接收窗口；因此，仅需重传出错帧。l 优点：仅需重传出错帧，不会产

19、生大量重发帧。优点：仅需重传出错帧，不会产生大量重发帧。l 缺点：需要多个接收缓冲区。缺点：需要多个接收缓冲区。24计算机与信息学院计算机与信息学院4.3 流量控制流量控制协议协议 发送窗口发送窗口 接收窗口接收窗口 停等 1 1 回退n 1 1 选择重传 1 1停停等等 、顺序接收管道、选择重传协议都可以看成是滑动窗口协、顺序接收管道、选择重传协议都可以看成是滑动窗口协 议，其差别仅在窗口的尺寸不同，如下表所示议，其差别仅在窗口的尺寸不同，如下表所示 ： 设帧序号的位数为设帧序号的位数为m，则：，则： WTWR WT+ WR2m若若WR WT ，则有，则有 WR-WT个窗口永远用不上。个窗口

20、永远用不上。 WT+ WR2m保证了上一轮帧序号和下一轮序号在保证了上一轮帧序号和下一轮序号在WT+ WR范围内不会范围内不会出现重复；否则，接收端无法判断落入窗口的帧是属于哪一轮的。出现重复；否则，接收端无法判断落入窗口的帧是属于哪一轮的。 25计算机与信息学院计算机与信息学院4.3 流量控制流量控制例：设例：设m=3, , WT =7, , WR=2，显然，显然，WR+WT2m。发送窗口首先连续发送发送窗口首先连续发送7帧（帧（0-6号帧）。号帧）。假设这假设这7帧全部正确到达，接收端收到后返回帧全部正确到达，接收端收到后返回“确认确认”，并将接，并将接收窗口向前滑动收窗口向前滑动7个窗口

21、，即当前窗口为个窗口，即当前窗口为7号和号和0号。号。假设假设“确认确认”丢失，由于发送端超时收不到丢失，由于发送端超时收不到“确认确认” 而误认为所而误认为所发送的帧全部丢失，于是重发发送的帧全部丢失，于是重发0-6号帧。号帧。重发的重发的0号帧又落入接收窗口而被重复接收，并被误认为下一轮号帧又落入接收窗口而被重复接收，并被误认为下一轮帧的帧的0号帧而递交给主机。号帧而递交给主机。26计算机与信息学院计算机与信息学院4.4 数据链路层协议举例数据链路层协议举例4.4.1 HDLC协议协议 HDLC (High Level Data Control) 是一种是一种典型的数据链路层协议，典型的数

22、据链路层协议，该协议该协议“面向比特面向比特”，即以，即以“比特比特”作为数据帧的基本数据单位。作为数据帧的基本数据单位。 HDLC帧格式帧格式l 标志标志标志标志地址地址 控制控制 数据数据帧检验帧检验标志标志 字节数： 1 1 1 任意 2 1帧同步标志，固定为帧同步标志，固定为“01111110”，标志着一个帧的开始与结束。，标志着一个帧的开始与结束。连续发送多帧时，可用一个标志字段，既表示帧的开始，又表示帧连续发送多帧时，可用一个标志字段，既表示帧的开始，又表示帧的结束。的结束。为了避免其它字段中出现为了避免其它字段中出现“01111110”，HDLC采用采用插插“0”技术：技术：27

23、计算机与信息学院计算机与信息学院4.4 数据链路层协议举例数据链路层协议举例其后为“0”，则自动去掉该“0”。为“1”则出错。其后为“1”，则检查下一位：为“0”则为标志位。 发送方：除标志位外，连续发送5个“1”后自动插“0”。接收方：连续收到5个“1”后， 0 1 0 0 1 1 1 1 1 1 0 0 0 1 0 1 0例：例：某一非标志字段中恰好出现“0111111001111110”，被误认为是标志字段：0 1 0 0 1 1 1 1 1 0 1 0 0 0 1 0 1 00 1 0 0 1 1 1 1 1 0 1 0 0 0 1 0 1 0发送端连续发送 5 个“1”后，填入1个“

24、0”：接收端将 5 个连 1 之后的“0”删除：28计算机与信息学院计算机与信息学院4.4 数据链路层协议举例数据链路层协议举例l 地址地址全全“1”为广播地址，全为广播地址，全“0”为无效地址。为无效地址。在多点通信中，表示目的地址。在多点通信中，表示目的地址。在点到点通信中，地址没有太大意义，一般用来区分发起方和响应方。在点到点通信中，地址没有太大意义，一般用来区分发起方和响应方。 l 控制控制 该字段表示帧类型，帧编号及其他控制信息。该字段表示帧类型，帧编号及其他控制信息。 信息帧：信息帧：用于传输数据监督帧：监督帧：应答帧不带编号和数据，相当于控制帧，包括：SNRMSNRM（置正常响应

25、模式）UAUA（无编号帧确认）FRMRFRMR（帧拒绝）DISCDISC（拆除连接）RESETRESET(复位)等。帧类型帧类型无编号帧：无编号帧：29计算机与信息学院计算机与信息学院4.4 数据链路层协议举例数据链路层协议举例0 0 N(S) N(S)P/FP/FN(R) N(R) 1 1 1 1M MP/FP/FM M1 10 0S SP/FP/FN(R)N(R) 1 2 3 4 5 6 7 8信息帧以“0”打头 监督帧以“10”打头 无编号帧以“11”打头 N(S):N(S):表示信息帧的帧序号（0-7）。N(R):N(R):接收端期望接收的下一帧的序号。P/F P/F ：轮询/结束位，

26、用于多点轮询访问方式。控制字段格式控制字段格式S S：00:00:确认以前各帧，准备接受序号从N(R)开始的后继帧。10:10:确认以前各帧，但暂停接收后继帧，用来进行流量控制。01:01:否认N(R)起的各帧，请求重发序号从N(R)开始的各帧。11:11:仅否认 N(R)帧，请求重发序号为N(R)的单帧。M M：共5位，表示32种控制功能。30计算机与信息学院计算机与信息学院4.4 数据链路层协议举例数据链路层协议举例要传输的数据，即高层的报文分组，可以是任意二进制位的组合。l 数据数据l 帧校验帧校验 16位CRCCRC码，G(X)= CRC-CCITT = xG(X)= CRC-CCITT = x1616+x+x1212+x+x5 5+1+1。 HDLC工作原理工作原理l 建立数据链路连接建立数据链路连接SNRM网络层网络层网络层网络层HDLCHDLC物理层物理层物理层物理层UASNRMUASNRM，UA位流位流31计算机与信息学院计算机与信息学院4.4 数据链路层协议举例数据链路层协议举例通过层间接口通过层间接口(服务服务)，请求建立物理连接。，请求建立物理连接。请求建立链路