基于正规序列的Omega网络路由构造方法

Method of Constructing Routing Based on Normal Sequence in Omega Networks

在混洗交换网络中,窗口检测法涉及的多窗口之间复杂的制约关系对无冲突路由的构造形成严重阻碍。为克服这一阻碍,提出正规序列概念,在此基础上给出构造无冲突路由的新依据——序列检测法。该方法将2n-1级Omega网络中无冲突路由的构造转化为单个序列的构造,与传统的窗口检测法相比,新方法不仅缩小了构造对象的空间规模,而且降低了构造对象的复杂度,为更方便地构造混洗交换网络路由创造了条件。

Constructing conflict-free routings is seriously prevented due to complex window restrictions of window de- tection in shuffle-exchange networks. In order to overcome this obstacle, the concept of normal sequence was proposed, and a new method called sequence detection which is used to construct conflict-free routings is offered based on the con- cept. This method translates constructing conflict-free routing into constructing a single sequence in 2n--1 stages Ome- ga networks, which reduces complexity and the size of space of object constructed relative to window detection. So, con- structing conflict-free routings becomes simpler.