| The problem of deadlock-free unicast routing in multicomputer interconnection networks and networks of workstations is investigated. We propose and evaluate several algorithms for improving end-to-end latency for message delivery in these networks. We show that these algorithms have higher performance than the well-known Up/Down and TP algorithms. Our principal goal in all proposed algorithms is to reduce the fraction of prohibited turns and thereby the average distance in the underlying topologies which results in improved sustained throughput in the network. Extensive simulation results comparing proposed algorithms and the previously known algorithms are presented.; A new theoretical lower bound for the number of prohibited turns is derived. The new lower bound is more precise than earlier reported lower bound. We prove that if an undirected graph has N nodes, M edges, and a minimum degree of delta > 2, it must have at least M - N + 1 + (delta - 1)(delta - 2)/2 turns prohibited breaking all cycles while preserving connectivity.; In the first proposed algorithm, called MTP, node selection rule changes so that it selects a minimum degree node with minimum degree neighbor(s). This is in contrast to the original TP algorithm which selects a node minimum degree node with neighbors of largest total degrees. Average network dilation is reduced from 24% in TP to 11% in MTP. Extensive simulation experiments for message delivery times demonstrate that MTP improves the average maximum sustained network throughput by up to 40%.; The second algorithm, based on flow analysis, determines the weight of each edge as the number of number of concurrent messages that each edge can carry. Turns in the graph are then prescribed to have a weight equal to the sum of the weights of its edges. Weights of edges and turns are favorable attributes that the Weighted Turn Prohibition algorithm then minimizes. With this approach, we improve the maximum sustained network throughput by up to 44% with an average dilation of about 10%.; The third algorithm, called Edge Deletion Algorithm provides an improvement of up to 50% for the maximum sustained network throughput with dilation between 8.4%--10%. The fourth algorithm called Cycle Breaking, CB, algorithm, which is operationally different than the original TP in which, node selection order is modified, principally to facilitate the proofs of its properties. This algorithm has no performance benefits over TP but we prove that it generates sets of prohibited turns that are irreducible. Using the CB algorithm, we also provide tighter upper bounds on the fraction of prohibited turns for regular topologies with small degree, such as degree 3 regular graphs, honeycomb meshes and tori. For several topologies, we show that CB algorithm is optimal in terms of minimizing the fraction of prohibited turns.; From topological perspective, we recommend the use of honeycomb torus over two dimensional torus in regular interconnection networks. Since the MTP algorithm is found to be most cost effective for all topologies that we investigated, we recommend it as the algorithm of choice. |
