计算机网络课程详细3

1、第三章 数据链路层1 组帧（framing）z使用字节（字符）填充的首尾标记法：y使用特殊的字节来表示帧的开始与结束y为避免在数据部分出现这些特殊字节时产生异义，在特殊字节前插入转义字符，称为字节填充（byte stuffing）y该方法依赖于特定的字符编码集，帧长必须是8比特的整倍数，灵活性差，处理开销大（必须由软件处理）。字节填充图例(a) A frame delimited by flag bytes(b) Four examples of byte sequences before and after stuffing.比特填充图例(a) The original data.(b) T

2、he data as they appear on the line.(c) The data as they are stored in receivers memory after destuffing.2 检错和纠错z传输出错的类型y单个错：由随机的信道热噪声引起，一次只影响1位。y突发错：由瞬间的脉冲噪声引起，一次影响许多位。用突发长度表示突发错影响的最大数据位数。z差错编码的类型y检错码：只能检测到数据传输发生了错误，但无法自行纠正，通常与反馈重传结合起来进行差错恢复。y纠错码：不权能够检测出数据传输发生了错误，而且能够自行纠正错误。如何检测与纠正错误？z 码字（codeword）：

3、由m比特的数据（消息）加上r比特的冗余（校验位）构成。z 有效编码集：由2m个（符合编码规则的）有效码字组成。z 检错：当收到的码字为无效码字时，称检测出错误。z 海明距离（Hamming Distance）：两个码字的对应位上取值不同的位数。z 纠错：将收到的无效码字纠正到距其最近的有效码字。z 检错码与纠错码的能力都是有限的。2.2 循环冗余码（CRC码）z CRC是一种多项式编码，它将位串看成是某个一元多项式的系数，如1011001看成是一元多项式X6 + X4 + X3 + 1的系数。z 信息多项式M(x)：由m个信息比特为系数构成的多项式。z 冗余多项式R(x)：由r个冗余比特为系数

4、构成的多项式。z 码多项式T(x)：在m个信息比特后加上r个冗余比特构成的码字所对应的多项式，表达式为T(x) = xrM(x) + R(x)。z 生成多项式G(x)：双方预先确定用来计算R(x)的一个多项式。z 编码方法：用对应于G(x)的位串去除对应于xrM(x)的位串，所得的余式即为R(x)，将其附加到信息比特串的后面一起发送。z 检错方法：用对应于G(x)的位串去除对应于T(x)的位串，若余式为0则认为传输正确，否则认为传输错误。z CRC码检错能力强，实现简单快捷，是应用最广泛的检错码。CRC编码及校验z 例1：G(X) = X4 + X + 1，对10110011进行CRC编码，为

5、101100110100。z 例2：仍取G(X) = X4 + X + 1，判断收到的位串100101111001是否有错？ 3 可靠交付z差错恢复的两种办法：y使用纠错码，由接收端自动纠正错误。y使用检错码，采用自动重传请求（ARQ）保证可靠交付。这是数据链路层（及传输层）上最常使用的可靠交付方式。z自动重传请求（Automatic Repeat Request）：y使用确认和超时实现可靠传输的策略。z两种ARQ方案：y停-等算法y滑动窗口算法3.1 停-等算法（stop-and-wait）z 基本思想：y发送方发完一帧后即停下来等待确认，同时启动一个定时器；y如果收到确认，复位定时器，发送

6、下一个帧；y如果定时器超时，重发刚才的帧。z 停-等算法的四种情形。z 停-等算法的超时值对性能影响很大，必须仔细选择。z 为区分新帧和重发帧，停-等算法使用一比特的帧序号。停-等算法的四种情形停-等算法的处理流程发送端：1）帧序号seq初始化为0。2）从缓冲区中取出一个帧，以seq作为帧序号发送。3）启动定时器，等待确认： i）收到确认帧，且seqack，则seq加1；从缓冲区中取出一个新的帧，加上seq发送。 ii）收到确认帧，但seq = ack，重发当前序号的帧。 iii）收到错误的确认帧，重发当前序号的帧。 iv）定时器超时，重发当前序号的帧。4）回到3） 接收端：1）帧序号ack初

7、始化为0，准备接收序号为0的帧。 2）等待接收。 3）帧到达，有以下三种情况： i）帧校验正确，且seq = ack，将帧存入接收缓冲区；ack 加 1，放入确认帧中发送，确认帧中的序号表明当前期待接收的帧。 ii）帧校验正确，但seqack，丢弃帧，重发确认帧。 iii）帧校验错误，丢弃帧，重发确认帧。4）回到2）停-等算法的处理流程发送端：1）帧序号seq初始化为0。2）从缓冲区中取出一个帧，以seq作为帧序号发送。3）启动定时器，等待确认： i）收到确认帧，且seqack，seq加1；从缓冲区中取出一个新的帧，加上seq发送。 ii）其它情况，重发当前序号的帧。4）回到3） 接收端：1）

