第五章 数据链路控制及其协议

主要内容 5.1 定义和功能 5.2 错误检测和纠正 5.3 基本的数据链路层协议 5.1.1 定义 5.1.2 为网络层提供服务 5.1 定义和功能 5.1.1 定义 5.1.2 为网络层提供服务 5.1.3 成帧 5.1.4 差错控制 5.1.5 流量控制 5.2 错误检测和纠正 5.2.1 纠错码 5.2.2 检错码 5.3 基本的数据链路层协议 5.3.1 无约束单工协议 5.3.2 单工停等协议 5.3.3 有噪声信道的单工协议

5.4 滑动窗口协议 5.5 协议说明与验证 5.6 常用的数据链路层协议 5.4.1 一比特滑动窗口协议 5.4.2 退后n帧协议 5.4 滑动窗口协议 5.4.1 一比特滑动窗口协议 5.4.2 退后n帧协议 5.4.3 选择重传协议 5.5 协议说明与验证 5.5.1 通信协议中的形式化描述技术 5.5.2 有限状态机模型 5.5.3 Petri网模型 5.6 常用的数据链路层协议 5.6.1 高级数据链路控制规程 HDLC 5.6.2 X.25的链路层协议LAPB 5.6.3 Internet数据链路层协议 5.6.4 ATM数据链路层协议

5.1 定义和功能（1） 5.1.1 定义 要解决的问题 ISO关于数据链路层的定义 5.1 定义和功能（1） 5.1.1 定义 要解决的问题 如何在有差错的线路上，进行无差错传输。 ISO关于数据链路层的定义 数据链路层的目的是为了提供功能上和规程上的方法，以便建立、维护和释放网络实体间的数据链路。 结点（node）：网络中的主机（host）和路由器（router）称为结点 链路（link）：通信路径上连接相邻结点的通信信道称为链路。 数据链路层协议定义了一条链路的两个结点间交换的数据单元格式，以及结点发送和接收数据单元的动作。

5.1 定义和功能（2） 端到端（end to end）与点到点（point to point） 虚拟数据通路，实际数据通路 5.1 定义和功能（2） 端到端（end to end）与点到点（point to point） 从源结点（source node）到目的结点（destination node）的通信称为端到端通信，通信路径（path）可能由多个链路组成。 在相邻结点间的一条链路上的通信称为点到点通信。 虚拟数据通路，实际数据通路 Fig. 3-1

5.1 定义和功能（2） 数据链路控制规程 数据链路层协议应提供的最基本功能 5.1 定义和功能（2） 数据链路控制规程 为使数据能迅速、正确、有效地从发送点到达接收点所采用的控制方式。 数据链路层协议应提供的最基本功能 数据在数据链路上的正常传输（建立、维护和释放） 定界与同步，也处理透明性问题 差错控制 顺序控制 流量控制

5.1 定义和功能（3） 5.1.2 为网络层提供服务 为网络层提供三种合理的服务 无确认无连接服务，适用于 5.1 定义和功能（3） 5.1.2 为网络层提供服务 为网络层提供三种合理的服务 无确认无连接服务，适用于 误码率很低的线路，错误恢复留给高层； 实时业务 大部分局域网 有确认无连接服务，适用于不可靠的信道，如无线网。 有确认有连接服务

5.1 定义和功能（4） 5.1.3 成帧（Framing） 将比特流分成离散的帧，并计算每个帧的校验和。 成帧方法： 字符计数法 5.1 定义和功能（4） 5.1.3 成帧（Framing） 将比特流分成离散的帧，并计算每个帧的校验和。 成帧方法： 字符计数法 在帧头中用一个域来表示整个帧的字符个数 缺点：若计数出错，对本帧和后面的帧有影响。 Fig. 3-3 带字符填充的首尾字符定界法 起始字符 DLE STX，结束字符DLE ETX 字符填充 Fig. 3-4 缺点：局限于8位字符和ASCII字符传送。

5.1 定义和功能（5） 注意：在很多数据链路协议中，使用字符计数法和一种其它方法的组合。 带位填充的首尾标记定界法 物理层编码违例法 5.1 定义和功能（5） 带位填充的首尾标记定界法 帧的起始和结束都用一个特殊的位串“01111110”，称为标记(flag) “0”比特插入删除技术 Fig. 3-5 物理层编码违例法 只适用于物理层编码有冗余的网络 802 LAN：Manchester encoding or Differential Manchester encoding 用high-low pair/low-high pair表示1/0，high-high/low-low不表示数据，可以用来做定界符。 注意：在很多数据链路协议中，使用字符计数法和一种其它方法的组合。

5.1 定义和功能（6） 5.1.4 差错控制 一般方法：接收方给发送方一个反馈（响应）。 出错情况 5.1 定义和功能（6） 5.1.4 差错控制 一般方法：接收方给发送方一个反馈（响应）。 出错情况 帧（包括发送帧和响应帧）出错； 帧（包括发送帧和响应帧）丢失 通过计时器和序号保证每帧最终交给目的网络层仅一次是数据链路层的一个主要功能。 5.1.5 流量控制 基于反馈机制 流量控制主要在传输层实现

