数据链路层

数据链路层

基本概念

数据链路层在物理连接提供的比特流传输服务基础上，通过一系列通信控制机制，构成透明的、相对无差错的数据链路，实现可靠、有效的数据传送。
数据链路层协议负责在物理网络与计算机的协议组之间提供一个接口。

• 数据电路：在传输信道两端加上信号变换设备之后所形成的二进制比特流通路。即数据电路由传输信道加上DCE组成，实现数据信号的传输。又常称为物理链路或链路.
• 数据链路：在数据电路建立的基础上，在链路协议控制下，使通信双方正确传输数据的终端设备与传输线路的组合体。又称为逻辑链路.

功能

• 链路管理
• 帧同步（帧定界）
• 流量控制
• 数据和控制信息的识别
• 寻址
• 透明传输
• 差错控制

---

流量控制和差错控制

现代数据通信传输，大多数采用了存储转发的分组交换技术，由于通信的随机性和突发性，当接收方的处理能力小于发送方的发送量时，必须采用流量控制。

停止-等待流量控制方式

t_P = t₂– t₀ = t₃ – t₁ = L / v 传播时延
t_F = t₁ – t₀ = t₃ - t₂ = F / C 发送时延
t_A = t₅ – t₄ = A / C 应答帧发送时延
t_proc = t₄ - t₃ 处理时延
L 节点A 与 B 之间的距离
v 信号传播速率 （3× 10^8 m / s）
F 数据帧长度 = H + D （帧头＋数据）
A 应答帧长度
C 数据发送速率 bits/s

性能分析:
正常情况信道利用率（无差错）
U = t_D / (t_F + t_A + 2t_P + 2t_proc)
假设收发双方处理时间相同；
不考虑处理时延和传播时延，及应答帧的开销，则
U 仅与帧结构相关；
U= t_D/ t_F =D/F = D/(H+D)
当传播时延较大时，发送时延与传播时延相比较小时，信道利用率很低。

滑动窗口流量控制方式

为了解决停止等待协议信道利用率低的问题，可以采用“滑动窗口”控制方法。
在滑动窗口流量控制方式中，根据通信双方对于出现差错和需要流量控制过程时所采用的处理方法不同，
分为：
连续 ARQ 和选择 ARQ。

连续ARQ方式Automatic Repeat-reQuest

• 当发送完一个数据帧后，不是停下来等待确认帧，而是继续发送若干数据帧；
• 如果收到了接收方发来的确认帧，则发送方可以继续发送数据帧；
• 如果出现差错，则从出现差错的数据帧开始全部重发。
• 重发的帧序号是连续的。

当用 n 个比特进行编号时，则只有在发送窗口的大小 W_T <=2^n-1时，连续 ARQ 协议才能正确运行（模－1）。

选择ARQ方式

为进一步提高信道的利用率，可设法只重传出错的数据帧或计时器超时的数据帧。

选择 ARQ 方式，接收方允许接收多个不严格按照顺序的帧。若用 n 比特进行编号，为避免编号混乱，接收窗口的最大值受下式的约束
W_R<= 2ⁿ/2
当接收窗口为最大值W_R ＝ 2ⁿ/2时，选择ARQ方式发送窗口
W_T ＝2ⁿ/2

---

差错控制

差错即误码，差错控制的核心是抗干扰编码。
在发送的数据码元序列中加入监督位，并进行某种变换，使它们和原来相互独立的数据码元之间具有某种约束关系。

所谓差错控制编码实际上就是在保持信息的位数不变的情况下，采用增加码长的方法来降低误码率。

差错控制编码

码间距离（d） ：两个码字的对应位取值不同的个数。例：
10001001
10110001
汉明距离（d₀） ：一个有效编码集中，任意两个码字的码间距离的最小值。即一组编码中的最小码距。
如果要能检测 e 个差错，则编码集的汉明距离至少为 e + 1；
如果要能纠正 t 个差错，则编码集的 汉明距离至少为 2 t + 1；
如果要能检测 e 个差错，同时能纠正 t 个差错（ e > t ） ，则编码集的汉明距离至少为 e + t + 1；

检错码

• 恒比码
• 正反码
• 奇偶校验码
• 循环冗余码（CRC）

纠错码

汉明码（Hamming)

汉明码

汉明码是一种能够纠正一位错码且编码效率较高的线性分组码。

若码长为n，信息位数为k，则监督位数为r=n-k。
如果希望用r个监督位构造出r个监督关系式来指示一位错码的n种可能位置，则要求
2^r-1>=n 或 2^r>=k+r+1

设分组码(n,k)中k=4，根据上式可得r>=3，则n=7。

S1S2S3	错码位置
001	a0
010	a1
100	a2
011	a3
101	a4
110	a5
111	a6
000	无错

S₁ = a₆⊕a₅⊕a₄⊕a₂

S₂ = a₆⊕a₅⊕a₃⊕a₁

S₃ = a₆⊕a₄⊕a₃⊕a₀

编码效率

