Chapter 3 Transport Layer

要理解传输层和网络层之间的关系，我们在下面用一个例子来近似模拟一下，我们继续使用上一章最后的 快递邮寄 的例子。我们将房子看作应用进程，将街道看成主机host，但现在我们要加入快递驿站（每个街道一个）。这样我们就可以模拟网络层及网络层向上的数据逻辑通信了。

每个街道中存在的房子中都有很多活动，其中就不乏有寄快递的activity。这时，”房子“就需要把这些 快递件 给驿站让驿站发出去（应用层应用将报文交给传输层）。”房子“可以选择提供的邮寄服务，快发还是慢发，有没有快递丢失赔款的服务（应用层进程可以规定传输层协议）。

如果快递很多，那么驿站还会将这些快递分成许多 包裹 按批次发出去（传输层将应用层报文分成一个个 chunks 然后封装传输层报文头变成传输层数据段）。驿站在发快递之前，”房子“需要将把xx街道xx收件人作为收件地址交给快递驿站，之后就不用操心任何东西了（传输层协议只为应用进程之间提供逻辑通信）。快递站将包裹交给邮寄公司，邮寄公司负责将快递送达到目标街道（网络层只为主机提供逻辑通信）。

我们可以在这个模拟中看到，应用进程只需要用socket接口将报文交给传输层，不需要关心之后发生了什么，而传输层需要把报文成段封装成数据段后给网络层，至于网络层之后链路带宽什么的都不需要关心。我们之后还会了解到，传输层是如何做到即使底下的网络层为用户提供不可靠的服务，传输层仍然可以保证传输是可靠的。

在计算校验和之前，先要明确一件事：我们在计算UDP Checksum 之前，我们要在UDP报文段的头部前加入一个伪头部(Pseudo header)。

校验和的计算过程其实很简单，其过程如下：

简单举个例子，我们要将数据从 IP source:192.168.2.1，Port src:8080传递到IP dest:192.168.2.2，Port source:9090。这里的8位协议字段(protocol)是17，表示UDP协议。再假设我们要传4字节的数据字段（0x55aa）。
小端方式表示的UDP segment如下：
Pseudo Header:

UDP Header:

Segment Body:

在接收端，传输层会将UDP segment中每16位相加并加上进位，最终与CHECKSUM相或，若结果不是0xFFFF（即全1）说明报文段出错，应舍弃。

尽管报文段在传播过程中会有链路和设备对段文信息进行检错，但只要过程中有一个链路(link)不提供这种可靠的保证，那么这一报文段的可靠性就存疑。再者，即使路由器检错没有问题，段文存储在buffer中还是可能造成错位。因此，我们需要在传输层上实现纠错机制。这也是系统设计中对 end-end principle 的典例。

还有就是，UDP 并不实现纠错机制。当 UDP 检测到段文错误，根据实现上的不同，可能会直接舍弃错误的报文段，如果要采纳一个不完全准确的报文段可能还会警告应用。下节课，我们将学习可靠数据传输应遵循的原则。

在 rdt1.0 中，我们暂且不考虑传输层下层信道的可靠性问题。下面，我们罗列出了 rdt1.0 的发送端(Figure 3.9a)和接收端(Figure 3.9b)双方的有限状态机(finite-state machine) 的模型操作定义。
在图中，我们看到，无论是接收端还是发送端，它们都只有一种状态(state)，一个事件(event) ，每个事件后对应两个动作(action)，动作完成后转换(transition)到原有状态。

在发送端，FSM从虚线箭头处初始化发送端的状态，之后等待来自上层应用发送信息报文。一旦有上层应用的报文传来，触发事件rdt_send(data)并执行动作packet=make_pkt(data)、udt_send(packet)，完成后返回到初始状态。
在接收端，同样先初始化接收端的状态，等待下层网络发来的信息报文。一旦报文到来，触发事件rdt_rcv(packet)并执行动作extract(packet,data)和deliver_data(data)将报文通过socket送到应用进程上。之后返回到初始状态。

从这个例子中，数据报文总是从发送方传播到接收方，有了下层信道的可靠性保证，接收端完全不需要给发送方反馈任何信息（前提假设下层信道完全可靠）。

