To Rearrange The Clos Network Algorithm

Distribution frame is the most basic part of a network information system. Its core function modules is switching network. The performance of the entire network is decided by the ability to deal with connection requests in switching network. If switching network could well handle multiple connection requests, and the requests are not in conflict, then the loss rate of the entire network will greatly reduced, the performance of the entire network is well. Otherwise, switching network couldn't do it excellent, couldn't promptly and effectively find the correct way for the request, then the entire network will always be a state of congestion, its performance is bad. At last it will deeply affect the use of network users.Considering the blocking property, switching network can be divided into non-blocking network and blocking network. Non-blocking network can also be divided into three categories: strictly non-blocking network, wide-sense non-blocking network and rearrangeable non-blocking network. The hardware requirements in strictly non-blocking network are relatively high, so it's difficult to realize in project. As to wide-sense non-blocking network, there is less research on it at present. Because the requirements in rearrangeable non-blocking are low, it's easy to realize it. The key to rearrangeable non-blocking is its routing algorithms. And the performance of blocking network is measured by its blocking probability.The thesis selects CLOS network as its research background, studies various rearrangeable algorithms over the recent years, and proposes two rearrangeable non-blocking algorithms: blocking and rearranging algorithms and reducing blocking probability rearrangeable algorithms. Blocking and rearranging algorithms improves the old way that reroute if exising a number of blockings, proposes a new method that if there is one blocking, immediately rearrange existed connections. It cuts the process for calling man-made connections, and raises the efficiency of algorithms. Moreover it is proved convergence in theory, reducing blocking probability rearrangeable algorithms introduces the concept of rearrange into blocking network. When routing for a request, it forecasts whether connection will influence the later requests, or blocking probability isn't zero. If the answer is yes, then call the algorithms, rearrange the existed connections, reducing the blocking probability.Firstly, the thesis briefly introduces the background: distribution frame, switching network and CLOS network. Secondly, it has a discussion on blocking and non-blocking property, related algorithms, and proposes a calculation method on blocking probability, doing some foreshadowing for the fifth chapter. Thirdly, the thesis introduces four advanced rearrangeable algorithms.Blocking and rearranging algorithms improves the traditional way of revising the specification matrix, proposes the concept of set matrix, and the way of revising the set matrix could directly express the connection way of network. In an intelligent way, the exchange of the elements in set matrix will greatly avoid retrospective and repeative exchange of the peer elements. Moreover it is proved convergence in theory.Reducing blocking probability rearrangeable algorithms makes the occupation of the middle-class switches greatly concentrated in a few ones, increases the utilization of the middle-stage switches, and lowers the blocking probability of network. The thesis verificates the blocking probability will reduced to one third compared to previous one through simulation. It notes that the algorithms is helpful to reduce the blocking probability.