构造可靠数据传输协议

前段时间真好在看《计算机网络自顶向下方法》。今天我们来聊聊聊聊计算机网络怎么在运输层提供可靠的数据传输协议。

谈到网络不得不谈OSI的七层模型。其中包括：

• 物理层: 将数据转换为可通过物理介质传送的电子信号相当于邮局中的搬运工人。

• 数据链路层: 决定访问网络介质的方式。

• 网络层: 使用权数据路由经过大型网络 相当于邮局中的排序工人。

• 传输层: 提供终端到终端的可靠连接 相当于公司中跑邮局的送信职员。

• 会话层: 允许用户使用简单易记的名称建立连接 相当于公司中收寄信、写信封与拆信封的秘书。

• 表示层: 协商数据交换格式 相当公司中简报老板、替老板写信的助理。

• 应用层: 用户的应用程序和网络之间的接口。

而我们现在普遍用的TCP/IP四层模型。其中包括：应用层、运输层、网络层、链路层。

而今天我们讲的是网络中应用层，可以说是TCP的由来，在谈TCP的由来，我们必须要了解什么是多路复用和多路分解

• 多路复用：在源主机从不同套接字中收集数据块，并为每个数据块封装上首部信息(这将在以后用于分解)从而生成报文段，然后将报文段传递到网络层，所有的工作称为多路复用
• 多路分解：将运输层报文段中的数据交付到正确的套接字的工作成为多路分解

我们都知道从应用层传下来的数据经过运输层的多路复用然后通过网络层中传输最后到达链路层，在另一台主机上同样是经过链路层再到网络层再到运输层经过多路分解然后发送给指定的应用。这个过程就是网络的通信，但是在这个过程中，我们发送的数据包可能会丢失，今天我们要讨论的是在运输层怎么保证我们的数据不会丢失，提供可靠的数据的传输。我们要跨越历史的长河，来一步步的探索出来。下面我会书写怎么从rdt1.0(经完全可靠信道的可靠数据传输)一步步演变成今天的TCP协议。

在看各种协议之前，我们要了解可靠数据传输的框架。具体如下图。为上层实体提供的服务抽象是：数据通过可以通过一条可靠的信道进行传输。借助可靠信道，传输数据比特就不会受到损害(由0变为1，或者相反)或丢失，而且所有数据都是按照其发送顺序进行交付。

1. 经完全可靠信道的可靠数据传输：rdt1.0

   我们都知道，如果这个信道是完全可靠，那么的我们的可靠数据传输会简单很多。

   

   上图中的箭头表示状态的迁移，引起变迁的事件显示在表示变迁的横线上方，事件发生时所采取的动作显示在横线的下方。

   rdt的发送端只通过rdt_send(data)事件接受来自较上层的数据，产生一个包含该数据的分组(经由make_pk(data)动作)，并将分组发送到信道中。rdt_send（data）事件是由较高层应用的过程调用产生的。

   rdt的接受端通过rdt_rcv(packet)事件从底层信道接受一个分组，从分组中取出数据(经由extract(packet,data)动作)，并将数据上传给较高层(通过deliver_data(data)动作)实际上，rdt_rcv(packet)事件是由较低层协议的过程调用产生的。

   总结：在这个简单的协议中，一个单元数据与一个分组没有差别。而且，所有分组是从发送方流向接收方；有了完全可靠的信道，接收端不需腰提供任何反馈信息给发送方，因为不必担心出现差错！注意到我们已经假定了接收方接收数据的速率能够与发送方的速率一样快。因此，接收方没有必要请求发送方慢一点。