5.2 错误检测和纠正（1） 差错出现的特点：随机，连续突发（burst） 处理差错的两种基本策略 5.2.1 纠错码 5.2 错误检测和纠正（1） 差错出现的特点：随机，连续突发（burst） 处理差错的两种基本策略 使用纠错码：发送方在每个数据块中加入足够的冗余信息，使得接收方能够判断接收到的数据是否有错，并能纠正错误。 使用检错码：发送方在每个数据块中加入足够的冗余信息，使得接收方能够判断接收到的数据是否有错，但不能判断哪里有错。 5.2.1 纠错码 码字（codeword）：一个帧包括m个数据位，r个校验位，n = m + r，则此n比特单元称为n位码字。 海明距离（Hamming distance）：两个码字之间不同的比特位数目。

5.2 错误检测和纠正（2） 最简单的例子是奇偶校验，在数据后填加一个奇偶位（parity bit） 5.2 错误检测和纠正（2） 例：0000000000 与0000011111的海明距离为5 如果两个码字的海明距离为d，则需要d个单比特错就可以把一个码字转换成另一个码字； 为了检查出d个错（单比特错），需要使用海明距离为 d + 1 的编码； 为了纠正d个错，需要使用海明距离为 2d + 1 的编码； 最简单的例子是奇偶校验，在数据后填加一个奇偶位（parity bit） 例：使用偶校验（“1”的个数为偶数） 10110101 ——> 101101011 10110001 ——> 101100010 奇偶校验可以用来检查单个错误。

5.2 错误检测和纠正（3） 设计纠错码 海明码 要求：m个信息位，r个校验位，纠正单比特错； 5.2 错误检测和纠正（3） 设计纠错码 要求：m个信息位，r个校验位，纠正单比特错； 对2m个有效信息中任何一个，有n个与其距离为1的无效码字，因此有：(n + 1) 2m  2n 利用 n = m + r，得到 (m + r + 1)  2r 给定m，利用该式可以得出校正单比特误码的校验位数目的下界 海明码 码位从左边开始编号，从“1”开始； 位号为2的幂的位是校验位，其余是信息位； 每个校验位使得包括自己在内的一些位的奇偶值为偶数（或奇数）。 为看清数据位k对哪些校验位有影响，将k写成2的幂的和。 例：11 = 1 + 2 + 8

5.2 错误检测和纠正（4） 海明码工作过程 使用海明码纠正突发错误 每个码字到来前，接收方计数器清零； 5.2 错误检测和纠正（4） 海明码工作过程 每个码字到来前，接收方计数器清零； 接收方检查每个校验位k (k = 1, 2, 4 …)的奇偶值是否正确； 若第 k 位奇偶值不对，计数器加 k； 所有校验位检查完后，若计数器值为0，则码字有效；若计数器值为m，则第m位出错。 若校验位1、2、8出错，则第11位变反。 Fig. 3-6 使用海明码纠正突发错误 可采用k个码字（n = m + r）组成 k  n 矩阵，按列发送，接收方恢复成 k  n 矩阵 kr个校验位，km个数据位，可纠正最多为k个的突发性连续比特错。

1 2 3 4 5 6 7 8 9 10 11 1 1 1 1 1 2 2 2 2 2 4 4 4 8 8 8

5.2 错误检测和纠正（5） 5.2.2 检错码 使用纠错码传数据，效率低，适用于不可能重传的场合；大多数情况采用检错码加重传。 5.2 错误检测和纠正（5） 5.2.2 检错码 使用纠错码传数据，效率低，适用于不可能重传的场合；大多数情况采用检错码加重传。 循环冗余码（CRC码，多项式编码） 110001，表示成多项式 x5 + x4 + 1 生成多项式G(x) 发方、收方事前商定； 生成多项式的高位和低位必须为1 生成多项式必须比传输信息对应的多项式短。 CRC码基本思想 校验和（checksum）加在帧尾，使带校验和的帧的多项式能被G(x)除尽；收方接收时，用G(x)去除它，若有余数，则传输出错。

5.2 错误检测和纠正（6） 校验和计算算法 CRC的检错能力 5.2 错误检测和纠正（6） 校验和计算算法 设G(x)为 r 阶，在帧的末尾加 r 个0，使帧为m + r位，相应多项式为xrM(x)； 按模2除法用对应于G(x)的位串去除对应于xrM(x)的位串； 按模2减法从对应于xrM(x)的位串中减去余数（等于或小于r位），结果就是要传送的带校验和的多项式T(x)。 Fig. 3-7 CRC的检错能力 发送：T(x)；接收：T(x) + E(x)； 余数((T(x) + E(x)) / G(x)) = 0 + 余数(E(x) / G(x)) 若 余数(E(x) / G(x)) = 0，则差错不能发现；否则，可以发现。