为了更贴合实际情况，我们在 rdt2.0 中引入位错误(bit error)。我们知道给传输层提供服务的下层网络不是可靠的，在报文的传输(transmission)、传播(propagation)和缓存(buffer)都可能会导致报文中出现位错误。现在我们依然假设 不会出现丢失 的情况。

传输层该如何实现在这种信道下的可靠性保证？在我们打电话时，当别人说完一句话后，我们会有肯定回应和不确定回应的方式，在我们不确定对方说了什么时，我们可以要求对方再说一遍。在这种信道上实现的可靠性的方式也类似。Message-dictation protocol 会让接收端用positive acknowledgments ("OK") 和 negative acknowledgments ("Please repeat") 的控制报文使发送端知道哪个报文出错了。最后发送端将出错的报文重传。这种可靠数据传输协议也叫 ARQ(Automatic Repeat reQuest) protocols。

要实现自动重传请求(ARQ)协议，就必须引入以下三个机制：

下图我们展示 rdt2.0 收发两端的有限状态机模型。在 rdt2.0 中，发送端的FSM有两个状态：（1）等待来自上层应用的发送信息报文；（2）等待来自接收端反馈控制报文。接收端的FSM仍然只有那一个状态。

在发送端，FSM先完成等待上层应用数据状态的初始化，一旦触发发送数据的事件rdt_send(data)就会产生相应动作（sndpkt=make_pkt(data,checksum)、udt_send(sndpkt)）。之后，发送端会停止发送报文并转变状态到等待接收端发来控制报文的状态。也因此，rdt2.0 这种协议叫做 stop-and-wait protocol。当发送端接收到来自接收端的控制报文后，如果收到 NAK 信号，就启动重传，如果收到 ACK 信号，发送端回到初始位置并等待下一次的数据发送。

在接收端，FSM先完成等待发送端数据状态的初始化。之后，当接收方收到来自发送方的数据，接收方会先校验 checksum 是否无误，如果无误就将数据传给上层应用并返回 ACK 的反馈，如果 checksum 检验后不一致，就会丢弃当前数据报并反馈 NAK 的报文。

rdt2.0 看似已经很完善了，但是我们仍然没有考虑到反馈过程中 ACK 或 NAK 若是出现位错误该怎么办？我们考虑以下三种解决方案：

而被大多数据传输协议所采用的方法是在数据包前面加入一个新字段——序列号(Sequence number)。现在，通过判断 序列号，接收方就知道收到的包是不是重传的。对于停等协议来说，1bit 的序列号就够了。1 bit 只能表示两位的状态。因此，我们用模2运算来表示包的先后顺序（前提假设下层网络的传输不会造成丢包），比如，对于0而言，1就表示下一个数据包的序列号，由于 module-2 运算，(1+1)/2结果余数0，这时序号0的数据报又变成了序号1的下一个数据包。（但注意：虽然序列号相同，但是数据包是不同的）

下面，我们来将接收端和发送端的两个 FSM 按部就班地解读一下。发送端等待并收到应用进程的第0号报文，将报文传输给接收端并等待接收端的控制报文。接收方发来控制报文后，判断如果发来的是 NAK 或者控制报文有位错误，就启动重传机制并继续等待。接收方再次发来的控制报文没有为错误且信号位ACK，这时的发送端转换状态并等待应用进程发来第1号报文。

在接收端，当收到第0号报文，接收端会检测位错误和序列号是否满足条件，若报文有位错误，则反馈 NAK 信号，如果没有位错误但序列号和当前等待接收的序列号不同则返回 ACK 信号，告诉发送端发重了。

rdt2.2 和 rdt2.1 最大的区别就是将报文nNAK信号和报文(n-1)的ACK信号放在一块检测。之前在rdt2.1中，接收方收到发送方的报文后会检查两个部分——报文有位错误？和报文发重了？然后根据这两个部分发送不同的反馈报文。但是在rdt2.2中，接收方将这些放在一起判断，并将判断结果放在一个反馈报文中返回给接收方。

我们再考虑丢包的情况进去，现在，我们不得不考虑：（1）怎么检测数据包的丢失；（2）数据包丢失之后该怎么办。考虑到这种新情况，我们需要在协议中引入一种新的机制来应对丢包。在这个机制中，我们只考虑让发送端来检测和恢复丢失的数据包。

