On non-blocking properties of parallel delta networks

The definition of a class of N*N interconnection networks called the parallel delta network (PDN) is studied. For this class of networks the nonblocking conditions are given. In particular, by the graph colouring technique, it has been proved that the minimum number of delta subnetworks (L) necessary to provide the nonblocking property is L=n where n is the size of the basic switching element and S the number of stages required by an N*N delta network. A routing algorithm for the establishment of any permutation has been defined. It operates for any value of n and shows a polynomial time complexity equal to O(N/sup 3///sup 2/). Moreover, in case of the setup of a single connection request, this algorithm assures a time complexity equal to O( square root N). This property makes it well suitable to an asynchronous telecommunication environment.<>