第三章数据链路层

1、计算机网络 第三章 数据链路层主要内容z组帧z差错检测z可靠交付y停-等协议y滑动窗口协议z数据链路层协议举例yHDLC协议yPPP协议1. 组帧z 使用字符填充的起止标记法y使用特殊的字符表示帧的开始与结束。y使用字符填充（在特殊字符前加转义字符）解决透明传输问题。y该方法依赖于特定的字符编码集，帧长必须是8比特的整倍数，灵活性差，处理开销大。z 使用比特填充的起止标记法y使用一个特殊的比特模式（01111110）作为帧的起始与结束标志。y使用比特填充（连续5个1后插入一个0）解决透明传输问题。y该方法不依赖于特定的字符编码集，灵活性强，处理简单。z 违法编码法y使用物理层编码中的无效编码表

2、示帧的边界。字符填充示例比特填充示例2. 差错检测z出错的类型y单个错：由随机的信道热噪声引起，一次只影响1位。y突发错：由瞬间的脉冲噪声引起，一次影响许多位，用突发长度表示突发错影响的最大数据位数。z差错编码的类型y检错码：只能检测出传输错误，但无法自行纠正，通常与反馈重传结合起来进行差错恢复。y纠错码：能够检测出传输错误并纠正。如何检测与纠正错误？z 码字（codeword）：由m比特的数据（消息）加上 r 比特的冗余（校验位）构成。z 有效编码集：由2m个有效码字组成。z 检错：当收到的码字为无效码字时检测出错误。z 海明距离（Hamming Distance）：两个码字的对应位上取值不

3、同的位数。z 纠错：将收到的无效码字纠正到距其最近的有效码字。z 检错码与纠错码的能力都是有限的。编码集的检错与纠错能力z 编码集的海明距离：编码集中任意两个有效码字的海明距离的最小值。z 检错能力：为检测出 d 比特错误，编码集的海明距离至少应为 d+1；奇偶校验是能够检测出1比特错误的检错码。z 纠错能力：为纠正 d 比特错误，编码集的海明距离至少应为 2d+1。z 结论：差错编码的检错/纠错能力与编码集的海明距离有关。海明距离越大，检错纠错能力就越强；但所需的冗余信息也越多，编码效率就越低。 二维奇偶校验z 对一个 kn 比特的信息矩阵的每一行和每一列计算奇偶校验位。 循环冗余码（CRC

4、）z CRC是一种多项式编码，它将位串看成是某个一元多项式的系数，如1011001看成是一元多项式X6 + X4 + X3 + 1的系数。z 信息多项式M(x)：由 m 个信息比特为系数构成的多项式。z 冗余多项式R(x)：由 r 个冗余比特为系数构成的多项式。z 码多项式T(x)：在 m 个信息比特后加上 r 个冗余比特构成的码字所对应的多项式，表达式为 T(x) = xrM(x) + R(x)。z 生成多项式G(x)：双方预先确定用来计算R(x)的一个多项式。z 编码方法：用对应于 G(x) 的位串去除对应于 xrM(x) 的位串，所得的余式即为 R(x)，将其附加到信息比特串的后面一起发

5、送。z 校验方法：用对应于 G(x) 的位串去除对应于 T(x) 的位串，若余式为0则认为传输正确，否则认为传输错误。z CRC码检错能力强，实现简单快捷，是应用最广泛的检错码。CRC的编码及校验z 例1：G(X) = X4 + X + 1，对10110011进行CRC编码。z 例2：仍取G(X) = X4 + X + 1，判断收到的位串100101111001是否有错？ 常见的CRC多项式CRCC(x)CRC-8X8 + X2 + X1 + 1CRC-10X10 + X9 + X5 + X4 + X1 + 1CRC-12X12 + X11 + X3 + X2 + 1 CRC-16X16 +

6、X15 + X2 + 1 CRC-CCITTX16 + X12 + X5 + 1 CRC-32X32 + X26 + X23 + X22 + X16 + X12 + X11 + X10 + X8 + X7 + X5 + X4 + X2 + X1 + 1 3. 可靠交付z差错恢复的两种办法：y使用纠错码，由接收端自动纠正错误。y使用检错码，采用自动重传请求（ARQ）保证可靠交付。这是数据链路层（及传输层）上最常使用的可靠交付方式。z两种ARQ算法：y停-等y滑动窗口 3.1 停-等算法z 基本思想：发送方发完一帧后即停下来等待确认；如果收到一个确认，接着发送下一个帧；如果定时器超时，重发刚才的帧

7、。z 停-等算法的四种情形。z 停-等算法的超时值对性能影响很大，必须仔细选择。z 为区分新帧和重发帧，停-等算法使用一比特的帧序号。停-等算法的四种情形停-等算法的过-发送方 1）帧序号初始化为0 2）从缓冲区中取出一个帧，加上当前帧序号发送。 3）等待确认 i）收到确认帧，且帧序号与当前维护的帧序号不同，将 帧序号加1，从缓冲区中取出一个新的帧，加上当前 帧序号发送。 ii）收到确认帧，且帧序号与当前维护的帧序号相同，重 发当前序号的帧。 iii）收到错误的确认帧，重发当前序号的帧。 iv）定时器超时，重发当前序号的帧。停-等算法的过程-接收方 1）帧序号初始化为0（表示当前期望接收的帧序

8、号） 2）等待接收 3）帧到达 i）帧校验正确，且序号为当前期望接收的帧序号，将帧 放入接收缓冲区，帧序号加1，放入确认帧中发送。 ii）帧校验正确，但序号与当前期望接收的帧序号不同， 丢弃帧，重发确认帧。 iii）帧校验错误，丢弃帧，重发确认帧。信道利用率与流水线技术z停-等算法在传输延迟较长的信道上传输效率很低。z假如将链路看成是一根管道，数据是管道中流动的水，那么停-等算法无法使数据充满管道，因而信道利用率很低。z管道的容量通常用延迟-带宽乘积表示，它表示发送端在收到第一个帧的确认前最多可以发送的数据量。z滑动窗口机制允许发送端连续发送多个帧来尽可能多地填充管道，从而提高信道的利用率。3

9、.2 滑动窗口z滑动窗口是计算机网络中最著名的算法，它可以应用在数据链路层及传输层，用来完成三个不同的任务：y在不可靠的链路（网络）上可靠地传输数据y保持数据的传输顺序y支持流量控制z在数据链路层上，以上三个功能组合在一个滑动窗口协议中。发送窗口z 发送窗口：发送端允许发送的帧序号表。z 发送窗口大小：发送端最大允许的未确认帧数目。z 发送窗口下沿：最早发送但尚未被确认的帧序号。z 发送窗口上沿：（发送窗口下沿发送窗口大小1）mod 2n。 z 当收到对发送窗口下沿帧的确认时，发送窗口整体向前滑动一个序号，将已被确认的帧移出发送窗口，并加入一个新的序号。（图）z 发送窗口中的帧都保留在缓冲区中

10、以备重传，当某个帧被移出发送窗口时，同时从缓冲区中删除。z 当发送窗口满时，停止从网络层接收数据，直到有一个缓冲区空出来为止。发送窗口和接收窗口图示接收窗口z 接收窗口：接收端允许接收的帧序号表。z 接收窗口大小：接收端允许接收的最大帧数。z 接收窗口下沿：接收端按顺序期待接收的帧序号。z 当接收端收到窗口下沿帧且校验正确时，将帧交给网络层，向发送方发回一个确认，然后窗口整体向前滑动一个序号。（图）z 接收窗口的大小可以设为任意值，通常的设置有两种：y接收窗口大小 = 1：意味着接收方只能按顺序接收；y接收窗口大小 = 发送窗口大小：意味着接收方可以不按顺序接收，但接收方交给上层实体的数据总是

11、有序的。捎带确认z 捎带确认（piggybacking）：将确认序号携带在数据帧中传输，提高线路的效率。z 推迟确认：当需要发送确认但没有要发送的数据时，可以让确认信息推迟一小段时间再发送；这一小段时间后若数据仍未准备好，接收端必须立即发送一个单独的确认帧。z 接收端对正确收到的若干个帧同时进行确认，通常用对某一个帧的确认来表示对该帧之前的所有帧进行确认。Go Back nzGo back ny当接收端收到一个出错帧或乱序帧时，丢弃所有的后继帧，并且不为这些帧发送确认；发送端超时后，重传所有未被确认的帧。y该策略对应接收窗口为1的情况，即只能按顺序接收帧。y若信道的误码率较高，这种方法会浪费很

12、多带宽，但对接收端内存的需求不大。Go Back N 示意图选择重传z选择重传y当接收端收到一个出错帧或乱序帧时，后续到达的帧只要校验正确且落在接收窗口内，都放入接收缓冲区中；发送端超时后只重传最早发送但未被确认的帧。y该策略对应接收窗口大于1的情况。y选择重传通常使用一个否定的确认（NAK）对校验出错或疑为丢失的帧进行确认，以便发送端尽快重传该帧。y当接收窗口很大时，这种方法要求接收端有较大的内存，但它不浪费带宽。选择重传示意图有限序号与窗口限制z 使用Go Back N协议，发送窗口的大小不能超过 2n-1。z 使用选择重传协议，若发送窗口与接收窗口大小相同，则发送窗口的大小不能超过2n-

13、1。4. 数据链路协议举例z高级数据链路控制（HDLC）z点到点协议（PPP）4.1 HDLCz 帧结构：y标志：01111110，标识一帧的开始与结束，以及作为帧间填充。y地址：在点到多点线路中用于指明通信的终端地址，在点到点线路中用于区分命令和响应。y控制：用于构成各种命令和响应，对链路进行监控。y信息：可以是任意的二进制比特串。y校验：CRC码，对两个标志之间的帧内容进行校验。帧类型z 信息帧：y以控制字段的第一比特为“0”标志。y用于传送数据，数据放在信息字段中。y采用滑动窗口协议，N(S)为发送序号，N(R)为捎带确认。帧类型（续）z 监视帧：y以控制字段的第一、二比特为“10”标志

14、。y用于差错控制和流量控制，没有信息字段。yS1S2：决定监控帧的类型 类型0：接收准备好 类型1：否定确认 类型2：接收未准备好 类型3：选择拒绝帧类型（续）z 无编号帧：y以控制字段的第一、二比特为“11”标志。y提供链路的建立、拆除及其它控制功能。y不包含 N(S) 或 N(R) 字段。y M1M5：修正位，构成各种链路命令和响应HDLC的访问规程z链路层的操作分为三个阶段：y建立链路：一方发送一个置模式命令，另一方发送UA帧进行响应，并初始化链路变量。y传输信息：x双方使用滑动窗口协议进行数据传输控制；x对收到的信息帧使用捎带确认或监视帧进行响应；x对检测到错误的帧使用否定确认或选择拒绝要求重发；x未准备好接收下一帧时，用接收未准备好暂停对方的发送。y断开链路：一方发送一个断连命令，另一方用一个UA帧进行响应。4.2 PPP协议zPPP是因特网中广泛使用的点到点