假设在数据传输的过程中，发送方的数据包或者接收方的 ACK 信号由于重重原因丢了。这时，发送方在会在一个设定的时间猛惊醒，这么长时间，数据包肯定是丢失了吧，随后重传(retransmit)数据包。至于这个时间多长合适呢？发送方发送数据包后，它至少需要一倍的往返延时时间收到 ACK 信号（还要包括中转路由器中的时间和接收方对这些数据的处理时间）。但是这种时间在现实中的网络环境是很难测量的。而做最坏延迟情况又会使发送方启动重传之前等待很长时间。所以要等多久启动重传由发送方决定。

在发送方确定一个重传时间后，只要它在这个事件内没有收到 ACK/NAK 等信号，发送方就重传。我们可能会想到，如果发送方的数据包没丢只是现在没有收到 ACK 信号怎么办？这样，在发送方-接收方信道中引入了重复的数据包(duplicate data packets)。对于这种情况的处理我们在 rdt2.2 中已经学过（序列号），这里不再赘述。

从发送方的角度看，重传(Retransmission) 好像一副万能药。数据包传输过程中丢失、接收方的ACK信号丢失、ACK信号过度延迟等都可以用重传解决。这种基于一个时间重传的机制需要一个 定时器(Countdown timer) 在到时间后叫醒发送方重传数据包。因而，发送方需要（1）每次发送数据包都要重设时间；（2）相应计数器的中断，重传数据包；（3）收到 ACK 信号后停止计数。

下图展示了发送方rdf3.0的FSM。In Figure 3.16, time moves forward from the top of the diagram toward the bottom of the diagram; note that a receive time for a packet is necessarily later than the send time for a packet as a result of transmission and propagation delays.
Because packet sequence numbers alternate between 0 and 1, protocol rdt3.0 is sometimes known as the alternating-bit protocol. We have now assembled the key elements of a data transfer protocol.


终于，经过完善，我们的传输层协议可以实现可靠的数据传输（不用担心信道中会发送位错误还是丢包）

发送方的一生会处理以下三种事件(events)，还有对这三种事件的处理方式(action)如下：

接收方要处理的事件和处理方式如下：

对于第二种接收方的事件处理的情形我们在下面的图中予以更直观的展示。为方便理解，下图中的窗口大小只有4个序列号。一旦发送方没有收到序列号为2的 ACK 报文，发送方的窗口就会卡在这里。这也就是我们为什么强调接收方在收到数据包序列号在接收窗口前时，就必须发送 re-ack 信号，不然发送方就一直卡在这里了。

从上面的例子我们能学到，发送方和接收方的同步非常重要。接着上面 Figure 3.26的例子继续，但我们的窗口大变为3。回忆之前了解过的模运算(modular arithmetic)，假如我们的系统是mod-4系统，不能够表示除了序列号范围0、1、2、3以外的数字。在mod-4系统中，我们要怎么才能够知道发送方发来的数据包是新的还是重传的？我们通过下面两个例子来了解一下这种情况。

在第一个例子（Figure 3.27a）中，接收方收到数据包后窗口向后挪动，由于我们窗口大小是3，一次性能够传输3个数据包。在接收方收到数据后返回这3个数据包的 ACK 报文，如果这三个 ACK 报文丢了怎么办？在发送方，超时后又开始重传这三个数据包，等 pkt0 到接收方时它会以为这是新的0号数据包。而第二个例子中，pkt0、pkt1、pkt2都正常传输接收并返回 ACK 数据包。随后传输pkt3、pkt0和pkt1，这次的pkt3在传播过程中丢失了，但后面传输的pkt0是新数据。

怎么辨别呢？在窗口大小等于3时没有办法知道收到的pkt0到底是重传还是新的报文。但是如果我们将窗口大小改为2或者1，那就很容易辨别后面传输的数据包属于哪种情况。因此在SR协议中的窗口大小必须小于等于序列号数的一半。

关于可靠数据传输协议的实现我们已经了解许多，我们在下表中回顾这些rdt的机制，所有的所有都使我们有能力看见"the big picture"。

