Summary
Routing data efficiently through networks shaped like triangles is tricky because the many directions can cause data traffic to get stuck. The authors found a way to route messages with as few restrictions as possible, avoiding deadlocks by forbidding just two types of turns and using one or two virtual channels. They also developed a method to handle network loops in a torus-shaped network by using special coordinates and controlling message flow, ensuring data always finds a path without cycles. Additionally, they showed how to adjust routing easily if a connection fails, keeping all possible routes open with only a small delay increase.
What this means in practice
- •For network hardware engineers: Design routing algorithms for hexagonal and toroidal network topologies that minimize deadlocks with low virtual channel overhead.
- •For data center network operators: Implement deadlock-free adaptive routing in complex mesh and torus networks to maintain connectivity and performance despite single link failures.
Abstract
Degree-six triangular-lattice interconnection networks offer substantial minimal-path diversity, but their additional directions complicate deadlock-free routing under wormhole flow control. We study a finite hexagon-shaped mesh and its periodic torus quotient in a common six-direction coordinate system. For the finite mesh, we construct a minimal partially adaptive routing relation that uses one virtual channel and forbids only two directed turns. For the torus, we prove that every source-destination pair has a unique closest lattice lift, but that the same two-turn physical routing relation still has a cyclic one-VC resource CDG for every n >= 3. We eliminate this residual periodic dependency by combining two virtual channels with Hamiltonian coordinates and group-specific datelines. Each same-group segment crosses its dateline at most once, which permits a global rank on VC-labelled channel resources. We prove minimal all-pairs connectivity for both physical routing relations and acyclicity of the complete resource CDG for the proposed one-VC mesh and two-VC torus constructions. For a single static bidirectional link failure known before a routing epoch, we further rotate the turn rule toward the failed orientation and replace a failed hop by a same-group two-hop triangle bypass. This restricted extension preserves all-pairs connectivity and the original VC counts, with at most one additional hop relative to the healthy shortest-path distance.