Network Congestion Avoidance through Packet-chaining Reservation

基于数据包链预约的主动拥塞控制协议

预约的本质就是在整个网络中做仲裁，而仲裁时间和仲裁粒度必须要匹配。基于此，本文提出了数据包链预约协议（Packet-chaining Reservation Protocol，PCRP），选取合适的预约粒度以和预约的时间相匹配，提升预约的准确性和灵活性；还通过在全网提升短流的优先级的方法，有效的保障了短流的利益，降低流完成时间。

数据包链预约协议

对应于在 SRP 中分配预约时间片的方法，PCRP 采用以数据包链（packet chaing）为单位进行预约的方法。术语“packet-chaing”是几年前首次提出的，它通过将发往同一目的地的数据包链接在一起来操作，以复用数据包在通过交换机时的交换机连接，减少交换机仲裁次数。本文借鉴了数据包链的概念来描述流中几个连续数据包的集合。为了优化流完成时间，PCRP 在发送端采用基于SRPT 的调度策略，并使用多优先级队列来支持接收端的基于优先级的调度。此外，PCRP 使用动态优先级表来执行多次授权。将详细描述 PCRP。

1.1设计空间

由预约协议表示的主动拥塞控制机制基本上通过调整发送端的行为来避免网络拥塞。发送端可以控制要发送的数据量：不发送，发送一个数据包或发送整个流。SRP，SMSRP 和 BFRP 都是极端的。它们实际上是以整个流为粒度进行预约的，第二章解释了这种情况的缺点。在另一个极端，预约是以数据包为粒度的，这就要求接收端在每次发送端想要发送数据包时发送信用数据包。但是，我们没有时间去安排和调度每个数据包。因此，短流将因等待接收端的调度决定而受到影响，并且大量的信用数据包将使网络负担加重。

PCRP 设计空间的一个挑战是如何选择链接数据包的大小来平衡准确性和预约开销之间的矛盾。一方面，在预约期调度每个数据包在时间上是昂贵的。另一方面，使用流的粒度进行调度将显着地降低预留准确性。为了匹配作为单个往返时间（RTT）的网络仲裁周期，我们将 RTT 的数据量作为数据包链的大小。这是一个很好的折衷方案。

PCRP 的另一个挑战是如何最大限度地避免短流受到协议本身的干扰。因为长流比短流长得多并且可以严重阻塞短流，所以我们必须在长流前安排短流传输以减少短流的完成时间。PCRP 为短流分配更高的优先级，以确保在发送端，网络和接收端中更早地调度这些流。此外，PCRP 允许多个请求和多个授权以实现过度匹配。我们缓冲到达的数据包链并优先考虑短流的数据包链接。结合过度匹配和优先级策略，PCRP 可以显着减少流完成时间。

1.2 执行过程

PCRP 将每个流划分为多个数据包链，每个数据包链包含固定数量的数据包（流的尾数据包链包含的数据包数可能少于此值）。如图（a）所示，数据包链的大小设置为可以在 RTT 中传输的数据量。Flow 1 分为三个数据包链，其中尾数据包链仅包含两个数据包。由于 flow 2 的长度小于数据包链，因此整个流是一个数据包链。

由于 PCRP 不需要预先进行发送预约请求，因此发送端可以以投机的方式直接将每个流的第一个数据包链发送到网络中。投机包具有比正常包更高的优先级，并且不会在网络中被丢弃。虽然第一个数据包链可以以投机方式直接发送，但剩余的数据包链必须在发送之前等待接收端的授权（grant）才能激活。图（b）显示了 PCRP 过程。发送源 S 直接将 flow 1 的第一个数据包链的数据包逐个注入网络，并向接收端请求发送下一个数据包链。在从 S 接收到数据包之后，接收端D 计算剩余的 flow 1 的长度，并确定是否有必要向 S 发送授权数据包。如果需要，则向 S 发送授权数据包。同时，授权数据包携带优先级信息，用于引导 flow1 的下一个数据包链（即非投机数据包链，正常数据包链）中在进入网络时的的优先级。在 S 从 D 接收到授权数据包并激活下一个数据包链之后，数据包链中的数据包可以参与发送方的调度仲裁，直到整个流被发送完成。由于合理的数据包链大小设置，flow 1 的传输过程是连续的。

PCRP 允许接收端同时授权多个不同的流，其中高优先级的短流优先于低优先级的长流。一个例子如图3.3（c）所示。当 D 从 S1 接受 flow 1 时，由 S2 发送的较短流 flow 2 到达 D。此时，D 将基于其优先级优先处理 flow 2 的数据包，并将到达的 flow 1 的数据包临时存储到 NIC。在完全接收 flow 2 之后，再从 NIC 的缓冲区中提取来自 flow 1 的数据包进行处理。发送源 S1 等待 D 发送的第二个授权数据包到达并重新开始 flow 1 的发送。由于数据包链的大小恰好是可以在 RTT中传输的数据量，所以当 flow 1 的最后一个数据包链到达时，存储在 D 的 NIC缓冲器上的数据包刚好被 D 处理完毕，因此在重新启动之后 flow 1 的传输仍然是连续的。

1.3发送端行为

当应用程序生成流时，PCRP 发送端首先将其划分为多个数据包链。数据包链具有以下状态：

投机：每个流的第一个数据包链可以在没有授权的情况下以投机模式直接发送，并承担向接收端发出类似预约请求的任务。

非活动：除流的第一个数据包链外，任何后续数据包链默认情况下都处于非活动状态。需要激活它们才可以进行发送，这些数据包链必须等待来自接收端的授权。

活动：收到授权后，发送端激活相应的数据包链。激活的数据包链可以参与调度仲裁，直到它被发送。

