LEOCraft: Towards Designing Performant LEO Networks

Low Earth Orbit (LEO) satellite constellations have revolutionized Internet access for millions of users. OneWeb and SpaceX are already operating constellations of hundreds and thousands of satellites, offering Internet service directly from space across 100+ countries. These exceptionally large networks come at a cost – thousands of routers (satellites) need to fly at ∼22× the speed of sound, thus making network design a non-trivial challenge. While the systems research community with decades of deep networking expertise has a relatively short window to influence the design of these networks, there is a serious lack of the right tools to enable such efforts. To address this, we introduce LEOCraft – an LEO network design framework to help the community visualize and evaluate the performance of different choices. LEOCraft offers integrated optimization techniques tuned upon the domain knowledge acquired from thousands of LEO constellation design’s performance evaluations to optimize a new constellation design ∼5× faster than other off-the-shelf black-box optimization techniques. LEOCraft scales up seamlessly, tested for 83K satellites across multiple shells (more than 2× SpaceX’s longterm proposal) with 1K ground stations, thus making it feasible for the community to explore LEO trajectory and topology design for even the largest of mega-constellations.

低地球轨道（LEO）卫星星座已经彻底改变了数百万用户的互联网接入方式。OneWeb和SpaceX等公司已经运营着由数百至数千颗卫星组成的星座，为全球100多个国家直接提供来自太空的互联网服务。这些规模庞大的网络也带来了高昂的成本——数千个路由器（即卫星）需要以约22倍音速的速度飞行，这使得网络设计成为一项极具挑战性的任务。

尽管拥有数十年深厚网络专业知识的系统研究界有一个短暂的窗口期来影响这些网络的设计，但目前严重缺乏能够支持这些工作的合适工具。

为了解决这一问题，我们推出了LEOCraft——一个用于LEO网络设计的框架，旨在帮助研究界可视化和评估不同设计选择的性能。

LEOCraft提供了集成的优化技术，这些技术基于从数千次LEO星座设计性能评估中获得的领域知识进行调优，从而使新星座设计的优化速度比其他现成的黑盒优化技术快约5倍。LEOCraft能够无缝扩展，经测试可支持跨多个壳层（shells）的83000颗卫星（超过SpaceX长期规划数量的2倍）和1000个地面站，从而使研究界探索超大规模巨型星座的LEO轨道和拓扑设计成为可能。

Introduction

In the past few years, thousands of satellites have been deployed in Low Earth Orbit (LEO) to serve worldwide high-speed Internet broadband service directly from space [44]. The early movers of this new networking landscape, SpaceX’s Starlink and OneWeb, initially relied upon bent-pipe connectivity in the first generation of constellations [58]. Further technological advancements have introduced robust laser Inter-Satellite Links (ISLs), enabling space-borne mesh networks with high bandwidth and speed-of-light grade latency [55]. Such a LEO satellite network can carry long-haul Internet traffic over the satellite network, thus reducing the requirement for denser Ground Station (GS) deployment across the globe [2]. This development enabled Starlink and Amazon’s Project Kuiper to propose a 2nd generation megaconstellation of 30,000 [3] and 3,236 satellites [1] respectively, to wrap the Earth with a dense mesh of LEO satellites. However, the FCC approved only 7,500 satellites of Starlink across three different altitudes [3]. SpaceX started launching these new generation satellites in December 2022 [61]. In contrast, Kuiper was recently in the testing phase of the optical mesh network in space [5]. Therefore, none of the operators has achieved the true scale of ISL-enabled megaconstellations yet, keeping the brief window open for the networking community to influence such design.

在过去几年中，数千颗卫星被部署到低地球轨道，用以直接从太空提供覆盖全球的高速互联网宽带服务[44]。

作为这一新兴网络领域的先行者，SpaceX的星链（Starlink）和OneWeb在其第一代星座中最初依赖于“弯管”（bent-pipe）连接技术[58]。

技术的进一步发展引入了强大的激光星间链路（Inter-Satellite Links, ISLs），实现了具有高带宽和光速级延迟的星载网状网络（mesh networks）[55]。这样的LEO卫星网络可以通过卫星网络承载长途互联网流量，从而减少了在全球密集部署地面站（Ground Station, GS） 的需求[2]。这一进展使得星链和亚马逊的柯伊伯计划（Project Kuiper）分别提出了包含30,000颗[3]和3,236颗[1]卫星的第二代巨型星座，旨在用密集的LEO卫星网覆盖地球。

然而，美国联邦通信委员会（FCC）仅批准了星链在三个不同高度部署的7,500颗卫星[3]。SpaceX于2022年12月开始发射这些新一代卫星[61]。相比之下，柯伊伯计划最近仍处于在太空中测试其光纤网状网络的阶段[5]。

因此，目前还没有任何运营商真正实现启用ISL的巨型星座的规模 ，这为网络研究界影响此类设计保留了一个短暂的窗口期。

The secret of constellation design: The success of Starlink’s early launches sparked researcher’s interest in exploring various aspects of LEO networks. Such recent works [44–46,50, 54–56,58,64,67,68,76] have used Starlink, OneWeb, and a few other constellation designs in their experiments since details are publicly available in the FCC filings [1,3,8,12,21,31]. However, none of these existing works include the complete set of design parameters determining the satellite’s trajectory as well as topology [45,72,92,93]. Most of these efforts are restricted to a single shell, considering the inter-shell connectivity and aggregated performance measurement of multiple independent shells as "an open problem" [93].

Furthermore, Starlink and OneWeb, the biggest constellation operators, rely on proprietary systems, making their LEO networks function like black boxes. Why they chose a particular design, and what traffic matrices it targets, is unknown to the community. Therefore, in this work, we aim to unveil the subtle crux of designing an optimized LEO network from scratch. Our effort will help networking researchers understand these ‘new space’ networks better.

星座设计的奥秘:

星链早期发射的成功激发了研究人员探索LEO网络各个方面的兴趣。近期的相关研究[44–46,50, 54–56,58,64,67,68,76]在其实验中使用了星链、OneWeb及其他一些星座设计，因为这些细节在FCC的备案文件[1,3,8,12,21,31]中是公开的。然而，这些现有工作均未包含决定卫星轨道及拓扑的完整设计参数集[45,72,92,93]。其中大部分研究仅限于单个卫星壳层，并将跨壳层连接和多个独立壳层的聚合性能测量视为一个“有待解决的问题”[93]。

