Parallel construction of multiple independent spanning trees on highly scalable datacenter networks
作者:
Highlights:
• We prove that a highly scalable data center network (HSDC) is vertex-symmetric.
• We investigate the independent spanning trees (IST) problem on HSDC.
• We propose an algorithm to construct n ISTs on the n-dimensional HSDC, denoted as HSn.
• The algorithm can be parallelized to run in O(n) time using N=2n processors.
• As a by-product, we obtain the connectivity ofHSn to be n.
摘要
•We prove that a highly scalable data center network (HSDC) is vertex-symmetric.•We investigate the independent spanning trees (IST) problem on HSDC.•We propose an algorithm to construct n ISTs on the n-dimensional HSDC, denoted as HSn.•The algorithm can be parallelized to run in O(n) time using N=2n processors.•As a by-product, we obtain the connectivity ofHSn to be n.
论文关键词:Datacenter networks,Independent spanning trees,Parallel algorithms,Fault-tolerant broadcasting,Secure message distribution
论文评审过程:Received 15 April 2021, Revised 17 August 2021, Accepted 18 August 2021, Available online 30 August 2021, Version of Record 30 August 2021.
论文官网地址:https://doi.org/10.1016/j.amc.2021.126617