概要

• 可靠的数据传输也可能建立在不可靠的数据传输的基础上
For example, TCP is a reliable data transfer protocol that is implemented on top of an unreliable (IP) end-to-end network layer.

• In this section, we will incrementally develop the sender and receiver sides of a reliable data transfer protocol, considering increasingly complex models of the underlying channel.

• 示意图：可靠的信道是建立在下层不可靠的信道基础之上的，通过传输层的协议使得数据传输变得可靠

• packets被接受的顺序相对于发送时是不会变的，但是有可能发生丢包的现象

• 讨论全双工通信
Both the send and receive sides of rdt send packets to the other side by a call to udt_send() (where udt stands for unreliable data transfer).

Building a Reliable Data Transfer Protocol

Perfectly Reliable Channel: rdt1.0

• 用有限状态自动机来描述发送方和接收方

• rdt的发送端
• 只接受来自上层的数据 rdt_send(data)
• 通过make_pkt(data) 创建一个包含data的包，并且将这个包发送进信道
• 实际上，rdt_send(data)事件是由较高层应用的过程调用产生的（例如rdt_send()）

• rdt的接收端
• rdt通过rdt_rcv(packet)事件从底层信道接收一个分组
• 从分组中提出数据（经由extract(packet,data)操作）
• 并将数据上传给较高层（通过deliver_data(data)操作）
• 实际上，rdt_rcv(packet)事件是由较底层协议的过程调用产生的（例如，rdt_rcv()）

• 这里假设了下层信道是完全可靠的，有了完全可靠的信道，接收端就不需要提供任何反馈信息给发送方，因为不必担心出现差错。这是最简单的情况。

rdt2.0：发送的data可能有几个bit会出错

• 情景：打电话时
In a typical scenario, the message taker might say “OK” after each sentence has been heard, understood, and recorded. If the message taker hears a garbled sentence, you’re asked to repeat the garbled sentence.

• This message-dictation protocol uses both positive acknowledgments (“OK”) and negative acknowledgments (“Please repeat that.”).

• 自动重传请求协议
In a computer network setting, reliable data transfer protocols based on such retransmission are known as ARQ(Automatic Repeat reQuest) protocols.

• 它需要另外三种协议的功能来应对bit errors
• Error detection
例如用checksum来检测错误和纠正错误
使用差错控制编码来纠错
For now, we need only know that these techniques require that extra bits (beyond the bits of original data to be transferred) be sent from the sender to the receiver; these bits will be gathered into the packet checksum field of the rdt2.0 data packet.
• Receiver feedback
发送方要了解到接收方情况（这里就是分组是否被正确接收）的唯一途径就是让接收方提供明确的反馈信息
The positive (ACK) and negative (NAK) acknowledgment replies in the message-dictation scenario are examples of such feedback.
rdt2.0就采用让接收方向发送方会送一个ACK与NAK分组
• Retransmission
接收方收到有差错的分组时，发送方将重传该分组文

• FSM

• rdt2.0也叫stop-and-wait protocol
It is important to note that when the sender is in the wait-for-ACK-or-NAK state, it cannot get more data from the upper layer; that is, the rdt_send() event can not occur; that will happen only after the sender receives an ACK and leaves this state.

• rdt2.0的致命缺陷：the ACK or NAK packet could be corrupted!

rdt2.1：ACK或NAK可能出现错误

解决方法思路

• 在data packet前面加上一个1bit的sequence number，然后每次接收方检查这个number，就能知道信息是否重复了
A simple solution to this new problem (and one adopted in almost all existing data transfer protocols, including TCP) is to add a new field to the data packet and have the sender number its data packets by putting a sequence number into this field.

• 因此，当对方接收到了数据，但ACK没有完整到达发送方时，仍然可以让发送方重新发送数据，只是接收方需要判断这个再次接收到的数据是新的还是重复的
由于我们假定了分组没有丢失，分组顺序也没有混乱，所以只用考虑分组重复造成错误的这一种情况。如果接收到的序号和上一次的不一样，就代表这次接收到的数据是新的数据，因此只需要0和1两个数就足以给分组标上序号来判断数据是否重复了

实际操作

• sender
• 状态1：等待来自上层的调用0，如果上层有调用，就把data封装，加上checksum和编码0
• 状态2：等待接收方发送过来的ACK或者NAK 0，如果没出错且ACK就转移到状态3，如果确认出错或者接收到NAK就把packet再发送一遍，并且继续等待ACK或者NAK
• 状态3：等待来自上层的调用1，如果上层有调用，就把data封装，加上checksum和编码1
• 状态4：与状态2相同