5.2 错误检测和纠正（7） 如果只有单比特错，即E(x) = xi，而G(x)中至少有两项，余数(E(x) / G(x))  0，所以可以查出单比特错； 如果发生两个孤立单比特错，即E(x) = xi + xj = xj (xi-j + 1)，假定G(x)不能被x整除，那么能够发现两个比特错的充分条件是：xk + 1不能被G(x)整除 (k  i - j)； 如果有奇数个比特错，即E(x)包括奇数个项，G(x)选(x + 1)的倍数就能查出奇数个比特错； 具有r个校验位的多项式能检查出所有长度  r 的突发性差错。长度为k的突发性连续差错（并不表示有k个单比特错）可表示为 xi (xk-1 + … + 1)，若G(x)包括x0项，且 k - 1小于G(x)的阶，则 余数(E(x) / G(x))  0; 如果突发差错长度为 r + 1，当且仅当突发差错和G(x)一样时， 余数(E(x) / G(x)) = 0，概率为1/2r-1; 长度大于 r + 1的突发差错或几个较短的突发差错发生后，坏帧被接收的概率为 1/2r。

5.2 错误检测和纠正（8） 四个多项式已成为国际标准 硬件实现CRC校验 5.2 错误检测和纠正（8） 四个多项式已成为国际标准 CRC-12 = x12 + x11 + x3 + x2 + x + 1 CRC-16 = x16 + x15 + x2 + 1 CRC-CCITT = x16 + x12 + x5 + 1 CRC-32 硬件实现CRC校验 网卡NIC（Network Interface Card）

5.3 基本的数据链路层协议（1） 5.3.1 无约束单工协议（An Unrestricted Simplex Protocol） 5.3 基本的数据链路层协议（1） 5.3.1 无约束单工协议（An Unrestricted Simplex Protocol） 工作在理想情况，几个前提： 单工传输 发送方无休止工作（要发送的信息无限多） 接收方无休止工作（缓冲区无限大） 通信线路（信道）不损坏或丢失信息帧 工作过程 发送程序:取数据，构成帧，发送帧； 接收程序：等待，接收帧，送数据给高层 Fig. 3-9

5.3 基本的数据链路层协议（2） 5.3.2 单工停等协议（A Simplex Stop-and-Wait Protocol） 5.3 基本的数据链路层协议（2） 5.3.2 单工停等协议（A Simplex Stop-and-Wait Protocol） 增加约束条件：接收方不能无休止接收。 解决办法：接收方每收到一个帧后，给发送方回送一个响应。 工作过程 发送程序：取数据，成帧，发送帧，等待响应帧； 接收程序：等待，接收帧，送数据给高层，回送响应帧。 Fig. 3-10

5.3 基本的数据链路层协议（3） 5.3.3 有噪声信道的单工协议（A Simplex Protocol for a Noisy Channel） 增加约束条件：信道（线路）有差错，信息帧可能损坏或丢失。 解决办法：出错重传。 带来的问题： 什么时候重传 —— 定时 响应帧损坏怎么办（重复帧）—— 发送帧头中放入序号 为了使帧头精简，序号取多少位 —— 1位 发方在发下一个帧之前等待一个肯定确认的协议叫做PAR（Positive Acknowledgement with Retransmission）或ARQ（Automatic Repeat reQuest）

5.3 基本的数据链路层协议（4） 发 送 接 收  工作过程 Fig. 3-11 注意协议3的漏洞 5.3 基本的数据链路层协议（4） 工作过程 Fig. 3-11 注意协议3的漏洞 由于确认帧中没有序号，超时时间不能太短，否则协议失败。因此假设协议3的发送和接收严格交替进行。 Fig. 3-11（与教材不同）的实现是正确的，确认帧有序号 发 送 接 收 ACK  1 ACK

5.4 滑动窗口协议（1） 单工 ——> 全双工 捎带/载答（piggybacking）：暂时延迟待发确认，以便附加在下一个待发数据帧的技术。 优点：充分利用信道带宽，减少帧的数目意味着减少“帧到达”中断； 带来的问题：复杂。 本节的三个协议统称滑动窗口协议，都能在实际（非理想）环境下正常工作，区别仅在于效率、复杂性和对缓冲区的要求。

5.4 滑动窗口协议（2） 滑动窗口协议（Sliding Window Protocol）工作原理： 5.4 滑动窗口协议（2） 滑动窗口协议（Sliding Window Protocol）工作原理： 发送的信息帧都有一个序号，从0到某个最大值，0 ~ 2n - 1，一般用n个二进制位表示； 发送端始终保持一个已发送但尚未确认的帧的序号表，称为发送窗口。发送窗口的上界表示要发送的下一个帧的序号，下界表示未得到确认的帧的最小编号。发送窗口大小 = 上界 - 下界，大小可变； 发送端每发送一个帧，序号取上界值，上界加1；每接收到一个正确响应帧，下界加1； 接收端有一个接收窗口，大小固定，但不一定与发送窗口相同。接收窗口的上界表示允许接收的序号最大的帧，下界表示希望接收的帧； 接收窗口容纳允许接收的信息帧，落在窗口外的帧均被丢弃。序号等于下界的帧被正确接收，并产生一个响应帧，上界、下界都加1。接收窗口大小不变。 Fig. 3-12