此外， 最大的星座运营商星链和OneWeb依赖于其专有系统，使其LEO网络的功能如同黑盒。 他们为何选择某种特定的设计，以及该设计针对何种流量矩阵，这些信息对于研究界来说都是未知的。因此，在这项工作中，我们的目标是揭示从零开始设计一个优化的LEO网络的精妙之处。我们的努力将帮助网络研究人员更好地理解这些“新太空”网络。

Why constellation design is non-trivial?: Designing a satellite network is not a new problem. In the 90s, serious efforts [37,41,52,65,66,89,90] have been devoted in studying constellation design. However, the current scale and design objectives have significantly transformed over time, imposing new challenges. Optimizing a satellite constellation in the 90s emphasized coverage with a limited budget of a few 10s of satellites, ensuring availability worldwide [42]. In contrast, now, with the scale of a few thousand or more satellites, network performance has become comparable to the terrestrial networks [53]. Therefore, optimizing a constellation today is no longer a geometrical optimization of overlapping satellite coverage [51], but rather, an optimization of the satellite’s orbital trajectories and their ISL topology for a given Internet traffic demand matrix. Therefore, given the number of satellites, the design problem is to decide upon several parameters describing ISL topology and each satellite’s orbital trajectory at ∼22× the speed of sound, such that network performance is maximized. A network design is already a hard problem [62]; further joint optimization of orbital parameters with added dynamics of satellite motion makes it a non-trivial high-dimensional optimization problem. A naive brute-force grid search approach looking for maximum network performance measurement could take years due to the curse of dimensionality. A few previous efforts explored the aspect of improving constellation performance with better ISL topology [45, 72]; however, the approach [45] suffers from scalability issues hence could not be extended to the direction towards superior constellation design, i.e., optimization of satellite’s trajectory at scale to enhance the network performance.

星座设计为何并非易事:

设计卫星网络并非一个新问题。

上世纪90年代，学界曾投入大量精力研究星座设计[37,41,52,65,66,89,90]。然而，当前的规模和设计目标已随时间发生了显著变化，带来了新的挑战。90年代优化卫星星座的重点是在几十颗卫星的有限预算内强调覆盖范围，以确保全球范围内的可用性[42]。

相比之下，如今随着卫星数量达到数千颗甚至更多，网络性能已可与地面网络相媲美[53]。因此，当今的星座优化不再是简单的卫星覆盖范围重叠的几何优化问题[51]，而是针对给定的互联网流量需求矩阵，对卫星的轨道轨迹及ISL拓扑进行优化。

因此，在给定卫星数量的情况下，设计问题就是确定描述ISL拓扑和每颗卫星以约22倍音速飞行的轨道轨迹的若干参数，从而使网络性能最大化。网络设计本身已是一个难题[62]；将轨道参数与卫星运动的动态性进行联合优化，使其成为一个非平凡的高维优化问题。由于“维度灾难”的存在，一种朴素的、旨在寻找最大网络性能指标的暴力网格搜索方法可能需要数年时间。先前的一些工作曾探索通过更优的ISL拓扑来提升星座性能[45, 72]；然而，其方法[45]存在可扩展性问题，因此无法扩展到更优星座设计的方向，即大规模优化卫星轨道以增强网络性能。

Missing the right tools: An in-depth study of trajectory and ISL topology optimization of the LEO network requires the execution of tens of thousands of simulations while varying one or more orbital/design parameters to measure how these choices impact the network performance. Therefore, an LEO network evaluation framework must offer the flexibility to (i) rapidly implement different ideas (topology, ISL connectivity, routing strategy, etc.), (ii) plug and play with various optimization strategies, (iii) evaluate the effectiveness of optimization strategies and further tuning these implementations. Existing platforms, i.e., Hypatia’s [64] packet-level simulator, or StarryNet’s [67] Docker container-based emulator, suffer from fundamental scalability issues [63]. Hence does not go well for large-scale (tens of thousands of satellites) trajectory simulation. Another LEO network emulation platform xeoverse [63] is built upon a lightweight process-based network emulator platform Mininet [20] and claims to outperform Hypatia and StarryNet by large margins; however, their source code is not public for community use. Therefore, the community lacks the right tools to approach large-scale trajectory and topology optimization problems.

现有工具的缺失:

对LEO网络的轨道和ISL拓扑进行深入的优化研究，需要执行数以万计的模拟，同时改变一个或多个轨道/设计参数，以衡量这些选择对网络性能的影响。

因此，一个LEO网络评估框架必须具备以下灵活性:

（i）快速实现不同想法（如拓扑、ISL连接、路由策略等）

（ii）与各种优化策略即插即用

（iii）评估优化策略的有效性并进一步调整这些实现

现有的平台，如Hypatia的包级模拟器[64]或StarryNet的基于Docker容器的仿真器[67]，都存在根本性的可扩展性问题[63]，因此不适用于大规模（数万颗卫星）的轨道模拟。

另一个LEO网络仿真平台xeoverse[63]建立在轻量级的基于进程的网络仿真平台Mininet[20]之上，并声称性能远超Hypatia和StarryNet；然而，其源代码并未公开给社区使用。

因此，研究界缺乏合适的工具来解决大规模的轨道和拓扑优化问题。

Our contributions: In this paper, we address these gaps with LEOCraft – an LEO satellite constellation design exploration, optimization, and visualization framework. LEOCraft relies upon process-based parallelism [14], thus bypassing the Global Interpreter Lock, a major computational bottleneck [17] in the existing platforms [64,67]. It is designed to be a modular framework that allows rapid implementation of new design ideas with minimal code change (typically 100 lines of code), which helps to run new experiments quickly. It operates at the flow level, computes network measurements from the intuitive mathematical model of the LEO network instead of resource-intensive packet-level simulations. For instance, the performance evaluation of Starlink’s Gen1 three shells of 3,888 satellites (S-1 to S-3 in Table 1) in LEOCraft takes ∼2.5 minutes on a standard Desktop PC. Whereas with Hypatia, it takes hours for only RTT measurement of Starlink’s single shell of 1,584 satellites. We also tested LEOCraft on a hypothetical mega-constellation of 83+ satellites across multiple shells (as shown in Table 1). Thus, LEOCraft enables rapid evaluation of design choices at a large scale. The visualization module also generates interactive views of the constellation, showcasing topology evolution and end-to-end route changes to augment the intuition of LEO dynamics.