Let’s conclude our discussion of reliable data transfer protocols by considering one remaining assumption in our underlying channel model. Recall that we have assumed that packets cannot be reordered within the channel between the sender and receiver. This is generally a reasonable assumption when the sender and receiver are connected by a single physical wire. However, when the “channel” connecting the two is a network, packet reordering can occur. One manifestation of packet reordering is that old copies of a packet with a sequence or acknowledgment number of x can appear, even though neither the sender’s nor the receiver’s win dow contains x. With packet reordering, the channel can be thought of as essen tially buffering packets and spontaneously emitting these packets at any point in the future. Because sequence numbers may be reused, some care must be taken to guard against such duplicate packets. The approach taken in practice is to ensure that a sequence number is not reused until the sender is “sure” that any previously sent packets with sequence number x are no longer in the network. This is done by assuming that a packet cannot “live” in the network for longer than some fixed maximum amount of time. A maximum packet lifetime of approximately three minutes is assumed in the TCP extensions for high-speed networks [RFC 7323]. [Sunshine 1978] describes a method for using sequence numbers such that reorder ing problems can be completely avoided.

序列号和确认号是 TCP 最重要的两个字段，这两个字段保障了 TCP 可靠数据传输的实现。在上节课中我们也讨论过相关的 rdt 实现。现在，我们就来看看 TCP 到底在这两个字段里面塞了什么。

如上图，TCP 将数据视为一种无结构有序的字节流。和我们想象的可能不同，TCP 用序列号并不用于段的编号，而是数据流中对各个字节所编号。每个段第一个字节的序列号就代表了这个段的序列号。因而，序列号的编号是只针对数据字段的。上图的文件包含了500 000字节的数据流，而每个 MSS 1000字节，因此我们有500个数据段，第一个段的编号就是0，第二个段的编号为1000，以此类推。这样段的编号就会作为序列号字段插在头部字段(header field)中。

OK，现在我们来学习另外的确认序列号(acknowledgment numbers)。回忆一下，我们说 TCP 是全双工(full-duplex)的，在接收方（Host B）接收数据段的同时向发送方（Host A）反馈段的接收情况。每个数据段都会对应唯一的序列号，Host B 在正确收到数据段后会向 Host A 发送序列号 + 1的 ACK 信号段文。举个例子，在 1st 段文（0-999）被 Host B 收到之后，Host B 会发送序列号为1000的 ACK 段。TCP 提供累计确认(cumulative acknowledgments) 的机制，如果 ACK 段中序列号是1000，就表示序列号小于1000的字节均已收到，等待序列号1000往上的数据。

在 TCP 的 RFC 相关文档中其实并没有规定 TCP 连接中的主机收到乱序的段该怎么办。结合我们之前讲过的，我们有两种办法：
（1）丢弃乱序的数据段；
（2）将乱序的数据段放在一个接收缓冲区中，等待丢失的数据段(missing bytes)来填满空隙。
尽管第一种方法简单且减少接收主机的部件设计，但由于第二种方案在网络带宽利用的更加高效，因此在现实中多采用第二种方案。

在图3.30中，我们假设初始序列号为0。实际上，TCP连接的双方会随机选择一个初始序列号。这么做是为了减少这样一种可能性：两个主机的连接已经终止了，但是先前的某个数据段还留存在网络之中，这个数据段就可能被之后同一对主机间新创建的连接当成有效的数据段（并且新连接恰好使用了与旧连接相同的端口号）

Telnet 是在 RCF 854 文档中规定的应用层协议。Telnet 跑在 TCP 协议上，可以用在任意一对主机上的远程登录。但由于 Telnet 连接并不加密，很多人会选择 SSH 协议。

假设我们现在有两个主机 Host A 和 Host B，其中 Host A 是客户端，初始化 Telnet 会话， Host B 是服务器。在 Telnet 上，Host A 键入的每个字符都会封装成一个 TCP 数据段发给远程主机；然后远程主机会回发每个字符的拷贝，显示到用户的屏幕上。这种”回发(echo back)“机制保证每个字符在远程主机上收到后都得到了处理。

