Research On Routing Algorithms In Clos Matrix

Clos network has widely used in telephone networks, multi-processor system and switch/routers since it was first proposed. And Clos network, one type of the multi-stage network, was extensively researched because of its characteristics of good scalability, lower hardware cost and excellent routing performance.At present, the development of intelligent optical network requires the matrix with high-capacity, rapid port configuration and multicast supported. But the widely used rearrangeable three stage Clos matrix should be rearranged when the call is blocked, and the current routing algorithm has the disadvantage of more time consuming, more existing connection influenced, higher percentage of multicast traffic blocking probability, and rearrange solution is not optimal.To solve this problem, two new routing algorithms are proposed for Clos network. The major works and contributions are the following two aspects.ORRA (Optimal Rearrangeable Routing Algorithm) which solves the problems of unicast connections rearrangement, searches path in sequence order at first. And the Clos matrix should be rearranged if the call is blocked. The rearrangeable algorithm of ORRA improved from Paull algorithm, is a type of optimal rearrangeable algorithm. It searches all the rearrangement solutions in the parallel fashion until the first rearrangement solution is found. For the sake of recording rearrangement solutions the input rearrange tree and output rearrangement tree are constructed. Every path of tree represents a rearrangement solution, and the rearrangement time could be denoted by the deep of the path. Simulations were carried out on different scale Clos matrix with OPNET software, and the results show that the optimal rearrangement solution is achieved through ORRA without increasing time consuming and blocking probability.PRA (Permutation Routing Algorithm) which applied for unicast and multicast traffic is introduced to four stages Clos matrix which adds one permutation stage before input stage of three stage Clos matrix. In the first place, the calls are permutated to different input ports by the permutation stage according to the fanout of call and the output port loads of input module, and then completed the fanout in the input stage. Finally, route the unicast calls through ORRA algorithm. Simulations were carried out in different scale four stages Clos matrix with OPNET software, and the results show that PRA achieves a lower blocking probability than other algorithms, especially for multicast traffic.