Research On The Extensible Multistage Packet Switching Fabrics

Confronted with the explosion of communication traffic in Internet, the communication networks architects make great efforts to provide scalability for switch architecture in the current routers and switches. Two approaches are available, one is to lift the switch capacity of the single-stage switch, but this alternative is always unsuccessful for the practical implementation limits of the single-stage switch. The other is to construct a larger switching fabric by using interconnection networks including several switch elements, which is commonly used as scalablity solutions. Currently, three stage Clos networks (C3) are the most popular network topology. Centering on the C3, we firstly address the nonblocking condition in the wide sense, the Evil-Twin randomized routing algorithm, and give a theoretical analysis under the assumption of the h -relation traffic. We also present performance analysis of the C3 with MSM(Memory-Space-Memory) structure and SSS(Space-Space-Space) structure respectively.But the problem to build a MIN (Multistage Interconnection Networks) with the size on demand, which frequently occurs in the practice of engineering, has not been extensively addressed in the literature. Obviously, the Clos networks topology cannot live up to it. Thus, the only choice left for the architect is to design a MIN of the size which is larger than the number needed, which will make many switch elements unnecessary and wasted, causing higher cost and complexity. To circumvent such problems, we propose the concepts of the extensibility and the extensible multistage networks, which are the main focus of this paper. Research shows that there are two classes of the extensible multistage networks, of which the connecting pattern between the adjacent stages are the Plus-Minus-Modulo-N and Shuffle-Exchange. Firstly, we present the P2I networks and PN2I networks, which are the extensible Banyan networks composed of 2×2 switch elements. Then we generalize this idea and propose the PkI networks. Secondly, we study another class of the extensible multistage networks, the shuffle-exchange connected multistage networks, including the Generalized Shuffle Exchange Networks (GSEN for short) and Generalized Delta Networks (GDN for short).In the study of the extensible multistage networks, the most intractable problem encountered is: when the size is a power, the extensible multistage networks possess the symmetry, hence the tag-based routing algorithm is very simple. Under the condition of the equiprobable address of uniform packet traffic at each input port, the traffic in each link is even and the network performance is good. In this case, we call the network is complete. As the size is no longer a power, the symmetry is broken. Under the same traffic condition at each input port, we find, the simple tag-based routing algorithm used in the complete networks will make the traffic in internal links uneven, which deteriorates the network performance. Thus we propose a new routing algorithm called balanced tag-based routing algorithm, which makes the incomplete extensible multistgae networks behave almost the same as the complete extensible mulitstage networks with respect to the performance issues.All in all, the contributions can be outlined as follows:1. The nonblocking condition in the wide sense of the C3 is studied, and the empirical necessary condition is acquired by the heuristic probing algrithm dubbed as Forced Algorithm. The Evil-Twin randomized routing algorithm is investigated in the C3. The essence of Evil-Twin permutations is shown and how to construct Evil-Twin permutations is implicitly given by the proof. A theoretical analysis of the C3 under the assumption of the h -relation traffic is presented. The nonblocking condition in the probabilistic sense and the average delay of the C3 with MSM structure are analyzed, and the performance analysis of the throughput of the C3 with SSS structure is also given.For the purpose of constructing a large scale switching fabric with the arbitrary number of ports, it will be not...