Research On Deadlock And Load Balance In K-ary N-cube Networks

As a popular topology of Interconnection network, k-ary n-cube has faced many problems currently, such as multi-application, multi-business and the imbalance of traffic distribution, which requires the routing algorithms to be load balanced and the deadlock-free algorithms to be adaptive under various traffic modes.Current technologies solve these problems inadequately, such as the imbalance of resource utilizing in load balancing routing algorithms and too high rate of false deadlock detection in previous deadlock detection algorithms. To solve these problems, two new algorithms are presented in this paper.Based on of the analysis of the existing deadlock technologies, CDD (Cycle based Deadlock Detection routing algorithm) is proposed firstly. Different from traditional deadlock detection mechanism of time-out, CDD uses the conditions of cyclic dependency to detect deadlock packets. Based on the features of topology of k-ary n-cube networks, the detection is divided into deadlock detection in the same dimension and deadlock detection in the different dimension. In the same dimension detection, CDD utilizes the strategy of flow control, i.e. the deadlock is detected according to the remained buffers in the channels before the packets come into these channels; While in different dimensions, deadlock is detected by the turning of the packets. Then, CDD uses the interval of busy time of all the output channels these packets applying for the final detection.Secondly, in view of problems of the existing load balancing routing algorithms, a new quadrant crossing routing (QCR) algorithm is proposed. According to source and destination node of each packet, network is divided into several quadrants with various weights. QCR sets quadrant crossing rules and allows packets to cross quadrants based on the network state, which makes traffic distribution more balanced. Network state is determined by the interval between the last two requests to the same output.Finally, performance of the proposed routing algorithms is evaluated by OPNET under various traffic modes and comparisons with the existing algorithms (CDD vs. soft-based, QCR vs. Dimension order routing algorithm, duato, and GAL) are made. The results show that CDD has lower rate of false deadlock detection, less sensitivity of the time-threshold and QCR achieves better performance.