多路复用和多路分解

多路分解： 多路分解指的是将报文段中的数据提交到正确的套接字 1

1. 应用程序接受信息的接口 ↩

多路复用：从主机不同套接字上收集数据，并为每个数据块加上首部信息（如源端口号和目的端口号等）形成报文段，然后传到网络层。

多路复用也就是从传输层到网络层的过程，而多路分解是从传输层到应用层的过程

要想提交到正确的套接字，其实也就是提交到正确的端口。在计算机中端口范围在 0-65535 中，其中 0-1023 是周知端口号，有特殊用途，而其他就是分配给应用程序使用的了。

UDP 的多路复用和多路分解

UDP 的运输层报文段包括应用程序数据，源端口号，目的端口号和其他两个值。通过目的端口号可以标识要送到目的的具体位置，而源端口号则是为了送回数据时使用的。

TCP 的多路复用和多路分解

TCP 和 UDP 区别是 TCP 套接字是一个四元组 (源 IP 地址， 源端口号， 目的 IP 地址， 目的端口号）来标识的。因此他还可以让两个到同一个端口号的 TCP 连接互不干扰（因为有了源 IP 地址，所以可以分辨出这个数据时从哪发出的）

UDP

UDP 是一种不可靠运输，数据可能会丢失，那为什么需要 UDP 而不使用 TCP 呢？

速度更快， TCP 在链接建立之前需要经过三次握手，而 UDP 直接传输
无连接状态： TCP 需要维护连接状态。包括接受发送缓存，用色控制参数和序号及确认号参数等。

报文段结构

UDP 报文段包括源端口号，目的端口号，长度，检验和和报文组成。长度指示了该报文段总的字节数（包括报文的）并且前面四个字段大小都是两字节

检验和是为了提供差错检验机制的。具体过程为将其他三个字段相加，舍去溢出并取反。之后检验就将这四个字段相加，如果结果全是 1 则正常。

例如：

0110011001100000
0101010101010101
1000111100001100

前两个相加为
1011 1011 1011 0101

再与第三个相加为
1 0100 1010 1100 0001‬
有溢出，把溢出部分与正常位相加，结果为0100 1010 1100 0010
c语言表示：
    check_sum = (check_sum & 0xffff) + (check_sum >> 16);

计算完成之后需要取反
取反为：
1011010100111101
这就是检验和的值

然后检验时将四个进行和上面一样的回滚加法结果应该是1111111111111111

可靠数据传输

传输过程为从应用层到传输层是可靠传输，然后从传输层到网络层是不可靠传输，然后从网络层到传输层是可靠传输。

经完全可靠信道的可靠数据传输

等待上层的调用指的是从应用层到网络层，等待下层代用相反。rdt_send 是从应用层向传输层传输（并且是可靠传输）。

这是一个有限状态自动机， 横线上方是引起变动的事件，横线下方是发生是采取的动作。

经比特差错信道的可靠数据运输

底层信道可能会出现某些问题导致数据不可靠。因此为了保证数据的可靠性，可能需要对传输过来的数据进行重新检测，返回报文可能会出现肯定确认和否定确认两种情况。为了保证传输稳定，可以使用自动重传请求协议（ARQ)

ARQ 还需要另外三种功能才能进行自动重传

  • 差错检测：
  • 接收方反馈： 也就是前面说的肯定确认 (ACK) 和否定确认 (NAK)
  • 重传： 当接收方收到有差错的分组时，发送方将重传该分组。

但是接收方反馈的信号也可能出现问题，本来是肯定确认现在变成了无意义的代码。为了解决这个问题可以使用下列方法

  • 让接收方再次发送信息，但是存在这次信息仍然被干扰的问题。
  • 增加足够多的检验和比特
  • 第三种方法是接收到模糊信息直接重发分组。但是这种方法的问题是接收方不知道下一个分组是否是重发的分组，因此无法决定信息用途。

为了解决第三种方法的问题，可以在分组前加一个序号字段。这个字段对分组进行了编号。现在假设这个字段不会受到干扰，那么接收方接受到的分组和上一个分组相同，表明这是重发分组。

