数据链路层
第三章
1linwei@
主要内容
数据链路层设计要点
错误检测和纠正
基本数据链路层协议
滑窗协议
协议验证
数据链路层协议示例
2linwei@
数据链路层的设计要点
为网络层提供的服务
成帧
差错控制
流量控制
3linwei@
链路层基本功能
向网络层提供一个服务接口
处理传输错误
调节数据流（流控）
4linwei@
分组与帧之间的关系
5linwei@
虚拟通信和实际通信
(a) 虚拟通信.
(b) 实际通信.
6linwei@
数据链路层提供的服务
无确认的无连接服务
用于低误码率链路或对误码不敏感的业务. (fiber,
utp, real-time )
有确认的无连接服务
用于高误码率链路 (Wireless)
有确认的面向连接的服务
保证每个帧真正接收到且只接收一次。
为网络层进程提供一个可靠的位流。
7linwei@
例子
数据链路协议的位置
8linwei@
DLL 将原始码流分解为离散的单元，该单元称为帧。那
么接收端如何检测帧的边界呢？或者说接收端如何界定帧
的开始和结束呢？讨论4种方法：
• 字符计数法
• 含字节填充的分界符法
• 含位填充的分界标志法
• 编码违例
成帧
9linwei@
字符计数法
一个字符流 (a) 无差错. (b)有一个差错.
10linwei@
字符填充
(a) 有标志字节作为分界的帧.
(b) 字节填充前后的4个字节序列例子.
11linwei@
比特填充
Bit 填充， 标记 01111110
(a) 原始数据.
(b) 线路上的数据.
(c) 删除填充后存储在接收方存储器中的数据.
12linwei@
编码违例
适用于“物理介质上的编码方法中包含冗余信
息”的网络。例如有些LAN用2个物理位来编码
1位数据。“1”位是“高-低”电平对，“0”位
是“低-高”电平对。而“高高”“低低”电平对
不用于数据，则可用于帧定界。
优点是没有额外带宽开销
13linwei@
• 为了保证所有的帧最终传送到（有可能顺序的）目的端，需要三个
部件。
Acknowledgments, Timers, Sequence Numbers
Acknowledgments:
• 当接收端正确接收一个帧，它会向发送端返回一个ACK帧用于指示
发端该帧已正确接收。
• 在某些系统，如果接收的帧不正确，接收端会发端返回一个NACK
（ Negative ACK ）用于指示该帧没有正确接收.
• 提示发端不用等待定时器超时就立即发送（重传）一个帧.
错误控制
14linwei@
Timers:
• 如果没有定时器，当帧丢失或者 ACK/NACK 丢失，
会出现什么情况？
• 定时器怎么工作呢？当发送一个帧的时候，发端开
启一个定时器，当在约定的时间内，发端接收到
ACK/NACK，则立即发送（重发）一个帧，且重置
定时器，否则当定时超时时，重发该帧。
Sequence Numbers:
• 主要解决接收端接收到重复帧的问题.
• 为了避免接收重复帧的问题，给发送的帧分配序列
号，这样接收端就能够区分原始帧和重传帧。.
Error Control
15linwei@
流控
流控主要是处理发端与接收端之间速率匹配的
问题。通常，流控是个动态的过程，取决于负
载强度、接收端缓存大小等，常用的方法：
基于反馈的流控制
基于速率的流控制（从来没有用于DDL）
16linwei@
错误检测和纠正
纠错码
检错码
17linwei@
错误
• 数据通信中，链路噪声无处不在，并且研
究发现，链路噪声引起的比特错误通常是
突发性的，而不是独立的，单比特错误，
例如：闪电会引起短暂的突发比特错误。
18linwei@
纠错码
检测和纠正数据中的错误
冗余（redundancy） - 在数据中加入附加的
信息。
两种策略：
检错码: 包含足够的冗余比特检错，然后使用
NACK告知发端重传。
纠错码:包含足够的冗余比特检测和纠正错误。
19linwei@
海明距离
给定两个码子，对其进行异或运算，然后计算
出异或结果中1的个数，两个码子中不相同的
位的个数称为海明距离.
它的意义在于：如果两个码子的海明距离为d
，则需要d个1位错误才能将一个码子转变成另
一个码子。
20linwei@
海明距离
通常，所有2m 种可能的数据报文都是合法的，
但是并非所有的2n （n = m+r； m为数据位，r
为冗余位）种码子都被用到。给定计算校验位
的算法后，可以构造合法码子列表，并且可以
从该表中找到海明距离最小的两个码子，此距
离是整个编码方案的海明距离。
为了检测d个错误，需要一个距离为d + 1 的编
码方案
为了纠正t个错误，需要一个距离为2t + 1 的编
码方案
21linwei@
奇偶位
保证码子中“1”位的数目是偶数（或者奇数）。.
1000000(1) 1111101(0)
奇偶位的海明距离为2，因此它可以检测单比特
错误，但是不能纠错
考虑以下的例子，4个有效码子的编码：
"00000 00000", "00000 11111", "11111 00000", and "11111 11111".
编码距离为5, 可以纠正2个错误。
22linwei@
纠错
设计一种编码方案，每个码子有m个报文位和r个
校验位，并且能够纠正所有的单个错误。对于2m 合
法报文，任一个报文都对应有n个非法的码子，它们
与该报文的距离为1。因此每个合法的报文都要求n+1
个位模式供他使用。由于总共有2n个位模式，所以有
( n + 1 ) * 2m < 2n , 利用 n = m + r , 有：
( m + r + 1) < 2r，
给定m的情况下，这个条件给出了用于纠正单
个错误所需要的校验位数目的下界
例如m = 10，r > 4
23linwei@
检错码
纠错码代价很大（计算量和带宽），因此用在无线
通信较为合适，但是在铜线或者光缆，错误检测和
重传机制往往更加有效。
例如，若误码是独立的，误码率为10-6。则对于
1000bit的数据块，需要10个校验位纠正1个单bit错
误，1Mbit的需要10Kbit，显然如果仅仅检测错误，
每个数据块1个奇偶位就足够了，每一千个数据块额
外传输一个块，因此开销小，利用检错/重传机制，
则1Mbit只需2001位，相比之下，海明码需要
10000位。
最广泛使用的检错码是多项式编码，也称CRC。
24linwei@
Cyclic Redundancy Check
基本思想：将位串看成系数为0或1的
多项式。
多项式的算术运算以2为模完成，加
减法等同于异或，除法为长除运算。
生成多项式G(x)：事先约定的，最低
位，最高位必须是1。
校验和：添加到帧序列多项式中，用
于检测传输是否有错误。
25linwei@
Cyclic Redundancy Check
校验和的计算方法：
(1) 假设G(x)的阶为r。在帧的低位端加上r
个0位，所以该帧现在包含m+r位。对应
的多项式为xrM(x)。
(2) 利用模2除法，用对应于G(x)的位串去
除xrM(x)的位串。
(3) 利用模2减法，从对应于xrM(x)的位串
中减去余数，结果就是将被传输的带校
验和的帧，记为：T(x)。
26linwei@
Cyclic Redundancy
Check
校验和的计算过程
27linwei@
Cyclic Redundancy Check
分析：
1. 所有的错误都能检测出吗？
错误多项式E(x)能被G(x)除尽，则这类错误无法被检测。
2. 所有的一位错误都将被检测到。
低阶的多项式可以保护长的帧（K<= i – j,两个独立的一
位错误）
奇数项多项式不可能被x+1除尽(奇数个位发生错误)。
带r个校验位的多项式编码可以检测到所有长度小于等于
r的突发性错误。
28linwei@
Cyclic Redundancy Check
通常用到的3种CRC生成多项式：
CRC-16 = x16+x15+x2+1 (used in HDLC)
CRC-CCITT = x16+x12+x5+1
CRC-32 = x32+x26+x23+ x22+x16+x12+
x11+x10+x8+ x7+x5+x4+ x2+x1+1(used in
Ethernet)
尽管复杂，可以用硬件构造出来
29linwei@
基本数据链路协议
一个无限制的单工协议
一个单工的停—等协议
有噪声信道的单工协议
30linwei@
基本数据链路协议
几个假设：
• 物理层、数据链路层和网络层都是独立
的进程，它们通过报文来相互通信。
• 可靠的、面向连接的服务
• 机器不会崩溃
31linwei@
协议定义
Continued
协议中需要用到的一些定义。这些定义包含在头文
件中.
32linwei@
协议定义
(ctd.)
协议中需要用到的
一些定义。这些定
义包含在头文件
中.
33linwei@
无限制的单工协议
假设条件:
数据单向传输
物理信道无误码，即无帧损坏或丢失
发/接收端缓存无限大
发端/收端的网络层总是处于准备就绪状态
34linwei@
无限制的
单工协议
35linwei@
一个单工的停/等协议
假设:
不再假设收端能够无限快速的处理到来的数据.
基本思想和特点
发端发送一个帧，然后等待确认 (stop and wait.)
确认帧的内容并不重要
数据传输是单向的，但是必须是双向链路，因此用
一个半双工的物理信道就足够了
36linwei@
单工的等/
停协议
37linwei@
有噪声信道的单工协议
假设:
信道有噪声，因此可能会丢/损坏帧
简单的方法:
发端设置一个定时器，如果在规定的时间内
没有接收到ACK，则重发该帧.
这种方法有没有问题？
38linwei@
有噪声信道的单工协议
考虑下面的场景：
A 传输一个帧
B 接收到A传来的帧A1
B 产生 ACK
ACK 丢失
A 定时器超时, 重传
B 得到A1的副本 ( 将会把副本送到网络层.)
(另外一种出现副本的情况是长的时延)
使用序列号
在这个例子里，1bit就够了。
在协议中，发送方在准备下一个数据项目之前先等待一个肯定
的确认，则这样的协议称为（ Positive Acknowledgment
with Retransmission (PAR)/Automatic Repeat reQuest
(ARQ)）
39linwei@
有噪声信道的单工协议
一个支持重传的肯
定确认协议
Continued
40linwei@
有噪声信道的单工协议
一个支持重传的肯定确认协议
41linwei@
滑窗协议
用于双向通信
使用同一条线路来传输两个方向上的数据
反向信道与前向信道有相同的容量.
有两种类型的帧( "kind" field):
数据（Data）
ACK ( 含有最新接收帧的序号).
42linwei@
捎带确认（Piggybacking）
Piggybacking – 确认信息附在往外
（反向链路）发送的数据帧上的行为。
优点 : 更好的利用信道带宽。
问题: 为了更好的利用带宽，数据链路
层应该等待下一个分组多长时间?
43linwei@
滑窗协议
每个外发的帧都包含一个序列号，其范围为0 ~ MaxSeq
(2n – 1). 这样的序列号正好可以填到一个n位的域
中。
等-停滑动窗口协议使用n = 1。
滑窗协议的本质：在任何时刻，发送方总是维持
着一组序列号，分别对应于允许它发送的帧。称
这些帧落在发送窗口内，接受方也维持一个接收
窗口，对应一组允许他接收的帧。窗口大小可以
固定或者不固定。
44linwei@
滑窗协议 (2)
滑窗大小为1，有3个序列号的滑动窗口
(a) 初始化
(b) 第1帧发送以后
(c) 第1帧接收以后
(d) 第一个确认收到后
45linwei@
滑窗协议
1位滑窗协议
Go Back N 协议
选择性重传协议
46linwei@
1位滑窗协议
Continued
47linwei@
1位滑窗协议 (ctd.)
48linwei@
1位滑窗协议 (2)
针对协议4的两种情况. (a) 正常情况. (b) 异常情况.
记号为 (seq, ack, packet number). 星号表示网络层接受一个分组.
49linwei@
Go back n 协议
停/等协议的一个问题是：往返时延过长
1000 bit frames
50kbps channel ，往返传播时延
500ms(satellite)
发送1000bit的帧到接收方完全接收需要
270ms，520ms后收端才能接收到确认（忽
略ACK带来的时延）。只有4%的有效带宽
被利用，效率很差！
50linwei@
管道化
利用管道:
使得多个帧可以同时在一条链路上传输.
性能改善
F = frame size (bits)
C = channel capacity (bps)
I = propagation delay plus processor service time
(seconds)
Time to transmit a single frame= F/C
Total Delay= 2I
line utilization=F/(F+2CI) < 50% if F<2CI
51linwei@
Go Back N协议
Go back n – 对用于“接收窗口尺寸为1”的情况
如果接收端收到坏帧，则后续的帧（管道中的）无论正确与否
全部丢弃
丢弃的帧没有ACKs.
52linwei@
Go Back
N滑窗协
议
Continued
53linwei@
Go Back N滑窗协议
Continued
54linwei@
Go Back N滑窗协议
Continued
55linwei@
Go Back N滑窗协议
56linwei@
窗口尺寸问题
考虑 MAX_SEQ = 7的场景：
发送方发送 0 ~ 7帧.
第7帧的捎带确认最终被送回到发送方.
发送方送出另外8帧，其序号仍然是0~7
现在第7帧的另一个捎带确认也回来了
问题是：属于第二批的8帧全部成功到达了吗？或者
是说这8帧全部丢失了（把出错之后丢弃的帧也算作
丢失了）？在这两种情况下，接收方都会发送第7帧
的确认。而发送方无从分辨。由于这个原因，未确认
帧（即窗口大小）必须限制为MAX_SEQ.
57linwei@
Go Back N滑窗协议
用软件模拟多个定时器.
58linwei@
选择性重传协议
选择性重传 – 接收窗口尺寸大于1.
缓存坏帧以后所有的帧.
只对最后一个正确接收的帧进行确认。
59linwei@
选择性重传协议
接收侧带宽与链路层缓存之间的折中
这两种情况下，发送侧需要缓存，只有接收到ACK后
占用的缓存才能释放。
为了强制执行“任何时候未确认帧的个数都不应该超
过Max_Seq”的流控规则，DLL应该能够
enable/disable 网络层
60linwei@
使用选择性重传的滑动窗口协议
Continued
61linwei@
Continued
使用选择性重传的滑动窗口协议(2)
62linwei@
使用选择性重传的滑动窗口协议(3)
Continued
63linwei@
使用选择性重传的滑动窗口协议(4)
64linwei@
非顺序接收问题
(a) 窗口大小为7的初始状态.
(b) 7帧都已送出并接收，但是均未被确认
(c) 窗口大小为4的初始状态
(d) 4帧都已送出并接收，但是均未被确认.
65linwei@
数据重叠（overlap）
问题的本质是，当接收方向前移动窗口后，新
的有效序列号与老的有效序列号之间有重叠，
因此后续的帧可能是重复的帧，也有可能是新
的帧，但是接收端无法区分。
解决的方法：最大的窗口尺寸应该不超过序列
号范围的一半，即 (MAX_SEQ + 1)/2. 因此对
3位序列号，窗口尺寸为4
66linwei@
反向流量轻的问题
之前的假设反向信道负载较重（因为采用捎带
确认）
如果反向业务轻会如何？
确认信息会滞留很长时间
极端情况，如果在一个方向上有很大的流量，而另
一个方向上根本没有流量，则只有MAX_SEQ个分
组被发出去，协议就阻塞了。
启用start_ack_timer辅助定时器，如果定时器
到期前没有出现反向流量，则发送一个单独的
确认帧。
67linwei@
协议验证
有限状态机模型
Petri 网模型
68linwei@
有限状态机模型
协议规范和验证:
本节的目的是学习验证协议的方法
状态图对于验证协议的正确性和完整性是非常重要的
协议机；状态；转换，死锁
一个协议的有限状态机模型可以看作是一个四元组
（S，M，I，T），其中：
S是指进程和信道可能的状态集合
M是指能在信道上进行交换的帧的集合
I是指进程的初始状态集合
T是状态之间转换的集合
69linwei@
Finite State Machined Models
（a）协议3的状态图 (b) 转换.
70linwei@
Petri 网模型
包含两个库所和2个转换的 Petri网.
库所，变迁，弧和标记
71linwei@
Petri 网模型 (2)
协议3的 Petri网模型
72linwei@
数据链路层协议示例
HDLC – High-Level Data Link Control
Internet中的数据链路层
73linwei@
High-Level Data Link Control
面向位的协议的帧格式.
74linwei@
HDLC Control Field
三种帧的控制域
(a) 信息帧
(b) 管理帧
(c) 无序号帧
75linwei@
High-Level Data Link Control
管理帧类型
Type 0 是一个确认帧，用于指示下一个期望的帧。
Type 1 是一个否定的确认帧，指示一个传输错误
已经被检测到，NEXT域指明了期望被重传的帧的
序列号。发送方必须重传从NEXT开始的所有未被
确认的帧。
Type 2 是接收尚未就绪，它确认直到Next的所有
帧，但是不包含Next帧，告诉发端不要在发送了。
Type 3 是选择性拒绝。它只要求重传特定的帧。
76linwei@
Internet中的数据链路层
Point-to-point 线路: 路由器之间的租用线路，
经由modem拨号登陆主机的线路
PPP - Point-to-Point Protocol: Standard
(RFCs 1661-1663)
77linwei@
PPP - Point-to-Point Protocol:
PPP提供了3类功能:
成帧方法，帧格式支持错误检测。
链路控制协议(LCP) ，可用于启动线路、
测试线路、协商参数以及当线路不再需要
的时候关闭线路。
网络控制协议 ：协商网络层选项的方法。
与 HDLC类似, 但是其是面向字符型的.
78linwei@
point-to-point communication
一台家庭个人计算机成为一台Internet主机
79linwei@
PPP – Point to Point Protocol
无序号模式下PPP的完整的帧格式.
80linwei@
状态机
线路启动到关闭的状态转移图
81linwei@
RFC1661: LCP Frame types
The LCP frame types.
82linwei@
