最小分布优先Clos网路由算法

Minimum Distribution Priority Algorithm for Clos Network

提出了一种新的Clos网无阻塞路由算法、最小分布优先算法,用该算法可以降低Clos路由算法的高时间复杂度。对于Clos网连接说明矩阵,提出并证明了矩阵中某一列的完全性问题是一个独立的问题,并据此提出了以最小分布优先的方式逐列计算Clos连接说明矩阵的策略,消除了产生在矩阵列之间的回溯以及列内元素之间的回溯,能够完全实现无阻塞路由,在最坏情况下的时间复杂度为O(N3/2),可以应用于Clos网路由控制。

This paper presents a new Clos network routing algorithm named MDP（minimum distribution priority） algorithm in order to reduce the high time complexity of original algorithm for Clos network. It illustrates that it is an independent problem whether a column in specification matrix is complete. As a result, it introduces a minimum distribution priority scheme handling Clos specification matrix column by column and eliminates backtracking among columns and backtracking among elements in the same column. The MDP algorithm ensures that non-blocking routing can be completely achieved and a low time complexity O（N^3/2） can still be reached in the worst case. So the algorithm is readily applicable to the control of Clos network.