我们的贡献:

在本文中，我们通过LEOCraft —— 一个用于LEO卫星星座设计探索、优化和可视化的框架——来弥补这些不足。

LEOCraft依赖于基于进程的并行计算[14]，从而绕过了现有平台[64,67]中的一个主要计算瓶颈——全局解释器锁（Global Interpreter Lock）[17]。它被设计为一个模块化框架，允许以最少的代码更改（通常约100行代码）快速实现新的设计思想，这有助于快速开展新实验。它在流级别（flow level）上运行，通过直观的LEO网络数学模型计算网络指标，而非采用资源密集型的包级模拟。

例如，在LEOCraft中对星链第一代三个壳层共3,888颗卫星（表1中的S-1至S-3）进行性能评估，在一台标准台式电脑上仅需约2.5分钟。而使用Hypatia，仅对星链单个壳层（1,584颗卫星）进行往返时延（RTT）测量就需要数小时。我们还在一个包含超过83颗卫星的跨多壳层假设性巨型星座上测试了LEOCraft（如表1所示）。

因此， LEOCraft使得对大规模设计选择进行快速评估成为可能。其可视化模块还能生成星座的交互式视图，展示拓扑演变和端到端路由变化， 以增强对LEO动态性的直观理解。

We use LEOCraft to rigorously study the constellation design for given traffic demand matrices across a set of GSes and illustrate how the choices of design parameters impact the performance of these LEO networks. Since Internet traffic demand is skewed towards specific regions of the Earth with higher populations, the performance measurements of constellation designs exhibit common trends irrespective of the satellite budget. We use this domain knowledge and predictable characteristics of network performance measurements to prune the search space drastically. This reduces the running time by ∼5× as compared to the naive off-the-shelf black-box optimization techniques. We also demonstrate how inter-shell ISL can improve the throughput of a constellation and highlight some shortcomings of such ISL usage. We made LEOCraft publicly available [35] for community use.

我们使用LEOCraft对给定地面站间流量需求矩阵的星座设计进行严谨研究，并阐述设计参数的选择如何影响这些LEO网络的性能。由于互联网流量需求偏向于地球上人口较多的特定区域，星座设计的性能测量表现出与卫星预算无关的普遍趋势。我们利用这一领域知识和网络性能测量的可预测特性来大幅削减搜索空间。与朴素的现成黑盒优化技术相比，这将运行时间缩短了约5倍。我们还展示了跨壳层ISL如何提高星座的吞吐量，并指出了使用此类ISL的一些缺点。我们已将LEOCraft公开发布[35]供社区使用。

Paper outline: The remaining paper is organized as follows – §2-3 summarize our overall background and problem overview. Then §4-6 discusses the development, optimization, and system design strategies used in LEOCraft framework. §7-8 present the experimental evaluation. §9 summarizes the related works. The paper is concluded in §10.

论文结构： 本文其余部分的组织如下——§2-3总结了我们的背景知识和问题概述。§4-6讨论了LEOCraft框架中使用的开发、优化和系统设计策略。§7-8展示了实验评估。§9总结了相关工作。最后在§10中对全文进行总结。

Background

Building an LEO constellation is a relatively new topic, so this section aids the reader with the relevant background.

这一章补充一些背景知识

2.1 LEO constellation design parameters

omitted here

文章汇总了现在常见的SNO卫星设计参数, 值得参考!

LEOCraft基于上面6个参数, 构建TLE数据, 模拟卫星星座的构成与运动情况

2.2 LEO network modelling and assumptions

The proprietary nature of the LEO constellation prohibits public disclosure of key details, such as satellite connectivity policies, user terminal associations, and bandwidth distribution mechanisms, etc. Thus, we base our assumptions on standards widely adopted in prior literature.

Network model: In LEOCraft, given a set of design parameters, we model the LEO satellite constellation as a big network graph, where nodes represent the satellites and GSes, and edges represent Ground to Satellite Links (GSLs) and ISLs. Unavailability of precise geospatial information prevents the modelling of individual user terminals [88]. Therefore, we assume the GS located in a city serves as a proxy for the demands of all the users in that city. Consequently, we allow a GS to establish GSLs with all the satellites available above the minimum angle of elevation \(e\) (from the horizon) at that particular time.

GSL budget model: In the above network, capacities of GSLs \(C\) are calculated from Shannon’s channel capacity theorem [82]. The atmospheric path loss is estimated using the Free-Space Path Loss (FSPL) model [60]. With these, the channel capacity is expressed as \(C = B\log_2(1 + \frac{P_t G_t \lambda^2}{(2\pi d)^2 k_B B} \times \frac{G_r}{T})\), where, \(P_t\) is the Tx power (EIRP), \(G_t\) and \(G_r\) are the Tx and Rx antenna gains respectively, \(\lambda\) is the wavelength, and antenna gain-to-noise-temperature ratio \(G_r/T\) are taken from Ka-band specification available in FCC filling [50]. \(d\) denotes the distance between the Tx and Rx antenna, i.e., the distance between the satellites and GSes, \(k_B\) is Boltzmann's constant, and \(B\) is the transmission bandwidth. Note that, in our implementation, \(B\) is divided equally among the GSes under the coverage of each satellite.

ISL budget model: The laser ISLs are expected to have extremely low beam divergence properties and narrow beam widths, minimizing interference issues [4]. Currently, ISLs are in the early phase of deployment [30] or the testing phase of different operators [5, 11]. Since the largest LEO network operator Starlink’s satellites use 4 ISLs [43] and subsequently all the prior work [45, 64, 67, 92, 93] made this a de facto standard, this work assumes and extends the same with capacity of each ISL conservatively set to 50 Gbps [6, 7, 9]. Although it is a configurable parameter in LEOCraft.

LEO星座的专有性质导致其关键细节无法公开披露，例如卫星连接策略、用户终端关联方式以及带宽分配机制等。因此，我们的假设基于先前文献中广泛采用的标准。

