AN O(n) PARALLEL ALGORITHM FOR SOLVING THE TRAFFIC CONTROL PROBLEM ON CROSSBAR SWITCH NETWORKS

In this paper, we propose a parallel algorithm for the traffic control problem (an NP-complete problem) on crossbar switch networks. This problem is to find a set of conflict-free paths such that the maximum number of message packets can be transmitted over the network. The problem can be represented by an energy function. Then by applying our parallel algorithm, the state of the energy function is iteratively updated toward a stable state. When the energy function reaches a stable state, the state represents a solution of the problem. The empirical results show that the throughputs of the proposed algorithm are much better than the linear algorithm. We have shown that the time complexity of a parallel algorithm is O(n) by using n² processors. Furthermore, since the traffic control problem can be reduced to the traveling salesman problem, the proposed algorithm can be further applied to some other NP-complete problems.