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.
On non-blocking properties of Parallel Delta Networks / F., Bernabei; A., Forcina; Listanti, Marco. - ELETTRONICO. - (1988), pp. 326-333. (Intervento presentato al convegno Infocom 1988 tenutosi a New Orleans (USA) nel March 1988) [10.1109/INFCOM.1988.12934].
On non-blocking properties of Parallel Delta Networks
LISTANTI, Marco
1988
Abstract
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.