Abstract
The Hamiltonian path serves as a robust tool for unicast or multicast communication in parallel and distributed systems. Embedding this path structure into large-scale systems, especially those with numerous failures, remains a formidable and pressing challenge. The arrangement graph is a topology that not only generalizes many renowned network architectures but is also a promising framework for future computer systems. Extensive research has been conducted on the fault-tolerant embedding of Hamiltonian paths in the arrangement graph or its subclasses, yet these efforts have not attained the desired fault tolerance levels. In this article, we focus on significantly improving the edge fault-tolerant embedding capabilities of arrangement graphs by adopting a novel fault model, termed the partitioned edge fault model. We first prove the existence of Hamiltonian path avoiding large-scale edge faults in arrangement graphs. Then we develop a corresponding Hamiltonian path embedding algorithm with high fault-tolerant capability for arrangement graphs. Both theoretical comparisons and experimental analyses reveal that our methods yield significant enhancements in fault tolerance over existing studies. Furthermore, building upon the generated Hamiltonian path, we devise a dual-path multicast routing strategy and evaluate its latency performance.
Funding Information
  • National Natural Science Foundation of China (62572124)
  • National Natural Science Foundation of China (62002062)
  • Natural Science Foundation of Fujian Province (2022J05029)
  • Hong Kong Research Grants Council (11211422)

This publication has 41 references indexed in Scilit: