《计算机网络原理与技术(第二版)》第3章数据链路层.ppt

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

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

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

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

5、G(x) 的位串去除对应于 T(x) 的位串，若余式为0则认为传输正确，否则认为传输错误。 CRC码检错能力强，实现简单快捷，是应用最广泛的检错码。,CRC的编码及校验,例1：G(X) = X4 + X + 1，对10110011进行CRC编码。 例2：仍取G(X) = X4 + X + 1，判断收到的位串100101111001是否有错？,常见的CRC多项式,3. 可靠交付,差错恢复的两种办法： 使用纠错码，由接收端自动纠正错误。 使用检错码，采用自动重传请求（ARQ）保证可靠交付。这是数据链路层（及传输层）上最常使用的可靠交付方式。 两种ARQ算法： 停-等 滑动窗口,3.1 停-等算法,

6、基本思想：发送方发完一帧后即停下来等待确认；如果收到一个确认，接着发送下一个帧；如果定时器超时，重发刚才的帧。 停-等算法的四种情形。 停-等算法的超时值对性能影响很大，必须仔细选择。 为区分新帧和重发帧，停-等算法使用一比特的帧序号。,停-等算法的四种情形,停-等算法的过-发送方,1）帧序号初始化为0 2）从缓冲区中取出一个帧，加上当前帧序号发送。 3）等待确认 i）收到确认帧，且帧序号与当前维护的帧序号不同，将 帧序号加1，从缓冲区中取出一个新的帧，加上当前 帧序号发送。 ii）收到确认帧，且帧序号与当前维护的帧序号相同，重 发当前序号的帧。 iii）收到错误的确认帧，重发当前序号的帧。

7、iv）定时器超时，重发当前序号的帧。,停-等算法的过程-接收方,1）帧序号初始化为0（表示当前期望接收的帧序号） 2）等待接收 3）帧到达 i）帧校验正确，且序号为当前期望接收的帧序号，将帧 放入接收缓冲区，帧序号加1，放入确认帧中发送。 ii）帧校验正确，但序号与当前期望接收的帧序号不同， 丢弃帧，重发确认帧。 iii）帧校验错误，丢弃帧，重发确认帧。,信道利用率与流水线技术,停-等算法在传输延迟较长的信道上传输效率很低。 假如将链路看成是一根管道，数据是管道中流动的水，那么停-等算法无法使数据充满管道，因而信道利用率很低。 管道的容量通常用延迟-带宽乘积表示，它表示发送端在收到第一个帧的确

8、认前最多可以发送的数据量。 滑动窗口机制允许发送端连续发送多个帧来尽可能多地填充管道，从而提高信道的利用率。,3.2 滑动窗口,滑动窗口是计算机网络中最著名的算法，它可以应用在数据链路层及传输层，用来完成三个不同的任务： 在不可靠的链路（网络）上可靠地传输数据 保持数据的传输顺序 支持流量控制 在数据链路层上，以上三个功能组合在一个滑动窗口协议中。,发送窗口,发送窗口：发送端允许发送的帧序号表。 发送窗口大小：发送端最大允许的未确认帧数目。 发送窗口下沿：最早发送但尚未被确认的帧序号。 发送窗口上沿：（发送窗口下沿发送窗口大小1）mod 2n。 当收到对发送窗口下沿帧的确认时，发送窗口整体向前

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

10、接收窗口大小 = 发送窗口大小：意味着接收方可以不按顺序接收，但接收方交给上层实体的数据总是有序的。,捎带确认,捎带确认（piggybacking）：将确认序号携带在数据帧中传输，提高线路的效率。 推迟确认：当需要发送确认但没有要发送的数据时，可以让确认信息推迟一小段时间再发送；这一小段时间后若数据仍未准备好，接收端必须立即发送一个单独的确认帧。 接收端对正确收到的若干个帧同时进行确认，通常用对某一个帧的确认来表示对该帧之前的所有帧进行确认。,Go Back n,Go back n 当接收端收到一个出错帧或乱序帧时，丢弃所有的后继帧，并且不为这些帧发送确认；发送端超时后，重传所有未被确认的帧。

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

12、过 2n-1。 使用选择重传协议，若发送窗口与接收窗口大小相同，则发送窗口的大小不能超过2n-1。,4. 数据链路协议举例,高级数据链路控制（HDLC） 点到点协议（PPP）,4.1 HDLC,帧结构： 标志：01111110，标识一帧的开始与结束，以及作为帧间填充。 地址：在点到多点线路中用于指明通信的终端地址，在点到点线路中用于区分命令和响应。 控制：用于构成各种命令和响应，对链路进行监控。 信息：可以是任意的二进制比特串。 校验：CRC码，对两个标志之间的帧内容进行校验。,帧类型,信息帧： 以控制字段的第一比特为“0”标志。 用于传送数据，数据放在信息字段中。 采用滑动窗口协议，N(S)

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