网络模型： 在LEOCraft中，给定一组设计参数，我们将LEO卫星星座建模为一个大型网络图。图中的节点代表卫星和地面站（GSes），边代表地星链路（GSLs）和星间链路（ISLs）。由于无法获得精确的地理空间数据，我们无法对单个用户终端进行建模[88]。因此，我们假设位于城市中的地面站作为该城市所有用户需求的代理。相应地，我们允许一个地面站与在特定时刻其最低仰角 \(e\)（相对于地平线）以上的所有可用卫星建立地星链路。

GSL预算模型： 在上述网络中，地星链路的容量 \(C\) 是根据香农信道容量定理[82]计算的。大气路径损耗则使用自由空间路径损耗（FSPL）模型[60]进行估算。综合这些，信道容量表示为 \(C = B\log_2(1 + \frac{P_t G_t \lambda^2}{(2\pi d)^2 k_B B} \times \frac{G_r}{T})\)。其中，\(P_t\) 是发射功率（EIRP），\(G_t\) 和 \(G_r\) 分别是发射和接收天线的增益，\(\lambda\) 是波长，天线增益噪声温度比 \(G_r/T\) 取自FCC文件[50]中提供的Ka波段规范。\(d\) 表示发射和接收天线之间的距离，即卫星和地面站之间的距离，\(k_B\) 是玻尔兹曼常数，\(B\) 是传输带宽。需要注意的是，在我们的实现中，每个卫星覆盖范围下的带宽 \(B\) 会在各个地面站之间平均分配。

ISL预算模型： 激光星间链路（ISL）预计将具有极低的波束发散特性和极窄的波束宽度，从而最大限度地减少干扰问题[4]。目前，ISL仍处于部署的早期阶段[30]或不同运营商的测试阶段[5, 11]。由于最大的LEO网络运营商Starlink的卫星使用4条ISL[43]，并且所有后续的先前工作[45, 64, 67, 92, 93]都已将其作为事实标准，本研究也采纳并扩展了这一设定，将每条ISL的容量保守地设置为50 Gbps [6, 7, 9]。不过，在LEOCraft中，这是一个可配置的参数。

2.3 Internet traffic demand matrices

Since a geospatial dataset of individual Starlink users is not public [88], we use the following intuitive traffic demand matrices (TM) that follow the gravity model [79].

High population TM: We use World Cities Database [34] for the population dataset, where GSes are located in 100 most populous cities around the globe. We assume that 10% of a city’s population is the targeted customer, with average data usage per head of 300 Kbps [76]. The traffic demand across the GSes is inversely proportional to their geodesic distances.

High GDP population TM: Apart from the city population, typically, the Internet traffic is also proportional to the city’s GDP [38]. So, in this demand matrix, we assume that the targeted market is 10% of the total population of the 100 most populous cities. However, the data usage is weighted based on the city’s GDP. We keep the mean data usage to be 300 Kbps. Similar to the previous matrix, the demand across the GSes is inversely proportional to their geodesic distances.

Country capital TM: In this matrix, the GSes are located in the capital of 233 countries. The demands across the GSes are weighted proportionately to the country’s population and in inverse proportion to the geodesic distances between GSes.

Global flight TM: In-flight Wi-Fi market is already a billion-dollar industry, forecasting an annual growth rate of 11.8% [18]. Therefore, domestic and international airlines are also potential target markets for the in-flight high-speed Wi-Fi service [80]. For that, we use FlightRadarAPI [33] to collect details of the in-flight aircraft worldwide. Then we assume 50% of passengers of each flight above 10,000 feet of altitude are communicating with GSes located at the 100 most populous cities via satellite network. We weighted the demand matrix between the flights and the GSes using the gravity model discussed above, whereas the weights are directly proportional to populations/passengers and inversely proportional to the distance between the flights and the GSes. Moreover, notice that the TMs are subject to the target market. A satellite constellation designed to serve the shipping industry might weight the demand matrices analogous to the busiest trade routes in the ocean. Hence, many such intuitive TMs can be formulated. However, our study is focused only on the TMs discussed above.

由于Starlink个人用户的地理空间数据集并未公开[88]，我们采用以下遵循引力模型[79]的直观流量需求矩阵（TM）。

高人口流量模型 (High population TM)： 我们使用世界城市数据库[34]作为人口数据集，其中地面站位于全球100个人口最多的城市。我们假设每个城市10%的人口是目标客户，人均数据使用量为300 Kbps[76]。地面站之间的流量需求与其测地线距离成反比。

高GDP人口流量模型 (High GDP population TM)： 除了城市人口，互联网流量通常也与城市的GDP成正比[38]。因此，在这个需求矩阵中，我们假设目标市场仍是100个人口最多城市总人口的10%，但数据使用量根据城市的GDP进行加权。我们保持人均数据使用量为300 Kbps。与前一个矩阵类似，地面站之间的需求与其测地线距离成反比。

国家首都流量模型 (Country capital TM)： 在此矩阵中，地面站位于233个国家的首都。地面站之间的需求根据国家人口进行比例加权，并与地面站之间的测地线距离成反比。

全球航班流量模型 (Global flight TM)： 空中Wi-Fi市场已是一个价值数十亿美元的产业，预计年增长率为11.8%[18]。因此，国内和国际航线也是空中高速Wi-Fi服务的潜在目标市场[80]。为此，我们使用 FlightRadarAPI [33] 收集全球在飞航班的详细信息。然后我们假设，在飞行高度超过10,000英尺的每个航班中，有50%的乘客通过卫星网络与位于100个人口最多城市的地面站进行通信。我们使用上文讨论的引力模型来加权航班与地面站之间的需求矩阵，其权重与人口/乘客数量成正比，与航班和地面站之间的距离成反比。此外，需要注意的是，流量矩阵取决于目标市场。一个为航运业设计的卫星星座可能会根据海洋中最繁忙的贸易路线来加权需求矩阵。因此，可以构建许多此类直观的流量矩阵。然而，我们的研究仅集中于上述讨论的几种流量矩阵。

2.4 Network performance metrics

We evaluate the constellations on the following three performance metrics.

我们通过以下三个性能指标来评估星座。