2. 经具有比特差错信道的可靠数据传输：rdt2.0

   正常情况下：完全可靠的信道是不存在的。现实中都是不可靠的信道，我们再想想在信号不好的时候，人们打电话是怎么说，一定会说，你刚才说的是什么？我一句没有听见，再简化一点，就是给发送方一个确认接收到，还是没有接收的消息。于是有了rdt2.0

   

   rdt2.0的发送端有两个状态。在最左边的状态中，发送端协议正等待来自上层传下来的数据。当rdt_send(data)这个事件出现时，发送方将产生一个包含待发送数据的分组(sndpkt),带有校验和，然后经由udt_send(sndpkt)操作发送该分组。在最右边的状态中，发送方的协议等待来自接收方的ACK或NCK分组。如果收到一个ACK分组，则发送方知道最近发送的分组已被正确接收，因此协议返回到等待来自上层的数据的状态，如果收到一个NAK分组，该协议重传上一个分组并且等待接收ACK或NAK的状态时，它不能从上层获取更多的数据；

   rdt2.0的接收端只有一种状态，当分组到达时，接收方要么回答一个ACK，要么回答一个NAK，这取决于收到的分组是否受损。rdt_rcv(rcvpkt)&&corrupt(rcvpkt)对应于收到一个分组并发现有错的事件。

   rdt2.0协议看似可以运行，但是有一个致命的缺陷，就是没有考虑ACK或NAK分组受损的可能性。

   处理ACK 和NAK分组受损的三种可能性：

   • 接收端不理解发送端发来的ACK或NAK分组，于是重复发送原来的内容，这是一条不归路，不具有可实施性
   • 增加足够的校验和比特，使发送方不仅可以检测差错，还可以恢复差错。对于会产生差错但不丢失分组的信道，这就可以直接解决问题。
   • 当发送方接收到含糊不清的ACK或NAK分组时，只需要传当前的分组即可。然而，这种方法在发送方到接收方的信道中引入了冗余分组。冗余分组根本的困难在于接收方不知道它上次所发送的ACK或NAK是否被发送方正确的收到。因此它无法事先知道接收到的分组是新的还是一次重传。

   解决上面的问题有一个简单的方法，就是在数据分组中添加一新字段。让发送风对其数据分组编号，即将发送数据分组的序号放在该字段。

   于是又了rdt2.1协议。

3. rdt2.1协议

   使用了从接收方到发送方的肯定确认和否定确认。当接收到失序的分组时，接收方对所接受的分组发送一个肯定确认。如果收到受损的分组，则接收方将发送一个否定确认，如果不发送NAK，而是对上次正确接收的分组发送一个ACK，我们也能实现与NAK一样的效果。发送方接收到对同一个分组的两个ACK(即接收冗余ACK)后，就知道接收方没有正确接收到跟在被确认两次的分组后面的分组。

   

   

4. rdt2.2协议：在具有差错信道上实现一个无NAK的可靠数据传输协议。

   与rdt2.1协议的区别：接收方此时必须包括一个ACK报文锁确认的分组序号(这可以通过在接收方FSM中，在make_pkt（）中包括参数ACK 0 或ACK 1 来实现)，发送方此时必须检查接收到ACK报文中被确认的分组序号(这可通过在发送方FSM中，在isACK()中包括参数 0 或 1来实现)

   

   

5. 经具有比特差错的丢包信道的可靠数据传输：rdt3.0

   上面的协议已经考虑到比特受损，底层信道会丢包，但是协议还有两个必须要关注的问题：怎样检测丢包以及发生丢包后该做什么

   在这里我们需要解决丢包的问题，我们让发送方负责检测和恢复丢包工作。假定发送方传输一个数据分组，该分组或者接收方对该分组的ACK发生了丢失。在两种情况下，发送方都收不到应当到来的接收方的响应。如果发送方愿意等待足够长的时间以便确认分组已丢失，则它只需重传该数据分组即可。

   这个时候我们只需要在发送方与接收方之间加上一个往返时延（可能会包括在中间路由器的缓冲时延）加上接收方处理一个分组所需的时间。此外理想的协议应尽可能快地从丢包中恢复出来；等待一个最坏的情况的时延可能意味着要等待一段较长的时间，直到启动差错恢复为止。

   如果在这个时间内没有收到ACK，则重传该分组。注意到如果一个分组经历一个特别大的时延。发送方可能会重传该分组，即使该数据分组及其ACK都没有丢失。这就是发送方到接收方的信道中引入了冗余数据分组。不过在rdt2.2中已经有足够的功能（序号）来处理冗余分组情况。

   为了实现基于时间的重传机制，需要一个倒计数定时器。发送方需要做到：每次发送一个分组（包括第一次分组和重传分组）时，便启动一个定时器。响应定时器中断(采取适当的动作)。终止定时器

   

   

   下面我们来画个图，说明rdt3.0协议在几种情况下的处理的方式

   • 无丢包操作

     

   • 分组丢失

     

   • 丢失ACK

     

   • 过早超时

     

     总结：数据传输协议的要点。在检验和、序号、定时器、肯定和否定确认分组这些技术中，每种机制都在协议的运行中起到了必不可少的作用。至此我们得到了一个可靠的数据传输协议。