假设用户输入了一个字母’C'，那客户端服务器之间的数据段传输是怎么样的？从传输开始到结束，客户端和服务器总共发了三个数据段，在TCP连接建立完毕后，客户端等待服务器端送来79号字节，服务器等待客户端的42号字节。双方对此心知肚明，因此客户端发送第一个报文段时会将42号序列号的字节发给服务器（包含 ASCII 的 'C"），并将服务器索要79号序列号的字节。

之后，服务器会在序列号为79的字节将字母 'C' 通过TCP报文回发给客户端，并请求客户端的43号报文（告诉客户端序列号42前面的数据都收到啦）。在服务器向客户端发送的TCP数据段中，我们可以发现这个数据段Seq=79, ACK=43, data='C'实际上发挥了两个作用——（1）ACK=43，收到前面的数据啦；（2）对数据 'C' 的回发。在同一个数据段中实现了对前面发送数据的确认，这种技术叫捎带确认(piggybacking)。

最后一个段只有一个作用——客户端对服务器发送信息的确认（ACKed）。这个数据段没有数据字段（这个 acknowledgment 就不是客户端-服务器数据字段的捎带确认了）。我们注意到这个数据段并没有数据字段但是仍然有序列号，这是因为TCP就是这样要求的。

现在，我们开始学习在 TCP 是怎么预估发送方-接收方之间的往返时间RTT的。我们用SampleRTT来表示数据段从传输层发送出去到接收到 ACK 报文段之间这么长的时间。SampleRTT在 TCP 的实现上通常表示目前还没收到 ACK 报文的这报文段发送后已经过了SampleRTT的时间。还有，TCP 不会记录重传段的SampleRTT，只记录发送一次的报文段。

显然的是，报文段传输路径拥塞度不同，SampleRTT值也会随之浮动变化，由此产生的SampleRTT时间我们通常称作非典型的(Atypical)。要想预估到更稳定的往返时间，我们就需要将每个段的SampleRTT来平均一下，获得的时间我们叫EstimatedRTT。我们通常用下面的公式计算：经过大量实验和应用，实验人员证明 的 α 值能够在大多数情况下提供稳定且准确的 RTT 估计。因而也将 1/8 的 alpha 值写进了 [RFC 6298]。这样，上面的公式就变成了：我们在这里计算的 EstimatedRTT 是 SampleRTT 的加权平均值，我们给当前的 SampleRTT0.125的权重，这样算得的EstimatedRTT就更好反应目前接收双方之间节点的拥塞度。在统计学中，这种平均被称为 exponential weighted moving average (EWMA)。下图展示gaia.cs.umass.edu和fantasia.eurecom.fr之间 TCP 连接的 RTT。我们看到EstimatedRTT比SampleRTT更加平滑。

然除了 RTT 的预估，RTT 的多变性也是我们要关注的。 在[RFC 6298]中同样定义了 RTT 变动，用DevRTT表示。用下列的公式计算：我们用DevRTT表示SampleRTT和EstimatedRTT之间的 EWMA 差异。DevRTT越小就说明网络越稳定，反之，网络则不稳定。对 β 的推荐值是0.25。

好了，现在我们知道怎么算得EstimatedRTT和DevRTT，很显然，我们所要的重传间隔得大于等于EstimatedRTT，但是不要大太多。而且我们想的重传间隔最好跟网络的拥塞变化要息息相关。当网络一时间更加拥塞了，我们需要调整重传间隔让它变得更大。这样我们就会得到下面式子：在[RFC 6298]中，建议初始的超时间隔为 1 秒。当发生超时时，TCP 会将当前的超时间隔值加倍。这是为了避免在接下来的数据段即将被确认时发生过早的超时。通过加倍超时间隔，可以减少不必要的重传，从而提高传输效率。一旦接收到数据段并更新了 EstimatedRTT（估计的往返时间），TCP 会重新计算超时间隔。新的超时间隔将基于更新后的 EstimatedRTT 计算。

虽然我们刚刚只是给出了 TCP rdt 的简化版本，但其中也不乏一些微妙之处。在图3.34中，Host A给Host B发送了包含 8 字节数据序列号为 92 的数据段，并期望收到来自Host B包含确认号 100 的确认字段。但是第一次Host B传输 ACK 报文段的时候段丢失了，Host A的计时器在一段时间间隔中没有收到来自Host B的 ACK 信号，就启动重传，之后成功收到Host B传来的响应报文段。

