八、信息发送与接收

每一个UDT实体包含2个逻辑部分：发送端和接收端。

发送端，根据拥塞控制和流量控制，发送/重传应用数据包。

接收端，接收数据包和控制包，并且根据接收到的信息包和定时器发出控制包。接收器 负责触发和处理所有的控制事件，包括拥塞控制、可靠控制以及相关的机制。

UDT总是试图将应用数据分组成固定大小的包(当连接建立后，遵循最大包大小约定)， 除非应用数据被发送时不够一个最大数据包的长度。

8.1 发送端算法

数据结构：

1) 发送端丢失链表(Sender’s Loss List)：丢失链表用于存储丢失包的数据序列 号。这些序列号，来源于接收端发送的NAK包的压缩信息或者在超时事件里的超 时包序号。链表序列号以升序存储。

数据发送算法：

1 如果发送端丢失链表非空，重传链表头部序列号的包，并且删除该头部节点序列 号。goto ⑤。

2 在消息模式(DGRAM)下，如果包的序号在发送端丢失链表里滞留的时间超过了申 请指定的包生存期(TTL)，发送消息丢弃请求，并从发送端丢失链表里删除关联的包。goto ①。

3 等待，直到有应用数据需要被发送。

4 如果，未应答的包个数超过了流量/拥塞窗口大小，等待直到一个ACK事件触发， goto ①。否则，封装一个新的数据包并发送它。

5 如果当前数据包的序列号是16n，n是一个整数，goto ②。

6 等待(SND - t)时间，SND是包与包的发送间隔时间(由拥塞控制更新)，t是从① 到⑤的总时间。goto ①。

8.2 接收端算法

数据结构和变量：

1) 接收端丢失链表(Receiver’s Loss List)：是包含“二元组和一个参数”的链表。

二元组包括：检测到的丢失数据包的序列号，最新丢包的反馈时间；一个参数k 是每一个丢失包被NAK反馈的次数。节点元素按照包序列号的升序进行排序。

2) ACK历史窗口：一个循环数组， 用来记录已经被发送的ACK序列号和ACK被 发送的时间。如果数组中没有更多空间的时候新的值将覆盖老的值。

3) PKT历史窗口：一个循环数组，用来记录每一个数据包到达的时间。

4) 包对(2个包作为一对)窗口：一个循环数组，用来记录探测包对之间的间隔时间。

5) LRSN：一个变量，用来记录接收到的数据包的最大序列号。初始化值等于初始包 序列号减1。

6) ExpCount：一个变量，用来记录持续EXP超时事件发生的次数。

数据接收算法：

1 查询系统时间，用来检查ACK、NAK或者EXP定时器是否期满。如果有定时器期 满，就去处理相应的事件(处理流程见8.2节的后续描述)，然后复位定时器。对于 ACK定时器，

2 绑定（Bind）UDP后，自接收数据开始计时。如果没有包到达，goto ①。

3 复位ExpCount为1。如果没有未应答的数据包，或者接收包是ACK/NAK控制包

复位EXP定时器。

4 检查信息包的包头第一位。如果是控制包，根据信息域的Type分别处理，并 goto ①。

5 如果当前数据包的序列号是16n + 1。n是一个整数，记录的是当前包与上一个包 对窗口的数据包的时间间隔。

6 在PKT历史窗口里记录包到达时间。

7 如果，当前数据包的序列号大于LRSN+1，将(LRSN+1，当前数据包序列号)开 区间内的数据包序列号放进接收端丢失链表里，然后将区间内的丢包信息压缩后 作为一个NAK控制包发给发送端。

如果，当前数据包的序列号小于LRSN，从接收端丢失链表里删除该数据包的序列 号。

8 更新LRSN值。goto ①。

ACK定时器事件处理流程：

1 根据以下规则，在接收端查找接收到的所有包之前的序列号：如果接收端丢失链 表是空的，ACK序列号设置为LRSN+1；否则，就是在接收端丢失链表里的最小

序列号。

2 如果，ACK序列号等于已经被ACK2应答的最大ACK序列号，或者等于上次应答 的ACK序列号并且两次应答包之间的时间间隔小于2个RTT，停止（不发送应答 包）。

