计算机网络——数据链路层
数据链路层
数据链路层主要讨论六方面的问题：
- 组帧
解决封装成帧，透明传输的问题
- 差错控制
纠错编码及检错编码
- 流量控制与可靠传输
- 介质访问控制
控制对物理介质的访问（物理的链接大多都是共享的）
- 局域网
- 广域网
- 数据链路层设备
网桥、交换机
写在前面一些需要注意的一些东西
数据链路层的主要作用在于加强物理层的传输原始比特流的作用，将物理层提供的可能出错的物理连接改造成逻辑上无差错的数据链路。
数据链路层传输单位是帧，范围是两个相邻的结点间。（其实各层的传输单元都可以笼统的称为数据帧）
数据链路要协调两个结点之间的速度，即流量控制。（保证接收方能过够及时的接收数据，防止数据丢失）
交换机能够实现存储交换，交换机两端可以使用不同的链路层协议，以及连接速率不同的链路。
CRC检验码能够检查出所有的单比特错误
数据链路层基本名词解释
三个基本问题
数据链路层协议有很多种，而有三个基本问题是共同的。（而不是指链路层只有这三个问题，比如还有流量控制，介质访问控制，可靠传输等）
- 封装成帧
封装成帧指的是在一段数据的前后分别添加上首部和尾部，构成帧。
帧是链路层传输的基本数据传送单元。
首部和尾部中包含控制信息，且一个重要的作用是确定帧的界限，即帧定界。
接收方能够从收到的比特流中区分出帧的起始与终止，即帧同步。
为了提高帧的传输效率，因尽可能的提高数据在帧中的比例，但随着帧长的增加，在传输过程中发生差错的概率也随之提升，而发生差错的代价也随之增大（时常直接丢弃出错的整个帧）。因此各种协议都会规定帧的数据部分的长度上限，即最大传送单元（Maximum Transmission Unit， MTU）。（！！！！！ 最大传输单元只包括数据部分，只包括数据部分，不要记错了。）
透明传输
透明传输指不论传输的数据是什么样的比特组合，都能够按照原样的在数据链路上传输。
差错检测
略，字面意思。
链路（物理链路）
指从一个结点到相邻结点的一段物理线路。
数据链路（逻辑链路）
在一条链路上传输数据时，除了需要链路本身，还需要一些必要的通信协议来控制数据的传输，把实现这些协议的软件和硬件加到链路上，就构成了数据链路。
帧
数据链路层对等实体之间进行逻辑通信的协议数据单元。
为网络层提供的三种服务
无确认的无连接服务
源主机发送数据帧之前不需要建立链路连接，目的主机接收到帧时不需要发送确认。数据传输的可靠性由高层负责。适用于误码率较低的信道，如以太网。
有确认的面向连接服务
帧传输分为三个阶段：建立链路、传输帧、释放链路。目的主机每收到一个帧都要返回确定。适合要求可靠性比较高的场合。
有确认的无连接服务
源主机发送帧前不需要建立链路连接，但目的主机接收到帧需要返回确认。源主机在所规定的时间内未收到确认则认为帧丢失，重传帧以提高传输的可靠性。该服务适用于误码率较高的信道，如无线通信。
有链接就一定有确认，不存在无确认的面向连接的服务
数据链路层使用的两种信道
- 点对点信道
PPP协议时目前使用最广泛的点对点协议。
- 广播信道
一对多的广播传播方式。
帧传输过程中可能出现的两种错误
- 位错
帧中某些位出错，通常采用循环冗余检验（CRC）来检测。
- 帧错
包括帧丢失、帧重复和帧失序等，都属于传输错误，常用帧编号的方式来检测这些错误。
组帧
组帧主要解决帧定界，帧同步和透明传输的问题。
由于字符计数法中的技术字段的脆弱性和字节填充法实现上的复杂性与不兼容性，所以目前较常用的是零比特填充法和违规编码法
字符计数法
字符计数法在帧首部使用一个计数字段来记录该帧所包含的字节数。接收方通过读帧首部的计数字段就能够计算出帧的结束位置（从而不需要尾部）。
这种方法最大的问题在于若计数字段出错，随后所有的帧边界划分依据都将出错，收发双方失去同步，造成灾难性后果。
字节填充法
使用特定的字节来定界一帧的开始与结束。
SOH放在帧的最前面表示帧的开始。
EOT放在帧的末尾表示帧的结束。
ESC是ASCII中的控制字符，是一个字符，而非’E’,’S’,’C’三个字符的组合。被用作转义字符，用来实现透明传输。当特殊字符需要出现数据中时，在其前加上转义字符，从而防止其被识别位控制信息。
零比特填充法
零比特填充法允许数据帧包含任意个数的比特，它使用一个特定的比特串01111110（六个1嗷）来标志一个帧的开始和结束。
为了不是数据字段出现01111110被误判为帧的首位标志。发送方在发射前先扫描整个数据字段，每遇到5个连续的1，就在其后插入一个0。接收方之后对其反操作即可恢复原始数据。
零比特填充法很容易使用硬件实现，性能优于字节填充法。
零比特填充法在数据链路层早期被使用在HDLC协议中。
违规编码法
在物理层进行比特编码时，常采用违规编码法。如曼彻斯特编码将数据比特’1’编码为’高-低’电平对，’0’为’低-高’电平对，而’高-高’与’低-低’电平对是违规的，可以借用这些违规编码来界定帧的开始和结束。
局域网IEEE 802标准就采用了违规编码法。违规编码法不采用任何填充技术便能够实现数据的透明传输，但只适用于采用冗余编码的特殊编码环境。
差错控制
实际通信链路都不是理想的，数据在传输过程中可能产生差错。
我们常讨论的传输差错常分为两种：
- 帧差错（帧错）
也就是上面说的帧失序，帧丢失，帧重复等
- 比特差错（位错）
下面我们仅讨论比特差错，帧差错会在可靠传输机制中讨论。
通常采用编码技术进行差错控制，主要分为两类：
- 自动请求重传（Automatic Repeat reQuest，ARQ）
接收方检测到错误是，就请求发送方重传，直到接收到正确的数据。
- 前向纠错（Forward Error Correction，FEC）
在FEC方式中，接收方不仅能够发现错误，而且能够确定错误的位置并加以改正。
因此差错控制分为
- 检错编码
- 纠错编码
两类。
检错编码
检错编码都采用冗余编码技术。常见的检错编码有
- 奇偶校验码
- 循环冗余检验码
奇偶检验码
奇偶检验码是奇检验码和偶检验码的统称，是一种最基本的校验码。它由n-1位数据和1位检验位组成，检验位的取值（0或1）将使整个检验码中“1”的个数为奇数或偶数。
特点：
只能检验奇数位数据是否出错，且无法知道哪些位错了，而且无法检验出偶数个出错位的情况。
循环冗余码
循环冗余校验（Cyclic redundancy check）被广泛引用于数据链路层。CRC实际上拥有纠错的能力，但在数据链路层常常只用其检错。
CRC能过够检测出所有的单比特错误。
- 约定好一个生成多项式，利用二进制串表示。此二进制串有r位，且最高位与最低为都为1
- 生成的冗余码位r位
- 检验时是数据与冗余码拼接，除生成多项式。若无差错，则可整除。
循环冗余校验的数学原理
CRC的数学基础是模2剩余类域上的一元多项式环。 - 模2剩余类域：
由0和1构成的集合，定义了以下的加法与乘法运算，并且加法满足交换律、结合律，乘法满足交换律、结合律，加法与乘法满足左、右分配律，便是一个 模2剩余类域。
加法规则：
$ 1 + 1 = (1+1)\mod2=0$
$ 1 + 0 = (1+0)\mod2=1$
$ 0 + 1 = (0+1)\mod2=1$
$ 0 + 0 = (0+0)\mod2=0$乘法规则：
$1\cdot1=(1\cdot1)\mod2=1$
$1\cdot0=(1\cdot0)\mod2=0$
$0\cdot1=(0\cdot1)\mod2=0$
$0\cdot0=(0\cdot0)\mod2=0$
模2剩余类域上，减法是基于加法定义的，减一个数就是加上这个数的负元。某个数的负元就是跟这个数相加等于0的的那个数。于是，由上面的加法规则，可以知道，1的负元是1自己，0的负元是0自己。于是便有如下的减法运算。
- 减法规则：
$1-1=1+(-1)=(1+1)\mod2=0$
$1-0=1+(-0)=(1+0)\mod2=1$
$0-1=0+(-1)=(0+1)\mod2=1$
$0-0=0+(-0)=(0+0)\mod2=0$
由上面，可以看出，模2剩余类域上的减法与加法运算法则是一样的，没有区别。另外，若把模2剩余类域中的数看作二进制数位，便可发现，其加法运算法则与减法运算法则，与二进制数位的异或运算法则等同。
// tood，补全数学原理
循环冗余码的计算过程
- 设生成多项式 $ G(x)$ 为r阶，在数据后面加上r个0，相当于乘以 $2^r$。
- 利用模二除法，用1）除 $ G(x)$ 得到的余数即为冗余码。