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.
This work considers the problem of finding, for a given degree sequence, the network structure displaying the smallest possible average shortest-path length and proposes a fast algorithm to construct approximate solutions to such a degree-constrained distance-minimization problem.
A new proof that the multiple-unicast conjecture holds for networks with at most six coding nodes, without computer-aided search, is given, and it is shown that if the conjecture holds on $\Gamma_{3,3}$, then it holds whenever no three sessions have six distinct terminal locations.
Sirui Liu, Linfeng Que, Zongpeng Li et al.· 0 citations
Modern communication networks may provide several heterogeneous links between the same pair of devices, including Wi-Fi, 5G, Bluetooth, and SparkLink. Existing multicast schemes often use simple-graph abstractions and therefore cannot distinguish these parallel links. We present ESMP, a multi-graph-based heuristic framework for efficient and stable multicast construction over heterogeneous parallel communication links. ESMP represents parallel channels as edges with delay and stability attributes. We show that an aggregate-edge-delay-constrained decision variant of the formulation is NP-hard. The framework includes six polynomial-time heuristics: delay-based DMA and DSMA, stability-based SMA and SDMA, and stability-delay-ratio-based RMA and MRMA. Each algorithm derives a metric-specific graph from the original multi-graph and constructs a tree according to its delay-stability preference. We also develop local adjustment strategies for vertex joins, vertex exits, and link dynamics. Experiments on connected synthetic multi-graphs reveal distinct metric preferences. Delay-oriented methods reduce delay, stability-oriented methods improve stability, and ratio-based methods provide stability-aware trade-offs at relatively low delay. In particular, RMA favors low delay, whereas MRMA uses pair-level average stability-delay information and shows comparatively favorable stability preservation and tree compactness in the evaluated scenarios. These findings characterize heuristic behavior in the evaluated synthetic settings and do not establish general optimality.
Reliability evaluation of an interconnection network is of great significance for construction and maintenance of the network. The extra connectivity and essentially edge-connectivity are two important parameters to evaluate network reliability. Let [Formula: see text] be a finite group. The power graph [Formula: see text] of [Formula: see text] is defined as an undirected graph whose vertex set is [Formula: see text] and two distinct vertices [Formula: see text] are adjacent if and only if one is a power of the other. In this paper, we determine the [Formula: see text]-extra connectivity and essentially edge-connectivity of the power graph of a cyclic finite group.
The recursive match networks (RMNs) represent an important family of communication networks characterized by their regularity and high fault tolerance, including the logic graph of the data center network BCube, the interconnection networks bijective connection (BC) networks, and even potentially other future networks. Protection routing is a key technology to enhance the reliability of communication networks, where dual completely independent spanning trees (dual-CISTs) have garnered significant attention as they suffice to configure a protection routing. In this paper, we propose a novel concept of dual protection routing spanning trees (dual-PRSTs) and demonstrate their application for protection routing construction in RMNs. Compared with dual-CISTs, dual-PRSTs provide more relaxed conditions, allowing for link intersections, internal vertex intersections, and vertices each serving as an inner-vertex in both trees, which are not permitted in dual-CISTs. We show that the research results in this paper are directly applicable to BCube, the BC networks, and other networks that fall within the definition of RMNs. Furthermore, it is proven that as long as a communication network contains dual-PRSTs, they can be utilized to configure a protection routing in it, although the protection routing scheme is conducted in RMNs. Empirical evaluations demonstrate that the protection routing based on dual-PRSTs is not only effective with competitive performance, but also generally outperforms that built with dual-CISTs in terms of path length metrics.
Bai Yin, Qianru Zhou, B. Cheng et al.· IEEE Transactions on Network...· 0 citations
Adding links generally improves classical transport by increasing the number of available paths. We show that coherent quantum transport can display the opposite behavior. Using continuous-time quantum walks on a percolated hierarchical small-world network, we identify a coherent overconnectivity penalty: root-to-boundary transport is maximized at intermediate bond probability and decreases as the network approaches full connectivity. The effect is quantified by the final-layer limiting probability $\chi_N$ and by the penalty $P_Q=1-\chi_N(p=1)/\max_p\chi_N(p)$, which measures the loss caused by making the architecture fully connected. The optimum results from a competition between shortcut-assisted spreading and interference-induced intra-layer recirculation. Spectral analysis shows that bond dilution creates motif-induced degeneracies and reorganizes the eigenstates connecting the root to the outermost layer. A comparison with dephased and classical transport shows that the non-monotonic landscape is not a purely geometrical percolation effect, but a coherent architecture-dependent phenomenon. These results provide a design principle for coherent transport in disordered photonic and quantum-network architectures.
