Abstract: | 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. |