Parallel construction of multiple independent spanning trees on 3-ary n-cube networks

High-performance computing utilizes powerful processor clusters to parallel process big data and solve complex problems at extremely high speeds, relying significantly on interconnection networks. As networks grow in scale and complexity, failures become unavoidable. Interconnection networks demand consistent operation and efficient routing algorithms to enable smooth data transmission among processors. Fault-tolerant routing is essential for assessing network reliability. The application of independent spanning trees (ISTs) is an effective method to enhance network fault tolerance. Regarded as a significant extension of the hypercube, the $3$-ary n-cube network (Q³ₙ) boasts many advantageous such as low vertex degree, regularity, and straightforward implementation. In this paper, we introduce parallel algorithms for generating $2n$ ISTs on Q³ₙ, where $2n$ represents the maximum achievable number, enhancing the efficiency and obtaining additional sets of ISTs and disjoint paths. Building upon previously constructed ISTs, a fault-tolerant routing system is developed, utilizing them as the routing table. Subsequently, the effectiveness of this mechanism is assessed through simulated data, showing an increment in transmission success rates as dimensionality grows, nearing near-perfection at almost $100%$. These results also reveal that the algorithm we proposed demonstrates better performance than traditional classical algorithms.