interconnection networks nxn formed by delta networks and method for the establishment of permutations entry - exit

摘要

This invention discloses a new class of NxN multistage interconnection networks which is called class of Parallel Delta Networks (PDN). For such a class of networks the non-blocking conditions are given, i.e. those conditions which guarantee the capability of establishing any connection request between an inlet link and an outlet link, both supposed free whichever the state of the network may be. In particular, by means of the graph colouring technique it has been proved that the minimum number of Delta subnetworks necessary to provide the non-blocking property in a PDN is n &boxdr& S/2 &boxdl& -1, where S and n are the number of stages in a NxN Delta network and the number of inlet and outlet links of a single switching element, which Delta network consists of, respectively, and &boxdr& x &boxdl& indicates the littlest whole number greater than x. For the establishment of the inlet-outlet connection request, a routing method has been defined. Such a method operates for switching elements of any size and in case of the set-up of a single connection request this method assures a complexity of the order of 2ROOT N. In case of a whole set of inlet-outlet point-to-point connection requests (inlet-outlet permutation), this method has a polynomial complexity of the order N3/2. As the complexity relevant to the establishment of a single connection request is extremely low, this method is particularly suitable to an application in an environment in which the connection requests are asynchronous, i.e. a telecommunication environment. Therefore, this network can be used as connection network within an automatic exchange. It is also disclosed a variant of this method applicable in case the size of the single switching element is 2qx2q, where q is a whole number. Such a variant has a complexity of the order of N.log2N and is suitable to a synchronous environment, in which the set of connection requests constitutes an inlet-outlet permutation.