相应地，每个流也有两种状态：就绪和等待。当流具有投机或活动数据包链时，流处于就绪状态; 如果流的数据包链都是非活动状态，则流处于等待状态。

PCRP 在发送端利用 SRPT（最短剩余处理时间）仲裁策略。SRPT 调度策略的基本机制是根据流的大小确定流的优先级，从而可以优先传输剩余最小的流。这种策略的优点是即将完成传输的流不会被另一个较小的短流中断。但是，使用SRPT，更多的投机数据包链将无节制注入网络，然后汇聚到接收端。为了减轻对接收端和网络的压力并更好地保证预约的效率，我们将变量 EU-Flow（最早未完成流）添加到调度器中。每次发送数据包时，发送端调度器将进行仲裁。调度器首先检查 EU-Flow 变量记录的流是否就绪。如果是，则调度器选择其为将要传输的流; 如果没有，它将使用 SRPT 策略选择另外一个已就绪的流进行传输。

图显示了 PCRP 发送端的调度策略。图的左侧是每个流的剩余长度。Flow 3 处于等待状态，不能参与仲裁。调度器首先检查 EU-flow 是否准备就绪。Flow 4 准备就绪，因此调度器选择它。其他已就绪的流，如 flow 2，其剩余大尽管小于 flow 4 的剩余大小，必须暂时等待。EU-Flow 机制确保了首先开始发送的流优先从发送端发送。这不仅避免了发送端向网络中注入大量投机数据包所造成的拥塞，而且避免了短流被超短流拦截而引起的不必要的性能下降。

在 HPC 的通信负载中，长流的长度经常是短流的几百倍。如果调度器总是执行上述方法，那么长流将被饿死。为了避免长流被饿死，PCRP 会考虑流在调度器中的等待时间。如果长流的等待时间超过流最大等待时间（Maximum Flow Wait Time，MFWT），则长流的优先级将增加，以便调度其可以及时将其发送。请注意，我们不会将长流的优先级提高到最高级别，以避免阻塞其他短流的发送。在我们的实现中，MFWT 根据 HPC 网络负载特性设置为固定值。

1.4 接受端行为

PCRP 接收端根据其优先级调度数据包链。我们在 NIC 上添加了一些轻量级缓冲区，以临时存储到达接收端的数据包，这些缓冲区以多个优先级队列的形式组织，如图3.5所示。接收端 NIC 首先根据优先级从队列中提取数据包，从最高到最低。但是，NIC 的接口速率是固定的，即每个周期只能接收一个 flit，并且必须串行处理 flit。到达的数据包不会自动驻留在缓冲区中，这样优先级队列就不能发挥作用。为此，我们在 NIC 上添加了一个等待窗口。在此窗口中，NIC 仅接收数据包但不处理它，因此这些数据包将驻留在缓冲区中。

PCRP 在接收端侧维护动态优先级表。当 NIC 从队列中提取新流数据包进行处理时，它会将流的信息添加到动态优先级表，并根据流的大小对表重新进行排序。然后，NIC 对动态优先级表进行索引，并通过比对流的大小和剩余的大小来确定提取的流是否需要授权。此外，NIC 从动态优先级表中获取该流的优先级，并通过授权报文向发送端通知优先级信息。当发送端收到授权时，它会激活相应的数据包链并用授权数据包携带的优先级标记它。当数据包链到达接收端时，它根据其优先级进入相应的队列。

但是，接收方无法在没有限制的情况下授予所有到达的流量。PCRP 设置了在接收端可以授权的流的数量的上限。也就是说，当表已满时，NIC 将不会在新的流到达时更新动态优先级表，并且除非表中的旧流已被处理掉，否则无法发送授权数据包。设置授权的上限阈值是一种预约的方式。PCRP 接收端可以同时响应多个流的预约请求，并将不能立即处理的数据包链临时存储到缓冲区中。

3.5 数据包链优先级

PCRP 发送端发送的每个数据包链都带有优先级。投机数据包链的优先级由集中统计单元根据流的大小分布决定，正常数据包链的优先级由接收端的授权决定。

每个数据包链中的所有数据包都具有相同的优先级。投机数据包链具有比正常数据包链更高的优先级。如果网络支持 8 个优先级，并且 P0 > P1 >…> P7，一种可能的解决方案是将 P0 到P3 分配给投机数据包链，将 P4 到P7 分配给正常数据包链。

投机数据包链优先级。投机数据包链的优先级由集中统计单元获得，集中统计单元计算网络中流的长度分布，然后通知发送方。如图3.6所示，集中统计单元收集接收端接收到的流的大小信息，然后计算网络中流的累积分布函数（CDF）。集中统计单元将 CDF 分成四个相等的部分（基于投机数据包链被分配四个优先级的假设），然后获得对应于每个优先级的大小范围。发送端收到该信息后，根据每个流的大小设置其第一个数据包链的优先级（投机数据包链接）。由于 HPC 网络中的实时流量不会频繁更改，因此无需实时更新优先级信息。因此，为了减少浪费网络带宽，以较低的固定频率动态更新投机数据包链的优先级信息。

**正常数据包链优先级。**正常数据包链的优先级信息由接收端实时动态调整。接收端维护一个动态优先级表，并根据流的大小对其进行排序。流的长度越小，优先级越高。如果表中的流的数量超过了可以分配给正常数据包链的优先级的数量，则所有后续所有的流都被赋予最低优先级。如图3.5所示，分配给第一个到第五个流的优先级分别是 P4，P5，P6，P7 和 P7，并且所有排序在更后面的流将被分配给最低优先级。

动态优先级表有助于接收端更准确地处理正常的数据包链优先级。另外，接收端不需要考虑整个网络的流的大小分布情况，而优先级可以由动态优先级表直接分配。这确保了在优先处理短流的同时网络性能受到的影响较小。