R=k/n=(2^r-1-r)/(2^r-1)=1-(r/(2^r-1))=1-r/n

循环码

把码长为n的码组与n-1次多项式建立一一对应的关系
若码组A=(a_n-1,a_n-2, … , a₁,a₀,)
则多项式为：A(x)=a_n-1x^n-1+a_n-2x^n-2+…+a₁x+a₀

如码组1100101对应的多项式为：
A₇(x)=1 x⁶+1 x⁵+0 x⁴+0 x³+1 x²+0 x+1

循环冗余码CRC的编码步骤（发送端）
1）求M(x)所对应的码字，可先求M(x), 并乘以x^{n - k}；
2）然后被G（x）除，求其余式；
3）得x^r M（x）

---

HDLC与PPP协议

HDLC

HDLC帧中存在多种 0/1 比特组合。
5个或5个以内连续1，或其他组合：正常数据。
01111110：帧标志 F，帧开始和结束标志，帧间填充，帧同步。
7~15个连续“1”：异常终止，丢弃此帧。
多于15个连续“1”：链路空闲，停止工作。
必须采取措施，实现 HDLC 帧中任意比特组合的传输，而不会造成误判。
采用“零比特自动插入/删除法”使一帧的两个 F 字段之间不会出现 6 个或6个以上连续 “1”。
在发送端，当一串比特流数据中有 5 个连续 1 时，就立即自动插入一个 “0”。
在接收帧时，先找到 F 字段以确定帧的边界。接着再对比特流进行扫描。每当发现 5 个连续 1 时，就将其后的一个 0 删除，以还原成原来的比特流。
采用零比特插入/删除法可传送任意组合的比特流，即实现数据链路层的透明传输。
当连续传输两个帧时，前一个帧的结束标志字段 F 可以兼作后一帧的起始标志字段。
当暂时没有信息传送时，可以连续发送标志字段，使收端可以一直和发端保持同步，同时表示链路处于工作状态。

HDLC的帧结构

• 信息字段 I
  • 高层信息，如 IP 报文或其它信息
  • 长度可变，且无字段长度说明
  • 某些控制类帧可能无此字段
• 帧校验序列 FCS
  • 差错控制，使用CRC校验
  • 长度16bit，也属于透明传输范围

信息帧 （I帧）

LSB 为 0 表明该帧是信息帧。
N(S) 号表明该帧的发送一个帧号。
N(R)号表明该帧的发送者期望接收的下一个帧号。
（对N(R) －1 及以前各帧的确认）
3比特编码表示为模 8 方式。
利用信息帧携带确认信息可提高传送效率。

监视帧（S帧）

监视帧，又称监督帧，监控帧，用于数据传送阶段。实现流量控制和差错控制，保证数据传输的正常进行。
根据传输控制的需要，S帧有以下类型：

• RR Receiver Ready 接收端准备好
• RNR Receiver Not Ready 接收端未准备好
• REJ Reject 帧拒绝（连续ARQ）
• SREJ Select Reject 选择拒绝（选择ARQ）

N(R) 用于向发送方确认接收端所收到帧的序号。 N(R)表示该帧的发送者期望接收的下一个帧的序号，同时对 N(R) －1及以前各帧确认。

无编号帧（ U帧）

LSB 为 11 表明该帧是无编号帧（U帧）

PPP

包含三个组成部分

• 将 IP 数据报封装到串行链路的方法。
• 链路控制协议 LCP (Link Control Protocol)。
• 网络控制协议 NCP (Network Control Protocol)。

PPP 协议的帧格式

PPP 的帧格式和 HDLC 的相似。
标志字段 F 仍为 0x7E （符号“0x”表示后面的字符是用十六进制表示。十六进制的 7E 的二进制表示是 01111110）。
地址字段 A 只置为 0xFF。地址字段实际上并不起作用。
控制字段 C 通常置为 0x03。

PPP 有一个 2 个字节的协议字段，用于指示帧的信息字段中所携带的内容。
当协议字段为 0x0021 时，PPP 帧的信息字段就是IP 数据报。
若为 0xC021, 则信息字段是 PPP 链路控制数据。
若为 0x8021，则表示是网络控制数据。
信息字段无特别要求，其内容由协议字段说明，长度不超过1500字节。
使用16位帧校验。

PPP 的透明传输

PPP帧在传输过程中，同样需要考虑透明传输问题。即帧标志之间的比特组合。
当 PPP 用在同步传输链路时，协议规定采用硬件来完成比特填充（和 HDLC 的做法一样，零比特自动插入/删除）。
当 PPP 用在异步传输时，就使用一种特殊的字符填充法。
将信息字段中出现的每一个 0x7E 字节转变成为 2 字节序列（0x7D, 0x5E）。
若信息字段中出现一个 0x7D 的字节, 则将其转变成为 2 字节序列（0x7D, 0x5D）。
若信息字段中出现 ASCII 码的控制字符（即数值小于 0x20 的字符），则在该字符前面要加入一个 0x7D 字节，同时将该字符的编码加以改变。