在这种一来一回的传输过程中，序号字段只需要一个 bit 就可以了，因为如果这个 bit 是 0 表示是初始信息，是 1 表示重传。

另外还可以使用 ACK 表示 ACK 和 NAK 两种信息。只需要把 ACK 中的序号字段标记位 0 表示这个 ACK 是上个分组的。

经丢包信道的可靠数据传输
假设现在发送的分组或者接收方反馈的信息发生了丢失，这种情况下发送方都接收不到反馈，那么发送方可以选择在等待足够长的时间过后认为分组已丢失，只需要重新发送分组即可。

为了实现等待一定时间重传的机制，可以使用倒计时计时器。每次经过一定时间后，如果没有受到恢复，则可以进行重传。

其中rdt2.2是没有在具有比特差错信道上传输的有限状态机图。虽然看起来复杂但是实际上概括起来就是有数据就发，发完后等待对应的ACK。如果ACK是对应的就等待应用层把下一个数据发过来。如果出现比特差错或者是收到不对应的ACK就重传

对于接收方，和发送方的动作类似，也就收到对应数据就发送对应ACK，如果不是对应数据或者出现比特差错就让他重传。

例如

发送数据0

接收方接收到了有比特差错的数据，发送ACK1让发送方重传

发送方接收到ACK1，重传数据0.

接收方接收到数据0，发送ACK0并且进入接收数据1的状态

rdt3.0是在具有丢包信道上的传输过程。它在rdt2.0的基础上增加了timer。在发送数据时启动timer，在接受到正确的数据时终止timer。

此外他和rdt2.0不同还在于它接收到比特差错的数据或者接收到不对应的ACK不会选择不做任何事，因为之后如果有问题可以让重传来解决。

它的接收方操作和rdt2.0完全相同

如上是预见不同情况时rdt3.0进行的操作。注意丢失ACK和过早超时。如果是丢失ACK，那么会超时重传并且接收方属于冗余（因为前面已经接收到了，会跳转到下一状态），然后由于发送方还是上一状态，所以发送方直接进入下一状态并发送。

如果是过早超时，那么会发送一个重复的ack，此时发送方已经跳转到下一状态了，于是接收到一个不对应的ACK，不做任何处理。（不做任何处理是对的，因为此时并没有丢包，但是如果是发送的包出现比特差错就应该立刻处理，但是却还是让超时进行处理）

流水线可靠数据传输协议

前面加上了计时器机制之后数据可靠性已经可以保证，但是它的速度不够快，因为它是停等协议。停等协议指的是它可以每次发送完数据之后都需要等待响应（ACK 或 NAK）才进行下一步发送。

一个简单的方法是发送方可以发送多个分组而无需等待，这种技术称为流水线。

为了保证流水线正常工作，还需要考虑以下内容

  • 需要增加序号的范围
  • 发送方和接收方不得不缓存多个分组，发送方最少要缓存那些已发送但是没有得到确认的分组，接收方也需要保存接收的分组
  • 对于丢失或损坏的分组，有两种基本方法是： 回退 N 步和选择重传

    回退 N 步（GBN）

    在 GBN 中序号范围分隔成四段。

基序号是最早未确认分组的序号，下一个序号是最小未使用序号。

窗口长度是被发送当未确认的分组最大数量。要限制最大长度是为了对发送方进行限制。

发送方需要响应三种事件

  • 上层调用：当上层调用 rdt_send () 发送数据时，如果窗口未满，则产生分组，如果已满，则通知上层。
  • 收到 ACK： 在 GBN 中，对序号为 n 的分组的确认采取累积确认。表示接收方已正确接收 n 及之前所有的分组
  • 超时事件： 如果出现超时，发送方重传所有已发送但未确认的分组（因为接收方会把所有乱序的抛弃）。

接收方只有接收到 n 分组并且前一个接收的分组是 n-1 分组才会交付到上层。其他情况都会丢弃分组并且发送需要接受分组的 ACK。之所以这样是为了减小接收方的负担及简化设计流程。也就是说接收方的窗口值大小是 1.

