考研_计算机网络_第三学时_数据链路层

《考研_计算机网络_第三学时_数据链路层》由会员分享，可在线阅读，更多相关《考研_计算机网络_第三学时_数据链路层（74页珍藏版）》请在金锄头文库上搜索。

1、计算机网络数据链路层数据链路层1 数据链路层的基本概念 2 停止等待协议 2.1 完全理想化的数据传输 2.2 具有最简单流量控制的数据链路层协议 2.3 实用的停止等待协议 2.4 循环冗余检验的原理 2.5 停止等待协议的算法 2.6 停止等待协议的定量分析数据链路层（续）3 连续 ARQ 协议 3.1 连续 ARQ 协议的工作原理 3.2 连续 ARQ 协议的吞吐量 3.3 滑动窗口的概念 3.4 信道利用率与最佳帧长 4 选择重传 ARQ 协议数据链路层（续）5 面向比特的链路层协议 HDLC 5.1 HDLC 协议概述 5.2 HDLC 的帧结构 6 因特网的点对点协议 PPP6.1

2、 PPP 协议的工作原理6.2 PPP 协议的帧格式6.3 PPP 协议的工作状态1 数据链路层的基本概念 n链路(link)是一条无源的点到点的物理线 路段，中间没有任何其他的交换结点。n一条链路只是一条通路的一个组成部分。n数据链路(data link) 除了物理线路外，还必须 有通信协议来控制这些数据的传输。若把实现 这些协议的硬件和软件加到链路上，就构成了 数据链路。n现在最常用的方法是使用适配器（即网卡）来实现 这些协议的硬件和软件。n一般的适配器都包括了数据链路层和物理层这两层 的功能。 数据链路层像个数字管道 n常常在两个对等的数据链路层之间画出 一个数字管道，而在这条数字管道上

3、传 输的数据单位是帧。n早期的数据通信协议曾叫作通信规程 (procedure)。因此在数据链路层，规程 和协议是同义语。 结点结点帧帧数据链路层的主要功能(1) 链路管理 (2) 帧定界 (3) 流量控制 (4) 差错控制 (5) 将数据和控制信息区分开 (6) 透明传输 (7) 寻址 2 停止等待协议n2.1 完全理想化的数据传输n先研究一下数据链路层的模型。数据链路层的简单模型局域网广域网主机 H1主机 H2路由器 R1路由器 R2路由器 R3电话网局域网主机 H1 向 H2 发送数据链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网

