数据链路层

数据链路层核心功能，封装成帧、差错控制、流量控制与介质访问控制原理

功能

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

功能一：为网络层提供服务。
- 无确认无连接服务
- 有确认无连接服务
- 有确认面向连接服务。（有连接一定有确认）
功能二：链路管理，即连接的建立、维持、释放（用于面向连接的服务）
功能三：组帧
功能四：流量控制（限制发送速度）
功能五：差错控制（帧错/位错）

封装成帧

封装成帧的目的就是让数据能够被识别，在数据丢失时，能够溯源

在实际操作上，封装成帧就是在一段 数据的前后添加首部和尾部 ，构成帧。接收端在收到物理层上交的比特流后，就能根据首部和尾部的标记，从收到的比特流中 识别帧的开始和结束。

因此，首部和尾部一个重要的作用就是：帧定界（由帧定界符控制），当然它还包含了许多的控制信息

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

datalink-1

组帧的四种方法：

字符计数法
字符（节）填充法
零比特填充法
违规编码法

透明传输

意思就是不管所传输的数据是什么样的比特组合，都可以在链路上传输。链路层看不见有什么东西妨碍了数据的传输，

帧使用首部和尾部进行定界

如果帧的 数据部分 含有和首部尾部 相同的内容 ，那么帧的开始和结束位置就会被 错误的判定 。需要在数据部分出现首部尾部相同的内容前面 插入转义字符。
如果数据部分出现转义字符，那么就在转义字符前面再加个转义字符。
在接收端进行处理之后可以还原出原始数据。这个过程透明传输的内容是转义字符，用户察觉不到转义字符的存在。

字符填充法

加头加尾分别标记开始结束，和零比特填充法（见下）对比，开始和结束的对应的字符不一样

但有可能出现数据内某段比特流数据正好与标记字段重复，从而导致误判断的情况

因此会通过添加 转义字符 ，来标记那些重复的数据，在解析的时候就不会认为这些数据为开始和结束了

datalink-2-1

零比特填充法

和字符填充的思路是差不多的，零比特填充首位的标志位都是一样的 0111110

因此，在数据流中也有可能存在相同的字符，这里会采用补 0 的方式，来解决这个冲突的问题

在发送端，会扫描整个信息字段，只要连续 5 个 1，就会填入 1 个 0
在接收端，会对比特流进行扫描，发现 5 个连续的 1 时，就会删除后面的 0

datalink-2-2

差错控制（检错编码）

传输中的差错都是由噪声引起的。可以通过 提高信噪比 来减少或者避免干扰。

1. 奇偶校验码

操作方法就是：发送的时候通过添加一位附加比特来形成奇数码

奇偶校验码特点：只能检查出奇数个比特错误，检错能力为 50%

因为，一段数据中，一个从 0 --> 1 ，一个从 1 --> 0 ，0，1 的数量是不变的，无法检测出错误。只能检测出 1，3，5 等这些奇位数错误

datalink-3

2. 循环冗余码 CRC

循环冗余检验 CRC
- 目前数据链路层广泛使用了 循环冗余检验（CRC）来检查比特差错。
帧检验序列 FCS
- 在数据后面添加上的冗余码 称为帧检验序列 FCS (Frame Check Sequence)。
概要: CRC 是一种常用的检错方法，而 FCS 是添加在数据后面的冗余码。
- FCS 可以用 CRC 这种方法得出，但 CRC 并非用来获得 FCS 的唯一方法。

如果数据链路层接收了这个帧，说明这个帧没有差错

这种也不是可靠传输，因为有一些帧会被丢弃掉，并不是发送什么就接受什么

差错控制（纠错编码）

海明码

首先需要确认检验码的位数
- 满足 2 的 r 次方大于等于 k + r + 1
确定校验码和数据的位置
- 检验码放在 2 的次方的位置，1，2，4，8...
- 数据依次添满
求出校验码的值
- 通过二进制位确定有几位
- 然后看检验码的二进制位的数值和所有信息位的对应位置的数值是否相同，然后找出来这些位
  - 例如第一个检验码 0001，那么和他一起的信息码就是第一位为 1 的，例如 0011,0111,这些都是
- 接着把这些数异或一下，就是这些检验码的值
检错并纠错
- 按照检错的位数，通过异或来得到出错的是第几位

流量控制与可靠传输机制

较高的发送速度和较低的接收能力不匹配，会造成传输出错，因此需要进行流量的控制

传输层和数据链路层都会进行流量控制，两者有一定的区别

数据链路层的流量控制是点对点的
接收方收不下就不回复确认（确认帧），这样就不会继续发送下一个
传输层的流量控制是端到端的
接收端给发送端发送一个窗口公告

可靠传输：发送端发啥，接收端收啥

流量控制：控制发送速率，使接收方有足够的缓冲空间来接收每一个帧

停止等待协议

停止等待协议存在的意义：除了比特出差错，底层信道还会出现丢包的问题

有两种不同的应用情况

无差错情况
有差错情况

1. 无差错情况

一次只发送一个帧，可以用 0、1 标记 ack

发送方收到了确认就可以继续发送下一帧