选择重传

GBN 缺点就是性能利用率低，可能需要不断大量的重复传输。选择重传（SR）协议让发送方仅重传怀疑接收方未正确接收的分组，从而避免不必要的重传。

这里和回退 N 步的模式大致相同，区别是在这个窗口中确认不一定是按序了，例如 2 已经确认但是 0 和 1 未确认。

如果定时器超时，这里只会发送第一个已发送但未确认的分组。

如果序号在 [base, base + N -1] 的数据被正确接收，那么一个 ACK 传给发送方。如果是 [base_ - N, base - 1] 的数据被接收，那么抛弃数据，但一定要发送 ACK（因为发送方重发就是因为没有接收到 ACK）。其他情况忽略分组。

图二是由于发送方和接收方窗口不一致和序号太小导致的。另外一个例子是假设接收方接收到了012并且ACK全部丢失，那么发送方现在重传的0在接收方看来是第二个0123中的0，但他实际上是第一个0123中的0.

为了解决这个问题，序号至少为窗口大小的两倍。

SR 接收方将缓存分组知道比他小的分组全部接收到为止。

使用技术总结

机制 用途
检验和 检验传输分组是否有错误
定时器 用于超过一定时间重传
序号 与定时器配合使用，让接收方知道这是新的还是重传的
确认 用于告诉发送方收到了
否定确认 告诉某个分组未被正确接收
窗口、流水线 用于连续发送分组 ，需要前面技术配合

TCP 连接

TCP 连接时点对点的协议，也就是说必须在两个进程之间建立联系然后发送数据。

建立 TCP 连接的大致过程为： 客户发送特殊的 TCP 报文段，服务器用特殊的 TCP 报文段响应。最后客户再用第三个特殊报文段进行响应。前两个报文段没有有效数据，而第三个可以由有效数据。经过三个报文段后，TCP 连接就可以说建立了。因为发送了三个特殊报文段，所以也可以说是三次握手。

前两次报文段中双方交换了连接意图和下一个接收的序号，那么为什么还要第三次握手呢？

假如只有两次握手，并且第二次握手发生了超时，并且如果超时发出的数据报等到连接结束后才到达服务端，那么服务端的连接就会再次打开。

在数据经过套接字之后就会受到 TCP 控制。TCP 首先将数据放到发送缓存中（在握手期间设置）。然后 TCP 会时不时的拿出一块数据放到网络层，每次可以拿的数据受限于最大报文段长度（通常由本地发送主机最大链路层帧长度也就是最大传输单元决定）

报文段结构


包括源端口号和目的端口号，检验和字段三个熟悉的。还有

  • 序号（Seq)： 序号就是报文段首字节编号。例如一个数据大小 50000 字节，MSS 为 1000 字节。那么第一个报文段就是 0-999, 第二个报文段是 1000-1999. 那么第一个报文段的序号是 0，第二个报文段的序号是 1000
  • 确认号（ACK）： 确认号是想对方发来的数据中首字节的序号。例如现在 0-100 和 200-300 已经接收到了，但是中间的可能由于某种原因没有接收到，这时候就需要用确认号让对方将 101 开始的数据重发一次。
  • 接收窗口字段： 用于指示接收方愿意接受的字节数量
  • 首部长度字段： 指示了 TCP 的首部长度
  • 选项字段：
  • 标志字段： 就是中间那些小的。ACK 表示确认字段中的值是有效的。RST、SYN 和 FIN 用于连接的建立和拆除。CWR 和 ECE 用于明确拥塞通告。PSH 指示需要将数据立即交给上层。

    往返时间估计

    首先样本往返时间（SampleRTT)。然后每次发送并接收到数据时（对重传的不计算 SampleRTT）对这个往返时间进行更新，因为网络会有波动。计算公式为

SampleRTT 是这次数据来回所需要的时间，EstimatedRTT 是估计出来的平均时间，最终使用 EstimatedRTT。$\alpha$ 一般取 0.125。

而估算 SampleRTT 偏移 EstimatedRTT 的程度也是有价值的。计算公式为

