Adaptive routing on mesh networks

In this research, we analyze routing strategies in multiprocessor networks and their performance. In specific, we focus on the routing strategies of systems whose interconnection topologies can be enumerated via a set of rules. An adaptive, deadlock-free and livelock-free routing strategy is proposed for a class of interval-labeled two-dimensional mesh-connected multiprocessor networks based on store-and-forward communication. Three virtual channels on each physical link along dimension 0 are needed, while only two virtual channels per physical link along dimension 1 are needed. The entire physical network is split into three virtual subnetworks: VN0, VNl and VN2. The routing algorithm is composed of two parts. Part one, implemented in VN0, is adaptive and deadlock-free. Without traffic congestion or faulty links/nodes, it routes packets along minimal paths towards the destination node. When both such channels are congested, part one of the algorithm allows misrouting along a path with minimal traffic congestion. Part two is used in VN} and VN2 for preventing livelock while being adaptive and deadlock-free. It uses fully adaptive and minimal routing here. The three subnetworks are disconnected. Part two routes packets along the path with minimum traffic congestion. Because only shortest paths may be chosen, it is livelock-free. The routing algorithm switches packets from VN0 to VNX or VN2 based on DR, the number of times a packet has been routed from an output buffer in one dimension to an output buffer in a neighboring node in a lower dimension. Packets being routed in VNX or VN2 can not be switched back to VN0. Moreover, packets can not be switched between VNl and VN2. Our routing algorithm allows adaptive and faulttolerant routing with moderate amounts of resources without deadlock and livelock problems. The routing algorithm has also several practical advantages in its simplicity in implementation. To evaluate the performance of the routing algorithm, we developed a simulation model. Simulation results show that the algorithm achieve good performance in both fault-free and faulty mesh networks.Master of Applied Scienc