• receiver
• 状态1：等待来自下层的调用0，如果接收到一个分组，且分组通过了校验且编码为0，则取出data，发送给发送方一个ACK的包附上ACK信息的checksum（ACK本身也需要校验），并且转到状态2
如果接收到包但是包出错了，则发送给发送方一个NAK包附上NAK信息的checksum，然后继续等待下层的调用0
如果接收到包且包没出错，但是data的编号是1，则说明发生重复了，发送方很可能没有接收到那个ACK才会再发一次重复的data，因此接收方发送给发送方一个ACK，发送方如果接收到了ACK，就会发送下一个编号为0的data，也就是接收方需要的data
• 状态2：与状态1类似，但是是在等待下层的调用1

讨论总结

rdt2.2：无NAK的协议

• 功能与2.1相同，但只使用ACK，ACK要编号

• 接收方对最后正确的分组发ACK，以替代NAK
• 接收方必须显式地包含被正确接收分组的序号
• 对当前分组的反向确认由对前面一个分组的正向确认来代替
比如目前发送方希望收到一个ACK5，接收方发送过来的却是ACK4，则说明编号为5的这个分组并没有发送到接收方，相当于当前等待的分组5发送了一个NAK

• 当发送方接收到重复的ACK（如：再次接收到ACK0），发送方与收到NAK采取相同的动作：重传当前分组

• sender
与2.1不同的就是发送方不再判断是NAK还是ACK，而是判断是ACK1还是ACK0

• receiver
发送ACK的时候不仅要附上checksum，还要附上ACK的编号
例如在等待底层调用0时，如果接收到data0且没出错，就发送ACK0，如果出错，就发送ACK1并且继续等待底层调用0

rdt3.0：具有比特差错和分组丢失的信道

• 下层信道可能会丢失分组（包括数据和ACK）
• 解决方法：超时重传
发送方等待ACK一段合理的时间（比正常信息传输一个来回的时间长一点）
如果ACK只是被延迟了，则会导致信息重复，但是信息带有序列号，因此这一点可以解决
这样一来，不管是发送方发送的包丢了，还是接收方发送的ACK丢了，都会导致发送方接收ACK的时间超出限制，从而发送方重传之前那个packet

• sender
• 新增超时定时器，如果timeout，重放分组
• 等待ACK0时为例，不管是ACK包出错了，还是ACK包序号出错，还是丢包了，都不做反应，直到timeout才重新发送一个包

• receiver

• 3.0与2.2的区别
新增time out，且当检测到bit error或者重复的时候，发送方都不会立即重传一个packet，而是不动，直到timer触发

• 流程图



timeout过早：重复发送packet1，接收方删除重复的packet1就行，接收方接收到重复的ACK1时什么都不做直到收到ACK0或者timeout

Pipelined Reliable Data Transfer Protocols 流水线

stop-and-wait protocol的缺陷

• consider an idealized case of two hosts, one located on the West Coast of the United States and the other located on the East Coast. 在这种情况下，信息长度为L，信道传输速率为R，将信息打入信道的时间是，一般来说这是一个微秒级别的数，因为L一般相对于R很小，而将packet发送到接收方则需要大概15s，接收方再把ACK发回来就需要30s了
而这之间的时间全都被浪费掉了，因为必须等到ACK成功接收，发送端才会有下一步动作

• 示意图：

采用流水线

• 不以stop-and-wait的方式进行，发送方发送多个packet，不需要等待接收ACK

• 这样的流水线技术对可靠数据传输协议可带来如下影响
• packet的序列号范围必须要增加：用多个bit来表示分组的序号
The range of sequence numbers must be increased, since each in-transit packet (not counting retransmissions) must have a unique sequence number and there may be multiple, in-transit, unacknowledged packets
• 在发送方/接收方必须设置缓存区，
• 发送方缓存：未得到确认的信息，可能需要重传
• 接收方缓存：正确接收到的信息可能乱序，需要进一步处理
• The range of sequence numbers needed and the buffering requirements will depend on the manner in which a data transfer protocol responds to lost, corrupted, and overly delayed packets. Two basic approaches toward pipelined error recovery can be identified: Go-Back N and selective repeat.

Go-Back-N（GBN）

• 发送方视角的GBN



• base：最前面一个没有收到对应ACK的分组
• nextseqnum：接下来应该发送的分组
• [0,base-1], Already ACK’d [base,nextseqnum-1], sent, not yet ACK’d [nextseqnum,base+N-1], Usable, not yet sent [base,+++], Not usable

FSM

