Research On Efficient Oblivious Routing Algorithm Based On Mesh Network

As a strictly orthogonal topology, Mesh network has been widely used in the current popular multi-core computer architecture and network on chip due to the simply router structure. The information exchange between the network needs a good routing algorithm to guarantee. A well-designed routing algorithm not only improve the network throughput, but also keeps path lengths as short as possible.reducing the number of hops and previous routing algorithms need to use multiple virtual channels to ensure the deadlock free, but increasing the number of virtual channels will reduce the transmission speed of the message, increase the overall latency of a message as well as the cost and power consumption of a router.An adaptive routing algorithm uses information about the network state, typically queue occupancies, to select among alternative paths to deliver a packet. We propose ePAR adaptive routing algorithm which ensures deadlock free while reducing the number of virtual channels. For uniform traffic pattern network,the performance of the ePAR algorithm is similar to the existing algorithms. For nonuniform traffic patterns network, ePAR performs well than the existing algorithm in terms of the average delay that the adaptive routing algorithm is 22%, while the ePAR algorithm is 31%. Furthermore, this algorithm can not only be applied to 3D-Mesh network,but also extend to n D-Mesh network.Oblivious routing, in which we route packets without regard for the state of the network, is simple to implement and can achieve better performance with a high routing flexibility. In this paper, a new oblivious routing algorithm called OETURN is proposed,which is based on the odd-even turn model. For different traffic patterns, OETURN performs better than DOR which not using virtual channel. Although when compared with the algorithm which use multiple virtual channels, the network throughput with OETURN performs not very satisfactory, while the average-case throughput is similar to the existing algorithms. The great improvement for this algorithm we proposed without virtual channels while the existing algorithms need at least two virtual channels.In the 3D-Mesh network, an Oblivious routing algorithm called OEPTURN is proposed, which achieve the Oblivious routing algorithm with multiple paths between the source node and the destination node without using the virtual channel. Simulation results show that OEPTURN performs better than DOR which not using any virtual channel and the average-case throughput is similar to the existing algorithms.