Conflict-aware Coflow Scheduling Based on Optical Circuit Switching for Satellite Distributed Computing Networks

On-board distributed computing can provide more powerful computation capabilities for future low-earth-orbit (LEO) satellite constellations, serving intelligent information sensing and spatial large model through multi-satellite cooperation. On-board distributed computing depends on the efficient exchanging data flows between satellites termed coflow. The application of laser inter-satellite links (LISLs) will drastically improve the transmission capacity among the satellite distributed computing network (SDCN). However, due to the temporary interruptions of LISLs and the characteristics of optical circuit switching (OCS), the flow interruptions and conflicts significantly affect the coflow completion time (CCT). In this paper, we propose a conflict-aware coflow scheduling scheme to reduce the CCT in the OCS-based SDCN. Firstly, the time-varying LISLs and OCS-based coflow transmission are modeled and the problem of minimizing CCT is formulated. After that, we characterize the routing paths of coflow as the conflict graph and transform the coflow concurrent matching problem into the maximum independent set (MIS) problem in conflict graph. Based on this, we design the coflow polling greedy scheduling (CPGS) algorithm, which not only considers the sequence of coflow scheduling, but more importantly maximizes concurrent flows by MIS search. We deploy three different simulation scenarios to evaluate the algorithm performance. Simulation results show that our algorithm can significantly reduce the CCT by about 28.9% to 42.1% compared with existing works.