Delay-Sensitive Coflow Routing for Time-Varying Topology in LEO Computing-Aware Networks

Low earth orbit (LEO) computing-aware networks (LCANs) are proposed as an intelligent information infrastructure providing a solution for delay-sensitive computing tasks worldwide. The utilization of distributed computing architecture in an LCAN is emerging as a prospective resolution to cope with the limited computational resources of single satellite. Distributed computing depends on the exchange of information between worker nodes, as a type of concurrent and interrelated data flows called coflow. However, huge delay of coflow transmission is caused by the time-varying network topology and dynamic ISL conditions in an LCAN. To solve this problem, we establish an LCAN topology model, elaborating the orbit movement and ISL connectivity. Then we propose a novel time-varying graph to depict coflow transmission, which can improve the adaptability of coflow routing. Based on the proposed time-varying graph, we formulate coflow routing problem as a path combinatorial optimization and present an iterative heuristic algorithm named dynamic priority coflow routing (DPCoR). The DPCoR can dynamically adjust the priorities of coflow according to their increments to CCT, and thereby ensure that flows with high priorities for better routing paths. Furthermore, we compare DP-CoR with traditional flow routing schemes, i.e., equal-cost multi-path routing (ECMP) and software defined routing algorithm (SDRA) in various LCAN scenarios with different numbers of worker nodes, workloads and link conditions. The simulation results demonstrated that DPCoR algorithm can reduce the coflow completion time (CCT) effectively.