3 分配给当前应答一个唯一的增长的ACK序列号。将RTT、RTT偏差和流量窗口大小 (可用的接收端缓冲区大小)封装入ACK控制包。如果ACK定时器未触发该ACK事 件，发送该ACK控制包，然后停止。

4 根据以下算法，来计算包的抵达速度：从PKT历史窗口中取出最近16个包到达的 间隔值，计算出中值(AI)。在这16个值中，删除那些大于AI * 8和小于AI / 8的 包。如果最后余下的值超过8个，再计算余下的平均值(AI’)，那么包抵达速度就是 1 / AI’（单位是每秒包的个数）；否则，(余下的值 <= 8)即是0。

5 根据下面的算法，来计算估计的链路容量：从包对窗口里取出最近的16个包对间 隔值，计算出中值(PI)，那么链路容量就是1 / PI(单位是每秒包的个数)。

6 将包到达速度和估计的链路容量封装进ACK控制包，然后发送出去。

7 记录当前的ACK序列号，ACK号和ACK被发送的时间。并且将ACK号和ACK被 发送的时间记录进ACK历史窗口里。

NAK定时器事件处理流程：

搜索接收端丢失链表，找出所有的最后反馈时间在 k * RTT 之前的包序列号。变量k， 初始值为2，并且每次一个包序列号被反馈时自增1。

将这些找出的包序列号信息压缩后，封装成一个NAK控制包发给发送端。

EXP定时器的事件处理流程：

1 将所有未应答的包，追加到发送端丢失链表里。

2 如果3分钟已经流逝，或者ExpCount > 16并且自从上次ExpCount复位为1 后又流逝了至少3秒时，关闭UDT连接，然后退出。

3 如果发送端丢失链表是空的，发送一个Keep-alive控制包给对等实体。

4 ExpCount自增1。

接收到ACK控制包时：

1 更新最大应答的包序列号。

2 回复一个ACK2控制包，ACK2的ACK序列号使用相同的ACK序列号。

3 更新RTT值和RTTVar值。

4 更新ACK和NAK的周期为 4 * RTT + RTTVar + SYN。

5 更新流量窗口大小。

6 如果控制包是轻量的应答，停止。

7 更新包的到达速率：A = (A * 7 + a) / 8，值a被接收的ACK控制包携带。

8 更新估计的链路容量：B = (B * 7 + b) / 8，值b被接收的ACK控制包携带。

9 更新发送端的缓冲区(释放已经被应答的缓冲区)。

10 更新发送端丢失链表(删除所有已经被应答的序列号)。

接收到NAK控制包时：

1 将NAK控制包里所有的序列号追加进发送端丢失链表里。

2 通过速率控制来更新SND周期。

3 复位EXP定时器。

接收到ACK2控制包时：

1 根据ACK2控制包的ACK序列号，在ACK历史窗口里定位关联的ACK记录。

2 更新已经被应答的最大ACK序列号。

3 根据ACK2 包到达时间和ACK 出发时间，计算新的rtt 值，并且更新RTT 值：

RTT = (RTT * 7 + rtt) / 8。

4 更新RTT偏差值：RTTVar = ( RTTVar * 3 + abs(RTT - rtt) ) / 4。

5 更新ACK和NAK的周期为 4 * RTT + RTTVar + SYN。

接收到消息丢弃请求时：

1 在接收缓冲区里，标记所有的消息包为不可读。

2 在接收丢失链表里，删除关联的包序列号。

接收到Keep-alive控制包时：Do nothing。

接收到握手/关闭控制包时：参见7.UDT连接和关闭。

8.3 流量控制

流量控制窗口初始大小为16。

接收到ACK控制包时：接收端的流量窗口大小更新成当前可用的缓冲区大小。

8.4 丢包信息的压缩方法

丢包信息是一个32位整数的数组，被NAK控制包携带。

如果数组里的一个整数是一个标准的序列号(第一位是0)，意思是该序列号的包丢失。

如果整数的第一位是1时，意思是从当前序列号的包到下一个整数序列号(第一位是0)之 间的包都丢失。

例如，以下信息被一个NAK控制包携带：

0x00000002, 0x80000006, 0x0000000B, 0x0000000E

意思是序号为2，6，7，8，9，10，11和14的包丢失。