The traffic of large-scale interconnection networks is increasingly showing high-speed and high-burst characteristics, which imposes a big challenge on the performance of switching systems. However, the existing scheduling and routing algorithms for the switching systems have either high computation complexity or high operation cost, which cannot keep up with the rapid development of the Internet. To cope with this problem, we present a parallel scheduling algorithm and a parallel routing algorithm for large-scale high-speed switching systems in this paper. Starting from the edge coloring problem of bipartite graphs, this paper first presents algebraic edge coloring approach, based on which we design the scheduling and routing algorithms. Our simulation results show that these algorithms possess the following features: 1) They have a low computation complexity; 2) They can provide 100% throughput; 3) They can achieve end-to-end delay in microseconds; 4) They do not require any hardware acceleration, and do not lead to packet out-of-sequence problem.

The three-stage fault-tolerant Clos network, where extra switch modules exist in the middle stage in case of switch failures, is widely used in the design of OTN switches. This paper proposes a route assignment algorithm for such Clos networks by solving its counterpart in edge-coloring problem. Based on complex coloring, a novel edge coloring method, the proposed algorithm possesses two properties. First, our algorithm can make full use of extra switch modules in the middle stage of Clos network. The extra switch modules provide additional colors for edge coloring, which help to reduce the running time of the coloring process remarkably. Second, our algorithm can be implemented in a parallel manner to further shorten the running time. The proposed routing algorithm achieves a low complexity of O(√N(m-1)/m-1+(m-√N)logN logN), where N is the network size and m is the number of switch modules in the middle stage. The performance of our algorithm has been verified by extensive simulation experiments.

This paper explores the scheduling problem of input-queued switches, based on a new algebraic method of edge coloring called complex coloring. The proposed scheduling algorithm possesses three important features inherent from complex coloring: parallelizability, optimality and rearrangeability. Parallelizability makes the algorithm running very fast in a distributed manner, optimality ensures that the algorithm always returns a proper connection pattern with the minimum number of required colors, and rearrangeability allows partially re-scheduling the existing connection patterns if the traffic patterns only changes slightly. The amortized time complexity of the proposed parallel scheduling algorithm, in terms of the time to compute a matching in a timeslot, is O(log N), where N is the switch size. As for the scalability of input-queued switches, due to its low complexity, our algorithm can achieve nearly 100 percent throughput and provide acceptable queuing delay when N is large. Furthermore, the complex coloring method naturally provides an adaptive solution to non-uniform input traffic pattern. Thus, the proposed parallel scheduling algorithm is highly robust in the face of traffic fluctuations.