Routing on Triangles, Tori and Honeycombs
Jop F. Sibeyn · International Journal of Foundations of Computer Science · 1997
The standard n × n torus consists of two sets of axes: horizontal and vertical ones. For routing h-relations, the bisection bound gives a lower bound of h · n/4. Several algorithms nearly matching this bound have been given. In this paper we analyze the routing capacity of modified tori: tessellations of the plane with triangles or hexagons and tori with added diagonals. On some of these networks the ratio of routing capacity and degree is higher than for ordinary tori, even though they are as easily constructed. Hence, they may constitute more cost effective alternatives. For networks with n2 PUs, we get the following results: on a torus of hexagons, node degree 3, h-relations are performed in 0.37 · h · n steps; on a torus of triangles, node degree 6, in 0.13 · h · n; and on a torus with added diagonals, node degree 8, in h · n/12. The latter result matches the bisection bound for this network. Even faster is the routing on a torus of hexagons with diagonals, node degree 12: 0.053 · h · n. The algorithms are simple, inspired by the algorithm of Valiant and Brebner. The results can easily be extended to sorting, dynamic routing or routing for average-case inputs.