虽然是 0、1 ，但是每一帧都是不一样的内容

2. 有差错情况

在发送数据的时候，会设置一个定时器，当超过时间后，没有收到对方的 ACK 确认应答报文后，会重发这个数据，也就是超时重传

定时器设定的时间也很有讲究，需要大于 RTT

RTT 指的是数据发送时刻到接收到确认的时刻的差值，也就是包的往返时间。

有可能因为这两种情况发送超时重传

数据包丢失
ACK 丢失
ACK 迟到
- 来晚了不会处理，会直接丢弃

缺点：停止等待协议的信道利用率比较低

GBN 协议

连续发送，提高信道利用率

datalink-4-1

这样每一帧的序号都需要是不一样的，接收端才能返回唯一对应的帧
发送方需要缓存多个分组，因为有可能会帧丢失，所以需要重发，需要先缓存下来

累计确认：就是收到一个确认帧，那么它和它之前的所有帧都默认已收到，反之，如果某个确认帧没收到，那么它和它之后的所有帧都默认丢失（即使收到了也丢掉），进行重传

发送方做的事情

datalink-4-2

接收方做的事

如果正确收到 n 号帧，并且按序，那么接收方为 n 帧发送一个 ACK，并将该帧中的数据部分交付给上层

其余情况都丢弃帧，并为最近按序接收的帧重新发送 ACK。接收方无需缓存任何失序帧，只需要维护一个信息：expectedseqnum（下一个按序接收的帧序号）

GBN 重点

累积确认
接收方只按顺序接收帧，不按序的会被丢弃
确认序列号最大的，按序到达的帧
发送窗口最大为 2^n - 1 接收窗口为 1

GBN 协议性能分析

因连续发送数据帧而提高了信道利用率

在重传时必须把原来已经正确传送的数据帧重传，使传送效率降低

滑动窗口

滑动窗口的大小决定了发送方连续发送帧的数量，不需要等待 ACK 可以继续发送，但是此时窗口不会移动，只是发窗口里的帧，由于数据中帧有可能会重复

例如： 01230123

那么如果窗口过长，窗口大小大于了 4 时，无法确定接收到的 ACK 0 为第一次的确认帧，还是第二次的确认帧，因此滑动窗口的大小应当限制在 2 ^ n - 1 内

SR 协议

发送方要做的事

收到数据后，检查下一个可用于该帧的序号，如果位于发送窗口，发送数据帧
收到 ACK 时，如果是窗口的下届，窗口移动，否则继续等
超时事件，超时重传

接收方做的事

SR 接收方，不管是否按序都会接收。如果不是按序的话，会先缓存起来，把这些都排好序，等到最小的那个帧被收到了，这时候就可以交付这些帧，窗口移动

每接收到一个帧都会发送一个 ACK

滑动窗口长度

发送窗口大小等于接收窗口，2 的（n - 1) 次方

重点

逐一确认
只重传出错的帧
接收方会缓存非按序的帧

信道复用技术

频分复用、时分复用和统计时分复用

频分复用 FDM
- 用户在分配到一定的频带后，在通信过程中自始至终都占用这个频带。
时分复用 TDM
- 时分复用则是将时间划分为一段段等长的时分复用帧。每一个时分复用的用户在每一个 TDM 帧中占用固定序号的时隙。
统计时分复用 STDM
- 是对时分复用的一种改进，不固定每个用户在时分复用帧中的位置，只要有数据就集中起来组成统计时分复用帧然后发送。

波分复用

波分复用 WDM
- 光的频分复用。由于光的频率很高，因此习惯上用波长而不是频率来表示所使用的光载波。

码分复用

码分复用 CDM
- 常用的名词是码分多址 CDMA
- 各用户使用经过特殊挑选的不同码型，因此彼此不会造成干扰。
- 这种系统发送的信号有很强的抗干扰能力，其频谱类似于白噪声，不易被敌人发现。
- 每一个比特时间划分为 m 个短的间隔，称为码片。

ALOHA 协议

1. 纯 ALOHA 协议

思想：不监听信道，不按时间槽发送，随机发送，想法就发

冲突解决：发送方在一定时间内收不到确认就判断为发生冲突，会等一个随机时间进行重传

2. 时隙 ALOHA 协议

和纯 ALOHA 相比，限制了发送的时间，有点类似于 Fiber，就只能在规定的时间片发送数据

纯 ALOHA 比时隙 ALOHA 吞吐量更低，效率更低
纯 ALOHA 想发就发，时隙 ALOHA 只有在时间片段开始时才能发

CSMA 对比

CSMA 是指载波监听多路访问协议

CS：载波监听，每一个站在发送数据之前都要检测一下总线上有没有其他的计算机在发送数据
MA：多点接入，许多计算机以多点接入的方式接在一根总线上

1-坚持 CSMA

如果一个主机要发送信息，会先监听信道，空闲则会直接传输，不等待

如果忙的话，会一直监听，直到空闲后马上传输
如果有冲突，会等待一个随机时间，再来一次

优点：只要媒体空闲，站点就马上发送，避免了媒体利用率的损失

非坚持 CSMA