8、帧序号ack初始化为0。 2）等待接收。 3）帧到达： i）帧校验正确，且seq = ack，将帧存入接收缓冲区；ack 加 1，放入确认帧中发送。 ii）其它情况，丢弃帧，重发确认帧。4）回到2）3.2 滑动窗口（sliding window）z滑动窗口的本质是，发送端在收到确认之前可以发送多个帧。z问题：y某个帧出错或丢失怎么处理？x接收端是否接收后续帧？x发送端只重发出错帧，还是重发从出错帧开始的所有后续帧？x若只重发出错帧，帧的顺序如何保证？y发送端一次可以发送多少个帧？滑动窗口协议的功能z滑动窗口是计算机网络中最著名的算法之一，它可以应用在数据链路层及传输层，用来完成三个不同的任务：

9、y在不可靠的链路（网络）上可靠地传输数据y保持数据的传输顺序y支持流量控制z在数据链路层上，以上三个功能组合在一个滑动窗口协议中。发送窗口的概念z 发送窗口：包含一组帧序号，这些帧已发送但尚未被确认。z 发送窗口的三个要素：y窗口下沿：最早发送但尚未被确认的帧。y窗口上沿：最近发送的帧。y窗口的最大值：一次最多允许发送的帧数。z 发送窗口如何变化：y窗口未达到最大值，且要发送一个新的帧时，窗口上沿向前推进一个序号（序号加1后模2n）。y收到窗口下沿帧的确认时，窗口下沿向前推进一个序号（将已被确认的帧移出发送窗口）。z 发送窗口中的帧都保留在缓冲区里以备重传，当某个帧被移出发送窗口时，同时从缓冲

10、区中删除。发送窗口和接收窗口图示接收窗口的概念z 接收窗口：允许接收的帧序号。凡落在接收窗口内的帧必须接收，落在窗口外的帧被丢弃。z 接收窗口的大小：固定不变，总是保持初始时的大小。z 接收窗口如何变化：y当窗口下沿帧被正确接收后，窗口整体向前滑动一个序号。z 数据链路层什么时候将帧递交到网络层？y仅当窗口下沿帧正确接收后，链路层才将帧递交给网络层，因此帧总是按顺序被递交到网络层。捎带确认（piggybacking）z 捎带确认：y在双向通信过程中，接收端可以将确认序号携带在数据帧中传输，提高传输效率。z 捎带确认带来的问题：y当需要发送确认时数据尚未准备好，怎么办？z 推迟确认：y让确认信息

11、推迟一小段时间再发送；若数据仍未准备好，接收端发送一个单独的确认帧。z 推迟确认带来的问题：y如何对正确收到的若干个帧同时进行确认？z 接收端通常用对某一个帧的确认来表示对该帧之前的所有帧进行确认。这也解释了为什么接收端仅当收到窗口下沿帧的时候才能发送确认。两种滑动窗口协议z 问题：y 当采用滑动窗口技术连续发送很多帧时，如果某个帧出现了传输错误怎么处理？z 两种解决方案：y 回退 n帧（go back n）y 选择重传（selective repeat）选择重传z 设计思想：y当接收端收到一个出错帧或乱序帧时，后续到达的帧只要校验正确且落在接收窗口内，都放入接收缓冲区中；y发送端超时后只重传

12、最早发送但未被确认的帧。z 该策略对应接收窗口大于1的情况。z 加快重传：y选择重传通常使用一个否定的确认（NAK）对校验出错或丢失的帧进行确认，以便发送端尽快重传该帧。z 当接收窗口很大时，这种方法要求接收端有较大的内存，但它不浪费带宽。选择重传示意图帧的序号空间与发送窗口大小z 发送窗口的最大值受制于哪些因素？y接收端处理能力（与接收端有关）y延迟-带宽乘积（与信道有关）y帧的序号空间（与协议有关）（）z 问题：y给定帧的序号空间，如何设置发送窗口的大小才能避免因序号重用出现的混乱？z 对于给定的帧序号空间，不同滑动窗口协议的发送窗口大小有不同的限制。Go Back n的发送窗口最大值z

13、使用Go Back n协议，发送窗口的大小不能超过2n-1。z 用一个反例说明：若n = 3，发送窗口大小取为23 = 8，考虑如下情形：y发送方连续发送序号从07的8个帧，等待确认；y接收方正确收到这8个帧，对最大序号7进行确认；y发送方有两种情况：x收到确认，发送序号为07的8个新帧；x因确认丢失而超时，重发8个老帧；y接收方无法判断收到的是8个新帧还是重发的8个老帧。Go Back n的发送窗口大小（续）z 若发送窗口大小取为7，以上问题不会发生：y发送方发送序号从06的7个帧，等待确认；y接收方正确收到这7个帧，对最大序号6进行确认，并准备接收序号为7的帧（接收窗口仅包含序号7）；y发