5.4 滑动窗口协议（3） 5.4.1 一比特滑动窗口协议（A One Bit Sliding Window Protocol） 协议特点 5.4 滑动窗口协议（3） 5.4.1 一比特滑动窗口协议（A One Bit Sliding Window Protocol） 协议特点 窗口大小：N = 1，发送序号和接收序号的取值范围：0，1； 可进行数据双向传输，信息帧中可含有确认信息（piggybacking技术）； 信息帧中包括两个序号域：发送序号和接收序号（已经正确收到的帧的序号） 工作过程 Fig. 3-13

5.4 滑动窗口协议（4） 存在问题 能保证无差错传输，但是基于停等方式； 若双方同时开始发送，则会有一半重复帧； Fig. 3-14（书上图有误） 效率低，传输时间长。

5.4 滑动窗口协议（5） 5.4.2 退后n帧协议（A Protocol Using Go Back n） 为提高传输效率而设计 例： 5.4 滑动窗口协议（5） 5.4.2 退后n帧协议（A Protocol Using Go Back n） 为提高传输效率而设计 例： 卫星信道传输速率50kbps，往返传输延迟500ms，若传1000bit的帧，使用协议4，则传输一个帧所需时间为： 发送时间 + 信息信道延迟 + 确认信道延迟（确认帧很短，忽略发送时间）= 1000bit / 50kbps + 250ms + 250ms = 520ms 信道利用率 = 20 / 520  4% 一般情况 信道带宽b比特/秒，帧长度L比特，往返传输延迟R秒，则信道利用率为 (L/b) / (L/b + R) = L / (L + Rb) 结论 传输延迟大，信道带宽高，帧短时，信道利用率低。

5.4 滑动窗口协议（6） 两种基本方法 解决办法 带来的问题 退后n帧（go back n） 5.4 滑动窗口协议（6） 解决办法 连续发送多帧后再等待确认，称为流水线技术（pipelining）。 带来的问题 信道误码率高时，对损坏帧和非损坏帧的重传非常多 两种基本方法 退后n帧（go back n） 接收方从出错帧起丢弃所有后继帧； 接收窗口为1； 对于出错率较高的信道，浪费带宽。 Fig. 3-15(a)

5.4 滑动窗口协议（7） 选择重传（selective repeat） 接收窗口大于1，先暂存出错帧的后继帧； 只重传坏帧； 5.4 滑动窗口协议（7） 选择重传（selective repeat） 接收窗口大于1，先暂存出错帧的后继帧； 只重传坏帧； 对最高序号的帧进行确认； 接收窗口较大时，需较大缓冲区。 Fig. 3-15(b) 注意：Fig. 3-15(b)中可能出现的错误

5.4 滑动窗口协议（8） 退后n帧协议 发送方有流量控制，为重传设缓冲； 发送窗口大小 < 序号个数（MaxSeq + 1）； 5.4 滑动窗口协议（8） 退后n帧协议 发送方有流量控制，为重传设缓冲； 发送窗口未满，EnableNetworkLayer 发送窗口满，DisableNetworkLayer 发送窗口大小 < 序号个数（MaxSeq + 1）； 考虑MaxSeq = 7的情况 1 发送方发送帧 0 ~ 7； 2 序号为 7 的帧的确认被捎带回发送方； 3 发送方发送另外 8 个帧，序号为 0 ~ 7； 4 另一个对帧 7 的捎带确认返回。 问题：第二次发送的 8 个帧成功了还是丢失了？ 退后n帧重发； 由于有多个未确认帧，设多个计时器。

5.4 滑动窗口协议（9） 工作过程 Fig. 3-16 计时器实现 Fig. 3-17

5.4 滑动窗口协议（10） P5协议实现分析 事件驱动 Network_layer_ready（内部事件） 5.4 滑动窗口协议（10） P5协议实现分析 事件驱动 Network_layer_ready（内部事件） 发送帧（帧序号，确认序号，数据） Frame_arrival （外部事件） 检查帧序号，落在接收窗口内则接收，否则丢弃； 检查确认序号，落在发送窗口内则移动发送窗口，否则不做处理。 Cksum_err （外部事件） 丢弃 timeout （内部事件） 退后n帧重传 计时器处理 启动，发送帧时启动 停止，收到正确确认时停止 超时则产生timeout事件

5.4 滑动窗口协议（11） 5.4.3 选择重传协议（A Protocol Using Selective Repeat） 目的 基本原理 5.4 滑动窗口协议（11） 5.4.3 选择重传协议（A Protocol Using Selective Repeat） 目的 在不可靠信道上有效传输时，不会因重传而浪费信道资源，采用选择重传技术。 基本原理 发送窗口大小：MaxSeq，接收窗口大小：(MaxSeq+1)/2 保证接收窗口前移后与原窗口没有重叠； 设 MaxSeq = 7, 若接收窗口 = 7，发方发帧 0 ~ 6，收方全部收到，接收窗口前移（7 ~ 5），确认帧丢失，发方重传帧0，收方作为新帧接收，并对帧6确认，发方发新帧 7 ~ 5，收方已收过帧 0，丢弃新帧 0，协议出错。 Fig. 3-19

5.4 滑动窗口协议（12） 发送窗口下界：AckExpected，上界：NextFrameToSend接收窗口下界：FrameExpected，上界：TooFar 缓冲区设置 发送方和接收方的缓冲区大小应等于各自窗口大小； 增加确认计时器，解决两个方向负载不平衡带来的阻塞问题； 可随时发送否定性确认帧NAK。 工作过程 Fig. 3-18