6. 流水线可靠数据传输协议

   rdt3.0虽然是一个功能正确的协议，但是rdt3.0性能问题的核心在于它是一个停等协议，所以性能方面会很差。最简单的解决办法就是：不以停等方式运行，允许发送方发送多个分组而无须等待确认。

   

   流水线技术对可靠传输协议会带来如下的影响：

   • 必须增加序号返回，因为每个输送中的分组（不计算重传的）必须有一个唯一的序号，而且也许有多个在输送中的未确认报文
   • 协议的发送方和接收方两端也许不得不缓存多个分组。发送方最低限度应当能缓冲哪些已发送但没有确认的分组
   • 所需序号范围和对缓冲的要求取决于数据传输协议如何处理丢失、损坏及延时过大的分组。主要有两种方法：回退N步、选择重传。

7. 回退N步（GBN协议）滑动窗口协议

   允许发送方发送多个分组（当多个分组可用时）而不需要等待，但是它也受限于在流水线中未确认的分组数不能超过某个最大允许数N。

   

   如上图，我们将基序号(base)定义为最早未确认分组的序号，将下一个序号(nextseqnum)定义为最小的未使用的序号（即下一个待发分组的序号）。则可将序号范围分割成四段。在[0,base-1]段内的序号对应的于已经发送并被确认的分组。在[base,nextseqnum-1]段内对应发送但未被确认的分组。[nextseqnum,base+N-1]段内的序号能用于哪些要被立即发送的分组。如果有数据来自上层的话，最后，大于或等于base+N的序号是不能使用的，直到当前流水线中未被确认的分组（特别是序号为base的分组）已经得到确认为止。

   

   GBN发送方必须响应三种类型的事件：

   • 上层调用：当上层调用rdt_send()时，发送方首先检查发送窗口是否已满，即是否有N个已发送但未被确认的分组。如果窗口未满，则产生一个分组并将其发送，并相应的更新变量。如果窗口已满，发送方只需将数据返回给上层，隐式地指示上层该窗口已满。然后上层可能会过一会儿再试。在实际现实中，发送更可能缓存（并不立刻发送）这些数据，或者使用同步的机制（如一个信号量或标志）允许上层在仅当窗口不满时才调用rdt_send()。

   • 收到一个ACK。在GBN协议中，对序号为n的分组的确认采取累计确认的方式，表明接收方已正确接收到序号为n的以前且包括n在内的所有分组。

   • 超时时间。协议的名字"回退N步"来源于出现丢失和时延过长分组时发送方的行为。就像在停等协议中那样，定时器会再次用于恢复数据或确认分组的丢失。如果出现超时，发送方冲传所有已发送但未被确认过的分组。

     

     如果分组N丢失，则该分组及分组N+1最终将在发送方根据GBN重传规则而被重传。因此，接收方只需要丢弃分组n+1即可。这种方法的优点就是接收缓存简单。

