第四章 数据链路层本章将介绍：
数据链路层的基本概念；
两个重要的数据链路层流量控制方法：停止等待协议和连续 ARQ协议；
差错控制方法：循环冗余校验；
连续 ARQ协议的实现机制：滑动窗口机制；
数据链路层的具体协议,BSC,HDLC,PPP
4.1数据链路层的基本概念
区分,链路,和,数据链路,的概念。
链路 是一条无源的点到点的物理线路段，中间没有任何其他交换结节，又称 物理链路 。
数据链路 是除了有一条物理线路外，还施加了一些必要的通信协议来控制数据的传输。又称 逻辑链路 。
数据链路层的作用：
在数据链路层协议的控制下，在不太可靠的物理链路上 实现相邻结点之间的可靠传输 。
时期链路层的主要功能,
1、链路管理当网络中的两个相邻结点要进行通信时，发送方必须知道接收方是否已经准备就绪。为此，通信双方必须先要交换一些必要的信息，
建立一条数据链路，在传输数据时要维持数据链路，传完后要释放数据链路。
帧同步在数据链路层，数据的传送单位是帧，数据一帧一帧地传送，帧同步是指接收方应当能从接收到的比特流中区分出一帧的开始和结束，不至错位。通过在帧的开始和结束处加帧标志来实现。
3、流量控制发送方发送数据的速率必须使接收方来得及接收。因此必须控制发送方的速率。
4、差错控制差错控制广泛采用了编码技术，通过在帧中添加一定的校验位（冗余位）来实现。编码技术有两大类：
(1)前向纠错,接收方收到出错的帧后，能自动将其改正过来，但这种方法开销大，编码复杂，在计算机通信中很少采用。如海明码,
(2)差错检测,一般是接收方检测到出错的帧后，
将其丢弃，然后通知发送方重发。如循环冗余码,
5、将数据和控制信息区分开数据和控制信息封装在同一帧中，要有一定的措施使接收方能够区分开来。可通过规定帧的格式来实现。
6、透明传输透明传输指不管所传数据是什么样的比特组合，
都能实现正确传输。如当所传数据中出现“帧标志”比特组合时，不能将其误认为是帧标志，
而要当成数据，为此，必须采取一定的控制措施。7、寻址帧中必须封装有接收方的物理地址（ MAC地址）。
4.2停止等待协议
停止等待协议是最简单但也是最基本的数据链路层协议。
4.2.1 不需要数据链路层协议的数据传输两台计算机通过一条数据链路进行通信的简化模型如下：
当同时满足以下 两个条件 时，不需要数据链路层协议：
(1)链路是理想的传输信道,不会出错 。
(2)不管发送方以多快的速率发送，接收方都 来得及收下,
并及时上交主机。
当接收方缓存的容量无限大且发送方的速率永远低于接收方的接收速率时才可能。
4.2.2 具有最简单流量控制的数据链路层协议保留上述的第一个假设，去掉第二个假设。
为了使接收方的缓存在任何情况下都不会溢出，最简单的方法是发送方每发送一帧就暂停，接收方收到并处理完后通知发送方，发送方才发下一帧。
这种由接收方控制发送方的发送速率是计算机网络中流量控制的基本方法。
具有最简单流量控制的数据链路层协议算法如下：
发送方：
(1)从主机取一个数据帧；
(2)将数据帧送到数据链路层的发送缓存；
(3)将发送缓存中的数据帧发送出去；
(4)等待；
(5)若收到接收方发来的通知，则从主机取一个新的数据帧，然后转到（ 2）。
接收方：
(1)等待；
(2)若收到发送方发来的数据帧，将其送入数据链层的接收缓存；
(3)将接收缓存中的数据帧上交主机；
(4)向发送结点发送通知，表示已上交主机；
(5) 转到（ 1）。
两种数据传输情况对比图见书 P73 图 4-2
4.2.3实用的停止等待协议
现在去掉前面的两个假定，讨论实用的数据链路层协议。设主机 A 主机 B，分以下几种情况讨论：
(1)B正确收到，向 A发送一个确认帧 ACK；
(2)B检测出帧在传输过程中出错，向 A发送一个否认帧 NAK，通知 A重传出错的帧。
(3)A发送的数据帧在传输过程中丢失，或 B发送的确帧在传输过程中丢失。会出现什么情况？
方法是给每一帧编号,编号应既能识别出重复帧，
又要尽可能短。如何编号最好？
编号占用一个比特位,0和 1交替编号 即可，为什么？
发送方“死等”。
解决方法是,A每发送一个数据帧，就启动一个 超时计时器,在规定的时间内未收到 B的任何应答，应重传该帧，重传时间不能设置过短或过长。
(4) 如果是 B发送的确认帧在传输过程中丢失，
则超时重传会使 B收到两个同样的数据帧，此时应丢弃，但主机 B如何识别出一个数据帧是否为 重复帧？
4.2.4循环冗余检验（ CRC）
用来检测帧在传输过程中有没有出错。
CRC的工作方法：
在发送端产生一个循环冗余码，附加在信息位后面一起发送到接收端，接收端收到的信息按发送端形成循环冗余码同样的算法进行校验，若有错，
需重发。
CRC将数据块看成是一个多项式系数系列。
如数据块,110011 对应的多项式,M(X)=X5+X4+X+1
双方约定一个生成多项式,如 P(X)=X4+X3+1，其系数系列为,11001
利用两个多项式相除,余数作为校验位，除法过程中所有的减法按 模二算法 （即异或运算）。
例：数据块 M(X)为 1010001101,
生成多项式 P(X)=X5+X4+X2+1，即 110101，
求 CRC
CRC的计算过程如下：
(1)设约定多项式 P(x)为 n阶，在数据块 M(X)的未尾添加 n个 0，得到 Xn M(X)。
(2)用 Xn M(X)/ P(X)，得到余数 R(X)。
(3)用 Xn M(X)+ R(X)，得 CRC码。
1 1 0 1 0 1 0 1 1 0←Q 商
110101) 1 0 1 0 0 0 1 1 0 1 0 0 0 0 0←X nM
1 1 0 1 0 1
1 1 1 0 1 1
1 1 0 1 0 1
1 1 1 0 1 0
1 1 0 1 0 1
1 1 1 1 1 0
1 1 0 1 0 1
1 0 1 1 0 0
1 1 0 1 0 1
1 1 0 0 1 0
1 1 0 1 0 1
0 1 1 1 0 ←R 余数
CRC码为 1 0 1 0 0 0 1 1 0 1 0 1 1 1 0
接收方的处理过程：
接收方用收到的信息，除以生成多项式，若除数为 0，则传输中没有出错，否则，出错。
现在国际上有一些标准的约定生成多项式。
停止等待协议的算法如下：
发送方：
(1)从主机取一个数据帧；
(2)V(S) 0； {发送状态变量初始化 }
(3)N(S) V(S); {将发送状态变量的数值写入发送序号 }并将数据帧送交发送缓存；
(4)将发送缓存中的数据帧发送出去；
(5)设置超时计时器
(6)等待以下三个事件中最先出现的一个；
(7)若收到确认帧 ACK，则：
从主机取一个新的数据帧；
V(S) [1- V(S)]； {更新发送状态变量，变为下一个序号 }
转到（ 3），发送下一帧。
(8)若收到否认帧 NCK，则转到（ 4），重传数据帧。
(9)若超时计时器时间到，则转到（ 4），重传数据帧。
接收方：
(1)V(R) 0;{接收状态变量初始化，为欲接收的序号 }
(2)等待；
(3)当收到一个数据帧，检查有无传输差错 (如用 CRC)，
若检查正确，则执行后续算法，否则转到 (8)。
(4)若 N(S)=V(R)，则执行后续算法； (序号正确 )
否则丢弃此数据帧，然后转到 (7) {为重复帧，发 ACK}
(5)将接收缓存中数据帧的数据部分上交主机；
(6) V(R) [1- V(R)],{更新状态变量，准备接收下一帧 }
(7)发送确认帧，并转到 (2)；
(8)发送否认帧，并转到 (2) 。
Tp为传播时延,tf为发送时间,tpr为处理时间,ta为
ACK的发送时间,tout为重传时间。
当 tpr和 ta都远小于 Tp时,tout =2Tp
停止等待协议 ARQ的优点是简单，但效率低。
tT
tf tout
tp tprta tp tpr
4.2.6停止等待协议中几个重要的时间关系
4.3.1连续 ARQ的工作原理
连续 ARQ不是每发一帧就停下来等待确认，而是可以连续发送若干个帧后，才等待确认。
在连续发送的若干个帧中，如果某一帧出错，
则其后发送的帧全部丢弃，从出错帧开始重发。
4.3连续 ARQ协议
4.3.2滑动窗口的概念
连续 ARQ中连续发送帧的数量不能太大，因为：
(1)出错是重传的帧数较多。
(2)给帧进行编号时，序号要占较多的比特位，
增大了开销。
如何控制发送方的发送和接收方的接收？
发送窗口 (WT),在还没有收到对方确认信息的情况下发送端最多可以发送多少个数据帧。
用来对发送端进行流量控制。停止等待协议中发送窗口的大小为 1。
设发送序号用 3个比特来编码，即发送序号可以从 0-7，又假定发送窗口 WT=5，发送窗口的规则如下：
(1)发送窗口内是允许发送的帧，而不考虑有没有收到确认。右侧是不允许发送的帧。
0 1 2 3 4 5 6 7 0 1 2
WT
允许发送 5个帧 不允许发送的帧
(2)每发送完一帧，允许发送的帧数就减 1，但发送窗口的位置不变。如已发送了 0号帧。
0 1 2 3 4 5 6 7 0 1 2
WT
还允许发送 4个帧不允许发送的帧已发送
(3)如果允许发送的 5个帧都发送完了，但还没有收到任何确认，就不能再发送了，进入等待状态。
0 1 2 3 4 5 6 7 0 1 2
WT
已发送 不允许发送的帧
(4)每收到对一个帧的确认，发送窗口就向前滑动一个位置，如发送方已收到 0,1和 2号帧的确认。
0 1 2 3 4 5 6 7 0 1 2
WT
已发送并已收到确认 不允许发送的帧已发送还允许发送 3帧为了减少开销，接收端可以在连续收到好几个帧后，才对最后一个数据帧发确认信息，或自己有数据要发送时才对以前收到的数据帧加以 捎带确认 。
对 某一数据帧的确认表示该帧及以前所有的数据帧均已正确收到 。如上例中接收端可以只发对 2号帧的确认，
表示 2号及 0,1号均已正确收到。减少开销。
接收窗口 (WR),接收端允许接收的帧的序号。
WR=1，接收窗口的规则如下：
(1)只有当收到的数据帧的发送序号落在接收窗口内才允许接收，否则，丢弃。
(2)每收到一个序号正确的帧，接收窗口就向前滑动一个帧的位置。同时可以向发送端发送对该帧的确认。
0 1 2 3 4 5 6 7 0 1 2
WR
准备接收
0号帧不允许接收这些帧
0 1 2 3 4 5 6 7 0 1 2
WR
准备接收 1
号帧不允许接收这些帧已收到
发送窗口的最大值,当采用 3个比特来编号时，
可以编出 8个不同的序号，发送窗口的最大值是不应为 8？
不能为 8！
如果发送窗口 WT=8，设发送方已发送完 0-7号共
8个帧。因发送窗口已满，发送暂停，等待确认。
假定这 8个帧已正确到达接收端，并且接收端已对这 8帧发回确认帧。下面考虑两种不同情况：
第一种情况是：确认帧正确到达了接收端，发送方又发送 0-7号共 8个新帧。
第二种情况是：确认帧丢失，接收端超时后重传这先前发送的 8个旧帧。
接收端第二次收到编号为 0-7的 8个帧时，无法判定是 8个新帧，还是重传的 8个旧帧。因为它不知道上次的确认帧是不已丢失。
当用 n个比特编号时,WT ≤2n-1
4.3.3信道利用率与最佳帧长
信道的利用率 指扣除控制信息后的数据率与信道容量之比。还受出错重传影响，不可能达到
100%，当信道不出错时，其值为数据位 /帧长。
最佳帧长
（ 1）当 帧长 取得 很短 时，控制信息所占的比重增大，开销增大，信道利用率降低。
（ 2）当 帧长 取得 很长 时，帧在传输过程中出错的概率增大，重传次数增大，也会使信道利用率降低。
数据 帧长的选择 与 信道的好坏 有很大的关系。
当信道质量好时，帧长应该长还是短？
当信道质量不好时，帧长应该长还是短？
4.4选择重传 ARQ协议
为进一步 提高信道利用率,可只重传出错帧或超时帧。必须做到：
（ 1） 加大接收窗口,以便先收下发送序号不连续但仍处在接收窗口中的帧。
（ 2）接收端要设置 相当容量的缓存空间,这样不够经济。所以目前应用较少，但目前随着存储器价格的下降，受到更多的重视。
接收窗口的最大值受下式约束：
WR≤ 2n/2
因 WT +WR≤ 2n
4.5面向比特的链路控制规程 HDLC
4.5.1HDLC概述
数据链路控制规程分两大类：
（ 1） 面向字符 的数据链路控制规程典型代表有 IBM的 BSC二进制同步通信规程。
特点：①所传数据及控制信息都必须是规定字符集
（如 ASCII码）中的字符,且控制字符很多。
②采用停止等待协议，效率低。
（ 2） 面向比特 的数据链路控制规程典型代表有 ISO的 HDLC高级数据链路控制规程。
特点,①所传数据可以是任意的比特流。
②采用连续 ARQ，效率高。
CCITT将 HDLC修改后称为链路接入规程 LAP，
并作为 X.25的数据链路层协议，不久后又将
LAP改为 LAPB平衡型链路接入规程。
HDLC可适用于链路的两种基本配置，即平衡配置与非平衡配置。
非平衡配置的特点 是站有主站和从站之分，由一个主站控制整个链路的工作，只有主站才能发起向次站的数据传输，而次站只有在主站对它进行轮询时，才能以响应帧的形式回答主站。
平衡配置的特点 是站是复合站，同时具有主站和从站的功能，能平等地发起数据传输。
4.5.2 HDLC的帧结构标志
F
地址
A
控制
C
信息
Info
帧检验序列
FCS
标志
F
HDLC的帧结构比特,8 8 8 可变 16 8
检验区间透明传输区间
1、各字段的意义
1、标志位 F
作用：用来 标识帧的开头和结尾 。
标志位 F为,01111110
透明性处理：
当两个标志位之间碰巧出现了和标志位 F一样的比特组合时，接收方会误认为帧结束了。
为了避免出现这种错误,HDLC采用零比特填充法。
发送方在数据 连续 5个 1之后自动插入一个 0，
这样数据中就不会出现 6个连续 1。
接收方在数据连续 5个 1之后自动去 0。
例如：
要发送的数据为,01001111110001010
实际发送的数据为,010011111010001010
接收方去 0,01001111110001010
采用零比特填充法就可传送任意的比特流。
2、地址字段 A
在平衡方式时，填入接收方的地址。 全 1为广播方式,全 0为无效地址，因此，有效地址为 254个。
当用户数很多时，可用地址字段的第一个比特表示扩展比特，当该位为 1时，表示后面还有地址字段，当为 0时，表示这已是最后一个地址字段了。
3、帧检验序列 FCS
为 CRC的校验码。
4、控制字段 C
长 8位，根据前两位的取值，将 HDLC帧分为三大类,信息帧 I、监督帧 S和无编号帧 U。
控制字段的结构如下：
比特序号 1 2 3 4 5 6 7 8
信息帧 I 0 N(S) P/F N(R)
监督帧 S 1 0 S P/F N(R)
无编号帧 U 1 1 M P/F N(R)
2、信息帧
第一位为 0，表示该帧为信息帧。
第 2~4位 N(S)为当前 发送的信息帧的序号
第 6~8位 N(R)为 接收序号,即接收方期望收到的帧的序号。 N(R) 带有确认的意思，它表示序号为 [N(R)-1](mod 8)的帧以及在这之前的各帧都已正确收到。如 N(R) 为 4，意思是？
通信的每一方都有一个 N(S)和 N(R)。
在全双工通信中，收发双方还设置了两个 状态变量 V(S)和 V(R)，由这两个状态变量的值确定发送序号 N(S)和接收序号 N(R) 的值。
每从主机取一帧新的数据就要将 V(S)和 V(R)
的值分别写入帧的控制字段 N(S)和 N(R) 中。
每发完一帧 V(S)+1(mod 8)。
当出错重传时，只需从缓存队列中取出已发送过的旧帧，重新发送,帧中的序号 N(S)仍为原序号； V(S)不变；
每收到一个无差错的信息帧 V(R)+1(mod 8)。
当出错重传时,N(R) 必须与 V (R)的当前值一致 。
信息帧中设置 N(R) 的目的是不必专门为收到的信息帧发送确认帧，可以在本站有信息发送时，将确认信息 捎带 走。提高信道利用率。
控制字段的第 5个比特是探询 /终止比特，即
P/F。主站发出的命令帧中若将 P置为 1表示要求对方立即响应。在平衡链路中若将 F置 1，
表示数据发送完毕。
3、监督帧 S
第 1~2比特为 10。监督帧共有四种，取决于
3~4比特的值。
第 3~4比特 帧名 功能
00 RR
接收准备就绪准备接收下一帧确认序号为 N(R)-1及以前的各帧
10 RNR
接收未就绪暂停接收下一帧确认序号为 N(R)-1及以前的各帧
01 REJ
拒绝从 N(R) 起的所有帧都被否认，但确认序号为 N(R)-1
及以前的各帧
11 SREJ
选择拒绝只否认序号为 N(R)的帧，
但确认序号为 N(R)-1及以前的各帧，较少用。
监督帧不包含数据，不需要发送序号 N(S)。
RR和 RNR还具有流量控制作用。
4、无编号帧 U
第 1~2比特为 11，无编号帧不带 V(S)和 V(R)字段,而用 5位，即 3,4,6,7,8来表示不同功能的无编号帧，无编号帧主要起控制作用。
如要与对方建立连接，可发 SABM（请求发送）帧，对方同意发 UA确认帧，断开连接发 DISC帧。
4.6因特网的点对点协议 PPP
用户拨号上网的示意图
用户拨通 ISP的号码 (如 163或 169),用户机中的 TCP/IP客户进程 就和 ISP的路由器中的 路由选择进程 建立了一个 PPP连接； ISP识别用户名和口令后,用户获得一个临时的 IP地址,
当用户结束通信时,该 IP地址被回收。
PPP协议由如下三个部分组成：
（ 1）一个将 IP数据报封装 到串行链路的方法。
IP数据报在 PPP帧中是其数据部分。
（ 2）一个建立、配置和测试数据链路连接的链路控制协议 LCP。双方可协商一些选项。
（ 3）网络控制协议 NCP。
PPP帧的格式标志
F
(7E)
地址
A
(FF)
控制
C
(03)
协议信息
(IP数据报 )
帧检验序列
FCS
标志
F
(7E)
字节,1 1 1 2 ≤ 1500字节 2 1
1、与 HDLC比较,PPP的特点：
（ 1）地址为固定值，控制字段与 U帧相同，
帧不使用编号，增加了一个协议字段，表示上层使用的协议，如 IP，则为 0x0021。
2,PPP是 面向字符 的协议。
3、透明性处理方法：在同步传输链路中采用位填充（与 HDLC相同），在异步传输链路中采用 字符填充,将 (0x7E)转换成
(0x7D,0x5E)。
4,PPP不提供可靠的传输服务 。当 CRC检验出帧出错时，只简单丢弃，其可靠性由高层来负责。目的是为了提高效率。
PPP建立连接过程：
（ 1）拨号，建立起物理连接。
（ 2） PC机向路由器发 LCP（封装成 PPP帧），
协商 PPP参数，如最大帧长，并鉴别用户身份。建立起数据链路层的连接。
（ 3）接着进行网络层配置，由 NCP给 PC机分配一个临时的 IP地址。
PPP释放连接的过程则正好相反。
使用 PPP协议的状态图 见书 P92，图 4-14
复习
作业
P93 12,16,17
数据链路层的基本概念；
两个重要的数据链路层流量控制方法：停止等待协议和连续 ARQ协议；
差错控制方法：循环冗余校验；
连续 ARQ协议的实现机制：滑动窗口机制；
数据链路层的具体协议,BSC,HDLC,PPP
4.1数据链路层的基本概念
区分,链路,和,数据链路,的概念。
链路 是一条无源的点到点的物理线路段，中间没有任何其他交换结节，又称 物理链路 。
数据链路 是除了有一条物理线路外，还施加了一些必要的通信协议来控制数据的传输。又称 逻辑链路 。
数据链路层的作用：
在数据链路层协议的控制下，在不太可靠的物理链路上 实现相邻结点之间的可靠传输 。
时期链路层的主要功能,
1、链路管理当网络中的两个相邻结点要进行通信时，发送方必须知道接收方是否已经准备就绪。为此，通信双方必须先要交换一些必要的信息，
建立一条数据链路，在传输数据时要维持数据链路，传完后要释放数据链路。
帧同步在数据链路层，数据的传送单位是帧，数据一帧一帧地传送，帧同步是指接收方应当能从接收到的比特流中区分出一帧的开始和结束，不至错位。通过在帧的开始和结束处加帧标志来实现。
3、流量控制发送方发送数据的速率必须使接收方来得及接收。因此必须控制发送方的速率。
4、差错控制差错控制广泛采用了编码技术，通过在帧中添加一定的校验位（冗余位）来实现。编码技术有两大类：
(1)前向纠错,接收方收到出错的帧后，能自动将其改正过来，但这种方法开销大，编码复杂，在计算机通信中很少采用。如海明码,
(2)差错检测,一般是接收方检测到出错的帧后，
将其丢弃，然后通知发送方重发。如循环冗余码,
5、将数据和控制信息区分开数据和控制信息封装在同一帧中，要有一定的措施使接收方能够区分开来。可通过规定帧的格式来实现。
6、透明传输透明传输指不管所传数据是什么样的比特组合，
都能实现正确传输。如当所传数据中出现“帧标志”比特组合时，不能将其误认为是帧标志，
而要当成数据，为此，必须采取一定的控制措施。7、寻址帧中必须封装有接收方的物理地址（ MAC地址）。
4.2停止等待协议
停止等待协议是最简单但也是最基本的数据链路层协议。
4.2.1 不需要数据链路层协议的数据传输两台计算机通过一条数据链路进行通信的简化模型如下：
当同时满足以下 两个条件 时，不需要数据链路层协议：
(1)链路是理想的传输信道,不会出错 。
(2)不管发送方以多快的速率发送，接收方都 来得及收下,
并及时上交主机。
当接收方缓存的容量无限大且发送方的速率永远低于接收方的接收速率时才可能。
4.2.2 具有最简单流量控制的数据链路层协议保留上述的第一个假设，去掉第二个假设。
为了使接收方的缓存在任何情况下都不会溢出，最简单的方法是发送方每发送一帧就暂停，接收方收到并处理完后通知发送方，发送方才发下一帧。
这种由接收方控制发送方的发送速率是计算机网络中流量控制的基本方法。
具有最简单流量控制的数据链路层协议算法如下：
发送方：
(1)从主机取一个数据帧；
(2)将数据帧送到数据链路层的发送缓存；
(3)将发送缓存中的数据帧发送出去；
(4)等待；
(5)若收到接收方发来的通知，则从主机取一个新的数据帧，然后转到（ 2）。
接收方：
(1)等待；
(2)若收到发送方发来的数据帧，将其送入数据链层的接收缓存；
(3)将接收缓存中的数据帧上交主机；
(4)向发送结点发送通知，表示已上交主机；
(5) 转到（ 1）。
两种数据传输情况对比图见书 P73 图 4-2
4.2.3实用的停止等待协议
现在去掉前面的两个假定，讨论实用的数据链路层协议。设主机 A 主机 B，分以下几种情况讨论：
(1)B正确收到，向 A发送一个确认帧 ACK；
(2)B检测出帧在传输过程中出错，向 A发送一个否认帧 NAK，通知 A重传出错的帧。
(3)A发送的数据帧在传输过程中丢失，或 B发送的确帧在传输过程中丢失。会出现什么情况？
方法是给每一帧编号,编号应既能识别出重复帧，
又要尽可能短。如何编号最好？
编号占用一个比特位,0和 1交替编号 即可，为什么？
发送方“死等”。
解决方法是,A每发送一个数据帧，就启动一个 超时计时器,在规定的时间内未收到 B的任何应答，应重传该帧，重传时间不能设置过短或过长。
(4) 如果是 B发送的确认帧在传输过程中丢失，
则超时重传会使 B收到两个同样的数据帧，此时应丢弃，但主机 B如何识别出一个数据帧是否为 重复帧？
4.2.4循环冗余检验（ CRC）
用来检测帧在传输过程中有没有出错。
CRC的工作方法：
在发送端产生一个循环冗余码，附加在信息位后面一起发送到接收端，接收端收到的信息按发送端形成循环冗余码同样的算法进行校验，若有错，
需重发。
CRC将数据块看成是一个多项式系数系列。
如数据块,110011 对应的多项式,M(X)=X5+X4+X+1
双方约定一个生成多项式,如 P(X)=X4+X3+1，其系数系列为,11001
利用两个多项式相除,余数作为校验位，除法过程中所有的减法按 模二算法 （即异或运算）。
例：数据块 M(X)为 1010001101,
生成多项式 P(X)=X5+X4+X2+1，即 110101，
求 CRC
CRC的计算过程如下：
(1)设约定多项式 P(x)为 n阶，在数据块 M(X)的未尾添加 n个 0，得到 Xn M(X)。
(2)用 Xn M(X)/ P(X)，得到余数 R(X)。
(3)用 Xn M(X)+ R(X)，得 CRC码。
1 1 0 1 0 1 0 1 1 0←Q 商
110101) 1 0 1 0 0 0 1 1 0 1 0 0 0 0 0←X nM
1 1 0 1 0 1
1 1 1 0 1 1
1 1 0 1 0 1
1 1 1 0 1 0
1 1 0 1 0 1
1 1 1 1 1 0
1 1 0 1 0 1
1 0 1 1 0 0
1 1 0 1 0 1
1 1 0 0 1 0
1 1 0 1 0 1
0 1 1 1 0 ←R 余数
CRC码为 1 0 1 0 0 0 1 1 0 1 0 1 1 1 0
接收方的处理过程：
接收方用收到的信息，除以生成多项式，若除数为 0，则传输中没有出错，否则，出错。
现在国际上有一些标准的约定生成多项式。
停止等待协议的算法如下：
发送方：
(1)从主机取一个数据帧；
(2)V(S) 0； {发送状态变量初始化 }
(3)N(S) V(S); {将发送状态变量的数值写入发送序号 }并将数据帧送交发送缓存；
(4)将发送缓存中的数据帧发送出去；
(5)设置超时计时器
(6)等待以下三个事件中最先出现的一个；
(7)若收到确认帧 ACK，则：
从主机取一个新的数据帧；
V(S) [1- V(S)]； {更新发送状态变量，变为下一个序号 }
转到（ 3），发送下一帧。
(8)若收到否认帧 NCK，则转到（ 4），重传数据帧。
(9)若超时计时器时间到，则转到（ 4），重传数据帧。
接收方：
(1)V(R) 0;{接收状态变量初始化，为欲接收的序号 }
(2)等待；
(3)当收到一个数据帧，检查有无传输差错 (如用 CRC)，
若检查正确，则执行后续算法，否则转到 (8)。
(4)若 N(S)=V(R)，则执行后续算法； (序号正确 )
否则丢弃此数据帧，然后转到 (7) {为重复帧，发 ACK}
(5)将接收缓存中数据帧的数据部分上交主机；
(6) V(R) [1- V(R)],{更新状态变量，准备接收下一帧 }
(7)发送确认帧，并转到 (2)；
(8)发送否认帧，并转到 (2) 。
Tp为传播时延,tf为发送时间,tpr为处理时间,ta为
ACK的发送时间,tout为重传时间。
当 tpr和 ta都远小于 Tp时,tout =2Tp
停止等待协议 ARQ的优点是简单，但效率低。
tT
tf tout
tp tprta tp tpr
4.2.6停止等待协议中几个重要的时间关系
4.3.1连续 ARQ的工作原理
连续 ARQ不是每发一帧就停下来等待确认，而是可以连续发送若干个帧后，才等待确认。
在连续发送的若干个帧中，如果某一帧出错，
则其后发送的帧全部丢弃，从出错帧开始重发。
4.3连续 ARQ协议
4.3.2滑动窗口的概念
连续 ARQ中连续发送帧的数量不能太大，因为：
(1)出错是重传的帧数较多。
(2)给帧进行编号时，序号要占较多的比特位，
增大了开销。
如何控制发送方的发送和接收方的接收？
发送窗口 (WT),在还没有收到对方确认信息的情况下发送端最多可以发送多少个数据帧。
用来对发送端进行流量控制。停止等待协议中发送窗口的大小为 1。
设发送序号用 3个比特来编码，即发送序号可以从 0-7，又假定发送窗口 WT=5，发送窗口的规则如下：
(1)发送窗口内是允许发送的帧，而不考虑有没有收到确认。右侧是不允许发送的帧。
0 1 2 3 4 5 6 7 0 1 2
WT
允许发送 5个帧 不允许发送的帧
(2)每发送完一帧，允许发送的帧数就减 1，但发送窗口的位置不变。如已发送了 0号帧。
0 1 2 3 4 5 6 7 0 1 2
WT
还允许发送 4个帧不允许发送的帧已发送
(3)如果允许发送的 5个帧都发送完了，但还没有收到任何确认，就不能再发送了，进入等待状态。
0 1 2 3 4 5 6 7 0 1 2
WT
已发送 不允许发送的帧
(4)每收到对一个帧的确认，发送窗口就向前滑动一个位置，如发送方已收到 0,1和 2号帧的确认。
0 1 2 3 4 5 6 7 0 1 2
WT
已发送并已收到确认 不允许发送的帧已发送还允许发送 3帧为了减少开销，接收端可以在连续收到好几个帧后，才对最后一个数据帧发确认信息，或自己有数据要发送时才对以前收到的数据帧加以 捎带确认 。
对 某一数据帧的确认表示该帧及以前所有的数据帧均已正确收到 。如上例中接收端可以只发对 2号帧的确认，
表示 2号及 0,1号均已正确收到。减少开销。
接收窗口 (WR),接收端允许接收的帧的序号。
WR=1，接收窗口的规则如下：
(1)只有当收到的数据帧的发送序号落在接收窗口内才允许接收，否则，丢弃。
(2)每收到一个序号正确的帧，接收窗口就向前滑动一个帧的位置。同时可以向发送端发送对该帧的确认。
0 1 2 3 4 5 6 7 0 1 2
WR
准备接收
0号帧不允许接收这些帧
0 1 2 3 4 5 6 7 0 1 2
WR
准备接收 1
号帧不允许接收这些帧已收到
发送窗口的最大值,当采用 3个比特来编号时，
可以编出 8个不同的序号，发送窗口的最大值是不应为 8？
不能为 8！
如果发送窗口 WT=8，设发送方已发送完 0-7号共
8个帧。因发送窗口已满，发送暂停，等待确认。
假定这 8个帧已正确到达接收端，并且接收端已对这 8帧发回确认帧。下面考虑两种不同情况：
第一种情况是：确认帧正确到达了接收端，发送方又发送 0-7号共 8个新帧。
第二种情况是：确认帧丢失，接收端超时后重传这先前发送的 8个旧帧。
接收端第二次收到编号为 0-7的 8个帧时，无法判定是 8个新帧，还是重传的 8个旧帧。因为它不知道上次的确认帧是不已丢失。
当用 n个比特编号时,WT ≤2n-1
4.3.3信道利用率与最佳帧长
信道的利用率 指扣除控制信息后的数据率与信道容量之比。还受出错重传影响，不可能达到
100%，当信道不出错时，其值为数据位 /帧长。
最佳帧长
（ 1）当 帧长 取得 很短 时，控制信息所占的比重增大，开销增大，信道利用率降低。
（ 2）当 帧长 取得 很长 时，帧在传输过程中出错的概率增大，重传次数增大，也会使信道利用率降低。
数据 帧长的选择 与 信道的好坏 有很大的关系。
当信道质量好时，帧长应该长还是短？
当信道质量不好时，帧长应该长还是短？
4.4选择重传 ARQ协议
为进一步 提高信道利用率,可只重传出错帧或超时帧。必须做到：
（ 1） 加大接收窗口,以便先收下发送序号不连续但仍处在接收窗口中的帧。
（ 2）接收端要设置 相当容量的缓存空间,这样不够经济。所以目前应用较少，但目前随着存储器价格的下降，受到更多的重视。
接收窗口的最大值受下式约束：
WR≤ 2n/2
因 WT +WR≤ 2n
4.5面向比特的链路控制规程 HDLC
4.5.1HDLC概述
数据链路控制规程分两大类：
（ 1） 面向字符 的数据链路控制规程典型代表有 IBM的 BSC二进制同步通信规程。
特点：①所传数据及控制信息都必须是规定字符集
（如 ASCII码）中的字符,且控制字符很多。
②采用停止等待协议，效率低。
（ 2） 面向比特 的数据链路控制规程典型代表有 ISO的 HDLC高级数据链路控制规程。
特点,①所传数据可以是任意的比特流。
②采用连续 ARQ，效率高。
CCITT将 HDLC修改后称为链路接入规程 LAP，
并作为 X.25的数据链路层协议，不久后又将
LAP改为 LAPB平衡型链路接入规程。
HDLC可适用于链路的两种基本配置，即平衡配置与非平衡配置。
非平衡配置的特点 是站有主站和从站之分，由一个主站控制整个链路的工作，只有主站才能发起向次站的数据传输，而次站只有在主站对它进行轮询时，才能以响应帧的形式回答主站。
平衡配置的特点 是站是复合站，同时具有主站和从站的功能，能平等地发起数据传输。
4.5.2 HDLC的帧结构标志
F
地址
A
控制
C
信息
Info
帧检验序列
FCS
标志
F
HDLC的帧结构比特,8 8 8 可变 16 8
检验区间透明传输区间
1、各字段的意义
1、标志位 F
作用：用来 标识帧的开头和结尾 。
标志位 F为,01111110
透明性处理：
当两个标志位之间碰巧出现了和标志位 F一样的比特组合时，接收方会误认为帧结束了。
为了避免出现这种错误,HDLC采用零比特填充法。
发送方在数据 连续 5个 1之后自动插入一个 0，
这样数据中就不会出现 6个连续 1。
接收方在数据连续 5个 1之后自动去 0。
例如：
要发送的数据为,01001111110001010
实际发送的数据为,010011111010001010
接收方去 0,01001111110001010
采用零比特填充法就可传送任意的比特流。
2、地址字段 A
在平衡方式时，填入接收方的地址。 全 1为广播方式,全 0为无效地址，因此，有效地址为 254个。
当用户数很多时，可用地址字段的第一个比特表示扩展比特，当该位为 1时，表示后面还有地址字段，当为 0时，表示这已是最后一个地址字段了。
3、帧检验序列 FCS
为 CRC的校验码。
4、控制字段 C
长 8位，根据前两位的取值，将 HDLC帧分为三大类,信息帧 I、监督帧 S和无编号帧 U。
控制字段的结构如下：
比特序号 1 2 3 4 5 6 7 8
信息帧 I 0 N(S) P/F N(R)
监督帧 S 1 0 S P/F N(R)
无编号帧 U 1 1 M P/F N(R)
2、信息帧
第一位为 0，表示该帧为信息帧。
第 2~4位 N(S)为当前 发送的信息帧的序号
第 6~8位 N(R)为 接收序号,即接收方期望收到的帧的序号。 N(R) 带有确认的意思，它表示序号为 [N(R)-1](mod 8)的帧以及在这之前的各帧都已正确收到。如 N(R) 为 4，意思是？
通信的每一方都有一个 N(S)和 N(R)。
在全双工通信中，收发双方还设置了两个 状态变量 V(S)和 V(R)，由这两个状态变量的值确定发送序号 N(S)和接收序号 N(R) 的值。
每从主机取一帧新的数据就要将 V(S)和 V(R)
的值分别写入帧的控制字段 N(S)和 N(R) 中。
每发完一帧 V(S)+1(mod 8)。
当出错重传时，只需从缓存队列中取出已发送过的旧帧，重新发送,帧中的序号 N(S)仍为原序号； V(S)不变；
每收到一个无差错的信息帧 V(R)+1(mod 8)。
当出错重传时,N(R) 必须与 V (R)的当前值一致 。
信息帧中设置 N(R) 的目的是不必专门为收到的信息帧发送确认帧，可以在本站有信息发送时，将确认信息 捎带 走。提高信道利用率。
控制字段的第 5个比特是探询 /终止比特，即
P/F。主站发出的命令帧中若将 P置为 1表示要求对方立即响应。在平衡链路中若将 F置 1，
表示数据发送完毕。
3、监督帧 S
第 1~2比特为 10。监督帧共有四种，取决于
3~4比特的值。
第 3~4比特 帧名 功能
00 RR
接收准备就绪准备接收下一帧确认序号为 N(R)-1及以前的各帧
10 RNR
接收未就绪暂停接收下一帧确认序号为 N(R)-1及以前的各帧
01 REJ
拒绝从 N(R) 起的所有帧都被否认，但确认序号为 N(R)-1
及以前的各帧
11 SREJ
选择拒绝只否认序号为 N(R)的帧，
但确认序号为 N(R)-1及以前的各帧，较少用。
监督帧不包含数据，不需要发送序号 N(S)。
RR和 RNR还具有流量控制作用。
4、无编号帧 U
第 1~2比特为 11，无编号帧不带 V(S)和 V(R)字段,而用 5位，即 3,4,6,7,8来表示不同功能的无编号帧，无编号帧主要起控制作用。
如要与对方建立连接，可发 SABM（请求发送）帧，对方同意发 UA确认帧，断开连接发 DISC帧。
4.6因特网的点对点协议 PPP
用户拨号上网的示意图
用户拨通 ISP的号码 (如 163或 169),用户机中的 TCP/IP客户进程 就和 ISP的路由器中的 路由选择进程 建立了一个 PPP连接； ISP识别用户名和口令后,用户获得一个临时的 IP地址,
当用户结束通信时,该 IP地址被回收。
PPP协议由如下三个部分组成：
（ 1）一个将 IP数据报封装 到串行链路的方法。
IP数据报在 PPP帧中是其数据部分。
（ 2）一个建立、配置和测试数据链路连接的链路控制协议 LCP。双方可协商一些选项。
（ 3）网络控制协议 NCP。
PPP帧的格式标志
F
(7E)
地址
A
(FF)
控制
C
(03)
协议信息
(IP数据报 )
帧检验序列
FCS
标志
F
(7E)
字节,1 1 1 2 ≤ 1500字节 2 1
1、与 HDLC比较,PPP的特点：
（ 1）地址为固定值，控制字段与 U帧相同，
帧不使用编号，增加了一个协议字段，表示上层使用的协议，如 IP，则为 0x0021。
2,PPP是 面向字符 的协议。
3、透明性处理方法：在同步传输链路中采用位填充（与 HDLC相同），在异步传输链路中采用 字符填充,将 (0x7E)转换成
(0x7D,0x5E)。
4,PPP不提供可靠的传输服务 。当 CRC检验出帧出错时，只简单丢弃，其可靠性由高层来负责。目的是为了提高效率。
PPP建立连接过程：
（ 1）拨号，建立起物理连接。
（ 2） PC机向路由器发 LCP（封装成 PPP帧），
协商 PPP参数，如最大帧长，并鉴别用户身份。建立起数据链路层的连接。
（ 3）接着进行网络层配置，由 NCP给 PC机分配一个临时的 IP地址。
PPP释放连接的过程则正好相反。
使用 PPP协议的状态图 见书 P92，图 4-14
复习
作业
P93 12,16,17