5.4 滑动窗口协议（13） P6协议实现分析 事件驱动 Network_layer_ready（内部事件） 5.4 滑动窗口协议（13） P6协议实现分析 事件驱动 Network_layer_ready（内部事件） 发送帧（帧类型，帧序号，确认序号，数据） Frame_arrival （外部事件） 若是数据帧，则检查帧序号，落在接收窗口内则接收，否则丢弃；不等于接收窗口下界还要发NAK 若是NAK，则选择重传； 检查确认序号，落在发送窗口内则移动发送窗口，否则不做处理。 Cksum_err （外部事件） 发送NAK timeout （内部事件） 选择重传 Ack_timeout （内部事件） 发送确认帧ACK

5.4 滑动窗口协议（14） 计时器处理 启动，发送数据帧时启动 停止，收到正确确认时停止 超时则产生timeout事件 Ack计时器处理 5.4 滑动窗口协议（14） 计时器处理 启动，发送数据帧时启动 停止，收到正确确认时停止 超时则产生timeout事件 Ack计时器处理 启动，收到帧的序号等于接收窗口下界或已经发过NAK时启动 停止，发送帧时停止 超时则产生ack_timeout事件

小结 可靠传输 通过确认和重传机制 传输层协议，如TCP，也提供可靠传输服务 链路层的可靠传输服务通常用于高误码率的连路上，如无线链路。

5.5 协议说明与验证（1） 5.5.1 协议工程与协议的形式化描述技术 协议工程： 协议说明 5.5 协议说明与验证（1） 5.5.1 协议工程与协议的形式化描述技术 协议工程： 协议说明（Protocol Specification） 协议验证（Protocol Verification） 协议实现（Protocol Implementation） 协议测试（Protocol Testing） 一致性测试（Conformance Testing） 互操作性测试（Interoperability Testing） 性能测试（Performance Testing） 协议说明 必须既定义一个协议实体提供给它的用户的服务，又定义该协议实体的内部操作。

5.5 协议说明与验证（2） 协议验证 协议实现 协议测试 5.5 协议说明与验证（2） 协议验证 验证协议说明是否完整、正确。 协议实现 用硬件和/或软件实现协议说明中规定的功能。 协议测试 用测试的方法来检查协议实现是否满足要求，包括：协议实现是否与协议说明一致（一致性测试）、协议实现之间的互操作能力（互操作性测试）和协议实现的性能（性能测试）等。 在协议的说明、验证、实现和测试过程中使用形式化描述技术，不仅可以比较容易地理解协议，而且可以使协议描述更加精确，大大简化了协议的研究工作。

5.5 协议说明与验证（3） 形式化描述的意义 自然语言描述协议的缺点 5.5 协议说明与验证（3） 形式化描述的意义 实际使用的协议非常复杂，给协议的理解、验证、实现和测试等工作带来困难，需要采用形式化的、数学的描述方法来描述协议。但是目前大多数协议还是采用自然语言描述。 自然语言描述协议的缺点 冗余； 多义性； 结构性不好； 不便于自动验证、测试、实现。 形式化描述技术FDT（Formal Description Technique）/形式化方法FM（Formal Method）广泛应用于协议工程研究中

5.5 协议说明与验证（4） 一种形式化方法总是以一种形式体系为基础，只是在具体应用时，大都做了便于描述的改进和扩充。 常用的形式化方法 5.5 协议说明与验证（4） 一种形式化方法总是以一种形式体系为基础，只是在具体应用时，大都做了便于描述的改进和扩充。 常用的形式化方法 有限状态机FSM（Finite State Machine） 扩展：EFSM 形式化语言模型 LOTOS，Estelle，SDL 都有相应扩展 Petri网 扩展：时间Petri网，随机Petri网，高级Petri网 过程代数（Process Algebra） 扩展：随机过程代数

5.5 协议说明与验证（5） 5.5.2 有限状态机模型 定义 通信协议建模 一个有限状态机是一个四元组(S, M, I, T)，其中 5.5 协议说明与验证（5） 5.5.2 有限状态机模型 定义 一个有限状态机是一个四元组(S, M, I, T)，其中 S是状态的集合，M是标号的集合，I是初始状态的集合， T是变迁的集合。 通信协议建模 基本出发点：认为通信协议主要是由响应多个“事件”的相对简单的处理过程组成； 事件 命令（来自用户） 信息到达（来自低层） 内部超时

5.5 协议说明与验证（6） 例 协议3 优点：简单明了，比较精确； 缺点：对许多复杂的协议，事件数和状态数会剧增，处理困难。 5.5 协议说明与验证（6） 优点：简单明了，比较精确； 缺点：对许多复杂的协议，事件数和状态数会剧增，处理困难。 例 协议3 每个状态用三个字母表示：XYZ X：发送方正发送的帧序号，为0或1； Y：接收方正等待的帧序号，为0或1； Z：信道状态，为0，1，A或 -（空）。 初始状态为（000） 半双工信道 Fig. 3-20 全双工信道 Fig. 3-21

