链路层的功能
链路层的信道
局域网&广域网
链路层的设备

基本概念

结点：主机、路由器
链路：节点之间的物理通道，经过传输介质
数据链路：节点之间的逻辑通道，为链路补充实现控制数据传输协议的硬件软件
帧：链路层的协议数据单元，封装网络层数据报

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

数据链路层在物理层提供的基础上向网络层提供服务的基础上向网络层提供服务，其最基本的服务是源自网络层来的可靠的传输到相邻节点的目标机网络层。作用为加强物理层传输原始比特流的功能，将可能出错的物理链路转化为逻辑无差错的数据链路，为网络层提供服务。

功能
- 为网络层提供服务
  - 无确认无连接服务
  - 有确认无连接服务
  - 有确认面向连接服务
- 链路管理，即建立、维持、释放面向连接的服务
- 组帧
- 流量控制（限制发送方）
- 差错控制（帧错/位错）

帧封装&透明传输

封装成帧是在网络层数据报前后添加帧定界符，帧首部及帧尾部，包含控制信息，从而有效达成接收方的帧同步。

从帧的开始到帧的结束称为数据链路层的帧长，通常希望帧数据远大于帧头部和帧尾部，从而达成有效数据传输。其中对于不同帧具有最大帧长度，而帧的数据部分最大称为最大传送单元MTU，通常要求数据部分小于等于MTU.

透明传输

不管传输数据是什么样的比特组合，都能在链路上传送，透明指看不见妨碍数据传输的事物。但当传送数据中的比特组合恰巧于某一控制信息相同时，要求采取适当措施使接收方不会将数据误认为控制信息。

四种成帧方法
1. 字符计数法
  - 帧首部通过计数字段标明帧内字符数
2. 字符填充法
  - 帧首和帧尾使用特定填充字符进行标明
  - 防止错误接收帧头尾信息，前填充转义字符
3. 比特填充法*
  - 开始结束01111110
  - 信息内连续5个1填充一个0
4. 违规编码法*
  - 作为编码中不会使用的标识作为帧定界符

差错控制

传输中的差错由噪声产生

由于线路本身电气特性产生的随机噪声，是信道固有随机存在的，需要尽可能提高信噪比（传感器）（全局性）
由外界特定短暂原因产生的冲击噪声，是产生差错的主要原因，通常利用编码技术解决（局部性）

差错
- 位错：比特出错
- 帧错：
  - 帧丢失
  - 帧重复
  - 帧失序

差错控制当今主要面向通信质量差的无线传输链路，如有确认无连接服务和有确认面向连接服务，而无确认无连接服务通常为当今可靠的光纤宽带，差错概率低

通过差错控制丢弃错误的帧，差错控制主要面向比特错，使用检错编码或纠错编码进行控制。物理层编码针对单个比特，解决传输过程中的比特同步。数据链路层编码针对一组比特，通过冗余码技术实现差错检验。

检错编码
- 奇偶校验码
- 循环冗余码CRC
纠错编码
- 海明码

检错编码

奇偶校验码
- n-1个信息元+1位校验元（奇校验，加入1或0使总码元中1个数为奇数）
- 只能检测奇数个比特错误，检错能力为50%
循环冗余码CRC
- 接收端判断余数是否为0，如存在差错则丢弃
- 循环冗余码基本可以确定接收帧无差错

纠错编码

海明码
- 发现双比特错，纠正单比特错
- 工作流程
  - 确定校验码位数r
    - 海明不等式$$2^r \ge k+r+1$$ （r为冗余信息位，k为信息位）
  - 确定校验码和数据位置
    - 校验码插入数据中，校验码置于二的次方位
  - 求出校验码值
    - 要求所有二进制排列校验集合异或为0
  - 检错并纠错
    - 令所有需要校验的位异或纠错

流量控制&可靠传输机制

较高发送速度和较低接受能力的不匹配，会造成传输出错。数据链路层流量控制点对点，控制手段为不进行回复。传输层流量控制端到端，控制手段为窗口公告。

流量控制方法：

