计算机网络课程详细3

第三章数据链路层1组帧（framing）使用字节（字符）填充的首尾标记法：使用特殊的字节来表示帧的开始与结束为避免在数据部分出现这些特殊字节时产生异义，在特殊字节前插入转义字符，称为字节填充（bytestuffing）该方法依赖于特定的字符编码集，帧长必须是8比特的整倍数，灵活性差，处理开销大（必须由软件处理）。字节填充图例(a)Aframedelimitedbyflagbytes(b)Fourexamplesofbytesequencesbeforeandafterstuffing.比特填充图例(a)Theoriginaldata.(b)Thedataastheyappearontheline.(c)Thedataastheyarestoredinreceiver’smemoryafterdestuffing.2检错和纠错传输出错的类型单个错：由随机的信道热噪声引起，一次只影响1位。突发错：由瞬间的脉冲噪声引起，一次影响许多位。用突发长度表示突发错影响的最大数据位数。差错编码的类型检错码：只能检测到数据传输发生了错误，但无法自行纠正，通常与反馈重传结合起来进行差错恢复。纠错码：不权能够检测出数据传输发生了错误，而且能够自行纠正错误。如何检测与纠正错误？码字（codeword）：由m比特的数据（消息）加上r比特的冗余（校验位）构成。有效编码集：由2m个（符合编码规则的）有效码字组成。检错：当收到的码字为无效码字时，称检测出错误。海明距离（HammingDistance）：两个码字的对应位上取值不同的位数。纠错：将收到的无效码字纠正到距其最近的有效码字。检错码与纠错码的能力都是有限的。2.2循环冗余码（CRC码）CRC是一种多项式编码，它将位串看成是某个一元多项式的系数，如1011001看成是一元多项式X6+X4+X3+1的系数。信息多项式M(x)：由m个信息比特为系数构成的多项式。冗余多项式R(x)：由r个冗余比特为系数构成的多项式。码多项式T(x)：在m个信息比特后加上r个冗余比特构成的码字所对应的多项式，表达式为T(x)=xr·M(x)+R(x)。生成多项式G(x)：双方预先确定用来计算R(x)的一个多项式。编码方法：用对应于G(x)的位串去除对应于xr·M(x)的位串，所得的余式即为R(x)，将其附加到信息比特串的后面一起发送。检错方法：用对应于G(x)的位串去除对应于T(x)的位串，若余式为0则认为传输正确，否则认为传输错误。CRC码检错能力强，实现简单快捷，是应用最广泛的检错码。CRC编码及校验例1：G(X)=X4+X+1，对10110011进行CRC编码，为101100110100。例2：仍取G(X)=X4+X+1，判断收到的位串100101111001是否有错？1011001100001001110101100100111010110011110101001110010100110100(a)计计计计计CRC计1001011110011001110001110100111001111111100111100010110100111011计3-6CRC计计计计(b)计计计计计计计计3可靠交付差错恢复的两种办法：使用纠错码，由接收端自动纠正错误。使用检错码，采用自动重传请求（ARQ）保证可靠交付。这是数据链路层（及传输层）上最常使用的可靠交付方式。自动重传请求（AutomaticRepeatRequest）：使用确认和超时实现可靠传输的策略。两种ARQ方案：停-等算法滑动窗口算法3.1停-等算法（stop-and-wait）基本思想：发送方发完一帧后即停下来等待确认，同时启动一个定时器；如果收到确认，复位定时器，发送下一个帧；如果定时器超时，重发刚才的帧。停-等算法的四种情形。停-等算法的超时值对性能影响很大，必须仔细选择。为区分新帧和重发帧，停-等算法使用一比特的帧序号。停-等算法的四种情形时间帧确认超时发送方接收方发送方接收方帧确认帧确认超时超时a)确认在超时前收到c)确认丢失发送方接收方帧帧确认超时超时b)原始帧丢失发送方接收方帧确认帧确认超时超时d)超时过快发生图3-7停等算法的4种不同情形的时间线停-等算法的处理流程发送端：1）帧序号seq初始化为0。2）从缓冲区中取出一个帧，以seq作为帧序号发送。3）启动定时器，等待确认：i）收到确认帧，且seq≠ack，则seq加1；从缓冲区中取出一个新的帧，加上seq发送。ii）收到确认帧，但seq=ack，重发当前序号的帧。iii）收到错误的确认帧，重发当前序号的帧。iv）定时器超时，重发当前序号的帧。4）回到3）接收端：1）帧序号ack初始化为0，准备接收序号为0的帧。2）等待接收。3）帧到达，有以下三种情况：i）帧校验正确，且seq=ack，将帧存入接收缓冲区；ack加1，放入确认帧中发送，确认帧中的序号表明当前期待接收的帧。ii）帧校验正确，但seq≠ack，丢弃帧，重发确认帧。iii）帧校验错误，丢弃帧，重发确认帧。4）回到2）停-等算法的处理流程发送端：1）帧序号seq初始化为0。2）从缓冲区中取出一个帧，以seq作为帧序号发送。3）启动定时器，等待确认：i）收到确认帧，且seq≠ack，seq加1；从缓冲区中取出一个新的帧，加上seq发送。ii）其它情况，重发当前序号的帧。4）回到3）接收端：1）帧序号ack初始化为0。2）等待接收。3）帧到达：i）帧校验正确，且seq=ack，将帧存入接收缓冲区；ack加1，放入确认帧中发送。ii）其它情况，丢弃帧，重发确认帧。4）回到2）3.2滑动窗口（slidingwindow）滑动窗口的本质是，发送端在收到确认之前可以发送多个帧。问题：某个帧出错或丢失怎么处理？接收端是否接收后续帧？发送端只重发出错帧，还是重发从出错帧开始的所有后续帧？若只重发出错帧，帧的顺序如何保证？发送端一次可以发送多少个帧？滑动窗口协议的功能滑动窗口是计算机网络中最著名的算法之一，它可以应用在数据链路层及传输层，用来完成三个不同的任务：在不可靠的链路（网络）上可靠地传输数据保持数据的传输顺序支持流量控制在数据链路层上，以上三个功能组合在一个滑动窗口协议中。发送窗口的概念发送窗口：包含一组帧序号，这些帧已发送但尚未被确认。发送窗口的三个要素：窗口下沿：最早发送但尚未被确认的帧。窗口上沿：最近发送的帧。窗口的最大值：一次最多允许发送的帧数。发送窗口如何变化：窗口未达到最大值，且要发送一个新的帧时，窗口上沿向前推进一个序号（序号加1后模2n）。收到窗口下沿帧的确认时，窗口下沿向前推进一个序号（将已被确认的帧移出发送窗口）。发送窗口中的帧都保留在缓冲区里以备重传，当某个帧被移出发送窗口时，同时从缓冲区中删除。发送窗口和接收窗口图示接收窗口的概念接收窗口：允许接收的帧序号。凡落在接收窗口内的帧必须接收，落在窗口外的帧被丢弃。接收窗口的大小：固定不变，总是保持初始时的大小。接收窗口如何变化：当窗口下沿帧被正确接收后，窗口整体向前滑动一个序号。数据链路层什么时候将帧递交到网络层？仅当窗口下沿帧正确接收后，链路层才将帧递交给网络层，因此帧总是按顺序被递交到网络层。捎带确认（piggybacking）捎带确认：在双向通信过程中，接收端可以将确认序号携带在数据帧中传输，提高传输效率。捎带确认带来的问题：当需要发送确认时数据尚未准备好，怎么办？推迟确认：让确认信息推迟一小段时间再发送；若数据仍未准备好，接收端发送一个单独的确认帧。推迟确认带来的问题：如何对正确收到的若干个帧同时进行确认？接收端通常用对某一个帧的确认来表示对该帧之前的所有帧进行确认。这也解释了为什么接收端仅当收到窗口下沿帧的时候才能发送确认。两种滑动窗口协议问题：当采用滑动窗口技术连续发送很多帧时，如果某个帧出现了传输错误怎么处理？两种解决方案：回退n帧（gobackn）选择重传（selectiverepeat）选择重传设计思想：当接收端收到一个出错帧或乱序帧时，后续到达的帧只要校验正确且落在接收窗口内，都放入接收缓冲区中；发送端超时后只重传最早发送但未被确认的帧。该策略对应接收窗口大于1的情况。加快重传：选择重传通常使用一个否定的确认（NAK）对校验出错或丢失的帧进行确认，以便发送端尽快重传该帧。当接收窗口很大时，这种方法要求接收端有较大的内存，但它不浪费带宽。选择重传示意图0123452678910111213141501891011121314EAck0Ack1Ack8Ack9Ack10Ack11Ack12Ack13计计计计计计计计3-10计计计计计计计345267Ack1Nak2Ack1Ack5Ack6Ack7帧的序号空间与发送窗口大小发送窗口的最大值受制于哪些因素？接收端处理能力（与接收端有关）延迟-带宽乘积（与信道有关）帧的序号空间（与协议有关）（√）问题：给定帧的序号空间，如何设置发送窗口的大小才能避免因序号重用出现的混乱？对于给定的帧序号空间，不同滑动窗口协议的发送窗口大小有不同的限制。GoBackn的发送窗口最大值使用GoBackn协议，发送窗口的大小不能超过2n-1。用一个反例说明：若n=3，发送窗口大小取为23=8，考虑如下情形：发送方连续发送序号从0~7的8个帧，等待确认；接收方正确收到这8个帧，对最大序号7进行确认；发送方有两种情况：收到确认，发送序号为0~7的8个新帧；因确认丢失而超时，重发8个老帧；接收方无法判断收到的是8个新帧还是重发的8个老帧。GoBackn的发送窗口大小（续）若发送窗口大小取为7，以上问题不会发生：发送方发送序号从0~6的7个帧，等待确认；接收方正确收到这7个帧，对最大序号6进行确认，并准备接收序号为7的帧（接收窗口仅包含序号7）；发送方有两种情况：收到确认，发送序号为7及0~5的7个新帧；因确认丢失超时，重发序号为0~6的7个老帧；接收方处理：收到序号为7的帧，表明这一批是新帧，接收，对序号5确认；没有收到序号为7的帧（重传帧，或是序号为7的帧丢失），不予接收，重发对序号6的确认。发送方处理：确认序号在发送窗口内：取下一批数据帧发送；确认序号不在发送窗口内或超时：重传发送窗口内的帧。选择重传协议的发送窗口大小使用选择重传协议，若发送窗口与接收窗口大小相同，则发送窗口的大小不能超过2n-1。用一个反例说明：若n=3，且发送窗口大小取为7，考虑以下情形：发送方：连续发送序号从0~6的7个帧，等待确认；接收方：正确收到这7个帧，对序号6进行确认，并准备接收序号为7和0~5的帧（接收窗口中包含序号7、0~5）；确认丢失，发送方超时后重发序号为0的帧；接收方：帧0落在接收窗口内，接收下来，并发送NAK7；发送方：收到NAK7，知道0~6的7个帧已全部收到，另取7个新帧，编号为7和0~5，发送；接收方：丢弃序号为0的帧，接收其余的5个帧。选择重传协议的发送窗口大小（续）若发送窗口大小取为4，以上问题不会发生：发送方：发送序号从0~3的4个帧，等待确认；接收方：正确收到这4个帧，对序号3进行确认，并准备接收序号为4~7的帧（接收窗口包含序号4~7）；确认丢失，发送方超时后重发序号为0的帧；接收方：帧0不在接收窗口内，丢弃，发送NAK4；发送方：收到NAK4，知道0~3已全部收到，另取4个新帧，编号为4~7，发送；接收方：接收序号为4~7的帧。滑动窗口的总结（1）使用前提：信号传播延迟远大于帧的发送时间。从实现的角度看，发送窗口相当于维护了一个环形的发送缓冲区：head为窗口上沿tail为窗口下沿环的大小等于帧的序号空间窗口操作：发送一个帧：移动head，将帧插入head的位置；收到tail帧的确认：移动tail，释放缓冲空间；当head与tail之间只有一个空闲缓