5.5 协议说明与验证（7） 协议验证 验证协议说明是否完整正确，以协议说明为基础，涉及逻辑证明。 5.5 协议说明与验证（7） 协议验证 验证协议说明是否完整正确，以协议说明为基础，涉及逻辑证明。 主要用于系统实现前的设计阶段，为了避免可能出现的设计错误。原则上验证涉及协议所有可能的状态。 可达性分析是一种常用的验证方法 利用图论知识可以解决状态的可达性问题； 可达性分析能够用来解决协议的不完整性、死锁和无关变迁等问题。

5.5 协议说明与验证（8） 5.5.3 Petri网模型 Petri网研究的系统模型行为特性包括 5.5 协议说明与验证（8） 5.5.3 Petri网模型 Petri网模型最早在1962年 Carl Adam Petri的博士论文中提出来，主要特性是具有较强的对并行、不确定性、异步和分布的描述能力和分析能力。 Petri网研究的系统模型行为特性包括 状态的可达（reachability） 位置的限界（boundedness） 变迁的活性（liveness） 初始状态的可逆达（reversibility） 标识（marking）之间的可达（reachability） 事件之间的同步距离（synchronic distance） 公平性（fairness）

5.5 协议说明与验证（9） 定义 一个Petri网的结构元素包括： 活动元素 —— 标记（token）： 5.5 协议说明与验证（9） 定义 一个Petri网的结构元素包括： 位置（place）：描述系统状态，用一个圆圈表示； 变迁（transition）：描述修改系统状态的事件，用一个长方形或线段表示； 弧（arc）：描述状态与事件之间的关系，包括输入弧和输出弧，用有向弧表示。 活动元素 —— 标记（token）： 包含在位置中，用点表示； 用来表示处理的信息单元、资源单元和顾客、用户等对象； 如果位置用来描述条件，它可以包含一个标记或不包含标记，当包含标记时，条件为真，否则，为假； 如果位置用来定义状态，位置中的标记个数用于规定这个状态；

5.5 协议说明与验证（10） 主要分析方法 变迁实施规则（firing rule）： Fig. 3-22 可达树 关联矩阵和状态方程 5.5 协议说明与验证（10） 变迁实施规则（firing rule）： 如果一个变迁的所有输入位置至少包含一个标记，则这个变迁可能实施； 一个可实施变迁的实施导致从它所有输入位置中都清除一个标记，在它所有输出位置中产生一个标记； 当使用大于1的弧权（weight）时，在变迁的所有输入位置中都要包含至少等于连接弧权的标记个数它才可实施，并根据弧权，在每个输出位置中产生相应标记个数； 变迁的实施是一个原子操作，输入位置清除标记和输出位置产生标记是一个不可分割的完整操作。 Fig. 3-22 主要分析方法 可达树 关联矩阵和状态方程 不变量 分析化简规则

5.5 协议说明与验证（11） Petri网的扩展 条件/事件（C/E）网 位置/变迁（P/T）网 5.5 协议说明与验证（11） Petri网的扩展 条件/事件（C/E）网 最简单，每个位置最多一个标记，表示条件。 位置/变迁（P/T）网 每个位置中的标记可以有多个。 高级Petri网（包括谓词/变迁网和着色网） 给标记以属性，即标记有区别 从没有参数的网，发展到时间Petri网和随机Petri网； 从一般有向弧发展到可变弧； 从自然数标记个数发展到概率标记个数； 从原子变迁发展到谓词变迁和子网变迁。

5.5 协议说明与验证（12） 例：协议3（半双工信道） 关于形式化方法的几点注意事项 Fig. 3-23 可达图（部分） 5.5 协议说明与验证（12） 例：协议3（半双工信道） Fig. 3-23 可达图（部分） 关于形式化方法的几点注意事项 模型描述能力的增强会在某种程度上增加模型分析的难度； 模型仅仅是手段，不是目的。 Modeling is a bridge.

M0 = ACG (000) 10 ADF (0A1) 3 BEF (111) 11 BDG (1A0) 1

5.6 常用的数据链路层协议（1） ISO和CCITT在数据链路层协议的标准制定方面做了大量工作，各大公司也形成了自己的标准。 5.6 常用的数据链路层协议（1） ISO和CCITT在数据链路层协议的标准制定方面做了大量工作，各大公司也形成了自己的标准。 数据链路层协议分类 面向字符的链路层协议 ISO的IS1745，基本型传输控制规程及其扩充部分（BM和XBM） IBM的二进制同步通信规程（BSC） DEC的数字数据通信报文协议（DDCMP） PPP 面向比特的链路层协议 IBM的SNA使用的数据链路协议SDLC（Synchronous Data Link Control protocol）； ANSI修改SDLC，提出ADCCP（Advanced Data Communication Control Procedure）； ISO修改SDLC，提出HDLC（High-level Data Link Control）； CCITT修改HDLC，提出LAP（Link Access Procedure）作为X.25网络接口标准的一部分，后来改为LAPB。