但在下图3.35中，没有数据段的丢失，但是Host B的 ACK 响应没有在超时间隔内传到Host A，因而Host A启动重传。重传后在间隔内收到Host B传来对两个数据段的确认，因为对两个数据段都进行了确认，Host A也就不需要重传第二个数据段了。

在下图3.36的第三种情形下，我们看到在 Host B 回传对两个数据段的确认时丢失了第一个响应报文。但是由于Host A收到第二个响应报文（ACK=120）因此并不会启动重传，因为 120 的确认号对前面的字节序列进行了累计确认。

现在我们做一些现实性的改变。在现实应用中，TCP 的重传时间并不是一成不变的，没多一次重传，TCP 都会设置重传时间为原先的两倍。比方说刚开始的超时间隔是 0.75 秒，如果时间内没有收到 ACK 确认段，TCP 就会启动重传并设置超时间隔为 1.5 秒，然后 3 秒。但如果如果在此期间接收到新的数据（定时器未工作）或 ACK 确认，超时间隔就会通过最新的 EstimatedRTT 和 DevRTT 重新计算。

这种超时间隔设置翻倍的改变是我们后面学习 TCP 拥塞控制的前提。因为定时器超时最可能是因为网络拥塞问题造成的。一次性太多数据包同时到达某一路由器队列就可能造成路由器的丢包或过久的排队时延。试想，网络状况本来就不太理想的情况下还频繁地发起重传，拥塞就会更加严重，但增加重传间隔就会在网络状况改善时能够迅速调整超时间隔。这种思想也会在我们 Chapter 6 中学习 CSMA/CD 时用到。

当然，超时间隔翻倍也有一个坏处，即超时间隔会变得很长。会出现每次丢包都会让重传的时间间隔翻倍，这样就增加了端到端的延时。但发送方可以通过检测重复的 ACK 来发现数据包丢失，而不必等待超时事件的发生。接收方通过重复 ACK(duplicate ACK) 告诉发送方还有还有哪一序列号的报文没有收到。发送方在收到多个重复ACK后（一般认为是3个）会认为某个数据段丢失，并立即重传该数据段。

下图我们总结了 TCP 接收方的ACK生成策略。一共有 4 种情况导致接收方生成ACK：

那么 TCP 采用的是 GBN 协议还是 SR 协议呢？我们之前说过，TCP 对报文的确认是累积性确认的，接收方并不会按个确认那些乱序但准确到达的数据段。发送方也只需要在那些未收到确认的序列号中维护最小的那个(SendBase)，另外

维护下一个要发送字节的序列号(NextSeqNum)就可以了。截至这里，TCP 看起来好像是一个 GBN 的协议。但是TCP 和 GBN 还有许多不同之处。因为 TCP 的实现需要缓存那些收到的无误的数据段。（GBN会丢掉那些乱序的数据段）

假想一下，发送方要发送序列号从 1, 2, 3,......, N 的数据段，若传输期间没有丢包或corrupted bits，那么无事发生。但是如果数据包 n<N 在传输过程中丢失了，那么两种回传协议就会大不同。GBN 协议下的传输层协议会把 n, n+1, n+2,......, N全部重传一遍，这会极大的增加网络拥塞。

我们前面提到，在 TCP 接收方收到数据段后并不会立即发送 ACK 数据段，而是等待500ms看看还有没有新到达的数据段，以便一同累计确认。TCP 发送方在开始序列号 n 的报文段重传前如果接收到序列号为n+1数据段的确认就会因为累计确认的关系滑动发送窗口。

TCP 也被叫做是 选择性确认(Selective ACKnowledgment) 的协议。TCP 允许接收方选择性地确认乱序数据段，而不是仅仅累计确认最后一个按顺序正确接收的数据段。TCP的错误恢复机制结合了GBN和SR协议的特点。虽然TCP使用累积确认（类似于GBN），但它也实现了选择性重传（类似于.SR），使得TCP在处理数据段丢失时更加高效。