$\beta$ 一般取 0.25.

重传时间间隔可以用 TimeoutInterval = EstimatedRTT + 4 * DevRTT 计算得出

可靠数据传输

首先考虑最简单的情况，即只需要考虑定时器。定时器重置的时期有

  • 如果从上层应用接收到数据并且定时器未启动，则启动定时器
  • 定时器超时重置定时器
  • 收到 ACK 并且 ACK 的确认号值比 SendBase（最早未被确认的字节序号）大，那么则更新 SendBase 并且重置定时器。这是因为 TCP 采取累积确认的模式，只有前面字节全部接收到才会继续往后确认。

例如主机 A 上传序号 92，长度 8 字节和序号 100，长度 20 字节的数据。结果两个都被接收但是两个的 ACK 都丢失了，那么这是时第二种情况一次只会上传一个，等到第二次超时或者接收 ACK 才会进行下一步。

或者接收到了序号 100 的 ACK，确认号是 120，那么下次直接从 120 开始传输数据，并且确认号是 100。

下面是超时重传的一些改进方法

超时间隔加倍

因为在某些情况下网络可能比较拥堵，原来推测出来的间隔值太小了。这就会导致不断的重传。为了避免这种问题，可以每次超时重传就让时间间隔乘 2.

快速重传

超时重传另外一个原因是超时周期可能过长。例如接收方接收到了许多失序的数据，但是低端始终有一块没有接收到，这种情况只有等待发送方超时重传，但是如果发送方重传时间间隔过长便会降低性能。

这里使用的重传方法既不是回退 N 步也不是选择重传，而是二者的综合。

事件 接收方动作
按序的报文段到达，并且所有在期望序号前的数据都被确认 等待 500ms 再发送 ACK。因为很可能下一个报文段也要到达，这样返回时只需要确认下一个报文段
按序报文段到达，并且另一个按序报文段等待 ACK 传输 2 立刻发送单个积累 ACK，以确认两个按序报文段
比期望序号的的失序报文段到达 立刻发送冗余 ACK，指示期望字节的序号
可以填充失序区间的报文段到达 若报文段起始于低端，则立刻发送 ACK
2. 也就是前面的报文段还没有发ACK ↩

如果发送方接收到三次确认号相同的 ACK（冗余 ACK）后选择立刻重传。接收方在接收失序的数据时会发送一个 ACK，它的确认号仍是未被接收数据中的首地址。

流量控制

TCP 通过让发送方维护一个叫接收窗口的变量来提供流量控制。接受窗口也就是接收方还有多少缓存可用于接收。定义下列变量进行控制

  • LastByteRead: 接收方应用程序从缓存中读出的最后一个字节编号
  • LastByteRcvd：到达接收方的最后一个字节编号

接受窗口 rwnd = RcvBuffer - [LastByteRcvd - LastByteRead]

LastByteSend 指的最后发送的字节，LastByteAcked 表示最后确认的字节。LastByteSend-LastByteAcked 表示已经发送但是没有得到响应的字节数。

接收窗口也就是接收方还可以接受的字节数量，他会随着返回报文的窗口字段返回给发送方，从而让发送方知道自己还可以发送多少字节。

当 rwnd 为零（缓存满）的时候，规定主机 A 继续发送一字节的报文段，这些报文段会被接收方确认，直到确认报文中 rwnd 非 0.

这样做的目的是只有发送方发送接收方才会发送确认报文，才会通知 rwnd 改变，如果发送方满了就不发送那么接收方已经处理完数据发送方也不知道。

TCP 连接和关闭过程

  1. 客户端的 TCP 首先向服务器的 TCP 发送一个报文，报文首部一个标志位（SYN 比特）被置为 1. 另外客户会随机选择一个初始序号，并将此编号放在序号字段中，用来保证安全。
  2. 报文到了服务器后，服务器将分配缓存和变量，并向客户发送允许连接的报文段。这个允许连接的报文中 SYN 被置 1，并且确认号字段是初始序号 + 1，并且服务器也选择了一个初始序号并且放入序号字段中。这个报文又叫 SYNACK 报文段
  3. 在收到返回报文后，客户也要给该连接分配缓存，然后又发送一个报文段，这个报文段的确认字段为服务器初始序号 + 1， 因为 TCP 已经建立，SYN 被置 0，并且这个报文段中可以存放数据。