5.6 常用的数据链路层协议（2） }语法 5.6.1 高级数据链路控制规程HDLC 5.6 常用的数据链路层协议（2） 5.6.1 高级数据链路控制规程HDLC 1976年，ISO提出HDLC（High-level Data Link Control） HDLC的组成 帧结构 规程元素 规程类型 语义 使用HDLC的语法可以定义多种具有不同操作特点的链路层协议。 HDLC的适用范围 计算机 —— 计算机 计算机 —— 终端 终端 —— 终端 }语法

5.6 常用的数据链路层协议（3） 数据站（简称站 station），由计算机和终端组成，负责发送和接收帧。HDLC涉及三种类型的站： 5.6 常用的数据链路层协议（3） 数据站（简称站 station），由计算机和终端组成，负责发送和接收帧。HDLC涉及三种类型的站： 主站（primary station）：主要功能是发送命令（包括数据），接收响应，负责整个链路的控制（如系统的初始、流控、差错恢复等）； 次站（secondary station）：主要功能是接收命令，发送响应，配合主站完成链路的控制； 组合站（combined station）：同时具有主、次站功能，既发送又接收命令和响应，并负责整个链路的控制。 HDLC适用的链路构型 非平衡型 点 — 点式

5.6 常用的数据链路层协议（4） 平衡型 多点式 适合把智能和半智能的终端连接到计算机。 主站 — 次站式 组合式 5.6 常用的数据链路层协议（4） 多点式 适合把智能和半智能的终端连接到计算机。 平衡型 主站 — 次站式 组合式 适合于计算机和计算机之间的连接

5.6 常用的数据链路层协议（5） HDLC的基本操作模式 正规响应模式 NRM（Normal Response Mode） 5.6 常用的数据链路层协议（5） HDLC的基本操作模式 正规响应模式 NRM（Normal Response Mode） 适用于点 — 点式和多点式两种非平衡构型。只有当主站向次站发出探询后，次站才能获得传输帧的许可。 异步响应模式 ARM（Asynchronous Response Mode） 适用于点 — 点式非平衡构型和主站 — 次站式平衡构型。次站可以随时传输帧，不必等待主站的探询。 异步平衡模式 ABM（Asynchronous Balanced Mode） 适用于通信双方都是组合站的平衡构型，也采用异步响应，双方具有同等能力。

5.6 常用的数据链路层协议（6） 帧结构 定界符 地址域（Address） 01111110 空闲的点到点线路上连续传定界符 5.6 常用的数据链路层协议（6） 帧结构 定界符 01111110 空闲的点到点线路上连续传定界符 地址域（Address） 多终端线路，用来区分终端； 点到点线路，有时用来区分命令和响应。 若帧中的地址是接收该帧的站的地址，则该帧是命令帧； 若帧中的地址是发送该帧的站的地址，则该帧是响应帧。

5.6 常用的数据链路层协议（7） 控制域（Control） 数据域（Data） 校验和（Checksum） 序号 确认 其它 5.6 常用的数据链路层协议（7） 控制域（Control） 序号 使用滑动窗口技术，3位序号，发送窗口大小为7 确认 其它 数据域（Data） 任意信息，任意长度（上层协议SDU有上限） 校验和（Checksum） CRC校验 生成多项式：CRC-CCITT

5.6 常用的数据链路层协议（8） 帧类型 控制域 信息帧（Information） 监控帧（Supervisory） 5.6 常用的数据链路层协议（8） 帧类型 信息帧（Information） 监控帧（Supervisory） 无序号帧（Unnumbered） 控制域 Fig. 3-25 序号（Seq） 使用滑动窗口技术，3位序号，发送窗口大小为7 捎带确认（Next） 捎带第一个未收到的帧序号，而不是最后一个已收到的帧序号

5.6 常用的数据链路层协议（9） 探询/结束 P/F位（Poll/Final） 类型（Type） 5.6 常用的数据链路层协议（9） 探询/结束 P/F位（Poll/Final） 命令帧置“P”，响应帧置“F”。有些协议，P/F位用来强迫对方机器立刻发控制帧； 多终端系统中，计算机置“P”，允许终端发送数据；终端发向计算机的帧中，最后一个帧置为“F”，其它置为“P”。 类型（Type） “0”表示确认帧 RR（RECEIVE READY）； “1”表示否定性确认帧 REJ（REJECT）。 “2”表示接收未准备好 RNR（RECEIVE NOT READY） “3”表示选择拒绝 SREJ（SELECTIVE REJECT） HDLC和ADCCP允许选择拒绝，SDLC和LAPB不允许。

5.6 常用的数据链路层协议（10） 无序号帧 命令 可以用来传控制信息，也可在不可靠无连接服务中传数据。 DISC（DISConnect） 5.6 常用的数据链路层协议（10） 无序号帧 可以用来传控制信息，也可在不可靠无连接服务中传数据。 命令 DISC（DISConnect） SNRM（Set Normal Response Mode） SARM（Set Asynchronous Response Mode） SABM（Set Asynchronous Balanced Mode） HDLC和LAPB使用。 SABME SABM的扩展 SNRME SNRM的扩展 FRMR（FRaMe Reject） 校验和正确，语义错误

