第三章 数据链路层
物理层给数据链路层提供的服务是传送数字信号，这个信号有可能是恒定的比特流或字节流
数据链路层在两个邻接的计算机之间提供可靠的，高效率的通信（点到点）
- 邻接：两个计算机之间用一个通信信道（有线或无线）连接在一起，也叫点到点。
通信信道在概念上就像一条线路（比如同轴电缆、电话线或者无线信道）。信道像一条线路的本质特性使得信道上传递的比特顺序与发送顺序完全相同。
数据链路层的设计问题
数据链路层使用物理层提供的服务在通信信道上发送和接收比特。它要完成一些功能，包括：
（1） 向网络层提供一个定义良好的服务接口。
（2） 把比特流或字节流封装成帧。
（3） 处理传输错误，尾部用于差错控制。
（4） 调节数据流，确保慢速的接收方不会被快速的发送方淹没。
数据链路层的功能:
为网络层提供业务接口
数据链路层通常会提供以下3种可能的服务：
无确认的无连接服务：源机器向目标机器发送独立的帧，目标机器并不对这些帧进行确认
有确认的无连接服务：数据链路层仍然没有使用逻辑连接，但其发送的每一帧都需要单独确认
有确认的有连接服务：在数据链路层提供确认只是一种优化手段，永远不应该成为一种需求
处理传输错误
调节数据流
成帧：
一个比特流（或是字节流）通过点到点链路从节点A发送到节点B。节点B必须准确地识别构成帧的比特集，也就是说，它必须确定帧的开始和结束位置，哪几个比特是一伙的
拆分比特流的4种方法：
字节计数法：
字符填充法：
比特填充法：
物理层编码违禁法：
比特编码成信号通常包括一些冗余比特，这种冗余意味着这种冗余不会出现在常规数据中。可以利用这些保留的信号来指示帧的开始和结束。
例如Manchester编码：一个周期内电压由低到高表示为0，由高到低表示为1。则当电压恒为高或恒为低时，不表示数据，可用做定界符。
例如4B/5B编码：11111表示空闲，11000表示一帧的开始
缺点：但只适用于存在冗余编码的环境。
差错控制：
数据链路层要确保所有的帧最终都被传递给目标机器的网络层，并且保持正确的顺序
对于无确认的无连接服务，不管发出去的帧是否正确抵达目标机器
但是对于可靠的、面向连接的服务，这样做肯定还远远不够
流量控制：
差错检测和纠正
纠错码(ECC)：
错误模型:
单比特错误：只有一个比特发生改变
突发错误：2个或多个比特发生改变
等价于在原始的数据基础上叠加了这么长的一个噪音
海明码：
码字： 一个包含了数据位和校验位的n位单元
海明距离： 两个码字中不相同的位的个数
纠正单个错误所需的校验位数：
m个消息位，r个校验位，n=m+r个码字
有$2^m$个合法的消息
则需要满足：
海明码：
在海明码中，码字的位被连续编号，从最左端的位开始，紧跟在右边的那位是2，依次从左到右编号。2的幕次方的位（1,2,4,8,16等）是校验位，其余位用来填充m个数据位
每一个校验位强制进行模2加，或对某些位的集合，包括其本身进行偶（或奇）校验
海明码纠正突发错误：
二进制卷积码
里德所罗门码
低密度奇偶校验码
检错码：
光纤或高品质铜线的错误率要低得多，因此对于偶尔出现的错误采用差错检测和重传的处理方式通常更加有效
海明码检测出错之后不用重传，可以自行纠错（翻转出错的比特）
CRC放在帧尾的原因：
如果把CRC放在帧头，那么在发送前要把整个帧扫描一遍来计算CRC，然后再从帧头开始发送，这样每一位都要处理两次，比较浪费时间
把CRC放在帧尾，边发送边计算校验位，数据比特发送完紧跟着把硬件寄存器里生成的校验比特发出去，可以一次完成，效率较高
## 初级数据链路层协议
wait_for_event(&event)：标示数据链路层正在等待事情发生，只有当确实发生了什么事情（比如到达了一个帧），该过程才返回
to_network_layer/from_network_layer：和网络层之间的接口
to_physical_layer/from_physical_layer：和物理层之间的接口
timer operations：定时器操作
enable_network_layer/disable_network_layer：流量控制，控制网络层是否可以发送数据
协议定义：
**一个乌托邦式的单工协议**
**不需要考虑任何出错**的情况，数据只能**单向**传输
发送方和接收方的网络层总是处于准备就绪状态，数据处理的时间忽略不计
**无错信道上的单工停-等式协议**
仍然假设通信信道**不会出错**，并且数据流量还是**单工**的
接收方只有有限的缓冲区容量和处理速度，因此协议必须有显式的应答，防止发送方以超过处理速度的数据淹没接收方
**有错信道上的单工停-等式协议**
区分第一次看到的帧和重传的帧,需要在每帧的头部放一个序列号，则 **序列号的最小位数为：**
* **链路层：** 1比特，编号空间大小为2
* **传输层：** 1比特编号空间太小，需要较大的编号空间，如：TFTP（16比特）
**发送方：**
seq_nr=0
从网络层获取一个分组放入buffer
label1:
发送buffer中的数据（带上序号seq_nr），新启动定时器
wait_for_event()
switch (event) {
case 收到了坏帧(校验和错):
case 定时器超时:
case 收到校验和正确的帧:
if（ack序号正确） {
关闭旧定时器
inc(seq_nr)
从网络层获取下一个分组放入buffer
}else
}
goto label1
从网络层获取一个分组放入buffer
next_frame_to_send = 0;
while(true) {
发送buffer中的数据，启动定时器
帧序号填写为next_frame_to_send
wait_for_event()
if (收到校验和正确的帧){
if(ack序号正确){
关闭旧定时器
从网络层获取下一个分组放入buffer
inc(next_frame_to_send)
}
}
}
|
frame_expected=0
while(true){
wait_for_event()
switch(event) {
case 坏帧:
do_nothing
case 收到校验和正确的数据帧:
if(序号==frame_expected){
向网络层上交分组
回ACK(序号为frame_expected)
inc(frame_expected)
}
回ACK(序号为frame_expected-1)
}
}
|
NAK：
当接收方有理由怀疑发生了错误，它将NAK帧发送回发送方，请求重新传输
有两种情况：
要避免对同一帧进行多个重传输请求，接收方应该跟踪是否已经为给指定帧发送了一个NAK帧
- 停等协议——无差错
- 停等协议——有差错
- 滑动窗口——无差错
- 捎带传输：$U=\frac{N}{2+2\alpha}$
数据链路协议实例
HDLC（High-level Data Link Control）：
不平衡：一个主站，一个或多个从站
平衡：两个混合站，全双工
HDLC帧格式：
使用比特填充法
Control字段：
(a)I-frame(INFO)：数据帧
(b)S-frame：监督帧
(c)U-frame：没有编号的帧
I-frame：
S-frame：
Code:RR, RNR, REJ, SREJ (3-bit N(R))
ACK帧：RR,RNR
NAK帧：REJ,SREJ
RR: 接收方准备好
表示期望的N(R)帧的ACK帧
只在没有反向流量可用于捎带时使用该帧
仍可以发送数据
RNR: 接收方没有准备好
它像RR一样，识别所有不包括N(R)的帧
但它告诉发送方停止发送(流量控制)
REJ: 拒绝
表示检测到传输错误
N(R)字段表示序列中第一个未正确接收的帧（即，要重传的帧）
发送端需要重传从N(R)开始的所有（悬而未决）帧
SREJ: 选择性拒绝
只调用N(R)指定的帧的重传
如果接收端希望缓冲无序帧以备将来使用，它可以使用SREJ强制重传任何特定帧
U-frame：
P/F：
非平衡方式：
Poll：邀请终端发送数据
Final：终端发送的所有帧，除最后一帧外，均将P/F位设置为0，最后一个是1
平衡方式：
Command（P位）：P=1以恳求(Poll)对方做出响应
Response（F位）：F=1表示对请求命令的响应
强制另一台机器立即发送一个监督帧，而不是等待反向通信，以便在反向通信上捎带窗口信息
HDLC操作实例：
PPP（点到点协议）
PPP协议子层：
特性:
PPP帧格式：
PPP状态转移图：
LCP链路控制协议(Link Control Protocol)：
PPP和HDLC的区别：
- PPP是面向字节而不是面向比特的。特别是PPP使用字节填充技术，所有帧的长度均是字节的整数倍
HDLC协议则使用比特填充技术， 允许帧的长度不是字节的倍数
- HDLC协议提供了可靠的数据传输，PPP是面向连接的不可靠的
……未完待续♬
