NONBLOCKING PROPERTIES OF INTERCONNECTION SWITCHING-NETWORKS

Self-routing interconnection networks with their low processing-overhe ad delay and decentralized routing, are an attractive option for switc hing fabrics in high speed networks. These interconnection networks, h owever, realize only a subset of all possible input-output permutation s in a non-blocking fashion. The non-blocking property of these networ ks is an extensively studied area in interconnection network theory fi eld and efficient algorithms exist to check if any given permutation i s passable by such networks without blocking. One of the most common i nterconnection network structures is the Inverse Omega Network and is topologically equivalent to the Reverse Banyan Network. In this paper we show how to check the passability by the Inverse Omega network of a ny given connection set and list some of the very general patterns pas sable by this network. We also show that the concentrate operation pas sable by the Inverse Omega network is just a special case of the more general alternate sequence operation that we show as being passable. T hese non-blocking properties will be useful for cell routing in switch es built with blocking networks in parallel or in cascade.