Optimal communication algorithms for manhattan street networks Original Research Article

We evaluate the mean internodal distance and the saturation throughput of the Manhattan Street network in the general case, and present a simple shortest path routing algorithm for this topology. We also propose efficient routing algorithms to execute generic communication tasks, such as the total exchange and the multinode broadcast, in a Manhattan Street network of processors. The proposed algorithms execute these tasks in an optimal number of steps, while achieving full (equal to 100%) utilization of the network links. Finally, we construct edge-disjoint Hamiltonian cycles for the Manhattan Street network.