停止等待协议（发送窗口大小=1，接收窗口大小=1）
滑动窗口协议
- 后退N帧协议（发送窗口大小＞1，接收窗口大小=1）
- 选择重传协议（发送窗口大小>1，接收窗口大小=1）

可靠控制：发送方发啥，接收端收啥

流量控制：控制发送速率，使接收方由足够缓存空间接收每个帧

滑动窗口解决——》流量控制（受确认限制），可靠传输（发送方自动重传）

停止-等待协议

解决比特差错及信道丢包问题，同时实现流量控制

研究前提：仅考虑单向发送，不考虑数据传送层次

没发送完一个分组就停止发送，等待确认，在收到确认后发送下一分组

有差错情况etc

协议简单但信道利用率低$$U=\frac{T_D}{T_D+RTT+T_A}$$（TD为发送时延，TA为确认时延，RTT为往返时延）

*信道利用率指发送方在一个发送周期内有效发送数据所需时间占整个发送周期的比率，信道利用率=（T内发送比特数据长度L/发送方传输速率C）/发送周期T=信道吞吐率/发送周期
信道吞吐率=信道利用率发送方发送速率

后退N帧协议(GBN)

对停等协议的补充：增加发送序号范围，发送方缓存多个分组

GBN协议，滑动发送窗口，发送一组连续允许发送帧的序号，接收方维持一组连续的允许接收帧的序号。即发送窗口大于1，接收窗口等于1。

发送方收到确认，向前平移窗口。发送方三个部分：发完已确认，发完待确认，可发送部分，不可发部分。

发送方响应
- GBN协议对上层响应当前窗口状态决定上层是否将数据下行（或进行缓存
- 响应收到ACK，可对n号帧累计确认，进行滑动窗口并发送可发送帧
- 响应超时事件，重发整个窗口
接收方响应
- 对正确收到的帧交付上层并返回ACK
- 其余情况丢弃，返回前顺序收到帧ACK

帧定界符中包含帧编号信息，若有n个比特对帧进行编号，则要求发送窗口尺寸WT满足$$1\le W_T\le2^n-1$$，以确保新旧帧可以有效区分

累计确认偶尔捎带确认
接收方只按序接收帧，不按序均丢弃
确认序号最大的，按序到达的帧
发送窗口最大$$2^n-1$$，接收窗口最大为1
因连续发送提高信道利用率
重传时丢失造成低下传送效率

选择重传协议(SR)

对GBN优化，只重传出错的帧，设置单个确认，加大接收窗口，设置接收缓存以缓存乱序到达帧

发送方响应
- 收到上层数据，同GBN，发送区或驳回或缓存
- 收到ACK，标记已接受，若为窗口下界则滑动窗口至最高未确认并发送可发送帧
- 超时时间，超时重传帧
接收方响应
- 收到窗内帧缓存返回ACK，若收到窗口下界则滑动窗口并提交上层
- 收到窗前帧丢弃并返回ACK
- 其他情况忽略帧

滑动窗口长度依旧受帧编码限制，发送窗口最好等于接收窗口，$$W_{R\max}=W_{R\max}=2^{n-1}$$

对数据帧逐一确认
只重传出错帧
接收方有缓存
窗口大小最大为$$W_{T\max}=W_{R\max}=2^{n-1}$$

信道划分介质访问控制

点对点链路：相邻节点通过链路连接，无第三者
- PPP协议
- 常用于广域网
广播式链路：所有主机共享通信介质
- 早期总线以太网
- 无线局域网
- 常用于局域网
- 典型拓扑结构：总线型、星形（逻辑总线、集线器）

通过介质访问控制，采用措施使得两对节点通信不会发生互相干扰

静态划分信道
- 信道划分介质访问控制
  - 频分多路复用FDM
  - 时分多路复用TDM
  - 波分多路复用WDM
  - 码分多路复用CDM
动态划分信道：动态媒体接入、多点接入，信道并非固定分配
- 轮询访问介质访问控制
  - 令牌传递协议
