流⽔线可靠数据传输协议；回退N步GBN（滑动窗⼝协议）；
选择重传SR
rdt 3.0 协议性能分析
假设有两台主机，分别位于美国西海岸和东海岸，它们之间的往返传播实验 RTT ⼤约为 30ms，假定它们通过⼀条速率 R 为 1Gbps 的信道相连。包括⾸部字段和数据的分组长 L 为 1000 bytes(8000 bits)，所以发送⼀个分组进⼊ 1Gbps 链路实际所需时间是： t_trans = L / R = (8000 bit/pkt) / (10^9 bit/s) = 8 μs/pkt
所以，如果发送端在 t = 0 时刻开始发送分组，则在 8μs 后，该分组全部进⼊了发送端信道。接着该分组经过 15ms 的旅途到达接收端，即该分组的最后 1 bit 在时刻 t = RTT/2 + L/R = 15.008ms 时到达接收端。假设 ACK 分组很⼩，可以忽略其发送时间，且接收端⼀旦收到⼀个数据分组的最后 1bit 后⽴刻发送 ACK，则 ACK 在时刻 t = RTT + L/R = 30.008ms 时回送到发送端。也就是说，经过30.008ms 后发送端才可以发送下⼀个分组。 设利⽤率为：发送端实际忙于将发送⽐特送进信道的那部分时间与发送时间之⽐。则
U_sender = (L/R) / (RTT + L/R) = 0.008 / 30.008 = 0.00027
可以看到，利⽤率极其低下，这是不可容忍的，所以我们需要改进性能。
流⽔线技术
流⽔线技术是解决这种特殊性能问题的⼀个⾮常简单的⽅法：不使⽤停等⽅式运⾏，允许发送端发送多个分组⽽⽆需等待确认。
虽然流⽔线可以直线提升 rdt 3.0 协议的性能，但是也会带来如下的影响：
必须增加序号的范围。因为每个传输中的分组（不计算重传的）必须有⼀个唯⼀的序号，⽽且也许有多个在输送中尚未确认的分组协议的发送端和接收端也必须缓存多个分组。发送⽅最低限度应当能缓冲那些已发送但没有确认的分组，接收⽅或许也需要缓存那些已正确接收的分组 所需序号范围和对缓冲的要求取决于数据传输协议如何处理丢失、损坏和延时过⼤的分组。
解决流⽔线的差错恢复有两种基本⽅法，分别为 回退 N 步（Go-Back-N, GBN） 和 选择重传（Selective Repeat, SR）。
GBN 协议（回退 N 步协议）
在 GBN 协议中，允许发送⽅发送多个分组（当有多个分组可⽤时）⽽不需等待确认，但它也受限于在流⽔线中未确认的分组数不能超过某个最⼤允许数 N。
上图显⽰了发送⽅看到的 GBN 协议的序号范围。将基序号（base）定义为最早的未确认分组的序号，将下⼀个序号（nextseqnum）定义为最⼩的未使⽤序号（即下⼀个待发分组的序号），则可将序号范围分割成 4 段。在 [0, base-1] 段内的序号对应于已经发送并确认的分组。[base, nextseqnum-1] 段对应已经发送但未被确认的分组。[nextseqnum, base+N-1] 段内的序号能⽤于那些要⽴即发送的分组，如果有数据来⾃于上层的话。最后，⼤于或等于 base+N 的序号是不能使⽤的，直到当前流⽔线中未确认的分组（特别是序号为 base 的分组）已得到确认为⽌。
在上图中，把 [base, base+N-1] 看做⼀个长度为 N 的窗⼝。随着协议的运⾏，该窗⼝在序号空间向前滑动。因此，N 常被称为窗⼝长度（window size），GBN 协议也常被称为滑动窗⼝协议（sliding-window protocol）。⾄于为什么需要限制 N 的范围，是因为这是流量控制的⽅法之⼀。
热熔铜螺母>管道防爬刺
在实践中，⼀个分组的序号承载在分组⾸部的⼀个固定长度的字段中。如果分组序号字段的⽐特数是 k，则该序号范围是 [0, 2^k - 1]。在⼀个有限的序号范围内，所有涉及序号的运算必须使⽤模 2^k 运算。
下图是GBN 协议发送⽅扩展 FSM 描述：
发送⽅必须响应三种类型的事件：
上层的调⽤。当上层调⽤ rdt_send() 时，发送⽅⾸先检查发送窗⼝是否已满，即是否有 N 个已发送但未被确认的分组。如果窗⼝未满，则产⽣⼀个分组并将其发送，并相应地更新变量。如果窗⼝已满，发送⽅只需将数据返回给上层，隐式地指⽰上层该窗⼝已满。然后上层可能会过⼀会⼉再试。在实际实现中，发送⽅更可能缓存这些数据，或者使⽤同步机制（如⼀个信号量或标志）允许上层在仅当窗⼝不满时才调⽤ rdt_send()。
收到⼀个ACK。在 GBN 协议中，对序号为 n 的分组的确认采取累积确认（cumulative acknowledgment）的⽅式，表明接收⽅已正确接收到序号为 n 的以前且包括 n 在内的所有分组。
棉花糖制造机
超时事件。协议的名字“回退 N 步”来源于出现丢失和时延过长分组时发送⽅的⾏为。就像在停等协议中那样，定时器将再次⽤于恢复数据或确认分组的丢失。如果出现超时，发送⽅重传所有已发送但未被确认过的分组。上图中发送⽅仅使⽤⼀个定时器，如果收到了⼀个 ACK，但仍有已发送但未被确认的分组，则定时器被重新启动。如果没有已发送但未被确认的分组，该定时器被终⽌。
下图是 GBN 协议接收⽅扩展 FSM 描述：
如果⼀个序号为 n 的分组被正确接收到，并且按序（即上次交付给上层的数据是序号为 n - 1 的分组），则接收⽅为分组 n 发送⼀个ACK，并将该分组中的数据部分交付到上层。
在所有其他情况下，接收⽅将丢弃该分组，并为最近按序接收的分组重新发送 ACK。
注意到因为⼀次交付给上层⼀个分组，如果分组 k 为已接受并交付，则所有序号⽐ k ⼩的分组也已经交付。因此，使⽤累积确认是 GBN 的⼀个⾃然的选择。
虽然 GBN 协议看起来很浪费，因为它会丢弃⼀个正确接收（但失序）的分组。但这样做是有道理的。因为接收⽅必须将数据按序交付给上层，假设现在期望接收分组 n，⽽分组 n + 1 却到了，因为数据必须按序交付，所以接收⽅可能缓存分组 n + 1，然后，在它收到并交付分组 n 后，再将该分组
交付到上层。但是，如果分组 n 丢失，则该分组及分组 n + 1 最终将在发送⽅根据 GBN 重传规则⽽被重传，所以，接收⽅只需要直接丢弃分组 n + 1 即可。
bimp
这种⽅法的优点是接收⽅不需要缓存任何失序分组，唯⼀需要维护的信息就是下⼀个按序接收的分组的序号。缺点就是随后对该分组的重传也许会丢失或出错，进⽽引发更多的重传。
可以看到，GBN 协议本⾝相对于 rdt 3.0 协议有了长⾜进步，但是仍然有它⾃⼰的性能问题，尤其是当窗⼝长度和带宽时延都很⼤的时，流⽔线中有很多分组更是如此。任何单个分组的差错就能引起 GBN 协议重传⼤量分组，事实上是很多分组根本没必要重传，所以，有了⼀个更加优化的协议，就是下⾯要说的 选择重传（SR） 协议。
SR 协议（选择重传协议）
SR 协议在 GBN 协议的基础上进⾏了改进，它通过让发送⽅仅重传那些它怀疑在接收⽅出错（即丢失或受损）的分组⽽避免了不必要的重传。选择重传协议只重传真正丢失的分组.
选择重传的接收窗⼝与发送窗⼝⼀样⼤.选择重传协议允许与接收窗⼝⼀样多的分组失序到达，并保存这些失序到达的分组，直到连续的⼀组分组被交付给应⽤层.因为发送窗⼝与接收窗⼝是相同的，所以发送出来的所有分组都可以失序到达,⽽且会被保留直到交付为⽌.但是必须强调⼀点，在⼀个可靠的协议中，接收⽅永远不会把分组失序地交给应⽤层.在他们被交付给应⽤层之前，先要等待那些更早发出来的分组到达.
计时器飞碟杯
理论上选择重传协议要为每个分组使⽤⼀个计时器.当某个计时器超时后，只有相应的分组被重传.换⽽⾔之，返回N协议将所有的分组当做⼀个整体对待,⽽选择重传协议则分别对待每⼀个分组.但是⼤多数SR的运输层仅使⽤了⼀个计时器. 注意只使⽤⼀个计时器⽽做到跟踪所有发出去的分组的情况的做法是：标记发出分组，当ACK=Sf 时，将窗⼝滑过所有连续的已确认的分组，如果还有未确认的分组，则重发所有检测到的未被确认的分组并重启计时器，如果所有分组都被确认了则停⽌计时器.
确认
在GBN中确认值(ACK) 是累计的，它定义了下⼀个希望接收的分组序号，同时也证实了此前所有的分组都已经被完好的接收了.在SR中，确认号(ACK)只定义完好接收的那⼀个分组的序号，并不反馈任何其他分组的信息.
下图描述了发送⽅与接收⽅的序号空间：
发送⽅的事件与动作：
从上层收到数据。当从上层接收到数据后，SR 发送⽅检查下⼀个可⽤于该分组的序号。如果序号位于发送⽅的窗⼝内，则将数据打包并发送；否则就像在 GBN 中⼀样，要么将数据缓存，要么将其返回给上层以便以后传输。
超时。定时器再次被⽤来防⽌丢失分组。然⽽，现在每个分组必须拥有其⾃⼰的逻辑定时器，因为超时发⽣后只能发送⼀个分组。
收到ACK。如果收到 ACK，倘若该分组序号在窗⼝内，则 SR 发送⽅将那个被确认的分组标记为已接收。若该分组的序号等于send_base，则窗⼝基序号向前移动到具有最⼩序号的未确认分组处。如果窗⼝移动了并且有序号落在窗⼝内的未发送分组，则发送这些分组。
接收⽅的事件与动作：
序号在 [rcv_base, rcv_base+N-1] 内的分组被正确接收。在此情况下，收到的分组落在接收⽅的窗⼝内，⼀个选择 ACK 被回送给发送⽅。如果该分组以前没收到过，则缓存该分组。如果该分组的序号等于接收端的基序号（rcv_base），则该分组以及以前缓存的序号连续的（起始于 rcv_base 的）分组交付给上层。然后，接收窗⼝按向前移动分组的编号向上交付这些分组。
序号在 [rcv_base-N, rcv_base-1] 内的分组被正确收到。在此情况下，必须产⽣⼀个 ACK，即使该分组是接收⽅以前确认过的分组。
其他情况。忽略该分组。
注意上⾯的第⼆步，接收⽅需要重新确认（⽽不是忽略）已收到过的那些序号⼩于当前窗⼝基序号的分组。为什么要返回 ACK？加⼊按照上图中所⽰的发送⽅和接收⽅的序号空间，如果分组 send_base 的 ACK 没有从接收⽅传播回发送⽅，则发送⽅最终将重传分组
send_base，即使显然接收⽅已经收了该分组。如果接收⽅不确认该分组，则发送⽅窗⼝将永远不能向前滑动。
上⾯的例⼦说明了对于 SR 协议（和很多其他协议⼀样） 对于哪些分组已经被正确接收，哪些没有，发送⽅和接收⽅并不总能看到相同的结果。也就是说，发送⽅和接收⽅的窗⼝并不总是⼀致。
窗⼝长度与序号空间⼤⼩
下⾯这个例⼦说明了，如果窗⼝长度与序号空间⼤⼩选择不当，将会产⽣严重的后果。
在这个例⼦中，有四个分组序号 0、1、2、3 且窗⼝长度为 3。假定发送了分组 0 ⾄ 2，并且接收⽅被正确接收且确认了。此时，接收⽅窗⼝落在 4、5、6 个分组上，其序号分别为 3、0、1.现在考虑两种情况。
在第⼀种情况下，如上图中的 a 图所⽰，对前 3 个分组的 ACK 丢失，因此发送⽅重传这些分组。因此，接收⽅下⼀步要接收序号为 0 的分组，即第⼀个发送分组的副本。
>罗口袜
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议