Throughput: We measure the throughput of the LEO satellite constellation as a multi-commodity flow across the GSes. We compute \(n\) shortest routes between the GSes at any given time using Yen’s algorithm [91]. Then, we use the following linear program to maximize the flow between all pairs of GSes.

Maximize: \(\sum_{f \in \mathbf{F}} D_f \times \sum_k R_f^k\) (1)

Subject to: \(0 \le \sum_k R_f^k \le 1 \quad \forall f \in \mathbf{F}\) (2)

\(\sum_{(f,r) \in \mathbf{S}_l} D_f \times R_f^r \le C_l \quad \forall l \in \mathbf{L}\) (3)

Here, \(\mathbf{F}\) is the set of flows, where a flow is defined as an ordered pair of GSes denoting traffic flow between one GS pair. \(D_f\) is the traffic demand for the flow \(f\) (demand between two GS). Since we have \(n\) shortest routes between each pair of GSes, \(R_f^k\) denotes the fraction of demand \(D_f\) flowing through the \(k\)-th shortest route. Therefore, \(\sum_k^n R_f^k\) the sum of \(n\) continuous variable bounded within zero and one in constraint (2), which ensures \(n\) shortest routes together can accommodate at most 100% of the demand \(D_f\) of any flow \(f \in F\). Finally, the links could be shared by more than one flow in the network. Therefore, aggregated traffic flows sharing a particular link are constrained by the capacity of that link. Hence, in constraint (3), \(\mathbf{L}\) is the set of all the links in the network, and \(\mathbf{S}_l\) denotes a set of flows \(f\) and their \(r\)-th shortest route that shares link \(l\). Therefore, \(\sum_{(f,r) \in \mathbf{S}_l} D_f \times R_f^r\) denotes total traffic flow via link \(l\), which is constrained by the \(C_l\), the capacity of link \(l\). For all our simulations, we use \(n=20\).

吞吐量 (Throughput)： 我们将LEO卫星星座的吞吐量作为地面站之间的多商品流进行测量。在任何给定时间，我们使用Yen算法[91]计算地面站之间的 \(n\) 条最短路径。然后，我们使用以下线性规划来最大化所有地面站对之间的流量。

• 最大化目标：\(\sum_{f \in \mathbf{F}} D_f \times \sum_k R_f^k\) (1)
• 约束条件：
  • \(0 \le \sum_k R_f^k \le 1 \quad \forall f \in \mathbf{F}\) (2)
  • \(\sum_{(f,r) \in \mathbf{S}_l} D_f \times R_f^r \le C_l \quad \forall l \in \mathbf{L}\) (3)

在这里，\(\mathbf{F}\) 是流的集合，其中一个流被定义为表示一个地面站对之间流量的有序对。\(D_f\) 是流 \(f\) 的流量需求（即两个地面站之间的需求）。由于我们为每对地面站计算了 \(n\) 条最短路径，\(R_f^k\) 表示流经第 \(k\) 条最短路径的需求 \(D_f\) 的比例。因此，\(\sum_k^n R_f^k\) 是 \(n\) 个连续变量的总和，其值在约束条件(2)中被限制在0和1之间，这确保了 \(n\) 条最短路径总共最多能满足任何流 \(f \in F\) 的100%需求 \(D_f\)。最后，网络中的链路可能被多个流共享。因此，共享特定链路的聚合流量受该链路容量的限制。因此，在约束条件(3)中，\(\mathbf{L}\) 是网络中所有链路的集合，\(\mathbf{S}_l\) 表示共享链路 \(l\) 的流 \(f\) 及其第 \(r\) 条最短路径的集合。因此，\(\sum_{(f,r) \in \mathbf{S}_l} D_f \times R_f^r\) 表示通过链路 \(l\) 的总流量，该流量受链路 \(l\) 的容量 \(C_l\) 的约束。在我们所有的模拟中，我们使用 \(n=20\)。

Stretch (latency): We measure stretch between source and destination GS pair as the ratio of the distance between two locations over the satellite network through ISLs and their geodesic distance. This metric demonstrates the inflation in the length of the end-to-end routes. Since the scope of this work is a comparative performance study of constellation design, lower stretch and lower hop counts for end-to-end routes are expected to give better network latency.

To understand the generalized nature of latency worldwide across diverse routes, we classify all the routes into five categories based on their nature. The first two categories are based on the distance between the source and destination GSes. Therefore, (a) any pair of GSes located within a distance of 2,000 km falls in the Low Geodesic (LG) distance class. Such routes will always come with higher stretch because of the route overhead of going up from the source GS to a satellite and coming down from a satellite to the destination GS, only to use one satellite hop (most of the time). (b) Any source and destination pair of GSes located far apart in different hemispheres (\(\ge\) 8,000 km) falls in the class of High Geodesic (HG) distance routes as illustrated in Fig. 2(a). All other routes that do not fall into the above two classes are classified based on the orientation of the path. Therefore, the routes between the GSes pairs oriented with (c) angle above 75º shown in Fig. 2(b) are classified as North-South (NS) routes, (d) angle below 15º shown in Fig. 2(c) are classified as East-West (EW) routes, and (e) angle within 15º and 75º shown in Fig. 2(d) are classified as NorthEast-SouthWest (NESW) routes. For overall stretch tendency, we report the median stretch and hop counts of each category.

伸展度 (延迟) (Stretch (latency))： 我们测量源和目标地面站对之间的伸展度，其定义为 两个位置之间通过ISL的卫星网络路径距离与其测地线距离的比值。该指标反映了端到端路径长度的膨胀程度。 由于本研究旨在对星座设计进行比较性能研究，较低的伸展度和较少的端到端路由跳数预计会带来更好的网络延迟。

为了理解全球范围内不同类型路径的普适延迟特性，我们根据其性质将所有路径分为五类:

(1) 前两类基于源和目标地面站之间的距离

1. 任何距离在2,000公里以内的地面站对属于低测地线距离 (LG) 类。这类路径的伸展度总是较高，因为存在从源地面站上升到卫星再下降到目标地面站的额外路径开销，而全程通常只使用一次卫星跳接

2. 任何位于不同半球且相距遥远（\(\ge\) 8,000公里）的源和目标地面站对属于高测地线距离 (HG) 类，如图2(a)所示