- 随机访问介质访问控制：所用用户任意发送信息，占全部带宽
  - ALOHA协议
  - CSMA协议
  - CSMA/CD协议
  - CSMA/CA协议

信道划分介质访问控制

将使用介质的每个设备与来自同一信道上的其他设备的通信隔离开，把时域和频域资源合理地分配给网络上的设备

频分多路复用FDM（并行）
- 用户处于不同的频段，所有用户在同样的时间占用不同的带宽资源
时分多路复用TDM（并发）
- 将时间划分为时分复用TDM帧，将每个时分复用用户在帧中占用固定序号的时隙，用户轮流占用信道
- STDM统计时分复用，根据近期使用时间分配时隙，时隙数小于用户数，动态按需分配
波分多路复用WDM
- 指光的频分多路复用，通过不同波长的光进行传输
码分多路复用CDM
- 码分多址CDMA是码分复用的一种方式
- 一个比特分为多个码片，每个站点指定一个m位的码片序列
- 发送1时发送码片序列，发送0时发送序列反码，多个站点同时发送数据时要求芯片序列正交，传输时将数据线性相加合并
- 分离时将合并数据和源站序列规格化内积
- 可以理解为源站序列作为掩码

ALOHA协议

纯ALOHA协议

不监听信道确认冲突，不按时间槽发送，随机等待重发，想发就发

时隙ALOHA协议

划分时间片，在时间片的开始上进行发送，随机等待重发。避免部分冲突，效率提高。

CSMA协议

载波监听多路访问协议

发送数据前检测总线上是否有其他计算机在发送数据

多点接入，表示多计算机多点接入总线

协议思想：发送帧之前监听信道

根据监听结果：

信道空闲：发送完整帧
信道忙：推迟发送

对应的存在三种CSMA方式

1-坚持CSMA：坚持监听信道空闲时传输，冲突则等待随机时长
- 效率高但易冲突降低效率
非坚持CSMA：随机再次监听，冲突随机等待
- 降低冲突概率但容易导致信道空闲
p-坚持CSMA：空闲时p概率传输，1-p下个时间槽传输，忙则持续监听
- 减少冲突减少空闲，但发生冲突后坚持发送数据帧造成浪费

CSMA-CD协议

载波监听多点接入/碰撞检测协议

发送数据时依旧监听信道，若振幅过大则放弃发送，节省时间

最迟需要2τ（端到端往返时延）才能发现信号未碰撞（争用期、冲突窗口、碰撞窗口）

如何确定重传时间（截断二进制指数规避算法：

确定基本退避时间（即争用期2τ）
定义参数k等于重传次数不超过10
从离散整数集合$$[0,1,\cdots,2^k-1]$$中随机取一个数r，重传退避r倍基本退避时间2rτ
当重传16次无法成功时抛弃帧报告出错

定义最小帧长，防止在冲突发生前帧长发完，因此规定帧长度大于2τ×数据传输速率

CSMA-CA协议

载波监听多点接入/碰撞避免协议

专用于无限局域网

无法做到360°全面检测碰撞
隐蔽站，当A和C都检测不到信号，认为信道空闲时，同时向B发生数据帧导致冲突

工作原理

发送数据前检测信道空闲
空闲发送RTS检测数据帧，信道忙则等待
接收端收到RTS时响应CTS，建立连接
发送端收到CTS后预约信道，告知其他站点占用时间
接收端收到数据帧后CRC检验，收到响应ACK
收到ACK进行发送，若没收到则二进制指数退避随机推迟

重点

预约信道
ACK帧
RTS/CTS可选

轮询访问介质访问控制

既要不产生冲突，又要发送时占全部带宽

轮询协议
- 主节点轮流邀请从属节点发送数据
- 问题：轮询开销、等待延迟、单点故障
令牌传递协议
- 令牌环网
- 令牌作为特殊格式MAC控制帧，控制信道使用，确保同一时刻一节点独占信道
- 在令牌上附加数据传递，回收后确认是否重传，传递完成退让
- 问题：令牌开销、等待延迟、单点故障、用于负载较重、通信量较大的网络