Hierarchical One-Link Interconnection Networks for Low-Degree Parallel Communication
TL;DR
The results support HON as a simple low-degree construction for structured inter-group communication, whereas higher-radix, adaptive, or more richly connected fabrics remain better suited to less structured traffic and larger bandwidth demand.
Abstract
This paper studies the Hierarchical One-Link Network (HON), a deterministic low-degree topology for parallel communication systems with a limited external-port budget. Starting from a regular [Formula: see text]-vertex base graph, HON forms [Formula: see text] copies and assigns one external matching edge to each vertex, so the degree increases by one while every pair of groups has a prescribed direct group-level connection. The analysis establishes the network’s order, degree, diameter, connectivity, routing, mean route length, recursive scaling, and channel-dependency properties. Five regular base graphs with 10, 16, and 32 vertices produce degree-four or degree-five networks with 110 to 1056 vertices and diameters from 5 to 9. Across these cases, the mean coordinate-route length exceeds the exact mean shortest-path length by at most 0.379 hops. Uniform-link communication simulations with shortest-path routing show clear advantages for coordinate-aligned workloads, while unstructured permutation traffic gives smaller or mixed differences, especially against complete-skeleton random-label graphs. The results support HON as a simple low-degree construction for structured inter-group communication, whereas higher-radix, adaptive, or more richly connected fabrics remain better suited to less structured traffic and larger bandwidth demand.