(2) 所有不属于上述两类的其他路径则根据路径的方位进行分类

1. 角度大于75°的地面站对之间的路径（如图2(b)所示）被归类为南北向 (NS) 路径

2. 角度小于15°的路径（如图2(c)所示）被归类为东西向 (EW) 路径

3. 角度在15°和75°之间的路径（如图2(d)所示）被归类为东北-西南向 (NESW) 路径

为了反映整体的伸展度趋势，我们报告每个类别的伸展度和跳数的中位数

Coverage: One of the unique potentials of the LEO satellite constellation is to offer genuinely global high-speed Internet service irrespective of geographical challenges. However, to sustain the business, the obvious choice of a constellation operator would be to optimize the satellite trajectories to provide higher availability where the volume of customers is high. Therefore, we measure the coverage of a constellation as \(\sum_{t=0}^T \sum_{g=0}^G \log_{10}(n_{t,g})/T\), where \(G\) is the number of GSes, \(T\) is the number of epochs, and \(n_{t,g}\) denotes the number of satellites visible from the g-th GS at t-th epoch. The \(\log(.)\) function models the diminishing returns as the number of visible satellites per GSes increases.

覆盖范围 (Coverage)： LEO卫星星座的独特潜力之一是提供真正全球性的高速互联网服务，而不受地理挑战的限制。然而，为了维持商业运营，星座运营商的明确选择将是优化卫星轨道，以便在客户集中的地区提供更高的可用性。因此，我们用公式 \(\sum_{t=0}^T \sum_{g=0}^G \log_{10}(n_{t,g})/T\) 来衡量星座的覆盖范围。其中，\(G\) 是地面站的数量，\(T\) 是时间纪元（epoch）的数量，\(n_{t,g}\) 表示在第 \(t\) 个时间纪元从第 \(g\) 个地面站可见的卫星数量。\(\log(.)\) 函数模拟了随着每个地面站可见卫星数量增加而产生的边际效益递减。

LEO network design from scratch

With the preceding background, we now delve into the LEO trajectory design problem, along with the research challenge of high dimensionality.

在了解了上述背景知识后，我们现在将深入探讨LEO轨道设计问题，及其伴随的高维度研究挑战。

Problem statement: We define our problem statement as follows – given the number of satellites (which is our network budget), location of GSes, and traffic demand matrix across these GSes, we need to find the constellation design parameters of one or more shells (s) and their operational altitude (h), inclination (i), minimum elevation angle (e), number of orbits (o), satellites per orbit (n), and the phase offset (p) between satellites in adjacent orbits that maximize some objective function such as throughput, coverage, latency, or a combination of these. However, in this work, we focus on a performant constellation that maximizes the throughput. Higher throughput produces more salable bandwidth, which might fetch higher revenue for the constellation operator.

问题陈述

我们将问题陈述定义如下——在给定卫星数量（即我们的网络预算）、地面站（GSes）位置以及这些地面站间的流量需求矩阵的条件下，我们需要找到一个或多个卫星壳层（s）的星座设计参数，包括其运行高度（h）、轨道倾角（i）、最低仰角（e）、轨道数量（o）、每轨道卫星数（n），以及相邻轨道卫星间的相位偏移（p），从而最大化某个目标函数，例如吞吐量、覆盖范围、延迟或这些指标的组合。

然而，在本项工作中，我们 专注于设计一个最大化吞吐量的高性能星座。 更高的吞吐量能产生更多可销售的带宽，这可能为星座运营商带来更高的收入。

The curse of dimensionality: Therefore, in a megaconstellation of multiple shells, a brute-force grid search approach to find near-optimal design parameters will require the execution of |s| × |h| × |i| × |p| × |o| × |n| × |e| × |t| simulations, where |x| means number of distinct choices of parameter x, and |t| denotes the number of epochs over 24 hours (one complete rotation of Earth) to estimate the performance fluctuation for LEO dynamics. Each simulation involves generating a network graph, calculating link budgets, computing routes globally, and evaluating network performance. That could take from a few minutes to hours or even days, depending on the number of satellites and GSes in the constellation. Therefore, executing these many simulations with many computational cores could take years.

维度灾难

因此，在一个包含多个壳层的巨型星座中，采用暴力网格搜索方法来寻找近乎最优的设计参数，将需要执行 \(|s| \times |h| \times |i| \times |p| \times |o| \times |n| \times |e| \times |t|\) 次模拟。其中，\(|x|\) 表示参数 \(x\) 的不同选择数量，而 \(|t|\) 表示24小时内（地球完整自转一周）的时间纪元（epochs）数量，用以评估LEO动态性带来的性能波动。每次模拟都涉及生成网络图、计算链路预算、全局计算路由以及评估网络性能。

根据星座中卫星和地面站的数量，单次模拟可能需要几分钟到几小时甚至几天的时间。因此，即便使用大量计算核心来执行如此多的模拟，也可能需要数年时间。

Can we prune the search space? Given the large search space, meta-heuristic methods like Simulated Annealing [85], Differential Evolution [83], and Adaptive Particle Swarm Optimization [81] can offer near-optimal solutions. In addition, we leverage domain knowledge and heuristics related to the design parameter’s impact on network performance to reduce the search space significantly. Our comprehensive analysis of design parameters highlights their performance characteristics and inter-dependencies. This insight refines meta-heuristic approaches. Further enables tuning of local search strategies to outperform out-of-the-box meta-heuristics.

我们能否削减搜索空间?

鉴于搜索空间巨大，元启发式方法，如模拟退火（Simulated Annealing）[85]、差分进化（Differential Evolution）[83]和自适应粒子群优化（Adaptive Particle Swarm Optimization）[81]，可以提供近乎最优的解。

此外，我们利用与设计参数对网络性能影响相关的领域知识和启发式方法来显著削减搜索空间。我们对设计参数的综合分析揭示了它们的性能特性及相互依赖关系。这种洞察力可以改进元启发式方法，并能进一步调整局部搜索策略，使其性能超越现成的元启发式算法。

Exploring the search space

这一部分是实验尝试的经验与规律, 太长了, 用gemini总结一下:

1. 性能稳定性与波动性:

   • LEO网络的整体性能是基本稳定的，但由于卫星的高速动态变化，吞吐量等指标会存在约6.5%的周期性小幅波动

