Channel Reservation Protocol for Over-Subscribed Channels and Destinations

Channel Reservation Protocol for Over-Subscribed Channels and Destinationsv

1. 信道保留协议CHANNEL RESERV ATION PROTOCOL

使用CRP，每个超额预订的信道和目的地都会保留一个预留表。该表中的每个单元代表一个未来的时隙，并以时钟周期（连续）粒度记录可用带宽。源发送记录参与资源可用性的请求。然后，目的地将计算满足请求大小的最早的公共可用性，并以授予进行响应。然后，Grant然后在转移回源时最终确定参与资源中的保留。

1.1 Reservation Tables

将预留表与每个资源相关联。表的每个单元格对应一个时隙，该单元格中的值表示相应时隙中可用带宽的cycles数。上图显示了32个表单元（$V_{cells}$）的示例配置，每个表单元占用512个周期（$C_{max}$）。在此示例中，将来最多可以保留16384个周期的资源。在图中，单元格A对应于包含周期0-511的时隙，单元格B代表周期512-1023的时隙，依此类推。如图所示，时隙（单元）A具有512个可用周期，而时隙B仅具有10个可用周期。
如果$t[i]>0,t[i]+t[i+1]\geq x$，则资源可以在时隙i内容纳大小为x的请求。也就是说，对应的表格单元必须至少有一个空闲时钟周期，并且该表格单元与下一个单元的总和必须至少为请求大小。这允许请求跨越两个相邻的单元格，从而减少碎片的不利影响。
当时间提前$C_{max}$个cycles时，保留表在逻辑上会移动一个单元格。在上面的示例中，当系统时间变为512时，删除单元格A，并将表向左移动一个。在右侧插入了一个值为$C_{max}$的新单元格。为了保持同步，必须使用某种技术*（A fine-grain clock synchronization mechanism for myrinet clusters. ）*将所有资源同步到全球时基，且精度至少为±$C_{max}$个cycles。
为每个关键资源维护保留表。每个目标的网络接口卡（NIC）均包含该目标的出口通道的表格。每个路由器为驱动潜在瓶颈通道（例如群集间通道）的每个输出端口维护一个表。

1.2 Reservation Handling in Channels

预留请求携带一个长度为$V_{cell}$的位向量，其中每个位都表示一个时隙的可用性。请求向量初始化为全true。每次请求向量传递资源时，该资源都会重置向量中与资源没有请求带宽的时隙相对应的任何位。实际上，每个资源在通过时将其可用性与请求向量进行“AND”运算。当请求向量到达目的地时，它表明：在请求通过资源时所有必需的关键资源都具有足够带宽来处理请求的时隙。

预留向量与预留表同时向左移动一位。当预留向量发生移位时，将在右边插入一个T比特，因为最初在新的时隙内资源可用。保留向量移位由路由器执行。

考虑下图。在此示例中，单元格A和C保持为T，因为该表可以容纳这些时隙中的80个周期的请求。单元D将其位设置为false，因为它没有剩余带宽，而单元E将其位设置为false，因为单元E和F的总和不足以进行请求。最后，单元格B保持为真，因为单元格B和C的总和可以容纳80个循环。

1.3 Rservation Handling in Destinations

目的地将到达的请求的预留向量与其自己的表进行比较，并计算出请求路径上所有参与资源（包括目的地）可以容纳的最早时隙。与信道中的向量处理类似，如果时隙具有可用周期并且其和下一个小区的可用带宽之和满足传入请求，则认为该时隙在目标位置可用。

在对它们的可用性进行“与”运算后放入请求向量中，目的地生成一个授权响应，该响应带有一个时间戳，该时间戳对应于最终向量的最左边的T位。这是所有必需资源都可用的最早时间。

此操作如下图所示。在此示例中，目的地的单元格A无法容纳请求，因为目的地的保留表中的单元格A和B的总和小于所请求的80个周期。但是，单元格B可以容纳该请求，因为合并的单元格B和C具有140个自由周期。单元C也能够容纳该请求。我们选择单元格B作为最早可以处理请求并减少单元格B和C的表条目的表格，以保留80个周期（每个单元格40个）。实际的预留周期跨越了两个时隙，包】括时隙B的最后40个周期和时隙C的前40个周期。时间戳记为984，对应于时隙B的最后40个周期的第一个周期

1.4 Grant and Retry Operation

当授权数据包返回源时，它们会沿其路由递减每个保留表的相应单元，以将分配的带宽标记为其他流不可用（图2中的C点）。如果那时与时间戳相对应的单元没有足够的周期来满足请求，则从下一个单元中减去任何剩余的时隙。在图5的示例中，目标为80个保留周期的周期生成了周期984的授予时间戳记。当该授权到达具有图4中所示的预留表的信道时，单元B对应于周期984，因此将减少10，并将其设置为0，而将单元C减少剩余的70个周期，从而将其设置为30。

如果两个表单元格不再具有足够的周期来满足请求，则授权将转换为重试响应。如果带宽是在保留请求到达其目的地，生成授权并返回到参与信道（从图2中的A点到C点）所花费的时间内由另一个流保留的，则可能会发生这种情况。如果预订请求的最终向量没有T位或不存在公共可用性，则目的地也会发出重试。重试指示在短暂的延迟($R_{cycles}$)后源重新传输。唯一的例外是当发出重试的原因是目的地的预订表在任何时间段内都无法使用指定的预订大小，而与预订请求的向量无关。在这种情况下，重试将指示源在$V_{cells}×C_{maxcycles}$之后减去往返延迟后重新发送其请求

当授权在信道上转换为重试时，目的地中预留和信道中回复已经遍历过的预留不会取消。我们的实验证实了推测性数据包（在下面说明）和控制数据包有效地利用了带宽。大量超额预订的资源更靠近流量源会增加带宽不必要地在下游资源中以这种方式分配的可能性。

为了防止由于多个流试图保留相同的时隙而导致重试，保留请求可以选择在它们遍历参与信道时急切地保留最早的时隙（图2中的A点）。如果有目的地，目的地将优先授予该预定的时隙。预留赠款会释放对赠款流程的所有不必要的急切保留。由于急切的预约与流标识符相关联，因此这需要标签匹配。为单个请求急于保留一个以上的时隙（$R_{res}$），会增加目的地授予预保留时隙的可能性，即使存在合格请求，也会增加空闲带宽的可能性。授予和重试被强制使用请求路径的相反方向返回，以便它们可以操纵正确的通道保留表。通过使请求数据包记录其路径或在确定性路由的情况下通过简单的计算来标识反向路径。