Ch3.数据链路层
一.数据链路层功能概述
1.数据链路层的研究思想
水平方向研究,数据从A的数据链路层自左向右传输到B的数据链路层
2.基本概念
结点:主机、路由器
链路:网络中两个结点之间的物理通道,链路的传输介质主要有双绞线、光纤和微波.分为有线链路、无线链路.
数据链路:网络中两个结点之间的逻辑通道.把实现的数据传输协议的硬件和软件加到链路上就构成数据链路.
帧:链路层的协议数据单元,封装网络层数据报
数据链路层负责通过一条链路从一个结点向 另一个物理链路直接相连的相邻结点传送数 据报
3.功能概述
数据链路层在物理层提供服务的基础上向网络层提供服务，其最基本的服务是将源自网络层来的数据可靠地传输到 相邻节点的目标机网络层。其主要作用是加强物理层传输原始比特流的功能，将物理层提供的可能出错的物理连接 改造成为逻辑上无差错的数据链路，使之对网络层表现为一条无差错的链路。
3.1功能一:
为网络层提供服务。无确认无连接服务，有确认无连接服务，有确认面向连接服务。
有连接一定有确认！
3.2功能二 :
链路管理，即连接的建立、维持、释放（用于面向连接的服务）。
3.3功能三:
组帧
3.4功能四:
流量控制。 限制发送方
3.5功能五:
差错控制（帧错/位错）。
习题
选择
1.下列不属于数据链路层功能的是(B)。
A.帧定界功能
B.电路管理功能
C.差错控制功能
D.流量控制功能
2.数据链路层协议的功能不包括（D)。
A.定义数据格式
B.提供结点之间的可靠传输
C.控制对物理传输介质的访问
D.为终端结点隐蔽物理传输的细节
3.为了避免传输过程中桢的丢失，数据链路层采用的方法是（D)。
A.帧编号机制
B.循环冗余校验码
C.汉明码
D.计时器超时重发
4.数据链路层为网络层提供的服务不包括(C)。
A.无确认的无连接服务
B.有确认的无连接服务
C.无确认的面向连接服务
D.有确认的面向连接服务
5.对于信道比较可靠且对实时性要求高的网络，数据链路层采用(A)比较合适。
A.无确认的无连接服务
B.有确认的无连接服务
C.无确认的面向连接服务
D.有确认的面向连接服务
6.流量控制实际上是对（A)的控制。
A.发送方的数据流量
B.接收方的数据流量
C.发送、接收方的数据流量
D.链路上任意两结点间的数据流量
7.下述协议中，（A)不是数据链路层的标准。
A.ICMP
B.HDLC
C.PPP
D.SLIP
8.假设物理信道的传输成功率是95%，而平均一个网络层分组需要10个数据链路层帧来发送。若数据链路层采用无确认的无连接服务，则发送网络层分组的成功率是()。
A.40%
B.60%
C.80%
D.95%
数据链路层的主要功能有：如何将二进制比特流组织成数据链路层的帧：如何控制帧在物理信道上的传输，包括如何处理传输差错；在两个网络实体之间提供数据链路的建立、维护和释放；控制链路上帧的传输速率，以使接收方有足够的缓存来接收每个帧。这些功能对应为帧定界、差错检测、链路管理和流量控制。电路管理功能由物理层提供，关于“电路”和“链路”的区别请参见本章疑难点1。
数据链路层的主要功能包括组，组帧即定义数据格式，A正确。数据链路层在物理层提供的不可靠的物理连接上实现结点到结点的可靠性传输，B正确。控制对物理传输介质的访问由数据链路层的介质访问控制(MAC)子层完成，C正确。数据链路层不必考虑物理层如何实现比特传输的细节，因此D错误。
为防止在传输过程中帧丢失，在可靠的数据链路层协议中，发送方对发送的每个数据帧设计一个定时器，当计时器到期而该帧的确认帧仍未到达时，发送方将重发该帧。为保证接收方不会接收到重复帧，需要对每个发送的帧进行编号：汉明码和循环冗余校验码都用于差错控制。
连接是建立在确认机制的基础上的，因此数据链路层没有无确认的面向连接服务。一般情况下，数据链路层会为网络层提供三种可能的服务：无确认的无连接服务、有确认的无连接服务、有确认的面向连接服务。
无确认的无连接服务是指源机器向目标机器发送独立的帧，目标机器并不对这些帧进行确认。事先并不建立逻辑连接，事后也不用释放逻辑连接。若由于线路上有噪声而造成某一帧丢失，则数据链路层并不会检测这样的丢帧现象，也不会回复。当错误率很低时，这一类服务非常合适，这时恢复任务可以留给上面的各层来完成。这类服务对于实时通信也是非常合适的，因为实时通信中数据的迟到比数据损坏更不好。
流量控制是通过限制发送方的数据流量而使发送方的发送速率不超过接收方接收速率的一种技术。流量控制功能并不是数据链路层独有的，其他层上也有相应的控制策略，只是各层的流
墅控制对象是在相应层的实体之间进行的。
网际控制报文协议(ICMP)是网络层协议，PPP是在SLP基础上发展而来的，都是数据链路层协议。
要成功发送一个网络层分组，需要成功发送10个数据链路层帧。成功发送10个数据链路层帧的概率是(0.95)^10≈0.598，即大约只有60%的成功率。这个结论说明了在不可靠的信道上无确认的服务效率很低。为了提高可靠性，应该引入有确认的服务。
二.封装成帧和透明传输
1.封装成帧
封装成帧:
封装成帧就是在一段数据的前后部分添加首部和尾部，这样就构成了一个帧。接收端在收到物理层上交的比特流 后，就能根据首部和尾部的标记，从收到的比特流中识别帧的开始和结束。 首部和尾部包含许多的控制信息，他们的一个重要作用：帧定界（确定帧的界限）。
帧同步:
接收方应当能从接收到的二进制比特流中区分出帧的起始和终止。
组帧的四种方式:
1.字符计数法
2.字符(节)填充法
3.零比特填充法
4.违规编码法
2.透明传输
透明传输:
透明传输是指不管所传数据是什么样的比特组合，都应当能够在链路上传送。因此，链路层就“看不见”有什么妨 碍数据传输的东西。
当所传数据中的比特组合恰巧与某一个控制信息完全一样时，就必须采取适当的措施，使收方不会将这样的数据误 认为是某种控制信息。这样才能保证数据链路层的传输是透明的
3.组帧的四种方式
3.1字符计数法
帧首部使用一个计数字段（第一个字节，八位）来标明帧内字符数。
痛点：鸡蛋装在一个篮子里了。 因为帧首部发生错误,后续都会出错
3.2字符填充法
3.3零比特填充法
操作：
1.在发送端，扫描整个信息字段，只要连续5个1，就立即填入1个0。
2.在接收端收到一个帧时，先找到标志字段确定边界，再用硬件对比特流进行扫描。发现连续5个1时，就把后面的0删除。
保证了透明传输：在传送的比特流中可以传送任意比特组合，而不会引起对帧边界的判断错误。
3.4违规编码法
习题:
1.在一个数据链路协议中使用下列字符编码：
A01000111; B11100011; ESC11100000; FLAG01111110
在使用下列成帧方法的情况下，说明为传送4个字符A、B、ESC、FLAG所组织的帧而实际发送的二进制位序列（使用FLAG作为首尾标志，ESC作为转义字符)。
1)字符计数法。
2)使用字符填充的首尾定界法。
3)使用比特填充的首尾标志法。
1.解答：
1)第一字节为所传输的字符计数5，转换为二进制为00000101，后面依次为A、B、ESC、FLAG的二进制编码：
00000101 01000111 11100011 11100000 01111110
2)首尾标志位FLAG(01111110),在所传输的数据中，若出现控制字符，则在该字符前插入转义字符ESC(11100000):
01111110 01000111 11100011 11100000 11100000 11100000 01111110 01111110
3)首尾标志位FLAG(01111110),在所传输的数据中，若连续出现5个“1”，则在其后插入“0”：
01111110 01000111 110100011 111000000 011111010 01111110
三.差错控制(检错编码)
1.差错从何而来?
概括来说,传输中的差错都是由于噪声引起的.
全局性 1.由于线路本身电气特性所产生的随机噪声(热噪声),是信道 固有的,随机存在的.
解决办法:提高信噪比来减少或避免干扰
局部性 2.外界特定的短暂原因所造成的冲击噪声,是产生差错的主要 原因
解决办法:通常利用编码技术来解决
2.数据链路层的差错控制
冗余编码:
简单来说,就是在发送数据时侯,我们不仅要发送原始数据,同时还要在数据后面附加上几位比特,这几位比特就是冗余码,作用就是和原来的数据构成某种规则,把这个组合发出去,接收方按照和发送方共识的规则来检查是不是有问题.
3.奇偶检验码
4.CRC循环冗余码
TIPS：多项式N位，阶为N-1。
在数据链路层仅仅使用循环冗余检验CC差错检测技术，只能做到对帧的无差错接收，即“凡是接收端数据链路层接受的帧，我们都能以非常接近于1的概率认为这些帧在传输过程中没有产生差错”。接收端丢弃的帧虽然曾收到了，但是最终还是因为有差错被丢弃。“凡是接收端数据链路层接收的帧均无差错”。
四.差错控制(纠错编码)
1.海明码
1.1海明距离
两个合法编码(码字)的对应比特取值不同的比特数称为这两个码字的海明距离(码距)，一个有效编码集中,任 意两个合法编码(码字)的海明距离的最小值称为该编码集的海明距离(码距)。
2.步骤
2.1确定校验码位数r
2.2确定校验码和数据的位置
2.3求出校验码的值
2.4.检错并纠错
Summary:
习题:
选择
1.通过提高信噪比可以减弱其影响的差错是（A)。
A.随机差错
B.突发差错
C.数据丢失差错
D.千扰差错
2.下列有关数据链路层差错控制的叙述中，错误的是（A)
A.数据链路层只能提供差错检测，而不提供对差错的纠正
B.奇偶校验码只能检测出错误而无法对其进行修正，也无法检测出双位错误
C.CRC校验码可以检测出所有的单比特错误
D.海明码可以纠正一位差错
3.下列属于奇偶校验码特征的是（A)。
A.只能检查出奇数个比特错误
B.能查出长度任意一个比特的错误
C.比CRC检验可靠
D.可以检查偶数个比特的错误
4.字符S的ASCII编码从低到高依次为1100101，采用奇校验，在下述收到的传输后字符
中，错误（D)不能检测。
A.11000011
B.11001010
C.11001100
D.11010011
5.为了纠正2比特的错误，编码的海明距应该为（D)。
A.2
B.·3
C.4
D.5
6.对于10位要传输的数据，如果采用汉明校验码，那么露要增加的冗余信息位数是(B)。
A.3
B.4
C.5
D.6
7.下列关于循环冗余校验的说法中，(B)是错误的.
A.带个校验位的多项式编码可以检测到所有长度小于等于r的突发性错误
B.通信双方可以无须商定就直接使用多项式编码
C.CRC校验可以使用硬件来完成
D.有一些特殊的多项式，因为其有很好的特性，而成了国际标准
8.要发送的数据是1101011011，采用CRC校验，生成多项式是10011，那么最终发送的
数据应是（)。
A.11010110111010
B.11010110110110
C.11010110111110
D.11110011011100
简答
1.在数据传输过程中，若接收方收到的二进制比特序列为10110011010，接收双方采用的生成多项式为G(x)=x+x+1,则该二进制比特序列在传输中是否出错？如果未出现差错，那么发
送数据的比特序列和CRC检验码的比特序列分别是什么？
所得余数为0，因此该二进制比特序列在传输过程中未出现差错。发送数据的比特序列是1011001，CRC检验码的比特序列是1010。
注意：
CRC检验码的位数等于生成多项式G(x)的最高次数，
一般来说，数据的传输差错是由噪声引起的。通信信道的噪声可以分为两类：热噪声和冲击噪声。热噪声一般是信道固有的，引起的差错是随机差错，可以通过提高信噪比来降低它对数据传输的影响。冲击噪声一般是由外界电磁干扰引起的，引起的差错是突发差错，它是引起传输差错的主要原因，无法通过提高信噪比来避免。
链路层的差错控制有两种基本策略：检错编码和纠错编码。常见的纠错码有海明码，它可以纠正一位差错。
奇偶校验的原理是通过增加冗余位来使得码字中“1”的个数保持为奇数或偶数的编码方法，它只能发现奇数个比特的错误。
既然采用奇校验，那么传输的数据中1的个数若是偶数个则可检测出错误，若1的个数是奇数个，则检测不出错误，因此选D。
海明码“纠错”d位，需要码距为2d+1的编码方案；“检错”d位，则只需码距为d+1。
在k比特信息位上附加r比特冗余信息，构成k+r比特的码字，必须满足2^r≥k+r+1。如果k的取值小于等于11且大于4，那么r=4。
在使用多项式编码时，发送端和接收端必须预先商定一个生成多项式。发送端按照模2除法，得到校验码，在发送数据时把该校验码加在数据后面。接收端收到数据后，也需要根据该生成多项式来验证数据的正确性。
假设一个帧有m位，其对应的多项式为Gx),则计算冗余码的步骤如下：
①加0。假设G(x)的阶为r,在帧的低位端加上r个0。
②模2除。利用模2除法，用G(x)对应的数据串去除①中计算出的数据串，得到的余数即为冗余码（共”位，前面 的0不可省略）。
多项式以2为模运算。按照模2运算规则，加法不进位，减法不借位，它刚好是异或操作。乘除法类似于二进制运算，只是在做加减法时按模2规则进行。根据以上算法计算可得答案选C。
根据题意，生成多项式Gx)对应的二进制比特序列为11001。进行如下的二进制模2除法,被除数为10110011010，除数为11001：