2. 运行高度 (Altitude, \(h\)) 的影响:

   • 高度是一个需要权衡的参数
   • 优点： 提高高度可以增大单颗卫星的覆盖面积，从而提升星座的整体覆盖率
   • 缺点： 高度过高会导致地星链路（GSL）距离变长，增加延迟，并在超过某个临界点后反而会降低网络吞吐量

3. 轨道倾角 (Inclination, \(i\)) 的影响:

   • 倾角是至关重要的参数，其最优值与地面站的地理分布密切相关
   • 对于覆盖全球人口密集区（大多在中纬度）的星座（如Starlink），中等倾角（如40°-50°） 能实现最佳吞吐量
   • 倾角决定了路由的优势方向：较低的倾角有利于东西向（EW） 的数据传输，而接近90°的极地轨道则更有利于南北向（NS） 的传输

4. 最低仰角 (Elevation Angle, \(e\)) 的影响:

   • 这是一个需要精细调优的参数，极端值通常效果不佳
   • 降低仰角可以增加覆盖，但过低的仰角（如<10°） 会导致严重的大气信号衰减
   • 合适的仰角（如>5°）甚至可以用单次卫星跳接实现跨洲际连接

5. 轨道数量与相位设计的核心发现 (最重要的结论):

   • 对于大规模星座（如超过300颗卫星），最大化吞吐量的关键在于优化轨道拓扑结构
   • 核心策略： 采用“宽”星座设计，即拥有非常多的轨道平面 (\(o\))，而每个轨道上的卫星数量 (\(n\)) 相对较少（满足 \(o \gg n\)）
   • 配合相位偏移 (\(p\))： 同时，将相邻轨道间的相位偏移设置为0.5
   • 效果： 这种 \((o \gg n, p=0.5)\) 的组合能够构建出最高效的星间网状网络。它极大地增加了长距离（尤其是跨半球）路由的路径多样性，减少了传输跳数，从而显著提升了整个星座的吞-吐量。这个规律在多个不同卫星壳层中都得到了一致的验证

Designing of LEOCraft

Overview of other simulation platforms: The well-known LEO network simulation and emulation platforms in the community are Hypatia [64], StarryNet [67], and xeoverse [63]. xeoverse is a relatively new LEO network emulation platform built upon network emulation platform Mininet [20]. xeoverse claims to outperform Hypatia and StarryNet by large margins [63]; however, xeoverse is not public for community use. On the other hand, StarryNet is a data-driven emulation platform partially available [70] to the community. StarryNet uses Docker containers [15] to emulate each node (satellites, GSes, user terminals) and Python’s thread-based parallelism [32] for updating the state of virtual links (ISLs and GSLs) connecting containers [63]. Thus, StarryNet is resource-intensive, and scalability by default is constrained by the Docker engine’s upper limit of its bridge interface (up to 1,023 containers [13] on a single machine [63]). Due to CPython’s Global Interpreter Lock (GIL) [17], the link state update procedure of StarryNet with thousands of threads experiences a bottleneck, too. Hypatia is based upon ns-3 packet-level simulation platform [22]; hence, the scalability is constrained by the ns-3’s limitations. Since Hypatia fails to utilise multiple CPUs, simulation execution drastically slows down with larger constellation [63,64].

在研究界，知名的LEO网络模拟与仿真平台主要有Hypatia [64]、StarryNet [67]和xeoverse [63]。

xeoverse是一个相对较新的LEO网络仿真平台，它构建于网络仿真平台Mininet [20]之上。xeoverse声称其性能远超Hypatia和StarryNet [63]，然而，该平台并未公开给社区使用。

另一方面，StarryNet是一个数据驱动的仿真平台，部分开放[70]给社区。StarryNet使用Docker容器[15]来仿真每个节点（卫星、地面站、用户终端），并采用Python的基于线程的并行计算[32]来更新连接各容器的虚拟链路（ISL和GSL）状态[63]。因此，StarryNet是资源密集型的，其可扩展性默认受到Docker引擎桥接接口上限的限制（在单台机器上最多支持1023个容器[13, 63]）。此外，由于CPython的全局解释器锁（GIL）[17]，StarryNet中使用数千个线程的链路状态更新过程也遇到了性能瓶颈。

Hypatia则基于ns-3包级模拟平台[22]，因此其可扩展性受限于ns-3本身的局限。由于Hypatia无法利用多CPU，随着星座规模的增大，模拟执行速度会急剧下降[63, 64]。

System design: After exploring the implementation of the above platforms, we found that a significant portion of the performance bottleneck arises from the software layer. This is because the LEO satellite constellation is treated as a single, monolithic block. However, within this block, most computations are independent of one another. For example, determining the coverage area of one satellite does not depend on calculations for other satellites. Similarly, computing a route from one GS to another is independent of the routes between other pairs of GSes, and so on. We exploit this in the implementation of LEOCraft [35], where each component (such as satellites and GSes) operates as an independent block with format-restricted data exchange APIs. This allows us to distribute workloads uniformly across all available CPUs, effectively shifting the performance bottleneck from the software layer to the underlying hardware.

在探索了上述平台的实现后，我们发现性能瓶颈的很大一部分源于软件层面。这是因为它们将LEO卫星星座视为一个单一的、庞大的整体模块。然而，在这个模块内部，大多数计算任务是相互独立的。例如，确定一颗卫星的覆盖区域不依赖于对其他卫星的计算；同样，计算从一个地面站到另一个地面站的路由也独立于其他地面站对之间的路由计算。我们在LEOCraft [35]的实现中利用了这一点，其中每个组件（如卫星和地面站）都作为一个独立的模块运行，并通过格式受限的数据交换API进行交互。这使我们能够将工作负载均匀地分配到所有可用的CPU上，从而有效地将性能瓶颈从软件层面转移到底层硬件。

