On non-blocking properties of Parallel Delta Networks

This paper deals with the definition of a class of NxN interconnection networks called Parallel Delta Network (PDN). For this class of networks the non-blocking conditions are given. In particular, by means of the graph colouring technique, it has been proved that the minimum number of Delta subnetworks (L) necessary to provide the non-blocking property is L=nfS/21-1 where n is the size of the basic switching element and S the number of stages required by an NxN 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(N3/2). Moreover, in case of the setup of a single connection request, this algorithm assures a time complexity equal to O(VN). This property makes it well suitable to an asynchronous telecommunication environment.