On the non‐blocking conditions of self‐routeing multistage interconnection networks

This paper studies the non‐blocking conditions of a generic N × N multistage interconnection network, such as an omega network or an n ‐cube network, in which only one path connects any inlet to each outlet and different I/O paths can share interstage links. It is widely known that any of these networks is non‐blocking for a compact and monotone pattern of k ≤ N I/O paths. Recently it has become very important to show the network non‐blocking property for permutation sets, wider than the compact and monotone, which are usually encountered in broadband ATM networks. By using a new approach based on the concept of distance between I/O paths, we show here that these networks are non‐blocking for a set of I/O paths obtained by shifting cyclically the inlets of a compact and monotone pattern of I/O paths by an arbitrary number of steps.