计算机网络第三章:数据链路层

§3.1 数据链路层功能概述

1.节点:

  计算机网络中的中的主机路由器等都可以叫节点。

2.链路:

  网络中两个节点之间的物理通道,链路的传输介质主要有双绞线光纤和微波。分为有线链路、无线链路。

3.数据链路:

  网络中两个节点之间的逻辑通道,把实现控制数据传输协议的硬件和软件加到链路上就构成了数据链路。

4.帧:

  链路层的协议数据单元,封装网络层数据报。

5.链路与数据链路之间的区别:

   链路是物理通道、而数据链路是逻辑通道。数据链路层负责通过一条链路从一个结点向另一个物理链路直接相连的相邻结点传送数据报。

6.数据链路层的功能:

  数据链路层在物理层提供服务的基础上向网络层提供服务,其最基本的服务是将源自网络层来的数据可靠地传输到相邻节点的目标机网络层。其主要作用是加强物理层传输原始比特流的功能,将物理层提供的可能出错的物理连接改造成为逻辑上无差错的数据链路,使之对网络层表现为一条无差错的链路。

  网络层是大老板、数据链路层是秘书、物理层是跑腿的。现在老板A要送文件给老板B,老板A就让秘书发文件,秘书把文件分成五段并标号,然后让跑腿的送文件,老板B的秘书一看文件不对,怎么只有三段,就得改正文件,保证让老板B拿到的是正确文件。

  • 为网络层提供服务:
    • 无确认无连接服务:适用于误码率低的通信。接收端收到信息不用发出响应。若物理层并没有成功传送数据,数据链路层也一声不吭悄悄地。
    • 有确认无连接服务:收发双发无需建立连接,但数据成功发送到的话、接收端要发送响应。
    • 有确认面向连接服务:收发双方建立连接。有连接必然有确认,所以不存在无确认有连接服务。
  • 链路管理,即连接的建立、维持、释放(用于面向连接的服务)。
  • 组帧:详见下一节讲解。
  • 流量控制:接收端收不过来的话,就得让发送方慢点儿。这就叫流量控制。
  • 差错控制:帧错 / 位错






§3.2 组装成帧和透明传输

一、封装成帧

1.概念:

  封装成帧就是在一段数据的前后部分添加首部和尾部,这样就构成了一个帧。接收端在收到物理层上交的比特流后,就能根据首部和尾部的标记,从收到的比特流中识别帧的开始和结束。首部和尾部包含许多的控制信息,他们的一个重要作用:帧定界(确定帧的界限)。

2.帧同步:

  接收方应当能从接收到的二进制比特流中区分出帧的起始和终止。

3.帧长:

  如图所示
计算机网络第三章:数据链路层
4.MTU:

  即最大传输单元,帧的数据部分要不大于MTU。

5.组帧的四种方法:

  • ① 字符计数法
  • ② 字符(节)填充法
  • ③ 零比特填充法
  • ④ 违规编码法

二、透明传输

  透明传输是指不管所传数据是什么样的比特组合,都应当能够在链路上传送。因此,链路层就“看不见”有什么妨碍数据传输的东西。

  当所传数据中的比特组合恰巧与某一个控制信息完全一样时,就必须采取适当的措施,使收方不会将这样的数据误认为是某种控制信息。这样才能保证数据链路层的传输是透明的。

三、组帧的四种方式

1.字符计数法:

  帧首部用一个计数字段(第一个字节,八位)来表明帧内的元素。
计算机网络第三章:数据链路层

  缺点:如果第一个字符发生失真编成了4,那后面就全乱了。所以这种方法其实也不常用。

