Research On Scheduling Algorithms In Three-Stage Clos Packet Switching Network

With the rapid popularization and development of the Internet and the continuous deployment of satellite Internet constellation plans,more user terminals are connected to the network,resulting in Internet applications that include all areas of people's production and life.The Internet traffic has shown an explosive growth trend.The development and application of optical fiber technology and inter-satellite laser communication technology has caused the bottleneck of the information transmission network to transferred to the switching equipment of the switching nodes in the Internet,such as switches and routers.The core technology of these switching equipment is switching technology,and switching technology includes two aspects:switching structure and scheduling algorithm.In order to improve the performance of the information switching network and meet the emerging needs of new applications and services,it is necessary to research on switching structures with larger capacity and better performance scheduling algorithms adapted to them.Clos switching network has good scalability and is a common multi-stage switching network suitable for building large-capacity switching networks.To achieve better performance for the existing scheduling algorithm of the three-stage Clos switching network,it needs to increase the number of inter-level iterations and the queue organization structure is complex.The multicast scheduling algorithm is a simple extension of the unicast scheduling algorithm and requires a more complex scheduling mechanism.Aiming at these problems,the thesis mainly studies the unicast and multicast scheduling algorithms of the three-stage Clos switching network.The main research results as follows:(1)Based on the study of the centralized scheduling algorithm for the three-stage Clos switching network,a centralized unicast algorithm based on the dichotomous idea suitable for the rearrangeable Clos network is proposed.The main idea is to transform the large-scale connection description matrix rearrangement problem into the rearrangement of multi-row and two-column matrices.The algorithm can rearrange all the columns independently after the bipartite preprocessing of the connection description matrix.In the process of the algorithm,it is proved that when each element of a multiple rows and two columns matrix occurs exactly twice,the matrix can be transformed into a complete one.The time complexity of the algorithm is(46)(km²log₂ m)in the worst case,and the proposed algorithm has lower complexity compared to some similar algorithms that exchange column elements in the same row.(2)On the basis of studying the distributed scheduling algorithm of the three-stage Clos switching network,a distributed weight matching scheduling algorithm is proposed.The algorithm uses a constrained network flow model to handle the weight matching problem,which improves performance while avoiding multiple iterations between stages.Multicast services can be supported under the condition that the organization structure of the unicast queue remains unchanged.In order to avoid repeated processing of the cell header,a remainder tag is inserted into the cell,and the cell can obtain fan-out port information through the remainder operation.The effectiveness of the algorithm is verified by OPNET simulation.