对于信道忙的信道就不再监听，忙的话就等待一个随机时间再进行监听

优点：采用随机的重发延迟时间可以减少冲突发生的可能性
缺点：可能存在大家都在延迟等待过程中，使得媒体仍可能处于空闲状态，媒体使用率降低

p - 坚持 CSMA

对于监听信道空闲的处理，空闲则以 p 概率直接传输，不必等待，概率 1-p 等待到下一个时间槽在传输

忙则持续监听直到信道空闲再以 p 概率发送

若冲突则等待下一个时间槽开始再监听

缺点：发生冲突后，还是要坚持把数据帧发送完，造成浪费

CSMA / CD 协议

CSMA/CD 表示载波监听多点接入 / 碰撞检测。

多点接入 ：说明这是总线型网络，许多主机以多点的方式连接到总线上。
载波监听 ：每个主机都必须不停地监听信道。在发送前，如果监听到信道正在使用，就必须等待。
碰撞检测 ：在发送中，如果监听到信道已有其它主机正在发送数据，就表示发生了碰撞。虽然每个主机在发送数据之前都已经监听到信道为空闲，但是由于电磁波的传播时延的存在，还是有可能会发生碰撞。

记端到端的传播时延为 τ，最先发送的站点最多经过 2τ 就可以知道是否发生了碰撞，称 2τ 为争用期。只有经过争用期之后还没有检测到碰撞，才能肯定这次发送不会发生碰撞。

当发生碰撞时，站点要停止发送，等待一段时间再发送。这个时间采用截断二进制指数退避算法来确定。从离散的整数集合 {0, 1, .., (2k-1)} 中随机取出一个数，记作 r，然后取 r 倍的争用期作为重传等待时间。

datalink-5

最小帧长

为了在碰撞检测的时候，数据还没有发送完，不然有可能一次全发送完了，还没有检查，那 CSMA / CD 协议的意义就没有了

因此需要规定最小的帧长，防止没有检测到碰撞

最小帧长 = 总线传播时延X数据传输速率 X 2
2t X 数据传输速率

CSMA / CA

和 CSMA / CD 不同的是，CD 是碰撞的检测，CA 是碰撞的避免

应用场景不同，主要用于无线局域网

工作原理

在发送数据前，会先检测信道是否空闲，如果空闲则会发送 RTS ，可以理解为是发送数据的信号，接收端会响应一个 CTS

CSMA / CD / CA 的差异

相同点

CSMA/CD 与 CSMA/CA 机制都从属于 CSMA 的思路，其核心是先听再说。换言之，两个在接入信道之前都需要进行监听。当发现信道空闲后，才能进行接入。

不同点

传输介质不同：CSMA/CD 用于总线式以太网【有线】，而 CSMA/CA 用于无线局域网【无线】
载波检测方式不同：因传输介质不同，CSMA/CD 与 CSMA/CA 的检测方式也不同。
- CSMA/CD 通过电缆中电压的变化来检测，当数据发生碰撞时，电缆中的电压就会随着发生变化；
- 而 CSMA/CA 采用能量检测（ED）、载波检测（CS）和能量载波混合检测三种检测信道空闲的方式
CSMA/CD 检测冲突，CSMA/CA 避免冲突，二者出现冲突后都会进行有上限的重传

局域网

局域网是一种典型的广播信道，主要特点是网络为一个单位所拥有，且地理范围和站点数目均有限。

主要有以太网、令牌环网、FDDI 和 ATM 等局域网技术，目前以太网占领着有线局域网市场。

可以按照网络拓扑结构对局域网进行分类：

datalink-6

以太网

以太网是一种星型拓扑结构局域网。

早期使用集线器进行连接，集线器是一种物理层设备，作用于比特而不是帧，当一个比特到达接口时，集线器重新生成这个比特，并将其能量强度放大，从而扩大网络的传输距离，之后再将这个比特发送到其它所有接口。如果集线器同时收到两个不同接口的帧，那么就发生了碰撞。

目前以太网使用交换机替代了集线器，交换机是一种链路层设备，它不会发生碰撞，能根据 MAC 地址进行存储转发。

以太网帧格式：

类型：标记上层使用的协议；
数据：长度在 46-1500 之间，如果太小则需要填充；
FCS ：帧检验序列，使用的是 CRC 检验方法；

以太网的帧结构

datalink-7-1

其中目的地址和源地址指的是 MAC 地址，即设备的物理地址。MAC 地址用于标示网卡，每个网卡都具有唯一的 MAC 地址
当在同一个局域网中，主机 A 需要给主机 B 发送消息时，主机 A 将以太网帧发出，此时局域网中所有主机均可收到这个桢，主机中的网卡接收到以太网桢后，会将目的 MAC 地址和自己的 MAC 地址进行比较, 如果不相同就会丢弃，如果相同则会接收，此时则Ｂ主机就收到了Ａ的消息。
其最后面是 CRC 循环冗余码，用于差错控制，即检验帧的正确性
在以太网协议中，目的地址分为三种单播地址、广播地址、多播地址，其中单播地址如上面Ａ给Ｂ主机发送，其接收者为一个，并且其目的地址的最高字节的低位为０