计算机网络数据链路层
功能一：为网络层提供服务。无确认无连接服务，有确认无连接服务，有确认面向连接服务
功能二：链路管理，即连接的建立、维持、释放(用于面向连接的服务)
功能三：组帧
功能四：流量控制
功能五：差错控制(帧错/位错)
不同的协议提供不同的功能组合!!!
组装成帧
封装成帧
帧首部和帧尾部作用有：帧定界、差错控制、流量控制以及物理地址
帧定界的方法(未必会在协议中使用、下仿)
字符计数法
每个帧的第一个字节描述帧的长度
字符填充法
ESC转义的字符填充法
零比特填充法
非常优秀的帧定界方法
违规编码法
注：网络总是发送低地址处的内容先，网络中的字节序是大端字节序(对整型和浮点型适用)
差错控制
位错：1变成0或0变成1
帧错：丢失、重复和失序
数据链路层不是所有协议都会有差错控制的；不进行差错控制的情况下，可靠传输由上层保证
检错编码：奇偶校验码、CRC
纠错编码：海明码
奇偶校验码
奇和偶是相对 1 的比特数量而言；只能检查出奇数个比特错误，检错率为50%
CRC
除法是模二除法；CRC检错率高，不能纠错；我们默认CRC能以接近100%的几率检测错误
模二除法
进行除法竖式计算的时候
加法不进位、减法不借位
但是进行减法时要保证被减数和减数(去前置零)位数相同
等价于：加法和减法都进行xor操作
海明码(能纠错1bit错误的编码)
海明距离定义：两个合法编码对应比特模式取值不同的比特位数称为这两个编码的海明距离。在一个有效编码集中，任意两个合法编码的海明距离的最小值称为该编码集的海明距离。
要检测d比特的错误，编码集的海明距离至少为 d+1；
要纠正d比特的错误，编码集的海明距离至少为 2d+1；
海明不等式： 2^r >= m + r + 1 ; m是raw数据的比特数，r是检验码的比特数
Example：
发送方处理：
raw数据为1100，海明比特分别插入第2^n (n>=0) 位
将r位检验码分别放在第2^n(n是非负整数)位中；其中，第2^n位作为检错位负责所有第n+1比特位为1的序号所对应的比特位的奇偶检验
假设传输工程中数据的第5位出错
接收方处理：
校验结果
求异或方程
纠错，写异或方程，转置比特结果
流量控制与可靠传输机制
(1) 数据链路层的流量控制手段：接收方收不下就不回复确认
(2) 传输层流量控制手段：接收方收不下就发送一个窗口公告
(3) 停止等待协议、滑动窗口协议适用于数据链路层或传输层
(4) 在当代计算机网络中，数据链路层一般不再负责可靠传输
基于可靠信道传输的停止等待协议
基于自动重传协议的停止等待协议
发送帧丢失的情况下
确认帧丢失
确认帧丢失
(1) 发送完一个帧后，需要保留它的副本(以便可能的重传)
(2) 数据帧和确认帧都需要编号
(3) 基于自动重传的停止等待协议一般用于有差错的链路
(4) 该协议的信道利用率巨低
(5) 发送窗口的最大的大小为帧序号取值范围减一
信道利用率及其计算公式，Ta为确认帧的发送时延，一般忽略不计
基于后退 N帧协议的滑动窗口协议
发送窗口大小 > 1，接收窗口大小 = 1
只有一个超时计时器负责最近的未被确认的帧，王道书的图是错误的
(1)GBN协议采用累积确认以及捎带确认的方式
(2)接收方只接受下一个连续的帧号(其余丢弃)
(3)接收方收到乱序的帧号后会重新累积确认帧
(4)超时计时器只负责下一个连续的未确认的帧
(5)当一个帧超时了，当前帧以及后面的所有帧都需要重传(后退N帧)
(6)收到一个帧后，计时器才会为下一个帧重开
注1：如果采用n个比特对帧编号，则发送方滑动窗口的大小为 [1, 2^n – 1]
注2：在数据链路层中的数据发送过程中，发送窗口和接收窗口的大小是不变的！
基于选择重传协议的滑动窗口协议
每一个已经发送但未被确认的帧都有一个计时器；发送窗口大小 > 1，接收窗口大小 > 1
对于滑动窗口协议有以下结论：发送、接收窗口大小之和不应该超过帧序号取值范围的一半；接收窗口的大小不应该大于发送窗口的大小
(1) 本质上，停止等待协议也是一种特殊的滑动窗口协议；进一步说，都是滑动窗口协议
(2) 滑动窗口协议的一个通讯周期为第一个窗口的帧刚开始发出到收到该帧的确认帧为止
(3) 在没有链路引起的其他任何差错的情况下，如果发送窗口大小内的所有比特的发送时延能达到一个通讯周期的时间的话，那么该信道的利用率能达到100%
介质访问控制
广播式链路
广播式链路的介质访问控制
频(率)分多路复用(FDM)：效率高，技术成熟
时(间)分多路复用(TDM)：
每个“发送用户”占用TDM中的一个时隙
(基于)统计时(间)分多路复用(STDM)：
波分多路复用/光纤专用的频(率)分多路复用(FDM)：
码分多路复用：
码分多址(CDMA)
(0): 每个发送站点分配一个芯片序列，例如(-1,+1,+1,-1,-1,-1,-1,+1)
(1): 每个源站的芯片序列都相互正交，即规格化内积/数量积为0
(2): 发送1的时候发送芯片序列，否则发送芯片序列的反码表示发送0
(3): 各个发送站点发送的数据(芯片序列/芯片序列的反码)线性相加再发送
(4): 信道上的合并后的数据与源站的芯片序列的规格化内积除以芯片序列的长度
纯Aloha协议/想发就发协议
时隙Aloha协议/仅在时隙开始想发就发协议
(1): 接收方负责判断是否冲突
(2): 超时重传
(3): 纯aloha协议的发送效率更低
载波监听多路访问(CSMA)
(0): 发送数据帧之前需要监听信道是否有其它计算机正在发送数据，若有则推迟发送
1-坚持CSMA
(1) 空闲则立即传输
(2) 忙则一直监听，一旦空闲马上传输
(3) 如果有冲突，随机时间后再监听
非坚持CSMA
(1) 空闲则立即传输
(2) 忙则随机时间后再监听
(3) 如果有冲突，随机时间后再监听(王道书未指明)
p-坚持CSMA
(1) 只能在时隙开端传输数据帧
(2) 空闲则以概率p传输，否则在下一个时隙的开端转(2)
(3) 忙则在下一个时隙的开端转(2)
(4) 如果有冲突, 在下一个时隙的开端转(2)(王道书未指明)
注意：书或网上资源与笔记不符合、以笔记为准
CSMA/CD 协议
(0): 发送数据帧之前和发送数据帧之时都需要监听信道是否有其它计算机正在发送数据
截断的二指数退避算法(争用期为最优RTT)
(1) 最小帧长 = 2 * 传输时延 * 数据传输速率
(2) 以太网的最小帧长是64字节
CSMA/CA 协议
使用RTS和CTS进行冲突避免
(0): 发送数据帧之前需要监听信道是否有其它计算机正在发送数据
(1): CSMA系列协议中唯一采用ACK帧进行确认的协议
- 如果该站最初检测到信道空闲，则会在称为分布式帧间空间 (DIFS) 的短时间后发送RTS
- Destination在收到RTS帧之后决定是否回应CTS，若回应则需要等待在称为最短帧间空间 (SIFS) 的短时间后发送CTS
- 发送站点收到CTS后，在SIFS之后发送数据
- 接收站点收到DATA后，在SIFS之后发送ACK
如果冲突避免不理想，考虑使用二进制指数退避算法结合重发
轮询协议
主节点轮流“询问”其它节点是否发送数据
令牌传输协议
适用于数据量较大的网络