# Rethinking LEO Mega-Constellation Routing to Provide Fast Internet Access Services
## 2 Background  
### Related Work  
The importance of routing in satellite networks has been mentioned by numerous papers in the context of the space information network [9; 10]. Most algorithms were developed long ago and were driven by the needs of the time. For example, a routing algorithm for datagram traffic was proposed in [11], which can generate the minimum delay paths for each packet. This algorithm does not require frequent switching of paths to establish connections, as routes can be computed locally without the network topology information. However, in this paper, the packets are routes between logical nodes, mapped by the nearest satellite. When the constellation size becomes quite large, the mapping between the logical location and the satellite will become inaccurate, resulting in packets not being able to be transmitted to the correct destination.  
In recent years, various routing algorithms based on LEO large-scale constellations, have been proposed [12; 13; 14; 15]. In [12], [PERSON] et al. measured large amounts of real-time communications (RTC) session data and found two critical causes of high latency in the current cloud-based wide-area RTC architecture: (i) additional latency introduced by underlying cross-domain protocols and suboptimal paths; (ii) insufficient cloud server deployments can also cause additional latency. To address the above issues, [PERSON] et al. proposed an RTC framework called SPACERTC, which utilizes large-scale constellations, to help improve the latency performance of RTC session tasks. To be specific, SPACERTC first models the minimum RTC delay problem in spatial information networks and constructs a collaborative hybrid cloud network between the terrestrial cloud server and the constellation. Then, RTC streams are scheduled in this hybrid cloud network, to minimize the average RTC latency.  
DRL-ER [13] is a routing algorithm based on deep reinforcement learning, which can balance link bandwidth resources and satellite battery resources. By modeling the energy consumption and acquisition in the large-scale satellite network into a Markov decision process (MDP), DRL-ER establishes the connection between link resources and routing decisions. Meanwhile, this algorithm trains the routing policies under different battery resources, through the experience replay strategy, to achieve better adaptability to delay bounds. To reduce the loss of data transmission failures in satellite networks, [PERSON] et al. designed RMPR [14], a multi-path routing algorithm with low-latency and failure tolerance. Compared with shortest path routing and backup dependent multi-path routing, RMPR transmits multiple copies over multiple independent shortest paths, in an optimal ratio, to ensure the reliability and timeliness of data. [PERSON] et al. were more interested in improving system throughput than reducing transmission latency, and proposed an innovative routing protocol in [15]. This protocol solves the indivisible multi-commodity flow problem in satellite networks, by a randomized rounding based heuristic algorithm, and optimizes the total amount of traffic across the constellation. Compared with the shortest path (SP) routing strategy, this protocol can significantly improve network throughput and alleviate network congestion.  
Although there has been much research on routing algorithms for LEO mega-constellations, most of them still solve the end-to-end transmission problem, ignoring the most important application scenario of LEO constellations, which is to provide internet access services. We try to design a routing algorithm from a different angle, to meet the needs of fast internet access. Considering the large number of satellite nodes in mega-constellations, it is complicated and unnecessary to calculate the shortest path between all satellites. We only need to calculate the matches between satellites nodes and compute the routes between satellites in the matching set.