• sender
• 如果window已经被用完了，发送方会把要发送的数据还给上一层，上层可能会过一会再尝试发送分组。一般来说，发送方实际上会缓存这个分组，或者设置同步机制（比如一个信号或flag），当信号或flag为特定值时才允许上层调用rdt_send()
• 对序列号为n的数据包的确认将被视为累积确认
也就是说，如果接收方发过来的一个ack n丢了，但是ack n+1传过来被发送方收到了，发送方就可以认为n+1及以前的包全部被确认，就继续发送第n+2个包
• 有一个timer，If a timeout occurs, the sender resends all packets that have been previously sent but that have not yet been acknowledged.





这里的start_timer就很重要：如果不新开start，那么在流式线式的批量发送下，第一条的ACK回来过后，不会触发base==nextseqnum，那么stop_timer不会执行，时间继续，同样的是第二条ACK，第三条…..，最终一定会触发timeout，到时又重新发一套从base到nextseqnum的packet，虽然接收方能够处理冗余，但是这部分重发是完全没有必要的，并且会一直存在，重发也不止一次，那么我们每次接到ACK后重新启动归零定时器就很重要了，并且在最坏的情况下（N=1），几乎是一条一条，如停等方式发送的情况下，仍然是成功的，哪怕第一次ACK回来比第二次发送慢一点点，也会start计时器，这个时候就是计时第二条packet的发送到接收过程了。而如果是最好的情况，一条条连续发送，那么计时器的工作也是正常的。

• receiver
• 如果接收到序列号为n的分组且这个顺序是对的，接收方发送ACKn并且将数据交付给上层，在所有其他不正常的情况下，接收方会把data n丢弃，并且向发送方发送最近一次正确的包的ACK
• 累积确认，Note that since packets are delivered one at a time to the upper layer, if packet k has been received and delivered, then all packets with a sequence number lower than k have also been delivered. Thus, the use of cumulative acknowledgments is a natural choice for GBN.

整个流程图

Selective Repeat (SR) 选择重传

GBN的缺陷和解决

• avoid unnecessary retransmissions by having the sender retransmit only those packets that it suspects were received in error(that is, were lost or corrupted) at the receiver.

• 需要接收方单独确认正确收到的包
This individual, as-needed, retransmission will require that the receiver individually acknowledge correctly received packets.

• 未完成的、未确认的包的数量还是用N来限制
A window size of N will again be used to limit the number of outstanding, unacknowledged packets in the pipeline.

• However, unlike GBN, the sender will have already received ACKs for some of the packets in the window.

SR的整个操作流程

• sender
• Data received from above. When data is received from above, the SR sender checks the next available sequence number for the packet. If the sequence number is within the sender’s window, the data is packetized and sent; otherwise, it is either buffered or returned to the upper layer for later transmission, as in GBN.
• 现在每个packet都要有自己的逻辑时钟，因为每次超时只用重传一个packet，多个逻辑时钟可以用一个硬件时钟来模拟
Timeout. Timers are again used to protect against lost packets. However, each packet must now have its own logical timer, since only a single packet will be transmitted on timeout. A single hardware timer can be used to mimic（模拟） the operation of multiple logical timers.
• 接收到ACK时，如果ACK序列号=send_base这个packet的序列号，则window向前移动
ACK received. If an ACK is received, the SR sender marks that packet as having been received, provided it is in the window. If the packet’s sequence number is equal to send_base, the window base is moved forward to the unacknowledged packet with the smallest sequence number. If the window moves and there are untransmitted packets with sequence numbers that now fall within the window, these packets are transmitted.

• receiver
• Packet with sequence number in [rcv_base, rcv_base+N-1] is correctly received.
• In this case, the received packet falls within the receiver’s window and a selective ACK packet is returned to the sender.
• If the packet was not previously received, it is buffered. 不连续的缓存
• If this packet has a sequence number equal to the base of the receive window(rcv_base in Figure b above), then this packet, and any previously buffered and consecutively numbered (beginning with rcv_base) packets are delivered to the upper layer. 连续的发送给上层
• The receive window is then moved forward by the number of packets delivered to the upper layer. As an example, consider the Figure below. When a packet with a sequence number of rcv_base=2 is received, it and packets 3,4, and 5 can be delivered to the upper layer. 窗口移动
• 接收到已经确认过的信息：仍然要发送ACK
Packet with sequence number in [rcv_base-N, rcv_base-1] is correctly received. In this case, an ACK must be generated, even though this is a packet that the receiver has previously acknowledged.
如果不让发送方知道接收方已经成功接收，因为每个packet都有单独的逻辑时钟，发送方就会再把这个包发一遍
• Otherwise. Ignore the packet.

关于序号大小范围和窗口大小范围的关系

GBN协议和SR协议的异同