Analysis And Optimization Of The Tree-shaped Multistage Interconnection Networks

Interconnection Network(IN)plays an important role in high performance computing,network on chip(NoC),data center and large-capacity switching systems.Its structure directly determines the overall performance of the corresponding system.The motivation of research on IN at home and abroad is to provide user nodes as high quality of communication services as possible with lower cost.Sponsored by the sub-project,the research and industrialization of the key technologies of Terabit PTN(packet transport network),from the Ministry of Industry and Information Technology,this dissertation studies the optimal structure design of the tree-shaped multistage IN(TSMIN),which includes two parts:The first part,this dissertation proposes a TSMIN model,and performs the optimal design of the networks structure using this model.On the basis of introduction of the topologies of the typical existing INs,it introduces the proposed TSMIN model,the switching modules and the way they are connected to form this model.Two methods for calculating the switching flux at each stage of the model is presented;To avoid the defection stemming from evaluating the performance of a network structure by only one metric,we study the integrated optimization of a network structure by comprehensively considering four metrics,including the number of switching modules,average hops,bisection bandwidth and network cost.To avoid congestion or the waste of resources,this dissertation also studies the issue of port rate match for the switching modules at different stages;The optimization algorithm for finding the optimal structures of the INs using the proposed TSMIN model was designed,and the results of the two methods for calculating the flux were compared.Besides,under different modes of input services,we analyze the optimal results of the network structure with different numbers of user nodes.Here the optimal results include the optimal structure and its port rate match at each stage.The second part is the optimal design of the structures of typical Fat Tree networks.There is a problem in typical Fat Tree networks that the higher the stage,the lower is the utilization of switches and links at that stage.So it needs to reduce the cost of the network structure by slimming(pruning)the equipment at upper stages without largely degrading performance.The network structure is slimed in this dissertation by using the methods of the rate match and recursion formula,i.e.,reducing the numbers of the switches and links at upper stages by reasonably configuring the numbers of the upward ports of the switches at each stage to be less than that of the downward ones.Then,we discuss the two factors that affect the slimming of Fat Tree networks,and introduce the slimed results by some examples and discuss their rationality.The model and the optimal design method proposed in this dissertation can be used to provide solutions to the optimization issues in areas of tree-shaped multistage interconnection of numerous users,switch networks,data center networks,etc.