计算机网络（十七）：可靠数据传输原理
可靠数据传输的框架。为上层实体提供的服务抽象是:数据可以通过一条可靠的信道进行传输。借助于可靠信道，传输数据比特就不会受到损坏或丢失，而且所有数据都是按照其发送顺序迸行交付。这恰好就是TCP向调用它的因特网应用所提供的服务模型。
实现这种服务抽象是可靠数据传输协议。
由于可靠数据传输协议的下层协议也许是不可靠的，因此这是一项困难的任务。例如，TCP在不可靠的(IP)端到端网络层之上实现的可靠数据传输协议。
我们的协议也需要在发送端和接收端两个方向上传输分组。
1、构造可靠数据传输协议
a、经完全可靠信道的可靠数据传输：rdt 1.0
首先假设底层信道是完全可靠的。这里有一个有限状态机FSM。发送方和接收方有各自的FSM。
rdt的发送端只通过rdt_send(data)事件接受来自较高层的数据，产生一个包含该数据的分组(经由make_pkt(data)动作)，并将分组发送到信道中。 实际上，rdt_send(dala)事件是由较高层应用的过程调用产生的(例如， rdt_send())。
在接收端，rdt通过rdt_rcv(packet)事件从底层信道接收一个分组，从分组中取出数据(经由extract(packet，data)动作)，并将数据上传给较高层(通过deliver_data(data)动作)。实际上，rdt_rcv( packet)事件是由较低层协议的过程调用产生的(例如，rdt_rev())。
在这个简单的协议中，一个单元数据与一个分组没差别。而且，所有分组是从发送方流向接收方;有了完全可靠的信道，接收端就不需要提供任何反馈信息给发送方，因为不必担心出现差错。
注意到我们也已经假定了接收方接收数据的速率能够与发送方发送数据的速率一样快。因此，接收方没有必要请求发送方慢一点。
b、经具有比特差错信道的可靠数据传输：rdt 2.0
比特差错通常会出现在网络的物理部件中。
报文协议使用了肯定确认与否定确认这些控制报文，使得接收方可以让发送方知道哪些内容被正确接收，哪些内容接收有误并因此需要重复。
计算机网络环境中，基于这样重传机制的可靠数据传输协议称为自动重传请求协议ARQ。主要处理差错检测（需要额外的比特）、接收方反馈（反馈分组只需要一个比特长）、重传（发送发可以重传分组报文）
rdt 2.0的发送端有两个状态。
首先，发送端协议正等待来自上层传下来的数据。当产生rdt_send (data)事件时，发送方将产生一个包含待发送数据的分组，带有检验和，然后经由 udt_send(sndpkt)操作发送该分组。
然后，发送方协议等待来自接收方的ACK或NAK分组。如果收到一个ACK 分组，则发送方知道最近发送的分组已被正确接收，因此协议返回到等待来向上层的数据的状态。如果收到NAK分组，该协议重传最后一个分组并等待接收方的响应。当发送方处于等待ACK/NAK的状态时，它不能从上层获得更多的数据;仅当接收到ACK并离开该状态时才能发生这样的事件。因此发送方将不会发送一块新数据，除非发送方确信接收方已正确接收当前分组。由于这种行为，rdt2.0这样的协议被称为停等协议
rdt 2.0接收方的FSM仍然只有一个状态。当分组到达时，接收方要么回答一个ACK，要么回答一个NAK，这取决于收到的分组是再受损。
rdt2.0协议存在一个致命的缺陷，即没有考虑到ACK/ NAK分组受损的可能性。至少，我们需要在ACK/NAK分组中添加检验和比特以检测这样的差错。更难的问题是协议应该怎样纠正ACK/NAK分组中的差错。这里的难点在于，如果一个ACK/NAK分组受损，发送方无法知道接收方是否正确接收了上一块发送的数据。
解决这个新问题的一个简单方法是在数据分组中添加一新字段，让发送方对其数据分组编号，即将发送数据分组的序号放在该字段。于是，接收方只需要检查序号即可确定收到的分组是否一次重传。
协议rdt2.1使用了从接收方到发送方的肯定确认和否定确认。当接收到失序的分组时，接收方对所接收的分组发送一个肯定确认。如果收到受损的分组，则接收方将发送一个再定确认。
如果不发送NAK，而是对上次正确接收的分组发送一个ACK，我们也能实现与NAK一样的效果。发送方接收到对同一个分组的两个ACK(即接收和冗余 ACK)后，就知道接收方没有正确接收到跟在被确认两次的分组后面的分组。
c、经具有比特差错的丢包信道的可靠数据传输：rdt3.0
假定会发生比特受损，而且底层信道会发生丢包，所以需要考虑怎样检测丢包以及发生丢包后该做什么。
可以让发送方负责检测和恢复丢包工作。假定发送方传输一个数据分组，该分组或接收方对该分组的ACK发生了丢失，在这两种情况下，发送方都收不到应当到来的接收方的响应 如果发送方愿意等待足够长的时间以便确定分组已丢失，则它只需重传该数据分组即可。
发送方至少需要等待这样长的时间:即发送方与接收方之间的一个往返时延(可能会包括在中间路由器的缓冲时延)加上接收方处理一个分组所需的时间。
理想的协议应尽可能快地从丢包中恢复出来；等待一个最坏情况的时延可能意味着要等待一段较长的时间，直到启动差错恢复为止。因此实践中采取的方法是发送方明智地选择一个时间值，以判定可能发生了丢包(尽管不能确保)如果在这个时间内没有收到ACK，则重传该分组。
注意，如果一个分组经历了一个大的时延，发送方可能会重传该分组，既是数据分组和ACK均没有发生丢失。这就需要考虑冗余数据分组的可能性。
为了实现基于时间的重传机制，需要一个倒计数定时器，在一个给定的时间量过期后，可中断发送方。因此，发送方需要能做到:
①、每次发送一个分组(包括第一次分组和重传分组)时，便启动一个定时器。
②、响应定时器中断(采取适当的动作)
③、终止定时器
因为分组序号在0和1之间交替，因此rdt3.0有时被称为比特交替协议。
综上，通过检验和、序号、定时器、肯定和否定确认分组（以及重传）等技术，可以实现一个可靠数据传输协议。
2、流水线可靠数据传输系协议：
定义发送方(或信道)的利用率为:发送方实际忙于将发送比特送进信道的那部分时间与发送时间之比，得到停等协议有非常低的发送方利用率。这是一个形象的网络协议限制底层网络硬件所提供的能力的示例。而且，我们还忽略了在发送方和接收方的底层协议处理时间，以及可能出现在发送方与接收方之间的任何中间路由器上的处理与排队时延。考虑到这些因素，将进一步增加时延，使其性能更糟糕。
解决这种特殊的性能问题的一个简单方法是:不使用停等方式运行，允许发送方发送多个分组而无需等待确认。因为许多从发送方向接收方输送的分组可以被看成是填充到一条流水线巾，故这种技术被称为流水线。流水线对可靠数据传输协议带来如下影响：
①、必须增加序号范围，因为每个输送中的分组(不计算重传的)必须有一个唯一的序号，而且也许有多个在输送中未确认的报文
②、协议的发送方和接收方两端也许缓存多个分组。发送方最低限度应当能缓冲那些已发送但没有确认的分组，接收方或许也需要缓存那些已正确接收的分组。
③、所需序号范围和对缓冲的要求取决于数据传输协议如何处理丢失、损坏及延时过大的分组。解决流水线的差错恢复有两种基本方法是:回退N步和选择重传。
3、回退N步（GBN）：
在回退N步协议中，允许发送方发送多个分组(当有多个分组可用时)而不需等待确认，但它也受限于在流水线中未确认的分组数不能超过某个最大允许数。
将基序号(base)定义为最早的未确认分组的序号，将下一个序号(nextseqnum)定义为最小的未使用序号(即下一个待发分组的序号)，则可将序号范围分割成4段。
[0,base-1]段内的序号对应于已经发送并被确认的分组
[base, nextseqnum-1]段内对应已经发送但未被确认的分组
[nextseqnum,base+N-I]段内的序号能用于那些要被立即发送的分组，如果有数据来自上层的话。
大于或等于base+N的序号是不能使用的，直到当前流水线中未被确认的分组(特别是序号为base的分组)已得到确认为止。
那些已被发送但还未被确认的分组的许可序号范围可以被看成是一个在序号范围内长度为N的窗口。随着协议的运行，该窗口在序号空间向前滑动。因此N常被称为窗口长度，GBN协议也常被称为滑动窗口协议。
一个分组的序号承载在分组首部的一个固定长度的字段中。如果分组序号字段的比特数是k，则该序号范围是[0,2k-1]。在一个有限的序号范围内，所有涉及序号的运算必须使用模2k运算,即序号空间可被看作是一个长度为2k的环，其中序号2k-1紧接着序号0。
GBN发送方必须响应三种类型的事件:
①、上层的调用：当上层调用rdt_sendO时，发送方首先检查发送窗口是否已满，即是否有N个已发送但未被确认的分组。如果窗口未满，则产生一个分组并将其发送，并相应地更新变量；如果窗口已满，发送方只需将数据返回给上层，隐式地指示上层该窗口已满。然后上层可能会过一会儿再试。在实际实现中，发送方更可能缓存(并不立刻发送)这些数据，或者使用同步机制(如一个信号量或标志)允许上层在仅当窗口不满时才调用rdt_send()
②、收到一个ACK：对序号为n的分组的确认采取累积确认的方式，表明接收方已正确接收到序号为凡的以前且包括在内的所有分组。
③、超时事件：协议的名字"回退n步"来源于出现丢失和时延过长分组时发送方的行为。就像在停等协议中那样，定时器将再次用于恢复数据或确认分组的丢失。如果出现超时，发送方重传所有已发送但还未被确认过的分组。如果收到一个ACK，但仍有已发送但未被确认的分组，则定时器被重新启动。如果没有已发送但未被确认的分组，该定时器被终止。
GBN接收方的动作也很简单：如果一个序号为n的分组被正确接收到，并且 按序(即上次交付给上层的数据是序号为n-1的分组) ，则接收方为分组n发送一个ACK，并将该分组中的数据部分交付到上层。在所有其他情况下，接收方丢弃该分组，并为最近按序接收的分组重新发送ACK。注意到因为一次交付给上层一个分组，如果分组k已接收并交付，则所有序号比k小的分组也已经交付。
在GBN协议中，接收方丢弃所有失序分组。
接收方必须按序将数据交付给上层。假定现在期望接收分组n，而分组n+1却到了。因为数据必须按序交付，接收方可能缓存(保存)分组n+1，然后，在它收到并交付分组n后，再将该分组交付到上层。然而，如果分组n丢失，则该分组及分组n+1最终将在发送方根据 GBN 重传规则而被重传，因此，接收方只需丢弃分组n+l即可。
发送方必须维护窗口的上下边界及nextseqnum 在该窗口中的位置，但是接收方需要维护的唯一信息就是下一个按序接收的分组的序号。该值保存在 expectedseqnum 变量中。
丢弃一个正确接收的分组的缺点是随后对该分组的重传也许会丢失或出错，因此甚至需要更多的重传。
因为窗口长度的限制，发送方发送分组0-3，然后在继续发送之前，必须等待直到一个或多个分组被确认。当接收到每一个连续的ACK(例如ACK0和ACK1)时，该窗口便向前滑动，发送方便可以发送新的分组(分别是分组4和分组5) 在接收方，分组2丢失，因此分组3、4、5被发现是失序分组并被丢弃。
4、选择重传：
GBN 协议潜在地允许发送方用多个分组"填充流水线"，因此避免了停等协议中所提到的信道利用率问题。
单个分组的差错就能够引起GBN重传大量分组，许多分组根本没有必要重传 随着信道差错率的增加，流水线可能会被这些不必要重传的分组所充斥。
选择重传(SR)协议通过让发送方仅重传那些它怀疑在接收方出错(即丢失或受损)的分组而避免了不必要的重传。这种个别的、按需的重传要求接收方逐个地确认正确接收的分组。再次用窗口长度N来限制流水线中未完成、未被确认的分组数。然而，与GBN不同的是，发送方已经收到了对窗口中某些分组的ACK。
SR发送方的动作：
1.从上层收到数据：当从上层接收到数据后，SR发送方检查下一个可用于该分组的序号。如果序号位于发送方的窗口内，则将数据打包并发送;否则就像在GBN中一样，要么将数据缓存，要么将其返回给上层以便以后传输。
2.超时：定时报再次被用来防止丢失分组。然而，现在每个分组必须拥有其向己的逻辑定时器，因为超时发生后只能发送一个分组。可以使用单个硬件定时苦苦模拟多个逻辑定时器的操作。
3.收到ACK：如果收到ACK，倘若该分组序号在窗口内，则SR发送方将那个被确认的分组标记为已接收。如果该分组的序号等于send_base则窗口基序号向前移动到具有最小序号的未确认分组处。如果窗口移动了并且有序号落在窗口内的未发送分组，则发送这些分组。
SR接收方的动作：SR 接收方将确认一个正确接收的分组而不管其是否按序 失序的分组将被缓存直到所有丢失分组(即序号更小的分组)皆被收到为止，这时才可以将一批分组按序交付给上层。
1.序号在[rcv_base,rcv_base+N-1]内的分组被正确接收。在此情况下，收到的分组落在接收方的窗口内，一个选择ACK被回送给发送方。如果该分组以前没收到过，则缓存该分组。如果该分组的序号等于接收窗口的基序号(rcv_base)，则该分组以及以前缓存的序号连续的(起始于rcv_base的)分组交付给上层。然后，接收窗口接向前移动分组的编号向上交付这些分组。
2.序号在[rcv_base-N,rcv_base-1]内的分组被正确收到，在此情况下，必须产生一个ACK，即使该分组是接收方以前已确认过的分组。
3.其他情况。忽略该分组。
注意，接收方重新确认(而不是忽略)己收到过的那些序号小于当前窗口基序号的分组。
在发送方和接收方之间有一副假想的帘子，因为接收方不能"看见"发送方采取的动作。接收方所能观察到的是它从信道中收到的以及它向信道巾发出报文序列。没有办法区分是第一个分组的重传还是第5个分组的初次传输。显然，窗口长度比序号空间小1时协议无法工作。
简单地讲，无论GBN和SR都是为了在不可靠的传输（不特指UDP）的情况下，通过下层网络的方式来实现一个可靠地传输。GBN传输协议就是流水线传输，但是只要有一个未成功或者出现了乱序，就将目前已经收到的分组（乱序部分）全部丢去，然后重新传输；而SR是为了提高效率，在一个未成功的时候，不会全部丢弃，而是先进行缓存，直到未成功的到达，并形成了有序的队列就进行向上传输，然后才向后移动窗口。