课件制作人：谢希仁计算机网络第 3 章 数据链路层课件制作人：谢希仁第 3 章 数据链路层
*3.1 数据链路层的基本概念
*3.2 停止等待协议
3.2.1 完全理想化的数据传输
3.2.2 具有最简单流量控制的数据链路层协议
3.2.3 实用的停止等待协议
3.2.4 循环冗余检验的原理
3.2.5 停止等待协议的算法
3.2.6 停止等待协议的定量分析课件制作人：谢希仁第 3 章 数据链路层（续）
*3.3 连续 ARQ 协议
3.3.1 连续 ARQ 协议的工作原理
3.3.2 连续 ARQ 协议的吞吐量
3.3.3 滑动窗口的概念
3.3.4 信道利用率与最佳帧长
3.4 选择重传 ARQ 协议课件制作人：谢希仁第 3 章 数据链路层（续）
*3.5 面向比特的链路层协议 HDLC
3.5.1 HDLC 协议概述
3.5.2 HDLC 的帧结构
*3.6 因特网的点对点协议 PPP
3.6.1 PPP 协议的工作原理
3.6.2 PPP 协议的帧格式
3.6.3 PPP 协议的工作状态课件制作人：谢希仁
3.1 数据链路层的基本概念
链路 (link)是一条无源的点到点的物理线路段，中间没有任何其他的交换结点。
一条链路只是一条通路的一个组成部分。
数据链路 (data link) 除了物理线路外，还必须有通信协议来控制这些数据的传输。若把实现这些协议的硬件和软件加到链路上，就构成了数据链路。
现在最常用的方法是使用适配器（即网卡）来实现这些协议的硬件和软件。
一般的适配器都包括了数据链路层和物理层这两层的功能。
课件制作人：谢希仁数据链路层像个数字管道
常常在两个对等的数据链路层之间画出一个数字管道，而在这条数字管道上传输的数据单位是 帧 。
早期的数据通信协议曾叫作 通信规程
(procedure)。因此在数据链路层，规程和协议是同义语。
结点 结点帧 帧课件制作人：谢希仁数据链路层的主要功能
(1) 链路管理
(2) 帧定界
(3) 流量控制
(4) 差错控制
(5) 将数据和控制信息区分开
(6) 透明传输
(7) 寻址课件制作人：谢希仁
3.2 停止 等待 协议
3.2.1 完全理想化的数据传输
先研究一下数据链路层的模型。
课件制作人：谢希仁数据链路层的简单模型局域网 广域网主机 H1 主机 H
2
路由器 R1 路由器 R
2
路由器 R3
电话网 局域网主机 H1 向 H2 发送数据链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层
R1 R2 R3
H1 H2从层次上来看数据的流动课件制作人：谢希仁数据链路层的简单模型
( 续）
局域网 广域网主机 H1 主机 H
2
路由器 R1 路由器 R
2
路由器 R3
电话网 局域网主机 H1 向 H2 发送数据链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层
R1 R2 R3
H1 H2仅从数据链路层观察帧的流动课件制作人：谢希仁
3.2 停止等待协议
3.2.1 完全理想化的数据传输数据链路层主机
A
缓存主机
B
数据链路
AP2AP1
缓存发送方 接收方帧高层帧课件制作人：谢希仁完全理想化的数据传输所基于的两个假定
假定 1,链路是理想的传输信道，所传送的任何数据既不会出差错也不会丢失。
假定 2,不管发方以多快的速率发送数据，收方总是来得及收下，并及时上交主机。
这个假定就相当于认为：接收端向主机交付数据的速率永远不会低于发送端发送数据的速率。
课件制作人：谢希仁
3.2.2 具有最简单流量控制的数据链路层协议
现在去掉上述的第二个假定。但是，仍然保留第一个假定，即主机 A 向主机 B
传输数据的信道仍然是无差错的理想信道。然而现在不能保证接收端向主机交付数据的速率永远不低于发送端发送数据的速率。
由收方控制发方的数据流,乃是计算机网络中流量控制的一个基本方法。
课件制作人：谢希仁具有最简单流量控制的数据链路层协议算法在发送结点：
(1) 从主机取一个数据帧。
(2) 将数据帧送到数据链路层的发送缓存。
(3) 将发送缓存中的数据帧发送出去。
(4) 等待。
(5) 若收到由接收结点发过来的信息 (此信息的格式与内容可由双方事先商定好 )，则从主机取一个新的数据帧，然后转到 (2)。
课件制作人：谢希仁具有最简单流量控制的数据链路层协议算法（续）
在接收结点：
(1) 等待。
(2) 若收到由发送结点发过来的数据帧，
则将其放入数据链路层的接收缓存。
(3) 将接收缓存中的数据帧上交主机。
(4) 向发送结点发一信息，表示数据帧已经上交给主机。
(5) 转到 (1)。
课件制作人：谢希仁两种情况的对比（传输均无差错）
A B
送主机 B
送主机 B
送主机 B
送主机 B
A B
送主机 B
送主机 B
时间不需要流量控制 需要流量控制课件制作人：谢希仁
3.2.3 实用的停止等待协议时间
A B
送主机送主机
(a) 正常情况
A B
送主机
(c) 数据帧丢失重传
tout
丢失
！
A B
送主机丢弃
(d) 确认帧丢失重传
tout 丢失
！
A B
送主机
(b) 数据帧出错重传出错四种情况课件制作人：谢希仁超时计时器的作用
结点 A发送完一个数据帧时，就启动一个超时计时器 (timeout timer)。
计时器又称为 定时器 。
若到了超时计时器所设置的重传时间 tout
而仍收不到结点 B 的任何确认帧，则结点 A 就重传前面所发送的这一数据帧。
一般可将重传时间选为略大于“从发完数据帧到收到确认帧所需的平均时间”。
课件制作人：谢希仁解决重复帧的问题
使每一个数据帧带上不同的发送序号。每发送一个新的数据帧就把它的发送序号加 1。
若结点 B 收到发送序号相同的数据帧，就表明出现了重复帧。这时应丢弃重复帧，因为已经收到过同样的数据帧并且也交给了主机 B。
但此时结点 B 还必须向 A 发送确认帧 ACK，
因为 B 已经知道 A 还没有收到上一次发过去的确认帧 ACK。
课件制作人：谢希仁帧的编号问题
任何一个编号系统的序号所占用的比特数一定是有限的。因此，经过一段时间后，发送序号就会重复。
序号占用的比特数越少，数据传输的额外开销就越小。
对于停止等待协议，由于每发送一个数据帧就停止等待，因此用一个比特来编号就够了。
一个比特可表示 0 和 1 两种不同的序号。
课件制作人：谢希仁帧的发送序号
数据帧中的发送序号 N(S) 以 0 和 1 交替的方式出现在数据帧中。
每发一个新的数据帧，发送序号就和上次发送的不一样。用这样的方法就可以使收方能够区分开新的数据帧和重传的数据帧了。
课件制作人：谢希仁可靠传输
虽然物理层在传输比特时会出现差错，
但由于数据链路层的停止等待协议采用了有效的检错重传机制，数据链路层对上面的网络层就可以提供 可靠传输 的服务。
课件制作人：谢希仁
3.2.4 循环冗余检验的原理
在数据链路层传送的帧中，广泛使用了循环冗余检验 CRC 的检错技术。
假设待传送的数据 M = 1010001101（共
k bit）。我们在 M的后面再添加供差错检测用的 n bit 冗余码 一起发送。
课件制作人：谢希仁冗余码的计算
用二进制的模 2运算进行 2n 乘 M 的运算，
这相当于在 M 后面添加 n 个 0。
得到的 (k + n) bit 的数除以事先选定好的长度为 (n + 1) bit 的数 P，得出商是 Q
而余数是 R，余数 R 比除数 P 至少要少
1 个比特。
课件制作人：谢希仁冗余码的计算举例
设 n = 5,P = 110101，模 2 运算的结果是：商 Q = 1101010110，
余数 R = 01110。
将余数 R 作为冗余码添加在数据 M 的后面发送出去，即发送的数据是
101000110101110，或 2nM + R。
课件制作人：谢希仁
1101010110 ← Q 商除数 P → 110101 101000110100000 ← 2nM 被除数
110101
111011
110101
111010
110101
111110
110101
101100
110101
110010
110101
01110 ← R 余数循环冗余检验的原理说明课件制作人：谢希仁帧检验序列 FCS
在数据后面添加上的冗余码称为 帧检验序列 FCS (Frame Check Sequence)。
循环冗余检验 CRC 和帧检验序列 FCS
并不等同。
CRC 是一种常用的 检错方法,而 FCS 是添加在数据后面的 冗余码 。
FCS 可以用 CRC 这种方法得出，但 CRC
并非用来获得 FCS 的惟一方法。
课件制作人：谢希仁检测出差错
只要得出的余数 R 不为 0,就表示检测到了 差错 。
但这种检测方法并不能确定究竟是哪一个或哪几个比特出现了差错 。
一旦检测出差错,就 丢弃 这个出现差错的帧 。
只要经过严格的挑选,并使用位数足够多的除数 P,那么出现检测不到的差错的概率就很小很小 。
课件制作人：谢希仁应当注意
仅用循环冗余检验 CRC 差错检测技术只能做到无差错 接受 (accept)。
,无差错接受,是指：,凡是接受的帧 （ 即 不包括丢弃的帧 ）,我们都能以非常接近于 1 的概率认为这些帧在传输过程中没有产生差错,。
也就是说：,凡是接受的帧都没有传输差错,
（ 有差错的帧就丢弃而不接受 ） 。
要做到,可靠传输,（ 即发送什么就收到什么 ）
就必须再加上 确认 和 重传 机制 。
课件制作人：谢希仁
3.2.5 停止等待协议的算法
这里 不使用否认帧 （ 实用的数据链路层协议大都是这样的 ）,而且确认帧带有序号 n。
按照习惯的表示法,ACKn 表示,第 n – 1 号帧已经收到,现在 期望接收 第 n 号帧,。
ACK1 表示,0 号帧已收到,现在期望接收的下一帧是 1号帧,；
ACK0 表示,1 号帧已收到,现在期望接收的下一帧是 0 号帧,。
课件制作人：谢希仁在发送结点
(1) 从主机取一个数据帧，送交发送缓存。
(2) V(S)←0 。
(3) N(S)←V(S) 。
(4) 将发送缓存中的数据帧发送出去。
(5) 设置超时计时器。
(6) 等待。 {等待以下 (7)和 (8)这两个事件中最先出现的一个 }
(7) 收到确认帧 ACKn，
若 n = 1 – V(s)，则：
从主机取一个新的数据帧，放入发送缓存；
V(S)←[1? V(S)]，转到 (3)。
否则，丢弃这个确认帧，转到 (6)。
(8) 若超时计时器时间到，则转到 (4)。
课件制作人：谢希仁在接收结点
(1) V(R)←0 。
(2) 等待。
(3) 收到一个数据帧；
若 N(S) = V(R)，则执行 (4)；
否则丢弃此数据帧，然后转到 (6)。
(4) 将收到的数据帧中的数据部分送交上层软件
（也就是数据链路层模型中的主机）。
(5) V(R)←[1? V(R)]。
(6) n←V(R) ；
发送确认帧 ACKn，转到 (2)。
课件制作人：谢希仁停止等待协议的要点
只有收到序号正确的确认帧 ACKn 后,才更新发送状态变量 V(S)一次,并发送新的数据帧 。
接收端接收到数据帧时,就要将发送序号 N(S)
与本地的接收状态变量 V(R) 相比较 。
若二者相等就表明是 新的数据帧,就收下,并发送确认 。
否则为 重复帧,就必须丢弃 。 但这时 仍须向发送端发送确认帧 ACKn,而接收状态变量 V(R) 和确认序号 n 都不变 。
课件制作人：谢希仁停止等待协议的要点（续）
连续出现相同发送序号的数据帧,表明发送端进行了 超时重传 。 连续出现相同序号的确认帧,表明接收端收到了 重复帧 。
发送端在发送完数据帧时,必须在其发送缓存中暂时保留这个数据帧的 副本 。
这样才能在出差错时进行重传 。 只有确认对方已经收到这个数据帧时,才可以清除这个副本 。
课件制作人：谢希仁停止等待协议的要点（续）
实用的 CRC检验器都是用 硬件 完成的 。
CRC 检验器能够自动丢弃检测到的出错帧 。 因此所谓的,丢弃出错帧,,对上层软件或用户来说都是 感觉不到 的 。
发送端对出错的数据帧进行重传是自动进行的,因而这种差错控制体制常简称为 ARQ (Automatic Repeat reQuest)，
直译是 自动重传请求,但意思是 自动请求重传 。
课件制作人：谢希仁
3.2.6 停止等待协议的定量分析
设 tf 是一个数据帧的 发送时间,且数据帧的长度是固定不变的。显然，数据帧的发送时间 tf 是数据帧的长度 lf (bit)与数据的发送速率 C (bit/s)之比，即
tf = lf /C = lf /C (s) （ 3-1）
发送时间 tf 也就是数据帧的 发送时延 。
数据帧沿链路传到结点 B还要经历一个 传播时延 tp。
结点 B 收到数据帧要花费时间进行处理，此时间称为处理时间 tpr，发送确认帧 ACK 的发送时间为 ta。
课件制作人：谢希仁停止等待协议中数据帧和确认帧的发送时间关系
A B
DATA
DATA
ACK
传播时延 tp
处理时间 tpr
确认帧发送时间 ta
传播时延 tp
处理时间 tpr
tT
时间两个成功发送的数据帧之间的最小时间间隔数据帧的发送时间 tf
设置的重传时间
tout
课件制作人：谢希仁重传时间
重传时间的作用是：数据帧发送完毕后若经过了这样长的时间还没有收到确认帧,就重传这个数据帧 。
为方便起见，我们设重传时间为
tout = tp + tpr+ ta + tp + tpr (3-2)
设上式右端的处理时间 tpr 和确认帧的发送时间 ta 都远小于传播时延 tp，因此可将重传时间取为 两倍的传播时延,即
tout = 2tp (3-3)
课件制作人：谢希仁简单的数学分析
两个发送成功的数据帧之间的最小时间间隔是
tT = tf + tout = tf + 2tp (3-4)
设数据帧出现差错 (包括帧丢失 )的概率为 p，
但假设确认帧不会出现差错 。
设 正确 传送一个数据帧所需的 平均时间 tav
tav = tT ( 1 + 一个帧的平均重传次数 )
课件制作人：谢希仁简单的数学分析（续）
一帧的平均重传次数
= {1? P[重传次数为 1] + 2? P[重传次数为 2] + 3? P[重传次数为 3] +…}
= {1? P[第 1 次发送出错 ]? P[第 2 次发送成功 ]
+ 2? P[第 1,2 次发送出错 ]? P[第 3 次发送成功 ]
+ 3? P[第 1,2,3 次发送出错 ]? P[第 4 次发送成功 ] +…}
= p(1 – p) + 2p2(1 – p) + 3p3(1 – p) + …
这里 P[X] 是出现事件 X 的概率。
课件制作人：谢希仁简单的数学分析（续）
得出正确传送一个数据帧所需的平均时间：
当传输差错率增大时,tav也随之增大。当无差错时,p = 0,tav = tT。
)1(/)1(
1
pttipptt
i
TT
i
Tav
(3-5)
课件制作人：谢希仁简单的数学分析（续）
每秒成功发送的最大帧数就是链路的最大吞吐量?max。显然，
max = 1/tav = (1? p) / tT (3-6)
在发送端，设数据帧的实际到达率为?，则?不应超过最大吞吐量?max，即
(1? p) / tT (3-7)
用时间 tf 进行归一化，得出归一化的吞吐量? 为
tf? (1? p) /? < 1 (3-8)
其中参数? 是 tT 的归一化时间：
tT / tf? 1 (3-9)
当重传时间远小于发送时间时, 1，此时的归一化吞吐量
1? p (3-10)
课件制作人：谢希仁停止等待协议 ARQ 的优缺点
优点,比较简单 。
缺点：通信信道的利用率不高，也就是说，信道还远远没有被数据比特填满。
为了克服这一缺点，就产生了另外两种协议，
即连续 ARQ 和选择重传 ARQ。这将在后面进一步讨论。
课件制作人：谢希仁
3.3连续 ARQ 协议
3.3.1 连续 ARQ 协议的工作原理
在发送完一个数据帧后，不是停下来等待确认帧，而是可以连续再发送若干个数据帧。
如果这时收到了接收端发来的确认帧，那么还可以接着发送数据帧。
由于减少了等待时间，整个通信的吞吐量就提高了。
课件制作人：谢希仁连续 ARQ 协议的工作原理
ACK1 确认 DATA0
ACK2 确认 DATA1
DATA2 出错,丢弃
DATA3 不按序,丢弃,重传 ACK2
DATA4 不按序,丢弃,重传 ACK2
DATA5 不按序,丢弃,重传 ACK2
ACK3 确认 DATA2
ACK4 确认 DATA3
超时重传时间
A B
tout
送交主机送交主机
…
课件制作人：谢希仁需要注意：
(1) 接收端 只按序接收 数据帧。虽然在有差错的 2号帧之后接着又收到了正确的 3 个数据帧，但接收端都必须将这些帧丢弃，因为在这些帧前面有一个 2 号帧还没有收到。虽然丢弃了这些不按序的无差错帧，但应重复发送已发送过的最后一个确认帧（防止确认帧丢失）。
(2) ACK1 表示确认 0 号帧 DATA0，并期望下次收到 1
号帧； ACK2 表示确认 1 号帧 DATA1，并期望下次收到 2 号帧。依此类推。
课件制作人：谢希仁需要注意：
(3) 结点 A 在每发送完一个数据帧时都要设置该帧的 超时计时器 。如果在所设置的超时时间内收到确认帧，就立即将超时计时器清零。但若在所设置的超时时间到了而未收到确认帧，就要重传相应的数据帧（仍需重新设置超时计时器）。
在等不到 2 号帧的确认而重传 2 号数据帧时，虽然结点 A 已经发完了 5 号帧，但仍必须向回走，将 2
号帧及其以后的各帧全部进行重传。连续 ARQ 又称为
Go-back-N ARQ，意思是当出现差错必须重传时，要向回走 N 个帧，然后再开始重传。
课件制作人：谢希仁需要注意：
(4) 以上讲述的仅仅是连续 ARQ 协议的工作原理。协议在具体实现时还有许多的细节。例如，用一个计时器就可实现相当于 N 个独立的超时计时器的功能。
课件制作人：谢希仁
3.3.2 连续 ARQ 协议的吞吐量
可以很方便地导出连续 ARQ 协议的吞吐量公式。
课件制作人：谢希仁
3.3.3 滑动窗口的概念
发送端和接收端分别设定发送窗口和接收窗口 。
发送窗口用来对发送端进行流量控制。
发送窗口的大小 WT 代表在还没有收到对方确认信息的情况下发送端最多可以发送多少个数据帧。
0 1 2 3 4 5 6 7 0 1 2
发送窗口
WT
不允许发送这些帧允许发送 5 个帧
(a)
0 1 2 3 4 5 6 7 0 1 2
不允许发送这些帧还允许发送 4 个帧
WT
已发送
(b)
0 1 2 3 4 5 6 7 0 1 2
不允许发送这些帧
WT
已发送
(c)
0 1 2 3 4 5 6 7 0 1 2
不允许发送这些帧还允许发送
3 个帧
WT
已发送已发送并已收到确认
(d)
课件制作人：谢希仁接收端设置接收窗口
在接收端只有当收到的数据帧的发送序号落入接收窗口内才允许将该数据帧收下。
若接收到的数据帧落在接收窗口之外，则一律将其丢弃。
在连续 ARQ 协议中，接收窗口的大小 WR = 1。
只有当收到的帧的序号与接收窗口一致时才能接收该帧。
否则，就丢弃它。
每收到一个序号正确的帧，接收窗口就向前（即向右方）
滑动一个帧的位置。同时发送对该帧的确认。
不允许接收这些帧
0 1 2 3 4 5 6 7 0 1 2
WR
准备接收 0 号帧
(a)
不允许接收这些帧
0 1 2 3 4 5 6 7 0 1 2
WR
准备接收
1 号帧已收到
(b)
不允许接收这些帧
0 1 2 3 4 5 6 7 0 1 2
WR
准备接收 4 号帧已收到
(c)
课件制作人：谢希仁滑动窗口的重要特性
只有在接收窗口向前滑动时（与此同时也发送了确认），发送窗口才有可能向前滑动。
收发两端的窗口按照以上规律不断地向前滑动，因此这种协议又称为滑动窗口协议。
当发送窗口和接收窗口的大小都等于 1
时，就是停止等待协议。
课件制作人：谢希仁发送窗口的最大值
当用 n 个比特进行编号时，若接收窗口的大小为 1，则只有在发送窗口的大小
WT? 2n? 1时，连续 ARQ 协议才能正确运行。
例如，当采用 3 bit 编码时，发送窗口的最大值是 7 而不是 8。
课件制作人：谢希仁
3.3.4 信道利用率
由于每个数据帧都必须包括一定的控制信息 (如帧的序号、地址、同步信息以及其他的一些控制信息 )，所以即使连续不停地发送数据帧，信道利用率 (即扣除全部的控制信息后的数据率与信道容量之比 )也不可能达到 100 %。
当出现差错时 (这是不可避免的 )，数据帧的不断重传将进一步使信道利用率降低。
课件制作人：谢希仁最佳帧长
若数据帧的帧长取得很短，那么控制信息在每一帧中所占的比例就增大，因而额外开销增大，这就导致信道利用率的下降。
若帧长取得太长，则数据帧在传输过程中出错的概率就增大，于是重传次数将增大，这也会使信道利用率下降。
由此可见，存在一个 最佳帧长,在此帧长下信道的利用率最高。
课件制作人：谢希仁
3.4 选择重传 ARQ 协议
可加大接收窗口，先收下发送序号不连续但仍处在接收窗口中的那些数据帧。等到所缺序号的数据帧收到后再一并送交主机。
选择重传 ARQ 协议可避免重复传送那些本来已经正确到达接收端的数据帧。
但我们付出的代价是在接收端要设置具有相当容量的缓存空间。
对于选择重传 ARQ 协议，若用 n 比特进行编号，则接收窗口的最大值受下式的约束
WR? 2n/2 (3-18)
课件制作人：谢希仁
3.5 面向比特的链路控制规程 HDLC
3.5.1 HDLC 协议概述
1974年,IBM 公司推出了面向比特的规程
SDLC (Synchronous Data Link Control)。
后来 ISO 把 SDLC 修改后称为 HDLC (High-
level Data Link Control)，译为高级数据链路控制，作为国际标准 ISO 3309。
CCITT 则将 HDLC 再修改后称为链路接入规程 LAP (Link Access Procedure)。不久，
HDLC 的新版本又把 LAP 修改为 LAPB，,B”
表示平衡型 (Balanced)，所以 LAPB 叫做链路接入规程 (平衡型 )。
课件制作人：谢希仁
3.5.2 HDLC 的帧结构
标志字段 F (Flag) 为 6 个连续 1 加上两边各一个 0 共 8 bit。在接收端只要找到标志字段就可确定一个帧的位置。
比特 8 8 8 可变 16 8
信息
Info
标志
F
标志
F
地址
A
控制
C
帧检验序列
FCS
透明传输区间
FCS 检验区间课件制作人：谢希仁零比特填充法
HDLC 采用零比特填充法使一帧中两个
F 字段之间不会出现 6 个连续 1。
在发送端，当一串比特流数据中有 5 个连续 1 时，就立即填入一个 0。
在接收帧时，先找到 F 字段以确定帧的边界。接着再对比特流进行扫描。每当发现 5 个连续 1 时，就将其后的一个 0
删除，以还原成原来的比特流。
课件制作人：谢希仁零比特的填充与删除数据中某一段比特组合恰好出现和 F 字段一样的情况
0 1 0 0 1 1 1 1 1 1 0 0 0 1 0 1 0
会被误认为是 F 字段发送端在 5 个连 1 之后填入 0 比特再发送出去填入 0 比特
0 1 0 0 1 1 1 1 1 0 1 0 0 0 1 0 1 0
在接收端将 5 个连 1 之后的 0 比特删除，恢复原样在此位置删除填入的 0 比特
0 1 0 0 1 1 1 1 1 0 1 0 0 0 1 0 1 0
课件制作人：谢希仁透明传输
采用零比特填充法就可传送任意组合的比特流，或者说，就可实现数据链路层的 透明传输 。
当连续传输两个帧时，前一个帧的结束标志字段 F 可以兼作后一帧的起始标志字段。
当暂时没有信息传送时，可以连续发送标志字段，使收端可以一直和发端保持同步。
课件制作人：谢希仁其他字段
地址字段 A 是 8 bit。
帧检验序列 FCS 字段共 16 bit。所检验的范围是从地址字段的第一个比特起，
到信息字段的最末一个比特为止。
控制字段 C 共 8 bit，是最复杂的字段。
HDLC 的许多重要功能都靠控制字段来实现。
课件制作人：谢希仁
3.6 因特网的点对点协议 PPP
3.6.1 PPP 协议的工作原理
现在全世界使用得最多的数据链路层协议是 点对点协议 PPP (Point-to-Point
Protocol)。
用户使用拨号电话线接入因特网时，一般都是使用 PPP 协议。
课件制作人：谢希仁用户拨号入网的示意图路由器调制解调器调制解调器因特网服务提供者 (ISP)用户家庭拨号电话线使用 TCP/IP 的
PPP 连接使用 TCP/IP 的客户进程路由选择进程至因特网…
PC 机课件制作人：谢希仁
PPP 协议
1992 年制订了 PPP 协议。经过 1993 年和 1994 年的修订，现在的 PPP 协议已成为因特网的正式标准 [RFC 1661]。
PPP协议有三个组成部分
一个将 IP 数据报封装到串行链路的方法。
链路控制协议 LCP (Link Control Protocol)。
网络控制协议 NCP (Network Control
Protocol)。
课件制作人：谢希仁
3.6.2 PPP 协议的帧格式
PPP 的帧格式和 HDLC 的相似。
标志字段 F仍为 0x7E （符号,0x”表示后面的字符是用十六进制表示。十六进制的 7E的二进制表示是 01111110）。
地址字段 A 只置为 0xFF。地址字段实际上并不起作用。
控制字段 C通常置为 0x03。
PPP 是面向字节的，所有的 PPP 帧的长度都是整数字节。
课件制作人：谢希仁
PPP 协议的帧格式
PPP 有一个 2 个字节的协议字段。
当协议字段为 0x0021 时,PPP 帧的信息字段就是
IP 数据报。
若为 0xC021,则信息字段是 PPP 链路控制数据。
若为 0x8021，则表示这是网络控制数据。
IP 数据报
1 21 1字节 1 2不超过 1500 字节
PPP 帧先发送
7E FF 03
F A C FCS F
7E协议 信 息 部 分首部 尾部课件制作人：谢希仁透明传输问题
当 PPP 用在同步传输链路时，协议规定采用硬件来完成比特填充（和 HDLC 的做法一样）。
当 PPP 用在异步传输时，就使用一种特殊的 字符填充法 。
课件制作人：谢希仁字符填充法
将信息字段中出现的每一个 0x7E 字节转变成为 2 字节序列 (0x7D,0x5E)。
若信息字段中出现一个 0x7D 的字节,则将其转变成为 2 字节序列 (0x7D,0x5D)。
若信息字段中出现 ASCII 码的控制字符
（即数值小于 0x20 的字符），则在该字符前面要加入一个 0x7D 字节，同时将该字符的编码加以改变。
课件制作人：谢希仁不提供使用序号和确认的可靠传输
PPP 协议之所以不使用序号和确认机制是出于以下的考虑：
在数据链路层出现差错的概率不大时，使用比较简单的 PPP 协议较为合理。
在因特网环境下,PPP 的信息字段放入的数据是 IP 数据报。 数据链路层的可靠传输并不能够保证网络层的传输也是可靠的。
帧检验序列 FCS 字段可保证无差错接受。
课件制作人：谢希仁
3.6.3 PPP 协议的工作状态
当用户拨号接入 ISP 时，路由器的调制解调器对拨号做出确认，并建立一条物理连接。
PC 机向路由器发送一系列的 LCP 分组（封装成多个 PPP 帧）。
这些分组及其响应选择一些 PPP 参数，和进行网络层配置,NCP 给新接入的 PC机分配一个临时的 IP 地址，使 PC 机成为因特网上的一个主机。
通信完毕时,NCP 释放网络层连接，收回原来分配出去的 IP 地址。接着,LCP 释放数据链路层连接。最后释放的是物理层的连接。
课件制作人：谢希仁
PPP 协议的状态图建立失败失败
NCP 配置鉴别成功通信结束载波停止检测到载波双方协商一些选项鉴别网络打开终止静止
*3.1 数据链路层的基本概念
*3.2 停止等待协议
3.2.1 完全理想化的数据传输
3.2.2 具有最简单流量控制的数据链路层协议
3.2.3 实用的停止等待协议
3.2.4 循环冗余检验的原理
3.2.5 停止等待协议的算法
3.2.6 停止等待协议的定量分析课件制作人：谢希仁第 3 章 数据链路层（续）
*3.3 连续 ARQ 协议
3.3.1 连续 ARQ 协议的工作原理
3.3.2 连续 ARQ 协议的吞吐量
3.3.3 滑动窗口的概念
3.3.4 信道利用率与最佳帧长
3.4 选择重传 ARQ 协议课件制作人：谢希仁第 3 章 数据链路层（续）
*3.5 面向比特的链路层协议 HDLC
3.5.1 HDLC 协议概述
3.5.2 HDLC 的帧结构
*3.6 因特网的点对点协议 PPP
3.6.1 PPP 协议的工作原理
3.6.2 PPP 协议的帧格式
3.6.3 PPP 协议的工作状态课件制作人：谢希仁
3.1 数据链路层的基本概念
链路 (link)是一条无源的点到点的物理线路段，中间没有任何其他的交换结点。
一条链路只是一条通路的一个组成部分。
数据链路 (data link) 除了物理线路外，还必须有通信协议来控制这些数据的传输。若把实现这些协议的硬件和软件加到链路上，就构成了数据链路。
现在最常用的方法是使用适配器（即网卡）来实现这些协议的硬件和软件。
一般的适配器都包括了数据链路层和物理层这两层的功能。
课件制作人：谢希仁数据链路层像个数字管道
常常在两个对等的数据链路层之间画出一个数字管道，而在这条数字管道上传输的数据单位是 帧 。
早期的数据通信协议曾叫作 通信规程
(procedure)。因此在数据链路层，规程和协议是同义语。
结点 结点帧 帧课件制作人：谢希仁数据链路层的主要功能
(1) 链路管理
(2) 帧定界
(3) 流量控制
(4) 差错控制
(5) 将数据和控制信息区分开
(6) 透明传输
(7) 寻址课件制作人：谢希仁
3.2 停止 等待 协议
3.2.1 完全理想化的数据传输
先研究一下数据链路层的模型。
课件制作人：谢希仁数据链路层的简单模型局域网 广域网主机 H1 主机 H
2
路由器 R1 路由器 R
2
路由器 R3
电话网 局域网主机 H1 向 H2 发送数据链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层
R1 R2 R3
H1 H2从层次上来看数据的流动课件制作人：谢希仁数据链路层的简单模型
( 续）
局域网 广域网主机 H1 主机 H
2
路由器 R1 路由器 R
2
路由器 R3
电话网 局域网主机 H1 向 H2 发送数据链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层
R1 R2 R3
H1 H2仅从数据链路层观察帧的流动课件制作人：谢希仁
3.2 停止等待协议
3.2.1 完全理想化的数据传输数据链路层主机
A
缓存主机
B
数据链路
AP2AP1
缓存发送方 接收方帧高层帧课件制作人：谢希仁完全理想化的数据传输所基于的两个假定
假定 1,链路是理想的传输信道，所传送的任何数据既不会出差错也不会丢失。
假定 2,不管发方以多快的速率发送数据，收方总是来得及收下，并及时上交主机。
这个假定就相当于认为：接收端向主机交付数据的速率永远不会低于发送端发送数据的速率。
课件制作人：谢希仁
3.2.2 具有最简单流量控制的数据链路层协议
现在去掉上述的第二个假定。但是，仍然保留第一个假定，即主机 A 向主机 B
传输数据的信道仍然是无差错的理想信道。然而现在不能保证接收端向主机交付数据的速率永远不低于发送端发送数据的速率。
由收方控制发方的数据流,乃是计算机网络中流量控制的一个基本方法。
课件制作人：谢希仁具有最简单流量控制的数据链路层协议算法在发送结点：
(1) 从主机取一个数据帧。
(2) 将数据帧送到数据链路层的发送缓存。
(3) 将发送缓存中的数据帧发送出去。
(4) 等待。
(5) 若收到由接收结点发过来的信息 (此信息的格式与内容可由双方事先商定好 )，则从主机取一个新的数据帧，然后转到 (2)。
课件制作人：谢希仁具有最简单流量控制的数据链路层协议算法（续）
在接收结点：
(1) 等待。
(2) 若收到由发送结点发过来的数据帧，
则将其放入数据链路层的接收缓存。
(3) 将接收缓存中的数据帧上交主机。
(4) 向发送结点发一信息，表示数据帧已经上交给主机。
(5) 转到 (1)。
课件制作人：谢希仁两种情况的对比（传输均无差错）
A B
送主机 B
送主机 B
送主机 B
送主机 B
A B
送主机 B
送主机 B
时间不需要流量控制 需要流量控制课件制作人：谢希仁
3.2.3 实用的停止等待协议时间
A B
送主机送主机
(a) 正常情况
A B
送主机
(c) 数据帧丢失重传
tout
丢失
！
A B
送主机丢弃
(d) 确认帧丢失重传
tout 丢失
！
A B
送主机
(b) 数据帧出错重传出错四种情况课件制作人：谢希仁超时计时器的作用
结点 A发送完一个数据帧时，就启动一个超时计时器 (timeout timer)。
计时器又称为 定时器 。
若到了超时计时器所设置的重传时间 tout
而仍收不到结点 B 的任何确认帧，则结点 A 就重传前面所发送的这一数据帧。
一般可将重传时间选为略大于“从发完数据帧到收到确认帧所需的平均时间”。
课件制作人：谢希仁解决重复帧的问题
使每一个数据帧带上不同的发送序号。每发送一个新的数据帧就把它的发送序号加 1。
若结点 B 收到发送序号相同的数据帧，就表明出现了重复帧。这时应丢弃重复帧，因为已经收到过同样的数据帧并且也交给了主机 B。
但此时结点 B 还必须向 A 发送确认帧 ACK，
因为 B 已经知道 A 还没有收到上一次发过去的确认帧 ACK。
课件制作人：谢希仁帧的编号问题
任何一个编号系统的序号所占用的比特数一定是有限的。因此，经过一段时间后，发送序号就会重复。
序号占用的比特数越少，数据传输的额外开销就越小。
对于停止等待协议，由于每发送一个数据帧就停止等待，因此用一个比特来编号就够了。
一个比特可表示 0 和 1 两种不同的序号。
课件制作人：谢希仁帧的发送序号
数据帧中的发送序号 N(S) 以 0 和 1 交替的方式出现在数据帧中。
每发一个新的数据帧，发送序号就和上次发送的不一样。用这样的方法就可以使收方能够区分开新的数据帧和重传的数据帧了。
课件制作人：谢希仁可靠传输
虽然物理层在传输比特时会出现差错，
但由于数据链路层的停止等待协议采用了有效的检错重传机制，数据链路层对上面的网络层就可以提供 可靠传输 的服务。
课件制作人：谢希仁
3.2.4 循环冗余检验的原理
在数据链路层传送的帧中，广泛使用了循环冗余检验 CRC 的检错技术。
假设待传送的数据 M = 1010001101（共
k bit）。我们在 M的后面再添加供差错检测用的 n bit 冗余码 一起发送。
课件制作人：谢希仁冗余码的计算
用二进制的模 2运算进行 2n 乘 M 的运算，
这相当于在 M 后面添加 n 个 0。
得到的 (k + n) bit 的数除以事先选定好的长度为 (n + 1) bit 的数 P，得出商是 Q
而余数是 R，余数 R 比除数 P 至少要少
1 个比特。
课件制作人：谢希仁冗余码的计算举例
设 n = 5,P = 110101，模 2 运算的结果是：商 Q = 1101010110，
余数 R = 01110。
将余数 R 作为冗余码添加在数据 M 的后面发送出去，即发送的数据是
101000110101110，或 2nM + R。
课件制作人：谢希仁
1101010110 ← Q 商除数 P → 110101 101000110100000 ← 2nM 被除数
110101
111011
110101
111010
110101
111110
110101
101100
110101
110010
110101
01110 ← R 余数循环冗余检验的原理说明课件制作人：谢希仁帧检验序列 FCS
在数据后面添加上的冗余码称为 帧检验序列 FCS (Frame Check Sequence)。
循环冗余检验 CRC 和帧检验序列 FCS
并不等同。
CRC 是一种常用的 检错方法,而 FCS 是添加在数据后面的 冗余码 。
FCS 可以用 CRC 这种方法得出，但 CRC
并非用来获得 FCS 的惟一方法。
课件制作人：谢希仁检测出差错
只要得出的余数 R 不为 0,就表示检测到了 差错 。
但这种检测方法并不能确定究竟是哪一个或哪几个比特出现了差错 。
一旦检测出差错,就 丢弃 这个出现差错的帧 。
只要经过严格的挑选,并使用位数足够多的除数 P,那么出现检测不到的差错的概率就很小很小 。
课件制作人：谢希仁应当注意
仅用循环冗余检验 CRC 差错检测技术只能做到无差错 接受 (accept)。
,无差错接受,是指：,凡是接受的帧 （ 即 不包括丢弃的帧 ）,我们都能以非常接近于 1 的概率认为这些帧在传输过程中没有产生差错,。
也就是说：,凡是接受的帧都没有传输差错,
（ 有差错的帧就丢弃而不接受 ） 。
要做到,可靠传输,（ 即发送什么就收到什么 ）
就必须再加上 确认 和 重传 机制 。
课件制作人：谢希仁
3.2.5 停止等待协议的算法
这里 不使用否认帧 （ 实用的数据链路层协议大都是这样的 ）,而且确认帧带有序号 n。
按照习惯的表示法,ACKn 表示,第 n – 1 号帧已经收到,现在 期望接收 第 n 号帧,。
ACK1 表示,0 号帧已收到,现在期望接收的下一帧是 1号帧,；
ACK0 表示,1 号帧已收到,现在期望接收的下一帧是 0 号帧,。
课件制作人：谢希仁在发送结点
(1) 从主机取一个数据帧，送交发送缓存。
(2) V(S)←0 。
(3) N(S)←V(S) 。
(4) 将发送缓存中的数据帧发送出去。
(5) 设置超时计时器。
(6) 等待。 {等待以下 (7)和 (8)这两个事件中最先出现的一个 }
(7) 收到确认帧 ACKn，
若 n = 1 – V(s)，则：
从主机取一个新的数据帧，放入发送缓存；
V(S)←[1? V(S)]，转到 (3)。
否则，丢弃这个确认帧，转到 (6)。
(8) 若超时计时器时间到，则转到 (4)。
课件制作人：谢希仁在接收结点
(1) V(R)←0 。
(2) 等待。
(3) 收到一个数据帧；
若 N(S) = V(R)，则执行 (4)；
否则丢弃此数据帧，然后转到 (6)。
(4) 将收到的数据帧中的数据部分送交上层软件
（也就是数据链路层模型中的主机）。
(5) V(R)←[1? V(R)]。
(6) n←V(R) ；
发送确认帧 ACKn，转到 (2)。
课件制作人：谢希仁停止等待协议的要点
只有收到序号正确的确认帧 ACKn 后,才更新发送状态变量 V(S)一次,并发送新的数据帧 。
接收端接收到数据帧时,就要将发送序号 N(S)
与本地的接收状态变量 V(R) 相比较 。
若二者相等就表明是 新的数据帧,就收下,并发送确认 。
否则为 重复帧,就必须丢弃 。 但这时 仍须向发送端发送确认帧 ACKn,而接收状态变量 V(R) 和确认序号 n 都不变 。
课件制作人：谢希仁停止等待协议的要点（续）
连续出现相同发送序号的数据帧,表明发送端进行了 超时重传 。 连续出现相同序号的确认帧,表明接收端收到了 重复帧 。
发送端在发送完数据帧时,必须在其发送缓存中暂时保留这个数据帧的 副本 。
这样才能在出差错时进行重传 。 只有确认对方已经收到这个数据帧时,才可以清除这个副本 。
课件制作人：谢希仁停止等待协议的要点（续）
实用的 CRC检验器都是用 硬件 完成的 。
CRC 检验器能够自动丢弃检测到的出错帧 。 因此所谓的,丢弃出错帧,,对上层软件或用户来说都是 感觉不到 的 。
发送端对出错的数据帧进行重传是自动进行的,因而这种差错控制体制常简称为 ARQ (Automatic Repeat reQuest)，
直译是 自动重传请求,但意思是 自动请求重传 。
课件制作人：谢希仁
3.2.6 停止等待协议的定量分析
设 tf 是一个数据帧的 发送时间,且数据帧的长度是固定不变的。显然，数据帧的发送时间 tf 是数据帧的长度 lf (bit)与数据的发送速率 C (bit/s)之比，即
tf = lf /C = lf /C (s) （ 3-1）
发送时间 tf 也就是数据帧的 发送时延 。
数据帧沿链路传到结点 B还要经历一个 传播时延 tp。
结点 B 收到数据帧要花费时间进行处理，此时间称为处理时间 tpr，发送确认帧 ACK 的发送时间为 ta。
课件制作人：谢希仁停止等待协议中数据帧和确认帧的发送时间关系
A B
DATA
DATA
ACK
传播时延 tp
处理时间 tpr
确认帧发送时间 ta
传播时延 tp
处理时间 tpr
tT
时间两个成功发送的数据帧之间的最小时间间隔数据帧的发送时间 tf
设置的重传时间
tout
课件制作人：谢希仁重传时间
重传时间的作用是：数据帧发送完毕后若经过了这样长的时间还没有收到确认帧,就重传这个数据帧 。
为方便起见，我们设重传时间为
tout = tp + tpr+ ta + tp + tpr (3-2)
设上式右端的处理时间 tpr 和确认帧的发送时间 ta 都远小于传播时延 tp，因此可将重传时间取为 两倍的传播时延,即
tout = 2tp (3-3)
课件制作人：谢希仁简单的数学分析
两个发送成功的数据帧之间的最小时间间隔是
tT = tf + tout = tf + 2tp (3-4)
设数据帧出现差错 (包括帧丢失 )的概率为 p，
但假设确认帧不会出现差错 。
设 正确 传送一个数据帧所需的 平均时间 tav
tav = tT ( 1 + 一个帧的平均重传次数 )
课件制作人：谢希仁简单的数学分析（续）
一帧的平均重传次数
= {1? P[重传次数为 1] + 2? P[重传次数为 2] + 3? P[重传次数为 3] +…}
= {1? P[第 1 次发送出错 ]? P[第 2 次发送成功 ]
+ 2? P[第 1,2 次发送出错 ]? P[第 3 次发送成功 ]
+ 3? P[第 1,2,3 次发送出错 ]? P[第 4 次发送成功 ] +…}
= p(1 – p) + 2p2(1 – p) + 3p3(1 – p) + …
这里 P[X] 是出现事件 X 的概率。
课件制作人：谢希仁简单的数学分析（续）
得出正确传送一个数据帧所需的平均时间：
当传输差错率增大时,tav也随之增大。当无差错时,p = 0,tav = tT。
)1(/)1(
1
pttipptt
i
TT
i
Tav
(3-5)
课件制作人：谢希仁简单的数学分析（续）
每秒成功发送的最大帧数就是链路的最大吞吐量?max。显然，
max = 1/tav = (1? p) / tT (3-6)
在发送端，设数据帧的实际到达率为?，则?不应超过最大吞吐量?max，即
(1? p) / tT (3-7)
用时间 tf 进行归一化，得出归一化的吞吐量? 为
tf? (1? p) /? < 1 (3-8)
其中参数? 是 tT 的归一化时间：
tT / tf? 1 (3-9)
当重传时间远小于发送时间时, 1，此时的归一化吞吐量
1? p (3-10)
课件制作人：谢希仁停止等待协议 ARQ 的优缺点
优点,比较简单 。
缺点：通信信道的利用率不高，也就是说，信道还远远没有被数据比特填满。
为了克服这一缺点，就产生了另外两种协议，
即连续 ARQ 和选择重传 ARQ。这将在后面进一步讨论。
课件制作人：谢希仁
3.3连续 ARQ 协议
3.3.1 连续 ARQ 协议的工作原理
在发送完一个数据帧后，不是停下来等待确认帧，而是可以连续再发送若干个数据帧。
如果这时收到了接收端发来的确认帧，那么还可以接着发送数据帧。
由于减少了等待时间，整个通信的吞吐量就提高了。
课件制作人：谢希仁连续 ARQ 协议的工作原理
ACK1 确认 DATA0
ACK2 确认 DATA1
DATA2 出错,丢弃
DATA3 不按序,丢弃,重传 ACK2
DATA4 不按序,丢弃,重传 ACK2
DATA5 不按序,丢弃,重传 ACK2
ACK3 确认 DATA2
ACK4 确认 DATA3
超时重传时间
A B
tout
送交主机送交主机
…
课件制作人：谢希仁需要注意：
(1) 接收端 只按序接收 数据帧。虽然在有差错的 2号帧之后接着又收到了正确的 3 个数据帧，但接收端都必须将这些帧丢弃，因为在这些帧前面有一个 2 号帧还没有收到。虽然丢弃了这些不按序的无差错帧，但应重复发送已发送过的最后一个确认帧（防止确认帧丢失）。
(2) ACK1 表示确认 0 号帧 DATA0，并期望下次收到 1
号帧； ACK2 表示确认 1 号帧 DATA1，并期望下次收到 2 号帧。依此类推。
课件制作人：谢希仁需要注意：
(3) 结点 A 在每发送完一个数据帧时都要设置该帧的 超时计时器 。如果在所设置的超时时间内收到确认帧，就立即将超时计时器清零。但若在所设置的超时时间到了而未收到确认帧，就要重传相应的数据帧（仍需重新设置超时计时器）。
在等不到 2 号帧的确认而重传 2 号数据帧时，虽然结点 A 已经发完了 5 号帧，但仍必须向回走，将 2
号帧及其以后的各帧全部进行重传。连续 ARQ 又称为
Go-back-N ARQ，意思是当出现差错必须重传时，要向回走 N 个帧，然后再开始重传。
课件制作人：谢希仁需要注意：
(4) 以上讲述的仅仅是连续 ARQ 协议的工作原理。协议在具体实现时还有许多的细节。例如，用一个计时器就可实现相当于 N 个独立的超时计时器的功能。
课件制作人：谢希仁
3.3.2 连续 ARQ 协议的吞吐量
可以很方便地导出连续 ARQ 协议的吞吐量公式。
课件制作人：谢希仁
3.3.3 滑动窗口的概念
发送端和接收端分别设定发送窗口和接收窗口 。
发送窗口用来对发送端进行流量控制。
发送窗口的大小 WT 代表在还没有收到对方确认信息的情况下发送端最多可以发送多少个数据帧。
0 1 2 3 4 5 6 7 0 1 2
发送窗口
WT
不允许发送这些帧允许发送 5 个帧
(a)
0 1 2 3 4 5 6 7 0 1 2
不允许发送这些帧还允许发送 4 个帧
WT
已发送
(b)
0 1 2 3 4 5 6 7 0 1 2
不允许发送这些帧
WT
已发送
(c)
0 1 2 3 4 5 6 7 0 1 2
不允许发送这些帧还允许发送
3 个帧
WT
已发送已发送并已收到确认
(d)
课件制作人：谢希仁接收端设置接收窗口
在接收端只有当收到的数据帧的发送序号落入接收窗口内才允许将该数据帧收下。
若接收到的数据帧落在接收窗口之外，则一律将其丢弃。
在连续 ARQ 协议中，接收窗口的大小 WR = 1。
只有当收到的帧的序号与接收窗口一致时才能接收该帧。
否则，就丢弃它。
每收到一个序号正确的帧，接收窗口就向前（即向右方）
滑动一个帧的位置。同时发送对该帧的确认。
不允许接收这些帧
0 1 2 3 4 5 6 7 0 1 2
WR
准备接收 0 号帧
(a)
不允许接收这些帧
0 1 2 3 4 5 6 7 0 1 2
WR
准备接收
1 号帧已收到
(b)
不允许接收这些帧
0 1 2 3 4 5 6 7 0 1 2
WR
准备接收 4 号帧已收到
(c)
课件制作人：谢希仁滑动窗口的重要特性
只有在接收窗口向前滑动时（与此同时也发送了确认），发送窗口才有可能向前滑动。
收发两端的窗口按照以上规律不断地向前滑动，因此这种协议又称为滑动窗口协议。
当发送窗口和接收窗口的大小都等于 1
时，就是停止等待协议。
课件制作人：谢希仁发送窗口的最大值
当用 n 个比特进行编号时，若接收窗口的大小为 1，则只有在发送窗口的大小
WT? 2n? 1时，连续 ARQ 协议才能正确运行。
例如，当采用 3 bit 编码时，发送窗口的最大值是 7 而不是 8。
课件制作人：谢希仁
3.3.4 信道利用率
由于每个数据帧都必须包括一定的控制信息 (如帧的序号、地址、同步信息以及其他的一些控制信息 )，所以即使连续不停地发送数据帧，信道利用率 (即扣除全部的控制信息后的数据率与信道容量之比 )也不可能达到 100 %。
当出现差错时 (这是不可避免的 )，数据帧的不断重传将进一步使信道利用率降低。
课件制作人：谢希仁最佳帧长
若数据帧的帧长取得很短，那么控制信息在每一帧中所占的比例就增大，因而额外开销增大，这就导致信道利用率的下降。
若帧长取得太长，则数据帧在传输过程中出错的概率就增大，于是重传次数将增大，这也会使信道利用率下降。
由此可见，存在一个 最佳帧长,在此帧长下信道的利用率最高。
课件制作人：谢希仁
3.4 选择重传 ARQ 协议
可加大接收窗口，先收下发送序号不连续但仍处在接收窗口中的那些数据帧。等到所缺序号的数据帧收到后再一并送交主机。
选择重传 ARQ 协议可避免重复传送那些本来已经正确到达接收端的数据帧。
但我们付出的代价是在接收端要设置具有相当容量的缓存空间。
对于选择重传 ARQ 协议，若用 n 比特进行编号，则接收窗口的最大值受下式的约束
WR? 2n/2 (3-18)
课件制作人：谢希仁
3.5 面向比特的链路控制规程 HDLC
3.5.1 HDLC 协议概述
1974年,IBM 公司推出了面向比特的规程
SDLC (Synchronous Data Link Control)。
后来 ISO 把 SDLC 修改后称为 HDLC (High-
level Data Link Control)，译为高级数据链路控制，作为国际标准 ISO 3309。
CCITT 则将 HDLC 再修改后称为链路接入规程 LAP (Link Access Procedure)。不久，
HDLC 的新版本又把 LAP 修改为 LAPB，,B”
表示平衡型 (Balanced)，所以 LAPB 叫做链路接入规程 (平衡型 )。
课件制作人：谢希仁
3.5.2 HDLC 的帧结构
标志字段 F (Flag) 为 6 个连续 1 加上两边各一个 0 共 8 bit。在接收端只要找到标志字段就可确定一个帧的位置。
比特 8 8 8 可变 16 8
信息
Info
标志
F
标志
F
地址
A
控制
C
帧检验序列
FCS
透明传输区间
FCS 检验区间课件制作人：谢希仁零比特填充法
HDLC 采用零比特填充法使一帧中两个
F 字段之间不会出现 6 个连续 1。
在发送端，当一串比特流数据中有 5 个连续 1 时，就立即填入一个 0。
在接收帧时，先找到 F 字段以确定帧的边界。接着再对比特流进行扫描。每当发现 5 个连续 1 时，就将其后的一个 0
删除，以还原成原来的比特流。
课件制作人：谢希仁零比特的填充与删除数据中某一段比特组合恰好出现和 F 字段一样的情况
0 1 0 0 1 1 1 1 1 1 0 0 0 1 0 1 0
会被误认为是 F 字段发送端在 5 个连 1 之后填入 0 比特再发送出去填入 0 比特
0 1 0 0 1 1 1 1 1 0 1 0 0 0 1 0 1 0
在接收端将 5 个连 1 之后的 0 比特删除，恢复原样在此位置删除填入的 0 比特
0 1 0 0 1 1 1 1 1 0 1 0 0 0 1 0 1 0
课件制作人：谢希仁透明传输
采用零比特填充法就可传送任意组合的比特流，或者说，就可实现数据链路层的 透明传输 。
当连续传输两个帧时，前一个帧的结束标志字段 F 可以兼作后一帧的起始标志字段。
当暂时没有信息传送时，可以连续发送标志字段，使收端可以一直和发端保持同步。
课件制作人：谢希仁其他字段
地址字段 A 是 8 bit。
帧检验序列 FCS 字段共 16 bit。所检验的范围是从地址字段的第一个比特起，
到信息字段的最末一个比特为止。
控制字段 C 共 8 bit，是最复杂的字段。
HDLC 的许多重要功能都靠控制字段来实现。
课件制作人：谢希仁
3.6 因特网的点对点协议 PPP
3.6.1 PPP 协议的工作原理
现在全世界使用得最多的数据链路层协议是 点对点协议 PPP (Point-to-Point
Protocol)。
用户使用拨号电话线接入因特网时，一般都是使用 PPP 协议。
课件制作人：谢希仁用户拨号入网的示意图路由器调制解调器调制解调器因特网服务提供者 (ISP)用户家庭拨号电话线使用 TCP/IP 的
PPP 连接使用 TCP/IP 的客户进程路由选择进程至因特网…
PC 机课件制作人：谢希仁
PPP 协议
1992 年制订了 PPP 协议。经过 1993 年和 1994 年的修订，现在的 PPP 协议已成为因特网的正式标准 [RFC 1661]。
PPP协议有三个组成部分
一个将 IP 数据报封装到串行链路的方法。
链路控制协议 LCP (Link Control Protocol)。
网络控制协议 NCP (Network Control
Protocol)。
课件制作人：谢希仁
3.6.2 PPP 协议的帧格式
PPP 的帧格式和 HDLC 的相似。
标志字段 F仍为 0x7E （符号,0x”表示后面的字符是用十六进制表示。十六进制的 7E的二进制表示是 01111110）。
地址字段 A 只置为 0xFF。地址字段实际上并不起作用。
控制字段 C通常置为 0x03。
PPP 是面向字节的，所有的 PPP 帧的长度都是整数字节。
课件制作人：谢希仁
PPP 协议的帧格式
PPP 有一个 2 个字节的协议字段。
当协议字段为 0x0021 时,PPP 帧的信息字段就是
IP 数据报。
若为 0xC021,则信息字段是 PPP 链路控制数据。
若为 0x8021，则表示这是网络控制数据。
IP 数据报
1 21 1字节 1 2不超过 1500 字节
PPP 帧先发送
7E FF 03
F A C FCS F
7E协议 信 息 部 分首部 尾部课件制作人：谢希仁透明传输问题
当 PPP 用在同步传输链路时，协议规定采用硬件来完成比特填充（和 HDLC 的做法一样）。
当 PPP 用在异步传输时，就使用一种特殊的 字符填充法 。
课件制作人：谢希仁字符填充法
将信息字段中出现的每一个 0x7E 字节转变成为 2 字节序列 (0x7D,0x5E)。
若信息字段中出现一个 0x7D 的字节,则将其转变成为 2 字节序列 (0x7D,0x5D)。
若信息字段中出现 ASCII 码的控制字符
（即数值小于 0x20 的字符），则在该字符前面要加入一个 0x7D 字节，同时将该字符的编码加以改变。
课件制作人：谢希仁不提供使用序号和确认的可靠传输
PPP 协议之所以不使用序号和确认机制是出于以下的考虑：
在数据链路层出现差错的概率不大时，使用比较简单的 PPP 协议较为合理。
在因特网环境下,PPP 的信息字段放入的数据是 IP 数据报。 数据链路层的可靠传输并不能够保证网络层的传输也是可靠的。
帧检验序列 FCS 字段可保证无差错接受。
课件制作人：谢希仁
3.6.3 PPP 协议的工作状态
当用户拨号接入 ISP 时，路由器的调制解调器对拨号做出确认，并建立一条物理连接。
PC 机向路由器发送一系列的 LCP 分组（封装成多个 PPP 帧）。
这些分组及其响应选择一些 PPP 参数，和进行网络层配置,NCP 给新接入的 PC机分配一个临时的 IP 地址，使 PC 机成为因特网上的一个主机。
通信完毕时,NCP 释放网络层连接，收回原来分配出去的 IP 地址。接着,LCP 释放数据链路层连接。最后释放的是物理层的连接。
课件制作人：谢希仁
PPP 协议的状态图建立失败失败
NCP 配置鉴别成功通信结束载波停止检测到载波双方协商一些选项鉴别网络打开终止静止