2.字符填充法
计算机网络第三章:数据链路层
  当传送的帧是由文本文件组成时(文本文件的字符都是从键盘上输入的,都是ASClI码)。不管从键盘上输入什么字符都可以放在帧里传过去,即透明传输。

  当传送的帧是由非ASClI码的文本文件组成时(二进制代码的程序或图像等就要采用字符填充方法实现透明传输。

  字符填充具体实现方法是这样的,有三种字节,开始字节、结束字节、转义字节。如果刚好传送的正常数据和开始字节结束字节或者转义字节一样,那就在他前面插入一个转义字节。如图:

计算机网络第三章:数据链路层
3.零比特传输法
计算机网络第三章:数据链路层

  标志字段01111110同时代表开始结束,并且严格遵守5110,即没出现五个连续的1,就在后面插入一个0,就算传输的数据中有01111110,那他也会变成011111010,不会与标志字段发生混淆。实现了透明传输。

4.违规编码法

  用违法的编码方式来表示起始结束,例如曼彻斯特编码中,只能有 低-高、高-低 两种编码方式,那就用高-高和低-低表示起始结束。

5.总结:

  由于字节计数法中Count字段的脆弱性(其值若有差错将导致灾难性后果)及字符填充实现上的复杂性和不兼容性,目前较普遍使用的帧同步法是零比特填充违规编码法






§3.3.1 差错控制(检错编码)

一、差错从何而来?

  主要还是由噪声而来。而差错的分类可以根据成因分两种、根据形式也分两种。

1.根据成因分:

  • ① 全局性:

    • 由于线路本身电气特性所产生的随机噪声(热噪声),是信道固有的,随机存在的。
    • 解决办法:提高信噪比来减少或避免干扰。(对传感器下手)
    • 信道电流流过发生的呲呲声导致。
  • ② 局部性:

    • 由于外界特定的短暂原因所造成的冲击噪声,产生差错,这是主要原因。
    • 解决办法:通常利用编码技术来解决。
    • 熊孩子拿木头棍子敲网线

2.按形式分:

  • 位错:1变0 0变1这种
  • 帧错:例如 [#1] - [#2] - [#3] 发生帧错
    • 丢失:收到 [#1] - [#3]
    • 重复:收到 [#1] - [#2] - [#2] - [#3]
    • 失序:收到 [#1] - [#3] - [#2]

二、数据链路层的差错控制

1.位错差错控制的方式:

  假设主机A和主机B进行通信,信道上有20个路由器等链路层设备。在数据在第五个路由器上发生了位错,第五个路由器就不会发位错的数据,然后往回发,五四三二一往回发到主机A上告诉主机A数据错了让它重新发。

  这比直接一股脑不管对错发到主机B上,然后发现错误又重新王芳一轮回要节省不少资源呢。

2.位错差错控制的编码方式:

  • 纠错编码:
    • 海明码
  • 检错编码:
    • 奇偶效验码
    • 循环冗余码

3.物理层的编码和数据链路层的编码的不同点

  数据链路层编码和物理层的数据编码与调制不同。物理层编码针对的是单个比特,解决传输过程中比特的同步等问题,如曼彻斯特编码。而数据链路层的编码针对的是一组比特,它通过冗余码的技术实现一组二进制比特串在传输过程是否出现了差错。

3.冗余编码:

  在数据发送之前,先按某种关系附加上一定的冗余位,构成一个符合某一规则的码字后再发送。当要发送的有效数据变化时,相应的冗余位也随之变化,使码字遵从不变的规则。接收端根据收到码字是否仍符合原规则,从而判断是否出错。

  我上淘宝买了五十颗糖,商家会把它打包起来,然后在上面写:“共计五十颗,没颗重2g,连带包装共计150g。”,这个就是冗余码。然后一路上会有一些相当于是路由器的官员,比如糖运到曹县了,曹县的负责官员就要称一下包裹,要是发现重量不对,与冗余码不符合,哦吼,原来是有一颗糖坏了。就让送货的把坏掉的扔了,没坏的继续送,并且再派一众人马去出发地商家,让商家的工作人员重新送一颗没坏的糖过来。不用说是我收到了糖,发现有一颗坏的,这时才给商家反馈。浪费时间浪费资源。

三、检错编码 — 奇偶效验码

1.概念:

  奇偶校验码分为一位校验码和 n - 1 位信息元。其编码方式分为奇校验偶校验。奇校验是在数据前面加一位0或1,使1的个数为奇数。偶校验码就是加一位1的数量变偶数

  对于奇(偶)校验只能检测出奇数个位==(1位错误、3位错误)==的比特错误,因而检错能力只有 50 %

2.例题:

  如果一个字符S的ASCI编码从低到高依次为1100101,采用奇校验,在下述收到的传输后字符中,哪种错误不能检测?

A.11000011   B.11001010
C. 11001100  D.11010011

  答案:D

  解析:

  显而易见的,S的正确奇校验码应该是11100101,四个答案都是错误的编码,但是错误的编码也有可能不会被找到对吧。ABC三项,1的个数均为4,是偶数,而奇校验需满足1的个数为奇数,那么ABC的错误必然能被检测出来。但是D中的1的个数是5个,是奇数,所以即便他是错的,数据链路层也看不来。就像是要买的五个十个糖,少了一颗糖,但放了一颗一样重的石头,冗余码也没用,只能默默认栽。

四、检错编码 — CRC循环冗余码

1.编码思想:

  比如发送端要发送的发送数据是5,生成多项式是2,然后5 % 2 = 1,那么1就是冗余码 / FCS帧检测序列。5 + 1 是6,所以发送端不发5发6,接收端一看:哦吼,666,发的是6,这玩意儿是2的倍数,那就没得错了。

  这个玩意儿有点麻烦,就不说他具体是怎么操作的了,直接上例题反而更好理解。

2.例题:

  假如我们要发的数据是1101011011,采用CRC校验,生成多项式为10011。

  10011表达成多项式应该是 x 4 + x + 1,阶数为4,那么我们就先用原始数据1101011011乘以2 4 也就是10000,得到的11010110110000,然后用这个11010110110000除以10011得到余数是1110,也就是说FCS就是1110,然后用11010110110000加上1110得到11010110111110即是要发送的数据。具体二进制除法要用到异或运算,如图(没必要怎么掌握,估计到时候数电要学二进制除法器)

计算机网络第三章:数据链路层
  然后对于接收端而言,他应该如何将11010110111110进行检错呢?很简单,判断11010110111110是不是生成多项式10011的倍数。

  另外FCS的生成以及接收端CRC检验都是由硬件实现,处理很迅速,因此不会延误数据的传输。

  为啥硬件就快,想想晚上睡觉前要关灯,你现在就在开关面前,直接按开关快还是掏出手机用智能开关装逼快。

3.总结:

  在数据链路层仅仅使用循环冗余检验CRC差错检测技术,只能做到对帧的无差错接收,即“凡是接收端数据链路层接受的帧,我们都能以非常接近于1的概率认为这些帧在传输过程中没有产生差错”。接收端丢弃的帧虽然曾收到了,但是最终还是因为有差错被丢弃。“凡是接收端数据链路层接收的帧均无差错”。

  这种传输方式仍然不能称作“可靠传输”,可靠传输是发送端数据链路层发什么,接收端数据链路层就收到什么。CRC检验虽然能实现无比特差错的传输,但这还不是可靠传输。





§3.3.2 差错控制(纠错编码)

1.海明码的特点:可以发现双比特错,纠正单比特错。
2.海明码的特点:动一发而牵全身。
3.海明码的工作原理:

确定校验码位数r 确定校验码和数据的位置 求出校验码的值 检错并纠错

一、确定校验码位数r

1.海明不等式:

  2 r ≥ k + r + 1

  r为冗余信息位,k为信息位

2.海明不等式的应用

  设要发送的数据为 D = 101101 ,数据的位数 k = 6 ,满足不等式的最小 r 为4,也就是说 D = 101101 的海明码应该有 6 + 4 = 10 位,其中原数据 6 位,校验码 4 位。

二、确定校验码和数据的位置

  对于原始数据 D = 101101 ,已知应有四位校验码,设它们分别为P1 , P2 , P3 , P4;数据从左到右为D1 , D2 , D3 , D4 , D5 , D6

  校验码Pn只能放在第 2 n,n ∈ N 位 上,将校验码填好后,再按顺序把原数据填好,填满这十位。

数据位 1 2 3 4 5 6 7 8 9 10
代码 P1 P2 D1 P3 D2 D3 D4 P4 D5 D6
实际值 ? ? 1 ? 0 1 1 ? 0 1

三、求出校验码的值

  首先,我们上一步已经得到了数据 D = 101101中相关数据的位置,如下表所示。

数据位 1 2 3 4 5 6 7 8 9 10
二进制 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010
代码 P1 P2 D1 P3 D2 D3 D4 P4 D5 D6
实际值 ? ? 1 ? 0 1 1 ? 0 1

  如何计算P1:P1所在位数的二进制位是0001,从右往左第一位为1,而除P1 外,D1 , D2 , D4 , D5的所在位数的二进制位从右往左的第二位也为1,那就另P1 ⊕ D1 ⊕ D2 ⊕ D4 ⊕ D5 = 0,即可算出 P1 的值为0 。

  如何计算P2:P2所在位的数的二进制位是0010,从左往右第二位是1,那就找他后面从左往右第二位也是1的,即D1 , D3 , D4 , D6,同样的令P2 ⊕ D1 ⊕ D3 ⊕ D4 ⊕ D6 = 0,即可得到P2 = 0 。

  同样的方法可得:P3 ⊕ D2 ⊕ D3 ⊕ D4 = 0 => P3 = 0,P4 ⊕ D5 ⊕ D6 = 0 => P4 = 1 。

那么101101的海明码就为0010011101

上面那个表就可以写完整了:

数据位 1 2 3 4 5 6 7 8 9 10
二进制 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010
代码 P1 P2 D1 P3 D2 D3 D4 P4 D5 D6
实际值 0 0 1 0 0 1 1 1 0 1

(想出这个的科学家真的是太牛太厉害了)

  上网查了一下,人家就是因为发明这个拿到了图灵奖。要多向牛人学习。没准将来我也能那个图领奖呢。狗屁个,拿个蓝桥杯三等奖都够呛了

上一篇:介质访问控制 MAC


下一篇:计算机网络(三)—— 数据链路层(1):数据链路层概述