The Turn Model for Adaptive Routing中的west-first算法

图5a显示了在2D网格中禁止两次旋转的一种方法。禁止转弯的是向西的两个转弯。因此，要向西，必须从那个方向出发。这就提出了west-first-routing算法：如果需要，先向西路由一个包，然后自适应地向南、向东和向北路由。west first算法的示例路径如图5b所示。在该图中，黑色方块表示节点，灰色条表示需要数据包等待（虚线）或采取替代路径的阻塞通道。注意，显示了最小路径和非最小路径。基于Dally和Seitz[14]的工作证明了west-first部分自适应算法是无死锁的，他们证明了如果互连网络中的信道可以被编号，那么路由算法是无死锁的，这样算法就可以沿着信道严格地减少（或增加）个数来路由每个包。由于west-first算法先向西然后在其他方向路由数据包，因此我们将较低的号码分配给越向西的信道，并将较低的号码分配给东、北和南信道。

定理2 west-first路由算法是无死锁的。
证明在m×n网格中给每个通道分配一个以r为底的两位数a，b，其中T是3m-2和n-1中的较大者。图6显示了分配给通道离开节点（z，V）的特定编号。图7说明了4x 4网格的编号。为了证明west-first是沿着严格递减的信道来路由每个分组的，最好证明，对于每个进入任意节点的信道，该算法只能沿着较低数目的信道来路由分组。图8显示了四种可能的情况。检验表明，在每种情况下，用于将分组路由出节点的信道的数目比输入信道的数目少。注意，在（c）部分中，数据包可以进行180度转弯。此回合仅适用于非最小路由。