一个针对洗牌交换网的最优路由算法

An Optimal Routing Algorithm for Shuffle-Exchange Networks

洗牌交换网是最流行的互连网络之一 ,然而 ,它的缺点之一便是缺少最短路由算法 .最短路由算法 ,通常也称为最优路由算法 ,能保证报文在任意一对结点之间沿着最短路径传送 .针对包含 2 n个结点的洗牌交换网 ,文中给出了一个 O(n2 )时间复杂度的最短路由算法 .该算法还可以很容易地适用于立方体连接圈 (CCC) ,且所得到的算法比已有的 CCC路由算法要简单得多 .

The shuffle exchange network is among the most interesting interconnection networks that have been subject to much research in the field of parallel computing. However, one of its drawbacks is the lack of the optimal routing algorithm. In a shuffle exchange network, each node is identified by a unique binary address, and two nodes are linked by an edge if either (a) their addresses differ in the last bit, or (b) one is a cyclic shift (by one bit) of the other. Edges of type (a) are called exchange edges, and those of type (b) are shuffle or unshuffle edges. Such a simple structure admits a simple routing algorithm: cycle through all the bits of the source address by traversing the shuffle/unshuffle edges, changing a bit whenever necessary by traversing an exchange edge. This algorithm takes at most 2 n steps for an n dimensional shuffle exchange network (whose node addresses have n bits). Considering the fact that any route from 00…0 to 11…1 must have 2 n -1 edges, this algorithm seems to be just good enough. A simple inspection, however, would reveal that many of the routes thus generated are not at all the shortest possible. It turns out that for some source destination address pairs, it is not necessary to cycle through all the bits because of the existence of some common substring in their addresses. The simple routing algorithm insists on traversing at least n -1 shuffle/unshuffle edges in order to cycle through all the bits, and the result is often a non optimal route. An optimal routing algorithm always directs a message along the shortest path between any two nodes. In this paper, we propose an O(n 2) time algorithm for the optimal routing in a shuffle exchange network having 2n nodes; in particular, it would avoid cycling through a common substring of the source and destination addresses if it is deemed profitable. The algorithm can be easily adapted to routing in the cube connected cycles (CCC)——the result is a much simpler algorithm than a previous algorithm for the CCC.