14、送方有两种情况：x收到确认，发送序号为7及05的7个新帧；x因确认丢失超时，重发序号为06的7个老帧；y接收方处理：x收到序号为7的帧，表明这一批是新帧，接收，对序号5确认；x没有收到序号为7的帧（重传帧，或是序号为7的帧丢失），不予接收，重发对序号6的确认。y发送方处理：x确认序号在发送窗口内：取下一批数据帧发送；x确认序号不在发送窗口内或超时：重传发送窗口内的帧。选择重传协议的发送窗口大小z 使用选择重传协议，若发送窗口与接收窗口大小相同，则发送窗口的大小不能超过2n-1。z 用一个反例说明：若n = 3，且发送窗口大小取为7，考虑以下情形：y发送方：连续发送序号从06的7个帧，等待确认；

15、y接收方：正确收到这7个帧，对序号6进行确认，并准备接收序号为7和05的帧（接收窗口中包含序号7、05）；y确认丢失，发送方超时后重发序号为0的帧；y接收方：帧0落在接收窗口内，接收下来，并发送NAK 7；y发送方：收到NAK 7，知道06的7个帧已全部收到，另取7个新帧，编号为7和05，发送；y接收方：丢弃序号为0的帧，接收其余的5个帧。选择重传协议的发送窗口大小（续）z若发送窗口大小取为4，以上问题不会发生：y发送方：发送序号从03的4个帧，等待确认；y接收方：正确收到这4个帧，对序号3进行确认，并准备接收序号为47的帧（接收窗口包含序号47）；y确认丢失，发送方超时后重发序号为0的帧；y

16、接收方：帧0不在接收窗口内，丢弃，发送NAK 4；y发送方：收到NAK 4，知道03已全部收到，另取4个新帧，编号为47，发送；y接收方：接收序号为47的帧。滑动窗口的总结（1）z 使用前提：信号传播延迟远大于帧的发送时间。z 从实现的角度看，发送窗口相当于维护了一个环形的发送缓冲区：yhead为窗口上沿ytail为窗口下沿y环的大小等于帧的序号空间z 窗口操作：y发送一个帧：移动head，将帧插入head的位置；y收到tail帧的确认：移动tail，释放缓冲空间；y当head与tail之间只有一个空闲缓冲区时：停止发送。滑动窗口的总结（2）z 从实现的角度看，接收窗口相当于维护了一个环形的接

17、收缓冲区：ytail为窗口下沿yhead为窗口上沿y环的大小等于帧的序号空间z 窗口操作：y收到一个帧：放入从head至tail之间的对应缓冲区中；y收到tail帧：将从tail开始的连续k个帧交给网络层，head和tail同时向前移动k个位置。滑动窗口的总结（3）z滑动窗口与停-等算法：y停-等算法可以看成是发送窗口和接收窗口均为1的滑动窗口算法；y滑动窗口要处理的问题比停-等算法复杂得多：x帧的乱序问题x发送端一次可以发送多少帧？5.1 High-level Data Link Control z 帧结构：y标志：01111110，标识一帧的开始与结束，以及作为帧间填充。y地址：在点到多点

18、线路中用于指明通信的终端地址，在点到点线路中用于区分命令和响应。y控制：用于构成各种命令和响应，对链路进行监控。y信息：可以是任意的二进制比特串。y校验：CRC码，对两个标志之间的帧内容进行校验。帧类型z 信息帧（Information frame）：y以控制字段的第一比特为“0”标志。y用于传送数据，数据放在信息字段中。y采用滑动窗口协议，N(S)为发送序号，N(R)为捎带确认的序号。HDLC的访问规程z链路层的操作分为三个阶段：y建立链路：一方发送一个置模式命令，另一方发送UA帧进行响应，并初始化链路变量。y传输信息：x双方使用滑动窗口协议进行数据传输控制；x对收到的信息帧使用捎带确认或监视帧进行响应；x对检测到错误的帧使用否定确认或选择拒绝要求重发；x未准备好接收下一帧时，用接收未准备好暂停对方的发送。y断开链路：一方发送一个断连命令，另一方用一个UA帧进行响应。PPP协议的组成zPPP由以下三部分组成：y一种在串行通信线路上的组帧方式，用于区分帧的边界，并可支持差错检测。y一个用于建立、配置、测试和拆除数据链路的链路控制协议LCP。y一组网络控制协议（NCP），用以支持