可靠数据传输原理 《计算机网络——自顶向下方法（James F. Kurose， Keith W. Rose）》读书笔记
可靠数据传输是网络中最为重要的问题之一。TCP所采用的许多原理，都是可靠数据传输的内容。
图1 说明了我们学习可靠数据传输的框架：
①为上层实体提供的服务抽象是：数据可以通过一条可靠的通道进行传输。借助于可靠通道，数据就不会受到损坏或丢失（如图1 的（a）所示）。
②实现这种服务抽象是可靠数据传输协议（reliabel data transfer protocol）的责任。由于可靠数据传输协议的下一层协议也许是不可靠的（如TCP的下层是不可靠的IP），所以这是一项困难的任务。
图1 的（b）说明了用于数据传输协议的接口。通过调用rdt_send()可以调用数据传输协议的发送方(rdt表示可靠数据传输协议，reliable data transfer），rdt发送方将数据封装成分组后传给下层协议进行运输。当分组从信道的接收端到达时，将调用rdt_rcv()。rdt接受方对分组进行一定的处理，然后rdt协议调用deliver_data来将可靠的数据向较高层交付。
在 本节中，考虑到底层信道模型越来越复杂，我们将不断开发一个可靠数据传输协议的发送方和接收方。
一、构建可靠数据传输协议
在开始讨论rdt前，我们需要了解一下有限状态机（Finite-State Machine,FSM）。
①FSM中的箭头表示协议从一个状态变迁到另一个状态；
②引起变迁的事件显示在表示变迁的横线上方；
③事件发生时所采取的动作显示在横线下方；
④如果对一个事件没有动作，或没有事件发生而采取一个动作，我们将在横线的上方或下方使用一个符号 A；
⑤FSM的初始状态用虚线表示；
1. 经完全可靠信道的可靠数据传输：rdt 1.0
rdt的发送端只通过rdt_send(data)事件接收来自较高层的数据，产生一个包含该数据的分组packet=make_pkt(data)，并将分组发送到通道。实际上，rdt_send(data)是由较高层应用的过程调用产生的（例如:rdt_send()，图中的虚线）。图2 的（a）的FSM定义了发送方的操作
rdt的接收端通过rdt_rcv(packet)事件从底层信道接收一个分组，从分组中取出data=extract(packet,data)，并通过deliver_data(data)将数据传送给较高层。实际上，rdt_rcv(packet)是由较低层协议的过程调用产生的（例如：rdt_rcv()，图中的虚线）。图2中的（b）定义了接收方的操作。
在这个简单的协议中，一个data与一个packet没有差别。而且，所有的分组是由发送方流向接收方；有了完全可靠的信道，接收方就不需要提供任何反馈信息给发送方，因为不必担心出现差错！这里也假设了接收方接收数据的速率能够与发送方发送数据的速率一样快，所以接收方不需要请求发送方慢一点！
2. 经具有比特差错信道的可靠数据传输
（一）rdt 2.0
底层信道更为实际的模型是分组中的比特可能受损。在分组的传输、传播和缓存中，这种比特差错通常会出现在网络的物理部件中。现在，仍继续假设，所有的分组（虽然比特可能受损）将按其发送顺序被接收。
由于信道可能会引入比特差错，为了让发送方知道哪些内容被正确接收，哪些内容接收有误并因此需要重传，接收方收到的报文后，
①如果没有差错，则给发送方返回一条肯定确认（positive acknowledgement, ACK）控制报文
②如果有差错，则给发送方返回一条否定确认（negative acknowledgement, NAK）控制报文
基于这种重传机制的可靠数据传输协议称为自动重传请求（Automatic Repeat reQuest, ARQ）协议。
基本上，ARQ协议还需要另外三种机制来处理存在比特差错的情况：
（1）差错检测。需要一种机制来使接收方检测到何时出了比特差错。（如校验和等）
（2）接收方反馈。接收方提供明确的反馈信息给发送方：ACK和NAK
（3）重传。接收方收到有差错的分组时，发送方将重传该分组。
图3的（a）(b) 说明了rdt 2.0的FSM，使用了差错检测、肯定确认/否定确认和重传机制。
rdt 2.0的发送端有两个状态。左边的初始状态等待来自上层的data，当产生rdt_send(data)事件时，发送方将产生一个带有data和校验和的分组（snd_pkt），然后使用udt_send(snd_pkt)发送该分组。在右边的状态中，发送方协议等待来自接收方的ACK或NAK分组：
①如接收到一个ACK（rdt_rcv(rcv_pkt)&&isACK()），发送方知道最近发送的分组已被正确接收，因此协议返回“等待来自上层的data”的状态；
②如接收到一个NAK（rdt_rcv(rcv_pkt）&&isNAK()），该协议重传最后一个分组并等待接收方为响应重传分组而回送的ACK或NAK。
因为当发送方在等待ACK或NAK时，不能够从上层获得更多的数据：只有接收到ACK并离开该状态时才能发生这样的事件。所以rdt 2.0被称为停等（stop-and-wait）协议。
rdt 2.0 接收方的FSM仍然只有一个状态。当分组到达时，接收方要么回答一个 ACK，要么回答一个NAK，取决于接收到的分组是否有受损。
（二）rdt 2.1
rdt 2.0有一个致命的缺陷：没有考虑到ACK 或NAK受损的可能性！在rdt 2.1 中，将其纳入考虑范围。处理受损的ACK或NAK时有一个简单的方法（几乎所有现有的数据传输协议中，包括TCP，都采用了这种方法）：
在数据分组中添加一个新的字段，让发送方对其数据进行编号，即将发送数据分组的序号放在该字段中。于是，接收方只需要检查序号就能知道这个分组是一个新的分组还是一次重传（corrupt（rcvpkt)表示冗余ack）。对于停等协议，只需一个比特序号就足够（0、 1）。目前，我们假设信道不丢分组，即每个ACK和NAK都不会丢。
图4 和图5给出了对rdt 2.1的FSM描述。当前的协议状态必须反映出当前（由发送方）正在发送的分组或（由接收方）正在接受的分组的序号是0还是1。当接收方收到一个失序分组时，它仍发送一个ACK【但是不保存这个分组，因为它已经有一个了（冗余数据分组，duplicate data packet）】，如果收到受损的分组，则接收方发送NAK。
（三）rdt 2.2
考虑rdt 2.1。如果收到错误分组是，接收方不发送NAK，而是对上一次正确分组发一个ACK，我们也能得到与NAK一样的效果：发送方收到冗余ACK后，就知道接受方没有正确收到这个被确认了两次的分组的后面的分组。这个需求要求了接收方发送的ACK应带有***信息（在接收方的make_pkt应包含ACK 0或ACK 1）。
与rdt 2.1的区别：①没有NAK；②ACK分组中应带有序号信息。
3. 具有比特差错的丢包信道的可靠数据传输： rdt 3.0
现在假定除了比特差错之外，信道还会丢包。这在现实的网络中是一个非常常见的现象。如何解决丢包的问题？在这里，介绍其中的一种方法。
在rdt 3.0 中，我们让发送方负责检测和恢复丢包工作。假设发送方发送了一个分组，该分组发生了丢失或接收方回送的ACK发生了丢失，在两种情况下，发送方都收不到来自接收方的响应。因此，发送方等待一个适当的时延，如果在这段时间内没有收到响应，则发送方重传一个分组。为了实现这个基于时间的重传机制，需要一个倒计数定时器（countdown timer），在给定的时间量结束后，可中断发送方。因此，发送方需要做到：①每次发送一个分组时，便启动一个定时器；②响应定时器的中断；③终止定时器
下图说明了rdt 3.0 的发送方的FSM：
图8 显示了rdt 3.0协议的运作情况。在图中，时间随着虚箭头的方向朝下移动。由于分组序号在0和1之间交换，所以rdt 3.0也称为比特交替协议（alternating-bit protocol）。
至此，我们得到了一个可到的数据传输协议（虽然效率不高），其运用的机制主要有：检验和、肯定和否定确认、序号、定时器等。
二、流水线可靠数据传输协议
rdt 3.0虽然是一个功能正确的协议，但其性能却让人不满意。因为它是一个停等协议，没发送一个分组之后，需要等接受到确认回复之后，才会继续发送另一个分组。因此，浪费了很多时间在等待上。
解决这种性能问题的一个简单方法是：不使用停等方式运行。允许发送方发送多个分组而无需等待确认。因为许多从发送方向接收方输送的分组可以被看成是填充到一条流水线上，所以，这种技术也被称为流水线（pipelining）。流水线技术对可靠运输协议可带来如下影响：
①必须增加序号范围。因为每个输送中的分组（除了重传的）必须有一个唯一的序号；
②协议的发送方和接收方两端也许必须缓存多个分组。
③所需序号范围和对缓存的要求取决于数据协议如何处理丢失、损坏及延时过大的分组。解决流水线的差错恢复有两种基本的方法：回退N步（Go-Back-N,GBN）和选择重传（Selective Repeat，SR）。
三、回退N步
在回退N不（GBN）协议中，允许发送方发送多个分组，而不需要等待确认，但它也受限于流水线中未确认的分组数不能超过某个最大的数N。
图8显示了发送方看到的GBN的序号的范围，其中，
基序号（base）:最早的未确认分组的序号；
下一个序号（nextseqnum）:最小的未使用序号（即下一个待发分组的序号）；
由此，可将序号范围分为4段，分别为
①[0,base-1] 已经发送并被确认的分组；
②[base, nextseqnum-1]: 已经发送但未被确认的分组；
③[nextseqnum, base+N-1]: 能用为那些立即要被发送的分组；
④>(base+N): 不能被使用的序号（知道②中未被确认的分组已得到确认为止）。
由上图可以看出，我们限制这些被发送的、未被确认的分组的数目为N（为什么要进行限制呢？“流量控制”是这些控制的原因之一，具体内容这边就不展开了）。随着协议的运行，该窗口在序号空间向前滑动，所以，GBN协议也常被称为滑动窗口协议（sliding-window protocol）。
在实践中，一个分组的序号存储在分组首部的一个固定的字段中，如果该字段的比特数是k,则该序号的范围是[0, 2^k-1]。在一个有限的序号范围内，所有涉及序号的运算必须使用模2^k运算（即序号空间被看成是一个长度为2^k的环，其中序号2^k-1紧跟着0）。
GBN发送方必须响应三种类型的事件：
①上层的调用。当上层调用了rdt_send()后，GBN发送方必须先检测其发送窗口是否已满（即是否有N个已发送但未被确认的分组）。如果没有满，则产生一个分组并将其发送；如果窗口已满，则GBN发送方将数据返回（退还）上层，告诉他现在还不能发送。
②收到一个ACK反馈报文。在GBN协议中，对序号为n的分组采用的是累积确认（cumulative acknowledge），即发送方当收到序号为n的ACK报文时，表明接收方已经正确接收了序号n 及n以前的所有的分组。如果发送方收到了一个损坏的反馈报文，则不做任何处理，继续等待。
③超时处理。当GBN协议中的发送方遇到超时事件时，将会重新启动计时器，并重新发送所有已发送但未被确认的报文。发送方只有一个定时器，指明当前最早发送但未被确认的分组（基序号base）；当发送方收到一个ACK，但仍有未被确认的分组时，则定时器重新被启动；但如果没有未被确认的分组，则定时器停止。
在GBN协议中，当接收方收到序号为n的分组且该分组是按序的（即上一个分组的序号是n-1），则接收方将该分组的数据部分提交给上层并回送一个序号为n的ACK，然后继续等待下一个分组的到来；但如果是其他情况（序号为n的分组是失序的或是损坏的），则接收方将扔掉这个分组，并为最近接收到的按序分组返回一个ACK。这种方法的有点是接收缓存简单，接收方不需要缓存任何失序分组。
注意到在该协议中，一次只能交付一个分组，所以当序号为k的分组提交了之后，很显然，k之前的分组也都提交过了。所以使用累积确认是很自然的事。图12是GBN接收方的扩展FSM描述：
图13给出了窗口长度为4个分组的GBN协议的运行情况。因为受到窗口长度的限制，当发送方发送完1~3的分组之后，必须等到一个或多个分组被确认，才能继续发送下一个分组。
四、选择重传
在上一节提到的GBN协议中，虽然解决了停等协议中信道利用率低的问题，但仍存在性能问题。尤其是当窗口的长度较大时，单个分组的差错就能引起大量分组的重传。很多分组其实没有必要重传。随着信道差错率的增加，流水线可能会被大量的重传分组所充斥。
顾名思义，选择重传协议让发送方仅需重传那些他怀疑在接收方出错（丢失、损坏）的分组。这种选择性地重传要求接收方逐个确认每个分组并缓存失序的分组并回送其对应的ACK；而发送方需要存储未完成的分组的确认状态。图14显示了发送方和接收方看到的序号空间：
1. 发送方的事件与动作
①从上层接收数据（与GBN一样，先检查窗口是否已满）
②超时。与GBN不同，每个分组有自己的逻辑定时器，如果发生超时，则只重传对应的分组
③收到ACK。发送方将对应序号的分组标记为已被接收。如果该分组序号等于send_base，则窗口向前移动到最小未被确认的序号处；如果窗口移动了之后，有在等待可用序号的未发送分组，则将可用序号分配给这些分组并发送。
2. 接收方的事件与动作
SR接收方将确认并缓存一个正确接收的分组而不管其是否有序。失序的分组将被缓存直到所有比它序号小的分组全部被正确接收到，然后才能将一批分组按序提交给上层。
①序号在[rcv_base, rcv_base+N-1]范围内的分组被正确接收。接收方回送一个对应的ACK。如果该分组没有被缓存过，怎缓存该分组，如果该分组的序号为rcv_base，则将与该分组连续的一整批分组提交给上层并移动窗口。
②序号在[rcv_base-N,rcv_base-1]范围内的分组被正确接收。接收方此时已经将这部分的分组提交给上级了，但是它仍需回送一个ACK，再次跟发送方确认（可能是上次该ACK丢失或者损坏了）
③其他情况。忽略该分组。
图15描述了SR的操作过程：
关于SR协议，有一个必须注意的点是：可用序号范围和窗口大小是两个不同的概念。
可用序号范围：是由分组首部序号字段的比特数决定的。如果这个字段有k位，那么该序号范围是[0, 2^k-1]
窗口大小：窗口大小N必须小于等于序号空间大小的一半【即N<（2^k）/2】！因为，由于ACK的丢失，接收方的窗口移动了一个N的距离之后，发送方还一动也不动，这时：
五、总结
下面用一张表格对本章内容进行一下总结：
可靠数据传输节制及其用途的总结
机制 | 用途和说明 |
检验和 | 用于检测分组中的比特错误 |
定时器 | 用于超时、重传一个分组（可能因为分组丢失、损坏、ACK丢失等原因） |
序号 | 数据分组按顺序编号，由此可检测出丢失的分组或冗余的分组 |
确认ACK | 接收方告诉发送方分组被正确收到了 |
|
否定确认 NAK | 接收方告诉发送方分组未被正确接收 |
窗口、流水线 | 允许发送方在未收到确认的情况下继续发送一个指定序号范围的分组 |