In Fig. 14, we represent LEOCraft’s simulation workflow. In LEOCraft LEO constellation builder creates a top-level instance of LEO constellation based on specified design parameters and GS locations. This LEO constellation instance consists of all LEO network component instances (GSes, satellites, and ISLs) in it. The LEO Constellation Simulator acts as an execution framework in LEOCraft. It accumulates LEO constellation instances in the Task queue and evaluates the given batch of instances in parallel. This parallelism is at the functional level across all the LEO constellation instances in the Task queue. For that, LEO Constellation Simulator creates a pool of worker processes corresponding to each available CPU [14]. These worker processes remain active for the entire duration of the simulation execution, thus minimizing process creation overhead too. Each worker receives data (instances of LEO network components) and function references, executes these functions on the data, and sends the results back to the respective LEO Constellation instance through the dispatcher. The LEO Constellation accumulates the results of each asynchronously called function. Once all the function calls return, it writes back the evaluation results. Then LEO Constellation Simulator removes the instance from the Task queue.

在图14中，我们展示了LEOCraft的模拟工作流程:

在LEOCraft中，LEO星座构建器根据指定的设计参数和地面站位置，创建一个顶层的LEO星座实例。这个LEO星座实例包含了所有的LEO网络组件实例（地面站、卫星和ISL）。

LEO星座模拟器在LEOCraft中充当执行框架。它将待处理的LEO星座实例累积到任务队列（Task queue）中，并并行地对这批实例进行评估。这种并行性是在任务队列中所有LEO星座实例之间的功能级别上实现的。

为此，LEO星座模拟器会为每个可用的CPU创建一个工作进程池[14]。这些工作进程在整个模拟执行期间保持活动状态，从而也最大限度地减少了进程创建的开销。每个工作进程接收数据（LEO网络组件的实例）和函数引用，对数据执行这些函数，然后通过分发器将结果发回给相应的LEO星座实例。LEO星座实例会累积每个异步调用的函数的结果。一旦所有的函数调用返回，它就会写回评估结果。随后，LEO星座模拟器将该实例从任务队列中移除。

This process-based concurrency [14] effectively bypasses the GIL [17], the primary performance bottleneck for CPUbound tasks, allowing uniform use of all CPUs even for a single LEO Constellation instance in the Task queue. As a result, LEOCraft evaluates a large constellation within a few minutes. For the interested readers, §A.5 provides an overview of LEOCraft APIs for simulating any LEO constellation.

这种基于进程的并发[14]机制有效地绕过了GIL[17]——这是CPU密集型任务的主要性能瓶颈——使得即使任务队列中只有一个LEO星座实例，也能均匀地使用所有CPU。因此，LEOCraft能够在几分钟内完成对一个大型星座的评估。对于感兴趣的读者，附录§A.5概述了用于模拟任何LEO星座的LEOCraft API。

Related work

Simulation and measurement: Several efforts [47,63,64,67, 68] have focused on creating simulation platforms for measuring LEO networks. Notable examples include Hypatia [64], StarryNet [67], and xeoverse [63], their strengths and limitations has been briefly discussed in §6. Additionally, [46] explores RTT fluctuation using intuitive mathematical modeling, avoiding resource-intensive simulations.

LEO topology: Most of recent studies [40,47,63,64,67,68, 92, 93] have widely adopted the +Grid topology as the de facto standard for LEO networks. In contrast, [45] proposed an improved ISL topology to minimize hand-offs and enhance throughput latency. Meanwhile, [72] highlighted the drawbacks of +Grid, advocating for ×Grid topology to reduce packet drops and hop counts. A recent study [92, 93] used Hypatia [64] to analyze single-shell LEO topologies with a limited set of design parameters. This work extends the analysis to all parameters, including multiple shells, optimizing satellite trajectories based on the traffic demand matrix between GSes.

模拟与测量： 已有多项工作[47, 63, 64, 67, 68]致力于创建用于测量LEO网络的模拟平台。其中著名的例子包括Hypatia [64]、StarryNet [67]和xeoverse [63]，它们的优缺点已在第6节中简要讨论。此外，文献[46]采用直观的数学建模方法来探索RTT（往返时延）波动，从而避免了资源密集型的模拟。

LEO拓扑结构： 近期的大多数研究[40, 47, 63, 64, 67, 68, 92, 93]已广泛采用 +Grid 拓扑作为LEO网络的事实标准。与此不同，文献[45]提出了一种改进的ISL（星间链路）拓扑，旨在最小化网络切换并提升吞吐量与延迟性能。同时，文献[72]指出了+Grid拓扑的缺点，并倡导使用 ×Grid 拓扑以减少丢包和跳数。最近的一项研究[92, 93]使用Hypatia [64]分析了仅包含有限设计参数的单壳层LEO拓扑。本项工作将该分析扩展至所有参数，涵盖了多个卫星壳层，并根据地面站之间的流量需求矩阵来优化卫星轨道。

Conclusion and future work

In this paper, we introduce LEOCraft [35], an open-source, modular, and scalable framework for evaluating and visualizing LEO constellations. LEOCraft analyzes high-dimensional search spaces to uncover the crux of LEO trajectory design that enables trimming of search space to optimize constellation design quicker. We also present findings on the performance gain for inter-shell ISL connectivity.

In the future, we plan to extend the LEOCraft towards topology and trajectory joint optimization [45,72]. While this work focuses on maximizing throughput, mega-constellation operators with humongous budgets often target diverse sectors. For instance, Starlink’s deployment of two polar-orbit shells improves connectivity in the polar region [27–29]. Additionally, seeks FCC approval for VLEO deployment to enable low-latency applications like fin-tech and gaming [16]. Optimizing mega constellations for multiple objectives presents another promising research direction.

在本文中，我们介绍了LEOCraft [35]，这是一个用于评估和可视化LEO星座的开源、模块化且可扩展的框架。LEOCraft通过分析高维搜索空间，揭示了LEO轨道设计的核心症结，从而能够削减搜索空间，更快速地优化星座设计。我们还展示了跨壳层ISL连接所带来的性能增益的发现。

未来，我们计划将LEOCraft扩展至拓扑与轨道的联合优化[45, 72]。虽然当前工作专注于最大化吞吐量，但拥有巨额预算的巨型星座运营商通常会瞄准多样化的应用领域。例如，Starlink部署了两个极地轨道壳层以改善极地地区的连接性[27-29]。

此外，它还在寻求FCC批准部署VLEO（极低地球轨道）星座，以支持金融科技和游戏等低延迟应用[16]。为多个目标优化巨型星座是另一个富有前景的研究方向。