参与 TCP 连接的双方都有权利终止连接，终止连接的过程为：

  1. 例如客户进程终止连接。客户向服务器发出一个特殊的 TCP 报文段，报文段中 FIN 标志位为 1
  2. 服务器接收到之后，发送确认报文段，然后发送它自己的终止报文段。

拥塞控制

在理想情况下，两个主机通过一个路由器传输数据，并且这个路由器的缓存无限大。假设这个链路的容量为 R，发送数据速率为$\lambda$ 字节 / 秒。那么当 $\lambda$ 小于 R/2 时，传输数据速率就是$\lambda$，当速率大于 R/2 时，传输速率为 R/2（因为是发送和接收双向的）。

现在考虑容量有限并且分组会丢失。这种情况下$\lambda$ = R/2 时传输速率达不到 R/2（因为要重传），大概在 R/3 左右。如果发送方提前发送分组会导致重复发送，利用率更低。

TCP 拥塞控制

为了实现拥塞控制，需要添加一个变量 cwnd，他和流量控制变量 rwnd 有类似的作用

LastByteSent - LastByteAcked <= min{cwnd, rwnd}

那么 cwnd 在什么情况下会被调节呢

  • 丢失报文段。 丢失报文段代表拥塞，因此用降低发送方的发送速率，也就是降低 cwnd。
  • 确认报文段。 当一个先前未被确认数据的确认报文段到达时，表示现在网络情况良好，可以增大速率。

    慢启动、拥塞避免和快速恢复

    慢启动

在启动时，cwnd 往往设置的比较小，然后每次被确认就增加一个 MSS（每次传输数据的最多数量）。然后第二次增加两个，第三次增加 4 个，也就是成指数级增长。

当存在一个由于超时导致的丢包事件时，就把 cwnd 设置为 1 并重启慢启动，他还将一个标记 ssthresh (慢启动阈值）设置为 cwnd/2。

之后如果缓存达到或超过 ssthresh 后，会终止慢启动并且开启拥塞避免模式。

如果检测到三个冗余 ACK，那么会快速重传并且执行一次快速恢复。

拥塞避免

进入拥塞避免状态时一般都在 ssthresh 左右，这时需要减慢 MSS 的增长速度，因此可以每过一个 RTT（平均往返时间）就增长一个 MSS。这样就由原来的指数级增长变为线性增长。

当又遇到超时导致的丢包后，就将 cwnd 重置并且将 ssthreash 更新为 cwnd 的一半。如果遇到三次 ACK 导致的丢包，因为这种情况说明网络情况还比较好，因此只需要将 cwnd 减半并且 sstresh 更新为 cwnd 的一半然后进入快速恢复状态

快速恢复

快速恢复变成了 每接收到一个冗余 ACK 就让 cwnd 加一个 MSS，直到对视报文段的一个 ACK 到达时，TCP 在降低 cwnd 后进入拥塞避免状态。这个过程是非常短暂的，一般只会持续一个回合。

有些版本的TCP协议是没有快速恢复的，快速恢复是为了在网络不拥堵的情况下尽快发送

出现三个重复的ACK就会导致快速恢复，出现超时就会导致慢启动

如图， 纵轴是cwnd，横轴是第几个RTT。纵轴代表了一个RTT可以发送多少个数据包。

在1-4和14-16都是慢启动阶段，因为成指数级增长。

黄色部分都是拥塞避免阶段，每一回合增长1.

而下降一半的都是快速启动阶段，要注意到本来都是应该下降一半的，但是实际上都没有下降一般。例如第一个是从15到10， 第二个是从10到8.这是因为进行了快速启动，每收到一个冗余的ack都会让窗口加1，而一个回合内就可能受到多个冗余ack，并且在一个回合内很有可能会接收到按序的数据报。