2003 · 15 citations · 17 references
ComputingComputer EngineeringComputer ScienceComputer NetworksInterconnection NetworksTheory Of ComputationCommunication NetworksGraph TheoryNetwork SwitchingNetwork TopologyRoutingRouting AlgorithmsBlocking BehaviorBlocking PropertiesDelta NetworksInterconnection GraphsNonblocking NetworksNonblocking PropertiesPolynomial Time ComplexityPolynomial-time Algorithms
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. \nIt operates for any value of n and shows a polynomial time \ncomplexity equal to O(N3/2). Moreover, in case of the setup \nof a single connection request, this algorithm assures a \ntime complexity equal to O(VN). This property makes it \nwell suitable to an asynchronous telecommunication \nenvironment.
17