HYPATIA ARCHITECTURE¶
To address the urgent need for tools that enable research on LEO networks, we built Hypatia. Hypatia provides a packet-level simulator that incorporates LEO dynamics, and a visualization module to aid intuition. The packet simulator is implemented as a module for ns-3 [60]. It takes into account satellite trajectories, coverage constraints for GS-satellite connectivity, and the structure of intersatellite connectivity. It can be used to implement and evaluate novel ideas for satellite trajectory design, inter-satellite topology, routing, and congestion control. The visualization component uses Cesium [13] to render views of the trajectories, GS-perspective on overhead satellites, end-end routes, evolving link utilization, and available bandwidth on routes.
为了解决低地球轨道（LEO）网络研究中迫切需要的工具问题，我们开发了Hypatia。Hypatia提供了一个包级仿真器，能够模拟LEO网络的动态，并且包含一个可视化模块，以帮助用户直观理解。该包级仿真器作为ns-3的一个模块实现 [60]，能够考虑卫星轨迹、地面站（GS）与卫星之间的覆盖约束以及卫星间的互联结构。它可用于实现和评估卫星轨迹设计、卫星间拓扑、路由和拥塞控制等新颖的研究思路。可视化组件则使用Cesium [13]来渲染卫星轨迹、地面站视角下的卫星、端到端的路由、演变中的链路利用率以及路由上的可用带宽等信息。
Setting up a simulated LEO network¶
At its simplest, Hypatia allows users to specify satellite trajectory parameters and ground station locations. From these, it automatically generates the state of each satellite over time in a space-industry standard data format, the GS-satellite and ISL connectivity, and time-varying forwarding state that decides the paths packets take. We discuss what parts users need to modify for more complex simulations.
最简单的情况下，Hypatia允许用户指定卫星轨迹参数和地面站位置。基于这些输入，它会自动生成每颗卫星随时间变化的状态，采用航天工业标准的数据格式，同时生成地面站与卫星之间的连接、卫星间链路（ISL）连接，以及决定数据包传输路径的时间变化转发状态。我们将讨论用户需要修改哪些部分以进行更复杂的仿真。
TLE generation: A two-line element is a standard format for representing the trajectory of an Earth-orbiting object [41]. For existing satellites and orbital debris, NORAD [59] regularly publishes TLEs [42]. These TLEs are an input dependency for the satellite mobility model we build on. This arrangement has thus far sufficed for ns-3’s limited use in this setting: studying connectivity with one existing satellite.
TLE生成：双行元件（TLE）是一种标准格式，用于表示地球轨道物体的轨迹 [41]。对于现有卫星和轨道碎片，NORAD [59] 定期发布TLE数据 [42]。这些TLE数据是我们构建卫星运动模型的输入依赖项。对于ns-3在该环境下的有限应用（如研究与一颗现有卫星的连接性），这种安排已经足够。
However, this meant that we needed to ourselves generate TLEs for satellites that are not yet in orbit, but for which we know orbital parameters in terms of the Keplerian orbital elements [54] from the FCC or ITU filings made by the operators. Table. 1 shows the values we obtained from these filings. We only include a simplified subset of the parameters in the table; the remaining ones can be easily derived from the symmetries in play, e.g., only using circular orbits [47, 68], satellites in one orbit being uniformly spaced out, and orbits being uniformly spread across the Equator.
然而，这意味着我们需要为尚未入轨但我们已知轨道参数（以开普勒轨道元素 [54] 表示）的卫星生成TLE。这些轨道参数来源于FCC或ITU的运营商备案。表1展示了我们从这些备案中获得的参数值。表格中只列出了简化的参数子集，其余参数可以通过利用对称性轻松推导出来，例如：仅使用圆形轨道 [47, 68]、卫星在同一轨道上均匀分布，以及轨道均匀分布在赤道上。
We built a utility that accepts Keplerian orbital elements as input, and outputs TLEs in the WGS72 world geodetic system standard [25]. To test that the output TLEs specify the same constellation as the input Keplerian orbital elements, we use pyephem, a Python library that can generate constellations from either the Keplerian elements or TLEs.
我们构建了一个工具，接受开普勒轨道元素作为输入，并输出符合WGS72世界大地测量系统标准的TLE。为了验证输出的TLE是否与输入的开普勒轨道元素描述的星座一致，我们使用了pyephem，一个Python库，可以从开普勒元素或TLE生成星座。
ISL connectivity: Hypatia implements what we believe to be a reasonable pattern of connectivity between satellites, but modifying this to support arbitrary alternative interconnects is easy. Our default implementation draws on past literature in satellite networking, and information in the regulatory filings of the newly proposed constellations.
卫星间链路（ISL）连接：Hypatia实现了我们认为合理的卫星间连接模式，但修改它以支持任意的替代互连方式是容易的。我们默认的实现借鉴了卫星网络领域的过去文献，以及新提议星座的监管备案中的信息。
The proposed mega-constellations hint at building 4 ISLs per satellite. Starlink’s filings [68], for example, mention 4 siliconcarbide components, and as recent work [6, 29] notes, these are typically components for ISLs. We thus use 4 ISLs per satellite in our default implementation.
提议中的超大星座暗示每颗卫星需要构建4个卫星间链路。例如，Starlink的备案 [68] 提到4个碳化硅组件，正如最近的研究 [6, 29] 所指出的，这些通常是用于卫星间链路的组件。因此，我们在默认实现中为每颗卫星使用了4个卫星间链路。
Further, a large body of work in satellite networking indicates a typical connectivity pattern for a satellite with 4 ISLs: two links to the immediate neighbors in the orbit, and two links to satellites in adjacent orbits, forming a mesh-like network [20, 21, 29, 30, 45, 51, 52, 63, 64, 77]. Recent work [6] has called the resulting mesh-like connectivity “+Grid”. We use +Grid as the default ISL interconnect.
此外，大量关于卫星网络的研究表明，具有4个卫星间链路的卫星通常采用以下典型的连接模式：两个链路连接到轨道中的直接邻近卫星，另外两个链路连接到相邻轨道中的卫星，从而形成一个类似网格的网络 [20, 21, 29, 30, 45, 51, 52, 63, 64, 77]。最近的研究 [6] 将这种网格状连接称为“+Grid”。我们采用+Grid作为默认的卫星间链路互连模式。
Hypatia also supports constellations eschewing ISLs entirely [31]; experiments demonstrating this are included in Appendix A. Further, alternative ISL interconnects can be trivially supported in Hypatia, if they do not involve dynamic ISLs, i.e., with satellites connecting to different satellites over time. This is a realistic assumption in most cases: ISL setup times can be tens of seconds, so reconfiguring ISLs dynamically is avoided [6]. Nevertheless, if such dynamic connectivity is desired, it will require modifying Hypatia.
Hypatia还支持完全避免卫星间链路的星座 [31]；相关实验已在附录A中展示。此外，Hypatia可以轻松支持替代的卫星间链路互连方式，前提是这些方式不涉及动态卫星间链路，即卫星之间的连接在时间上是固定的。对于大多数情况来说，这是一个现实的假设：卫星间链路的建立时间可能长达几十秒，因此避免动态重新配置卫星间链路 [6]。然而，如果需要这种动态连接，则需要对Hypatia进行修改。
GS-satellite connectivity: We currently simulate only static GSes with multiple parabolic antennas, not user terminals with single phased-array antennas that can be mobile [38]. However, Hypatia can be easily extended to model such terminals. Hypatia inherits from ns-3 the ability to impose sophisticated models on the GSsatellite channel, e.g., for loss. Nevertheless, Hypatia’s current implementation makes several simplifying assumptions about the GS-satellite links:
地面站与卫星连接：目前我们仅模拟静态地面站（GS），这些地面站配备多个抛物面天线，而不是配备单一相控阵天线且可移动的用户终端 [38]。然而，Hypatia可以轻松扩展，以模拟此类终端。Hypatia继承了ns-3的能力，可以对地面站与卫星之间的信道施加复杂的模型，例如，用于丢包的模型。然而，Hypatia当前的实现对地面站与卫星链路做了若干简化假设：
• Hypatia supports multiple GSL (ground-satellite link) network devices per satellite and GS. As default in our experiments, we set one GSL network device for both satellites and ground stations. Each network device can send packets to any other GSL network device, as long as the forwarding plan allows it. Additional connectivity restrictions can be imposed, e.g., to restrict user terminals such that they can only connect to one satellite at a time.
• Hypatia支持每颗卫星和地面站（GS）多个地面站与卫星链路（GSL）网络设备。作为我们实验中的默认设置，我们为每颗卫星和地面站设置了一个GSL网络设备。每个网络设备可以将数据包发送到任何其他GSL网络设备，只要转发计划允许。可以施加额外的连接限制，例如限制用户终端只能与一颗卫星连接。
• Across satellites and ground stations, no connections interfere with each other. While this is a strong assumption, Starlink and Kuiper mention [47, 68] that frequency management will be software-defined and done online to optimize towards this goal.
• 在卫星和地面站之间，连接不会相互干扰。虽然这是一个较强的假设，但Starlink和Kuiper [47, 68] 提到，频率管理将通过软件定义并在线进行，以优化朝着这一目标发展。
• Each GS can be configured to either: (a) connect to multiple satellites; or (b) connect to its nearest satellite.
• 每个地面站可以配置为：（a）连接到多个卫星；或（b）连接到其最近的卫星。
• Since many loss-free handoff techniques are known for other mobile settings, when GS-Satellite connections are handed off, there is no loss. Hypatia delivers in-flight packets from the now out-of-reach satellite, while new packets stop arriving at it.
• 由于在其他移动场景中已知许多无损切换技术，当地面站与卫星之间的连接发生切换时，不会发生数据丢失。Hypatia会将飞行中的数据包从现在无法接触的卫星转发出来，同时停止从该卫星接收新的数据包。
We make these simplifications, which relax practical constraints and are favorable to LEO networks, for two reasons: (a) this framework suffices to draw out many of the challenges; and (b) doing anything else requires substantial design work that is not within our scope, e.g., frequency management for this setting will likely be studied extensively in future work, for which Hypatia can serve as a vehicle.
我们做出这些简化，放宽了实际约束，并且有利于低地球轨道（LEO）网络，主要出于两个原因：（a）该框架足以揭示许多挑战；（b）做出其他设计修改需要大量的设计工作，这超出了我们的研究范围。例如，频率管理在这一背景下可能会在未来的研究中得到广泛研究，Hypatia可以作为这一研究的工具。
Forwarding state: We compute the forwarding state of satellites and ground stations at a configurable time granularity, with the default being 100 ms. Note that this step converts what is necessarily a continuous process of satellite motion into discrete intervals where we check and update the forwarding state. In between these intervals, the latencies are correctly calculated based on satellite motion, but the paths being used may deviate from the shortest. We discuss the implications of this experimentally in §5.3.
转发状态：我们在可配置的时间粒度下计算卫星和地面站的转发状态，默认时间粒度为100毫秒。需要注意的是，这一步将卫星的连续运动过程转换为离散的时间间隔，在这些间隔内我们检查并更新转发状态。在这些间隔之间，延迟是基于卫星运动正确计算的，但所使用的路径可能偏离最短路径。我们将在第5.3节中实验性地讨论这一点的影响。
For every time interval, we use a networkx [58] module to generate the network graph, accounting for satellite positions and link lengths between satellites and to ground stations. On this graph, the forwarding state for each node can be calculated based on arbitrary routing strategies. Our current implementation simply uses shortest-path routing, computed with the Floyd-Warshall algorithm. The forwarding state changes are also added into ns-3’s discrete event queue: at the first time the event fires, it reads new forwarding state into static routing table entries, and then adds the next forwarding state change event at exactly the configured time interval. Any routing strategy implementable with static routes can be easily supported. This is also true for multi-path routing, but obviously, would require additional logic to be implemented for splitting traffic across these paths.
对于每个时间间隔，我们使用networkx [58] 模块生成网络图，考虑卫星的位置以及卫星与地面站之间的链路长度。在该图上，可以根据任意的路由策略计算每个节点的转发状态。我们当前的实现简单地使用最短路径路由，并通过Floyd-Warshall算法计算。在ns-3的离散事件队列中也加入了转发状态的变化：当事件首次触发时，它会将新的转发状态读取到静态路由表条目中，并在配置的时间间隔后添加下一个转发状态变化事件。任何可以通过静态路由实现的路由策略都可以轻松支持。这对于多路径路由也是适用的，但显然需要额外的逻辑来实现流量在这些路径之间的拆分。
这一段算法层面没太看懂
不要紧，先跳过，回头再看
Running packet-level simulations¶
The packet-level simulator can be used to run simulations of LEO satellite networks for arbitrary satellite trajectories, GS locations, routing, congestion control, and queuing. While the generated TLEs for satellites, and routing and forwarding states are pre-computed and fed to the simulator, it is responsible for simulating the mobility of satellites and thereby accounting for varying link latencies over time. For this purpose, we adapt an available ns-3 satellite mobility model [61]. While this model adds a 1-3 km error per day to satellite trajectories, this can be ignored safely for simulations that simulate less than a few hours, as the networking implications of these distances are minimal.
该包级仿真器可用于运行任意卫星轨迹、地面站位置、路由、拥塞控制和排队的低地球轨道（LEO）卫星网络仿真。尽管为卫星生成的TLE数据、路由和转发状态是预先计算并输入给仿真器的，但仿真器仍负责模拟卫星的运动，从而考虑链路延迟随时间变化的影响。为此，我们采用了一个现有的ns-3卫星运动模型 [61]。虽然该模型为卫星轨迹每天增加1-3公里的误差，但对于仿真时间少于几个小时的情况，这一误差可以安全忽略，因为这些距离对网络的影响可以忽略不计。
Post-processing and visualizations¶
Hypatia’s ns-3 module can simulate both UDP and TCP traffic and log the relevant metrics for each transport, including RTTs, congestion window, and application level flow progress over time. We use gnuplot to generate all plots included in this paper, and Cesium for visualizations. Cesium is a general-purpose 3D mapping library for Javascript. We extend it to render the following interactive visualizations, writing python code that takes the outputs of our simulations and generates the visual elements for Cesium to render.
• The satellite trajectories over time.
• The ground observer view over time, showing the satellites visible in the sky at different angles of elevation.
• Changes in end-end paths over time.
• Changes in link utilization and available bandwidth on an endend path over time.
Hypatia 的 ns-3 模块能够模拟 UDP 和 TCP 流量，并记录每种传输协议的相关指标，包括往返时延（RTT）、拥塞窗口和应用层流量进展等时间序列数据。我们使用 gnuplot 生成本文中的所有图表，使用 Cesium 进行可视化。Cesium 是一个通用的 3D 地图渲染库，基于 Javascript。我们对其进行了扩展，编写 Python 代码处理模拟结果并生成 Cesium 渲染所需的交互式可视化元素，具体包括：
• 卫星轨迹随时间的变化。
• 地面观测者视角随时间的变化，显示不同仰角下可见的卫星。
• 端到端路径随时间的变化。
• 端到端路径上链路利用率和可用带宽随时间的变化。
Simulator scalability¶
We briefly assess the scale at which Hypatia can run simulations in reasonable time. We use Kuiper’s K1 shell as the LEO network, and the 100 most populous cities as the GSes. The traffic is a random permutation between the GSes. We test both TCP and UDP traffic. For TCP, each GS-pair sends each other a long running TCP flow, and we calculate network-wide goodput as the total rate of all acknowledged data, counting only packet payloads and excluding headers. For UDP, each GS-pair sends each other constant-rate, paced UDP traffic at the line rate, and goodput is calculated as the total rate of network-wide payload arrivals. For both types of traffic, to control the traffic rate of the simulation, we vary the line rate of each network link, all assumed to be uniform; we test line rates of 1, 10, 25, 100 and 250 Mbit/s, and 1 and 10 Gbit/s. We run the simulations on a single core on a 2.26 Ghz Intel Xeon L5520.
我们简要评估了 Hypatia 在合理时间内运行仿真的规模。我们使用 Kuiper 的 K1 外壳作为低地球轨道（LEO）网络，并选取全球人口最多的 100 个城市作为地面站（GSes）。流量为 GSes 之间的随机排列。我们测试了 TCP 和 UDP 流量。对于 TCP，每对 GS 之间发送一个长期运行的 TCP 流量，并计算网络范围内的有效吞吐量（goodput），即所有确认数据的总速率，仅计算数据包有效负载，排除头部。对于 UDP，每对 GS 之间发送恒定速率、限速的 UDP 流量，速率为线路速率，goodput 计算为网络范围内有效负载到达的总速率。为了控制仿真中的流量速率，我们调整每个网络链路的线路速率，假设所有链路的速率一致；我们测试了 1、10、25、100 和 250 Mbit/s 以及 1 和 10 Gbit/s 的线路速率。所有仿真均在一颗 2.26 GHz Intel Xeon L5520 处理器的单核上运行。
We quantify ‘slowdown’: if Hypatia takes 𝑏 real seconds to simulate 𝑎 virtual seconds, slowdown is 𝑏 𝑎 . The results, shown in Fig. 2, allow an experimenter to directly answer the question: if I want to run the system at 𝐶 Gbit/s goodput and obtain data for 𝑎 virtual seconds, how long will it take? If slowdown for 𝑥-axis = 𝐶 is 𝑦 , then the answer is 𝑦 · 𝑎 seconds. The results show that, e.g., to simulate ∼10 Gbps network goodput for 10 virtual seconds, Hypatia would need ∼33 minutes for UDP traffic and ∼100 minutes for TCP. The goodput alone determines the slowdown 𝑏 𝑎 , implying a simple trade-off: given a fixed real time budget, 𝑏, one can either simulate at high goodput for a short virtual time, or simulate at lower goodput for a longer virtual time. For the same experiment setup in terms of a constellation and traffic matrix, setting the line-rate of links allows control over goodput (up to a point; as utilization increases, goodput plateaus even with increasing load).
我们量化了“慢化”：如果Hypatia需要 \(b\) 秒的真实时间来模拟 \(a\) 秒的虚拟时间，则慢化为 \(\frac{b}{a}\) 。
图2所示的结果允许实验者直接回答以下问题：如果我希望以 \(C\) Gbit/s的好效能（goodput）运行系统，并获得 \(a\) 秒的虚拟数据，那么需要多长时间？
如果在x轴上， \(C\) 的慢化为 \(y\) ，则答案是 \(y \cdot a\) 秒。结果显示，例如，要模拟大约10 Gbps的网络好效能，虚拟时间为10秒，Hypatia需要大约33分钟来处理UDP流量，而对于TCP流量则需要大约100分钟。
好效能本身决定了慢化比例 \(\frac{b}{a}\) ，从而形成一个简单的权衡：在固定的真实时间预算 \(b\) 下，实验者可以选择在较短的虚拟时间内模拟较高的好效能，或者在较长的虚拟时间内模拟较低的好效能。对于相同的实验设置（如星座和流量矩阵），设置链路的线路速率可以控制好效能（但有一定限制；随着利用率的增加，好效能会在负载增加时趋于平稳）。
The simulation is bottlenecked at per-packet event processing. As satellite network paths often comprise a large number of hops, each end-end packet delivery results in many more events than, e.g., for a data center network simulation. The satellite network’s scale is also not a significant factor, at least for tens of thousands of satellites; the simulation setup costs, which increase with network scale, are only incurred at the start, while the packet events dominate the real time incurred for simulation.
该仿真受限于每包事件处理的瓶颈。由于卫星网络路径通常包含大量的跳数，因此每个端到端数据包的传输会产生比 数据中心网络仿真 更多的事件。卫星网络的规模并不是一个显著因素，至少在数万个卫星的情况下，网络规模对仿真性能的影响较小；仿真设置成本虽然随着网络规模的增大而增加，但这些成本仅在开始时发生，而数据包事件则主导了仿真所需的实际时间。
We find that opportunities for speeding simulations up may be limited. Beyond ns-3’s per-packet processing time, Hypatia only adds a minor overhead for calculating the per-packet delay through the mobility model. Forwarding tables are pre-computed, and MAC tables are pre-filled to prevent ARP activity. We are exploring to what extent ns-3’s distributed mode affords speedup, but for a variety of use cases, Hypatia’s current simulation pace will suffice, as our later analysis shows.
我们发现，加速仿真的机会可能有限。除了ns-3的每包处理时间外，Hypatia仅为通过运动模型计算每包延迟增加了少量开销。转发表是预先计算的，MAC表也已预填充，以防止ARP活动。我们正在探索ns-3的分布式模式在多大程度上能够提供加速，但对于各种使用场景，Hypatia当前的仿真速度已足够，如我们后续的分析所示。