4、络层物理层R1R2R3H1H2从层次上来看数据的流动数据链路层的简单模型( 续）局域网广域网主机 H1主机 H2路由器 R1路由器 R2路由器 R3电话网局域网主机 H1 向 H2 发送数据链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层R1R2R3H1H2仅从数据链路层观察帧的流动2 停止等待协议 2.1 完全理想化的数据传输数据链路层主 机A缓存主 机B数据链路AP2AP1缓存发送方接收方帧高层帧完全理想化的数据传输 所基于的两个假定 n假定 1： 链路是理想的传输信道，所传 送的任何数据既不会出差错也不会丢失 。n假定 2

5、： 不管发方以多快的速率发送数 据，收方总是来得及收下，并及时上交 主机。n这个假定就相当于认为：接收端向主机交 付数据的速率永远不会低于发送端发送数 据的速率。 2.2 具有最简单流量控制的数 据链路层协议n现在去掉上述的第二个假定。但是，仍 然保留第一个假定，即主机 A 向主机 B 传输数据的信道仍然是无差错的理想信 道。然而现在不能保证接收端向主机交 付数据的速率永远不低于发送端发送数 据的速率。n由收方控制发方的数据流，乃是计算机 网络中流量控制的一个基本方法。 具有最简单流量控制的 数据链路层协议算法在发送结点：(1) 从主机取一个数据帧。(2) 将数据帧送到数据链路层的发送缓存。(

6、3) 将发送缓存中的数据帧发送出去。(4) 等待。(5) 若收到由接收结点发过来的信息(此信息的格式与内容可由双方事先商定好)，则从主机取一个新的数据帧，然后转到(2)。具有最简单流量控制的 数据链路层协议算法（续）在接收结点：(1) 等待。(2) 若收到由发送结点发过来的数据帧，则将其放入数据链路层的接收缓存。(3) 将接收缓存中的数据帧上交主机。(4) 向发送结点发一信息，表示数据帧已经上交给主机。(5) 转到(1)。两种情况的对比（传输均无差错）ABDATADATADATADATA送主机 B送主机 B送主机 B送主机 BABDATA送主机 BDATA送主机 B时 间不需要流量控制需要流量

7、控制2.3 实用的停止等待协议时 间ABDATA0送 主 机ACKDATA1送 主 机ACK(a) 正常情况ABDATA0DATA0送 主 机ACK(c) 数据帧丢失重 传tout丢 失！ABDATA0送 主 机ACKDATA0丢 弃ACK(d) 确认帧丢失重 传tout丢 失！ABDATA0NAKDATA0送 主 机ACK(b) 数据帧出错重 传出错四种情况超时计时器的作用n结点A发送完一个数据帧时，就启动一个 超时计时器(timeout timer)。n计时器又称为定时器。n若到了超时计时器所设置的重传时间 tout 而仍收不到结点 B 的任何确认帧，则结 点 A 就重传前面所发送的这一数

8、据帧。n一般可将重传时间选为略大于“从发完数 据帧到收到确认帧所需的平均时间”。 解决重复帧的问题 n使每一个数据帧带上不同的发送序号。每发送 一个新的数据帧就把它的发送序号加 1。 n若结点 B 收到发送序号相同的数据帧，就表明 出现了重复帧。这时应丢弃重复帧，因为已经 收到过同样的数据帧并且也交给了主机 B。n但此时结点 B 还必须向 A 发送确认帧 ACK， 因为 B 已经知道 A 还没有收到上一次发过去 的确认帧 ACK。 帧的编号问题 n任何一个编号系统的序号所占用的比特数一定 是有限的。因此，经过一段时间后，发送序号 就会重复。 n序号占用的比特数越少，数据传输的额外开销 就越小。

9、 n对于停止等待协议，由于每发送一个数据帧就 停止等待，因此用一个比特来编号就够了。n一个比特可表示 0 和 1 两种不同的序号。 帧的发送序号 n数据帧中的发送序号 N(S) 以 0 和 1 交替 的方式出现在数据帧中。n每发一个新的数据帧，发送序号就和上 次发送的不一样。用这样的方法就可以 使收方能够区分开新的数据帧和重传的 数据帧了。 可靠传输 n虽然物理层在传输比特时会出现差错， 但由于数据链路层的停止等待协议采用 了有效的检错重传机制，数据链路层对 上面的网络层就可以提供可靠传输的服 务。 2.4 循环冗余检验的原理 n在数据链路层传送的帧中，广泛使用了 循环冗余检验 CRC 的检错

10、技术。n假设待传送的数据 M = 1010001101（共 k bit）。我们在M的后面再添加供差错检 测用的 n bit 冗余码一起发送。 冗余码的计算 n用二进制的模 2 运算进行 2n 乘 M 的运算 ，这相当于在 M 后面添加 n 个 0。n得到的 (k + n) bit 的数除以事先选定好的 长度为 (n + 1) bit 的数 P，得出商是 Q 而余数是 R，余数 R 比除数 P 至少要少 1 个比特。 冗余码的计算举例 n设 n = 5, P = 110101，模 2 运算的结果 是：商 Q = 1101010110，余数R = 01110。n将余数 R 作为冗余码添加在数据 M

11、 的后 面发送出去，即发送的数据是 101000110101110，或 2nM + R。 1101010110 Q 商除数 P 110101 101000110100000 2nM 被除数110101111011 11010111101011010111111011010110110011010111001011010101110 R 余数循环冗余检验的原理说明 帧检验序列 FCS n在数据后面添加上的冗余码称为帧检验 序列 FCS (Frame Check Sequence)。n循环冗余检验 CRC 和帧检验序列 FCS 并不等同。nCRC 是一种常用的检错方法，而 FCS 是添 加在数据后

12、面的冗余码。nFCS 可以用 CRC 这种方法得出，但 CRC 并非用来获得 FCS 的惟一方法。 检测出差错 n只要得出的余数 R 不为 0，就表示检测 到了差错。n但这种检测方法并不能确定究竟是哪一 个或哪几个比特出现了差错。n一旦检测出差错，就丢弃这个出现差错 的帧。n只要经过严格的挑选，并使用位数足够 多的除数 P，那么出现检测不到的差错 的概率就很小很小。 应当注意 n仅用循环冗余检验 CRC 差错检测技术只能做 到无差错接受(accept)。n“无差错接受”是指：“凡是接受的帧（即不包括 丢弃的帧），我们都能以非常接近于 1 的概率 认为这些帧在传输过程中没有产生差错”。n也就是说

13、：“凡是接受的帧都没有传输差错”（ 有差错的帧就丢弃而不接受）。n要做到“可靠传输”（即发送什么就收到什么） 就必须再加上确认和重传机制。 2.5 停止等待协议的算法n这里不使用否认帧（实用的数据链路层协议大 都是这样的），而且确认帧带有序号 n。n按照习惯的表示法，ACKn 表示“第 n 1 号帧 已经收到，现在期望接收第 n 号帧”。nACK1 表示“0 号帧已收到，现在期望接收的下一帧 是 1 号帧”；nACK0 表示“1 号帧已收到，现在期望接收的下一帧 是 0 号帧”。 在发送结点 (1) 从主机取一个数据帧，送交发送缓存。 (2) V(S)0。 (3) N(S)V(S)。 (4)

14、将发送缓存中的数据帧发送出去。 (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

15、)。 (6) nV(R)；发送确认帧 ACKn，转到(2)。 停止等待协议的要点n只有收到序号正确的确认帧 ACKn 后，才更新 发送状态变量 V(S)一次，并发送新的数据帧。n接收端接收到数据帧时，就要将发送序号 N(S) 与本地的接收状态变量 V(R) 相比较。n若二者相等就表明是新的数据帧，就收下，并发送 确认。n否则为重复帧，就必须丢弃。但这时仍须向发送端 发送确认帧 ACKn，而接收状态变量 V(R) 和确认序 号 n 都不变。 停止等待协议的要点（续）n连续出现相同发送序号的数据帧，表明 发送端进行了超时重传。连续出现相同 序号的确认帧，表明接收端收到了重复 帧。 n发送端在发送完

16、数据帧时，必须在其发 送缓存中暂时保留这个数据帧的副本。 这样才能在出差错时进行重传。只有确 认对方已经收到这个数据帧时，才可以 清除这个副本。 停止等待协议的要点（续）n实用的 CRC 检验器都是用硬件完成的。nCRC 检验器能够自动丢弃检测到的出错 帧。因此所谓的“丢弃出错帧”，对上层软 件或用户来说都是感觉不到的。n发送端对出错的数据帧进行重传是自动 进行的，因而这种差错控制体制常简称 为 ARQ (Automatic Repeat reQuest)， 直译是自动重传请求，但意思是自动请 求重传。 2.6 停止等待协议的定量分析n设 tf 是一个数据帧的发送时间，且数据帧的长度是固定不变的。显然，数据帧的发送时间 tf 是数据帧的长度 lf (bit)与数据的发送速率 C (bit/s)之比，即tf = lf /C = lf /C (s)