Bilateral Flow Reservation Protocol，BFRP

​ 与基于数据包的调度机制不同，BFRP通过调度流来避免拥塞。我们的设计基于SRP的调度策略。流完成时间与大流和小流的发送顺序有关。首先安排小流量可以减少平均流量完成时间。但是，当调度程序每次选择最小流量时，大流量可能会饿死。为了避免这种情况，我们为每个流设置优先级p，并且p等于流大小。每次调度程序对流进行舍入时，p的值都会减少d。当大流量四舍五入时，p的值将变得非常小，调度程序每次都会选择具有最小p的流量，以避免出现饥饿的情况。

​ 图3显示了BFRP的过渡过程。在一个节点中，整个过程分为三种状态：SPECa，SPECb和NORMAL。如果网络没有拥塞，则BFRP将不会进入NORMAL状态。 SPECa状态是BFRP中发送方的初始状态。首先，发送方将选择具有最小p的流，并将推测性数据包发送到网络中。当发送方收到否定确认数据包（NACK）时，它将发送y预留数据包到目标，然后进入SPECb状态。但是，在SPECb状态下，如果发送方在预留数据包发送开始到授权时间到达之间的时间内未执行任何操作，则会急剧增加准备发送的其他流的排队延迟，从而导致平均流量延迟增加。因此，建议在达到授权时间之前，先发送其他流的推测包。详细地说，在发送方发送预留数据包之后，数据包调度程序会在其他发送队列中选择具有最小p的就绪流，然后提前发送这个流推测性数据包。当发送方收到确认数据包（ACK）时，它将继续发送推测数据包。当接收到NACK时，为了确保源的多个预约流没有冲突授予时间，发送方将不对此流进行预留，以确保只有一个流预约给目标。但是，调度程序将选择另一个具有最小p的流进行传输。在授予时间到来之前，BFRP进入正常状态，并且数据包调度程序选择保留的流，发送方以正常模式发送该流的数据包。传输完成后，调度程序将根据此规则选择其他准备传输的流。

image-20200803203856734

​ 下图显示了BFRP的操作。首先，我们假设网络没有拥塞。数据包调度程序从发送方队列（1）中选择具有最小p的流。之后，发送方将推测性数据包发送到目的地（2）。推测数据包在低优先级VC上传输。每个推测性分组都与生存时间survival time（ST）和排队时间相关联，如果网络中的推测性分组的排队时间大于ST，则该推测性分组将被丢弃。在我们的实现中，ST是基于高负载均匀流量下网络的数据包延迟分布的固定值，当推测性数据包进入路由器的输入端口时，数据包的排队时间开始。当排队时间到达输出端口中VC的开头时，将检查排队时间。接收到推测性数据包后，目的地需要用ACK进行回复，以通知发送方这些数据包已被接受。当网络没有拥塞时，通常会接受推测性数据包，并且目标返回ACK（3）。这样，分组将以推测性分组的形式传输，并且不会带来任何其他开销。

image-20200804090633984

​ 在拥塞的网络中，初始操作与上述相同。但是，当面临端点拥塞时，由于到达ST的排队时间，推测性数据包将被丢弃。届时，NACK将在路由器中生成并发送回发送方（5）。发送方中的NACK管理器收到NACK数据包后，发送方将从SPECa状态转换为SPECb状态，然后发送预约数据包与目标进行握手（6）。预留数据包很小，优先级最高。它在单独的VC上传输，以确保高优先级传递。预留数据包包含一个值n，它是将要发送的数据包的数量。

​ 一旦接收到预留包，接收器中的时间管理器将根据预留包中的n为发送方分配授权时间（$t_s$），并在回复包中返回相应的授权时间（7）。之后，时间管理器状态将正确更新。如果有另一个发送方发送的其他保留数据包到达此接收方，则时间管理器将返回给该保留数据包不早于$t_s + n(1+ε)T_p$的开始时间，其中常数$T_p$是接收方接收所需的时间信道来接收消息，并且ε取决于控制分组的带宽开销。发送方的授权管理器将在收到授权数据包后开始计时，然后数据包调度程序将选择准备发送到其他发送队列中的，具有最小p的流（8）。然后，选定的流以推测性数据包的形式发送数据包（9）。如果目的地没有拥塞，将返回ACK数据包（10）。发送方继续发送推测性分组（11）。但是，如果端点在某个时刻过载，则推测包将被丢弃，路由器将生成NACK包并将其返回给发送方（12）。在接收到NACK之后，发送方将不会调度该流以发送保留数据包，而是选择具有最小p的另一个流并继续发送推测性数据包（13）。当预留流达到授予时间时，BFRP从SPECb状态进入正常状态，并且调度程序调度发送队列以发送普通数据包(14)(15)。在所有剩余的数据包都已发送后，BFRP从正常状态进入SPECa状态。所有传输将重复此过程。应当强调的是，为了最小化由控制操作引起的开销，所有预留分组，ACK，NACK和授权分组都是小的并且在单独的高优先级信道上发送。