建设英文品牌网站,中信建设有限责任公司是央企吗,页面设计在哪里找,易网网站多少哈工大计算机网络传输层详解之#xff1a;流水线机制与滑动窗口协议
哈工大计算机网络课程传输层协议详解之#xff1a;可靠数据传输的基本原理哈工大计算机网络课程传输层协议详解之#xff1a;TCP协议哈工大计算机网络课程传输层协议详解之#xff1a;拥塞控制原理剖析 …哈工大计算机网络传输层详解之流水线机制与滑动窗口协议
哈工大计算机网络课程传输层协议详解之可靠数据传输的基本原理哈工大计算机网络课程传输层协议详解之TCP协议哈工大计算机网络课程传输层协议详解之拥塞控制原理剖析
在上一节中我们逐步分析了可靠传输协议的设计过程最后讲到rdt3.0的设计和实现机制。但是rdt3.0为了实现可靠性牺牲了很大一部分性能其中最主要的原因就在于停止等待协议在发送完数据后发送端需要等待至少RTT后才能收到ACK期间什么都不能做。
因此我们需要设计方案来解决这个问题这就是本节所讲述的内容。
流水线机制提高资源利用率 在之前的停止等待协议中发送端每发送一个数据包都会等待至少RTT的时间。现在采用流水线机制每一次发送端多发送几个数据包比如上图中的发送3个数据包。即每次发送端发完3个数据包后再执行停止等待协议此时的发送方利用率发送方发送时间百分比就相当于原先的3倍。
流水线协议
现在利用流水线机制允许发送方在发送完数据包后不用立即停止等待而是可以在发送多个数据包后再执行停止等待协议等待每个数据包的ACK反馈。
允许发送方在收到ACK之前连续发送多个分组
需要更大的序列号范围只有原先的0和1显然是不够了发送方和/或接收方需要更大的存储空间以缓存分组。原来的接收方只需要一个分组的存储空间但是现在需要多个分组的缓存空间。 左边就是只有一个数据包发送的过程。右图就是流水线机制下多个数据包的发送和接收。
滑动窗口协议
窗口用来管理那些发送端已经发出但还未来得及确认的数据包。
允许使用的序列号范围每个数据包都对于一个序列号因此滑动窗口中是已发送的数据包也就表示使用的序列号范围窗口尺寸为N最多有N个等待确认的消息。N也表示发送端一次允许发送的最大数据包个数。
滑动窗口随着协议的运行窗口在序列号空间内向前滑动
滑动窗口协议GBN、SR 如上图所示窗口左边表示的是已经发送且已经得到ACK确认的数据分组。 黄色部分表示已经发送带还没确认的数据分组。蓝色则表示还可以使用的序列号范围最大为N蓝色表示接下来发送可以使用的序列号范围。当蓝色部分用完后就必须等待窗口内的数据包得到ACK确认后窗口继续右移来发送加下来的序列号数据包。
接下来我们分别对GBN和SR两种滑动窗口协议进行介绍介绍其实现原理和区别便于我们理解滑动窗口协议的改进。
滑动窗口协议Go-Back-N协议GBN
发送方
分组头部包含k-bit序列号窗口尺寸为N最多允许N个分组未确认。 如上所述窗口左边的绿色部分表示已经获得ACK确认的数据分组。黄色的表示已经发送但未ACK确认的分组蓝色部分表示继续发送分组可使用的序列号范围比如此时如果需要再发送一个数据分组使用的序列号就是图中nextseqnum对于的序列号值。最右边的白色是还不能使用的序列号需要等待窗口滑动右移才能到达。
累计确认机制
对于GBN协议来说发送端对于ACK的确认采用的是累计确认的方式。
ACKn表示确认到序列号n包含n的分组均已被正确接收。即n-1、n-2,…往前的分组都已经被正确接收了。为传输中的分组设置计数器timer超时(timeout)时间重传序列号大于等于n还未收到ACK的所有分组。
GBN发送方的有限状态机示例如下图所示 if(nextseqnum baseN)表示如果下一个序列号小于窗口的最大范围说明还可以继续发送数据包则取nextseqnum的序列号来构造数据包并发送。同时如果在窗口的最左侧时启动当前窗口内流水线发送数据包的定时器。可以看到整个窗口内发送数据包时只会有一个定时器。refuse_data如果窗口内的序列号已经用光了也就是发送的数据包序列号达到了窗口的最大值。此时发送方再需要发送数据包时会被拒绝refuse。timeout如果触发了timeout超时则会从窗口最左侧的数据包开始逐个重发知道窗口最右端。rdt_rcg notcorrupt由于是累计确认在收到ACKn后表示认到序列号n包含n的分组均已被正确接收此时起始偏移base会更新为所收到的确认号ACK(n)的值1n1。这里也就是窗口滑动的原理过程了。
GBN接收方的有限状态机示例如下图所示 ACK机制发送拥有最高序列号的、已被正确接收的分组的ACK累计重传机制
可能产生重复ACK只需要记住唯一的expectedseqnum。因为流水线机制可能会使到达接收方的数据包序列号乱序此时接收方只需记住期待接收的最大序列号即可比如期待序列号为5此时收到了一个序列号为7的数据包此时GBN会直接丢弃掉这些已经收到的但不是当前期望的分组序号。丢弃完后还是需要做ACK的所以重新确认序列号最大的按序到达的分组。比如上述例子的收到序列号7期望5应该确认的是序列号4因为5之前的都已经收到了。
乱序到达的分组
直接丢弃—接收方没有缓存重新确认序列号最大的、按序到达的分组
GBN示例 假定窗口的大小是4所以在发送方可以发送pkt0、pkt1、pkt2、pkt3发送完pkt3后达到了窗口的最大序列号因此发送端开始停止等待ACK反馈。
前两个pkt0、pkt1都正确到达了分组pkt2在发送过程中丢失了而pkt3也正确到达了接收端。在接收端接收到pkt0、pkt1之后接收端期望的序列号expectedseqnum应该为2而此时pkt3分组到达了接收端但不是接收端期望的序列号。按照上面的分析我们知道此时接收端会丢弃序列号3对应的分组然后发送一个ACK1的返回因为期望序列号是2所以发送ACK1表示序列号2前面的数据分组都收到了。
但是这个ACK1在返回时也不幸丢失了。由于pkt1的分组和该分组的ACK1的反馈被成功接收到了此时发送端的窗口就可以向右移动两位有了序列号来发送pkt4、pkt5。
在发送完pkt4、pkt5之后由于pkt2的ACK一直没有收到所以发送端触发了timeout超时又由于上一次接收到的最大ACK确认序列号为1即序列号为1和1之前的都已经确认了所以发送方会重发序列号为1之后的分组即上图中的pkt2、pkt3、pkt4、pkt5。对于接收方收到的重复分组会根据序列号进行去重所以不怕分组重复。
练习题 数据链路层采用后退N帧GBN协议发送方已经发送了编号为0~7的帧。当计时器超时时若发送方只收到023号帧的确认则发送方下需要重发的帧数是多少分别是哪几个帧
解 根据GBN协议工作原理GBN协议的确认是累计确认由于发送端已经得到的最大ACK确认序列号为3表示序列号3和之前的分组都已经确认即使ACK1的确认序列号可能在反馈途中丢失了。因此发送方需要重新下发的帧数是4个依次分别是4、5、6、7号帧。
滑动窗口协议Selective Repeat协议SR GBN有什么缺陷 通过上面的介绍也能发现GBN一个比较明显的缺陷就是当需要重传时可能一次会重传很多个分组比如当某个序列号n的分组丢失时发送端会重传序列号n和n之后到窗口右侧最大序列号之间的数据分组。 这会导致网络中充斥着很多这些不必要的重复分组造成网络拥塞性能变差。所以一个显然的改进就是我们不使用累计确认机制而是对每个分组单个确认同时不丢弃那些乱序的分组接收端缓存起来。
SR协议
接收方
接收方对每个分组单独进行确认。只要这个分组到达就会返回一个ACK确认。这点跟GBN的不同在于GBN的确认是累计确认在确认时会有一个期望序列号expectedseqnum对于接收端接收到的分组序号不是期望序号的是直接丢弃不返回ACK的。只有在是期望序号时才返回对应序号的ACK并便是这个序号之前的分组都正确收到了这是上面GBN采用的ACK累计确认机制。接收方设置缓存机制缓存乱序到达的分组。 因为现在分组是乱序到达的还不是一个完整的数据报文所以不能直接向上交付需要先缓存起来。接收方也有一个窗口
发送方
发送方只重传那些没收到ACK的分组。发送方为每个分组设置单独的定时器。发送窗口包含N个连续的序列号限制已发送且未确认的分组。
SR协议中发送方和接收方的窗口如下所示 图b表示的是接收方的窗口。接收方的窗口大小也是N窗口前面是那些已经按序到达成功交付的数据分组。窗口里的灰色部分表示接收方期望收到的但是还没收到的分组序号。红色的则表示那些乱序到达的分组这些乱序到达的分组此时接收方会缓存起来并返回ACK。蓝色的部分表示接收方可以接收的序列号范围。
从上两个图可以发现在SR协议中发送方和接收方的窗口不是同步的发送方的窗口可能是滞后于接收端的因为可能某些已发送的分组还没收到ACK。
SR协议的整体逻辑如下所示
对于发送方来说如果窗口内收到了序列号为N的ACK且该序列号是窗口中最小序列号的还没被ACK确认的序列号则此时该分组确认后窗口会向右滑动到下一个还没确认ACK的序列号最小的分组位置。对于接收方来说如果接收到的分组序列号是在接收窗口序列号范围内的会对该分组返回ACK如果这个分组是乱序到达的则缓存起来。如果是按序到达的则跟其它按序到达的分组拼接起来并且如果这个分组序号是接收端窗口中的未接收的最小序号则窗口向右移动到下一个还未接收的最小序号位置。如果接收端接收到的分组序号不在接收端窗口范围内同样要发送ACK。因为这种情况可能是之前返回的ACK丢失了发送端触发了超时操作重传了分组因此这种情况仍然要重新发ACK。
SR协议示例 上图中发送方连续发送pkt0~pkt3的数据分组首先接收方接收接收到pkt0向上层交付并返回ACK0同时窗口右移。pkt1同理。但是pkt2在发送过程中丢失了接收方接收端乱序到达的pkt3。因此SR协议的独立确认机制此时接收方会返回对pkt3的确认ACK。当发送方收到pkt0、pkt1的确认ACK后同样的窗口会右移继续发送数据pkt4、pkt5。由于pkt2的ACK一直没有返回因此发送方的窗口最左侧移动到序号2的位置就不动了。在这个过程中接收方会接收到发送方窗口右移后的pkt4、pkt5的数据分组由于SR协议有缓存机制因此会对乱序到达的分组缓存起来并返回对应序号的确认ACK。但此时由于窗口中序列号最小的pkt2还未接收到所以接收端窗口不会右移。终于发送端pkt2分组的定时器超时了触发重传。等到pkt2到达接收端后由于这个序号是窗口内最小未到达的序号并且其他序号的分组都已经收到了此时接收方会将窗口内的分组一起交付给上层。同时窗口会右移到下一个未接收的最小序列号的位置也就是pkt6的位置如上右图最下边所示。对于发送端来说第二次对于pkt2分组的确认ACK被正确收到了那么窗口也会右移到下一个最小未确认ACK的序号所在的位置也就是pkt6的位置。
SR困境 上图给出了a、b两种场景图中窗口大小是3序列号只包括0、1、2、3四个序列号循环使用。思考接收方能区分开上面两种不同的场景吗
在a场景中接收方对pkt0、1、2的ACK都丢失了在超时后发送端会重发pkt0在b场景中接收方在收到ack0、1确认后窗口右移并继续发送后面的pkt3、pkt0而这时pkt3的分组丢失了。两种场景的共性在于接收端的窗口位置一样而且在某一时刻接收端都接收到了一个pkt0的分组。
那么在a场景中发送方重发分组0接收方收到后会如何处理
从上帝视角我们直到这两种场景是不一样的a场景中的pkt0是重传而b场景下的分组是正常的数据分组。但是接收端并不能区分这两种场景就有可能导致错误。比如在a场景下接收端可能以为这次收到的pkt0是正常的数据分组进行了接收并按序向上交付。但此时这个分组并不是正确按序到达的分组就会导致上层数据解析错误。
之所以会导致上述的问题显而易见是由于我们的序号太少而窗口尺寸相对序号又比较大。因此在SR协议中需要考虑序号个数与窗口大小之间的关系。 序列号个数与窗口尺寸需满足什么关系 NsNr 2k
上式中k表示序列号的位数Ns表示发送方窗口尺寸Nr表示接收方窗口尺寸。