8. 选择重传协议（SR）

   GBN协议同时也存在性能问题。当窗口长度和带宽时延都很大的时，单个分组的差错就能够引起GBN重传大量的分组，许多分组根本没必要重传。

   选择重传(SR)协议通过让发送方仅重传哪些它怀疑在接收方出错(即丢失或受损)的分组而避免不必要的重传。

   

   SR接收方将确认一个正确接收的分组而不管其是否按序。失序的分组将被缓存直达所有丢失分组（即序号更小的分组）皆被收到为止。

   SR发送方的事件与动作：

   • 从上层收到数据。当从上层接收到数据后，SR发送方检查下一个可用于该分组的序号。如果序号位于发送方的窗口内，则将数据打包并发送；否则就像在GBN中一样，要么将数据缓存，要么将其返回给上层以便以后传输。
   • 超时。定时器再次被用来防止丢失分组。然而，现在每个分组必须拥有其自己的逻辑定时器。因为超时发生后只能发送一个分组。可以使用单个硬件定时器模拟多个逻辑定时器的操作。
   • 收到ACK。如果收到ACK，倘若该分组序号在窗口内，则SR发送方将那个被确认的分组标记为已接收。如果该分组的序号等于send_base，则窗口基序号向前移动到具有最小序号的未确认分组处。如果窗口移动了并且有序号落在窗口内的未发送分组，则发送这些分组。

   SR接收方的事件与动作：

   • 序号在[rcv_base,rcv_base+N-1]内的分组被正确接收。在情况下，收到的分组落在接收方的窗口内，一个选择ACK被回送给发送方。如果该分组以前没有收到过，则缓存该分组。如果该分组的序号等于接收窗口的基序号，则该分组以及以前缓存的序号连续的(起始于rcv_base的)分组交付上层。然后，接收窗口按向前移动分组的编号向上交付这些分组。举个例子来说。当收到一个序号为rcv_base=2的分组时，该分组及分组3、4、5可被交付给上层。
   • 序号在[rcv_base-N,rcv_base-1]内分组被正确收到。在此情况下，必须产生一个ACK，即使该分组时接收方以前已确认过的分组。
   • 其他情况。忽略该分组。

   

   当我们面对有限序号范围的现实时，发送方和接收方窗口间缺乏同步会产生严重的后果。

   

   如上图a)所示，对前3个分组的ACK丢失，因此发送方重传这些分组。因此，接收方下一步要接收序号为0的分组，即第一个发送分组的副本。

   如上图b)所示，对前3个分组的ACK都被正确交付。因此发送方向前移动窗口并发送第4、5、6分组，其序号分别为3、0、1。序号为3的分组丢失，但序号为0的分组到达（一个包含新数据的分组）

   所以窗口长度必须小于或等于序号空间大小的一半。

9. 总结

   机制	用途和说明
   检验和	用于检测在一个传输分组中比特错误
   定时器	用于超时/重传一个分组，可能因为该分组（或其ACK）在信道中丢失了。由于当一个分组延时但未丢失（过早超时），或当一个分组已被接收方收到但从接收方到发送方的ACK丢失时，可能产生超时事件，所以接收方可能会收到一个分组的多个冗余副本。
   序号	用于为从发送方流向接收方的数据分组按顺序编号。所接收分组的序号间的空隙可使接收方检测出丢失的分组。具有相同序号的分组可使接收方检测出一个分组的冗余副本
   确认	接收方用于告诉发送方一个分组或一组分组已被正确地接收到了。确认报文通常携带着被确认的分组或多个分组的序号。确认可以是逐个的或累积的，这取决于协议。
   否定确认	接收方用于告诉发送方某个分组未被正确地接收。否定确认报文通常携带着未被正确接收的分组的序号
   窗口、流水线	发送方也许被限制仅发送哪些序号落在一个指定范围内的分组。通过允许一次发送多个分组但未被确认，发送方的利用率可在停等操作模式的基础上得到增加。我们很快将会看到，窗口长度可根据接收方接收和缓存报文的能力、网络中的拥塞程度或两者情况来进行设置