5.6 常用的数据链路层协议（11） HDLC的功能组合 无序号确认UA（Unnumbered Acknowledgement） 5.6 常用的数据链路层协议（11） 无序号确认UA（Unnumbered Acknowledgement） 对控制帧进行确认，用于确认模式建立和接受拆除命令。 UI（Unnumbered Information） HDLC的功能组合 三种站，两种构型，三种操作模式，以及规程元素中定义的各种帧的各种组合产生多种链路层协议。 HDLC定义了选择构成链路层协议的良序结构： 选择站构型 ——> 基本操作模式 ——> 基本帧种类 ——> 12种任选功能 ——> 得到协议

5.6 常用的数据链路层协议（12） 5.6.2 X.25的链路层协议LAPB X.25协议 5.6 常用的数据链路层协议（12） 5.6.2 X.25的链路层协议LAPB X.25协议 分组级，PLP 帧级，X.25 LAP（Link Access Procedure），X.25 LAPB（Balanced） 物理级，X.21 “X.25协议规程使用HDLC规程的原理和术语” X.25 LAP：HDLC非平衡规程帧的基本清单 + 任选功能2、8、12，也可组成主站 — 次站式平衡规程。 X.25 LAPB：HDLC组合站平衡规程帧的基本清单 + 任选功能2、8、11、12。 因此，X.25 LAP、LAPB是HDLC的子集。

5.6 常用的数据链路层协议（13） X.25的帧格式与HDLC完全相同 X.25链路级的命令和响应

5.6 常用的数据链路层协议（14） X.25 LAPB的各种检错和纠错措施 a 帧格式上采用CRC校验，只检错，不纠错，丢弃出错帧； 5.6 常用的数据链路层协议（14） X.25 LAPB的各种检错和纠错措施 a 帧格式上采用CRC校验，只检错，不纠错，丢弃出错帧； b 设立超时机制，计时器 超时重传，重传N次，则向上层协议报告。 超时机制用来检错，重传用来纠错。 c 帧序号 若接收方发现帧序号错，就发拒绝帧给发送方，发送方重传，既检错也纠错。 d 采用P/F位来进行校验指示 发送置为 P 的命令帧，等待置为 F 的响应帧，能及时发现远程数据站是否收到命令帧。 规程规定：a 必须使用；b, c, d 组合使用。

5.6 常用的数据链路层协议（15） 5.6.3 Internet数据链路层协议 点到点通信的两种主要情形 5.6 常用的数据链路层协议（15） 5.6.3 Internet数据链路层协议 点到点通信的两种主要情形 路由器到路由器（router-router leased line connection） 通过modem拨号上网，连到路由器或接入服务器（Access Server）（dial-up host-router connection）

5.6 常用的数据链路层协议（16） SLIP —— Serial Line IP 5.6 常用的数据链路层协议（16） SLIP —— Serial Line IP 1984年，Rick Adams提出，RFC1055，发送原始IP包，用一个标记字节来定界，采用字符填充技术； 新版本提供TCP和IP头压缩技术，RFC 1144 存在的问题 不提供差错校验 只支持IP IP地址不能动态分配 不提供认证 多种版本并存，互连困难

5.6 常用的数据链路层协议（17） 点到点协议 PPP —— Point-to-Point Protocol 5.6 常用的数据链路层协议（17） 点到点协议 PPP —— Point-to-Point Protocol RFC 1661，RFC 1662，RFC 1663 与SLIP相比，PPP有很大的提高，提供差错校验、支持多种协议、允许动态分配IP地址、支持认证等。 以帧为单位发送，而不是原始IP包； 包括两部分 链路控制协议LCP（Link Control Protocol） 可使用多种物理层服务：modem，HDLC串线，SDH/SONET等 网络控制协议NCP（Network Control Protocol） 可支持多种网络层协议 帧格式与HDLC相似，区别在于PPP是面向字符的，采用字符填充技术

5.6 常用的数据链路层协议（18） 标记域：01111110，字符填充； 地址域：11111111 控制域：缺省值为00000011，表示无序号帧，不提供使用序号和确认的可靠传输；不可靠线路上，也可使用有序号的可靠传输。 协议域：指示净负荷中是何种包，缺省大小为2个字节。 净负荷域：变长，缺省为1500字节； 校验和域：2或4个字节 总结：PPP具有多协议成帧机制，可以在modem, HDLC bit-serial lines, SDH/SONET等物理层上运行，支持差错检测、选项协商和包头压缩功能，并具有利用HDLC帧进行可靠传输的可选功能。

5.6 常用的数据链路层协议（19） PPP链路 up / down 过程（简单状态图）

5.6 常用的数据链路层协议（20） LCP用来在ESTABLISH状态协商数据链路协议选项，并不关心选项内容，而是提供一种协商机制，并且提供检测链路质量的方法。RFC 1661 定义了11种LCP帧类型：

小结 介绍三种主要数据链路层协议：HDLC、LAPB（面向比特）和PPP（面向字符） HDLC具有三种站，两种构型，三种操作模式 X.25 LAPB是HDLC的子集 PPP 提供差错校验、支持多种协议、允许动态分配IP地址、支持认证 PPP包括两部分：LCP和NCP PPP帧没有序号域，不使用滑动窗口技术。