On torus topologies with random extra links

We study networks based on torus topologies enhanced with additional, arbitrary assigned links. We develop a method for analyzing the expected number of hops which can be applied to any torus topology with randomly assigned extra links when the simplest greedy routing is used. Using this method, we study the following topologies with extra links: one-dimensional unidirectional and bidirectional torus (i.e., ring), and two-dimensional bidirectional and unidirectional torus (e.g., bidirectional Manhattan network and Manhattan street network). We also show how these results can be extended to some non-torus topologies with extra links, such as the bus and the two-dimensional grid. From our analysis we find that the expected number of hops in a D-dimensional N-node torus with extra links grows as O(/sup D+1//spl radic/N) and that it can be reduced to O(/sup 2D//spl radic/N) with the orthogonal assignment of extra links.