Minimum-hop Constellation Design for Low Earth Orbit Satellite Networks

Abstract

We consider a Low Earth Orbit (LEO) satellite network with each satellite capable of establishing inter-satellite link (ISL) connections for satellite-to-satellite communication. Since ISLs can be reoriented to change the topology, we optimize the topology to minimize the average shortest path length (ASPL). We characterize the optimal ASPL ISL topology in two families of topologies, 1) vertex-symmetric in which the ISL connections at a satellite node represent a motif that is repeated at all other satellite nodes, and 2) general regular topologies in which no such repeating pattern need exist. We establish ASPL lower bounds for both scenarios and show constructions for which they are achievable assuming each satellite makes 3 or 4 ISL connections. For the symmetric case, we show that the mesh grid is suboptimal in both ASPL and diameter. Additionally, we show there are constructions that maintain intra-orbital ISL connections while still achieving near-optimal ASPL performance. For the general case we show it is possible to construct networks with ASPL close to the general lower bound when the network is sufficiently dense. Simulation results show that for both scenarios, one can find topologies that are very close to the lower bounds as the network size scales.

Index Terms—Satellite networks, topology design, LEO, ISL

我们研究低地球轨道（LEO）卫星网络，其中每颗卫星均能建立星间链路（ISL）以进行卫星间通信。由于星间链路可以重新定向以改变网络拓扑，我们致力于优化拓扑结构，以最小化平均最短路径长度（ASPL）。我们在两类拓扑结构中对最优平均最短路径长度的星间链路拓扑进行了刻画：

1）顶点对称（vertex-symmetric）拓扑，其中每颗卫星节点的星间链路连接呈现为一种在所有其他卫星节点上重复的模式（motif）

2）一般正则（general regular）拓扑，其中无需存在此类重复模式

我们为这两种情景建立了平均最短路径长度的下界，并展示了当每颗卫星建立3或4条星间链路时，能够达到这些下界的网络构造。对于对称情景，我们证明了网格（mesh grid）拓扑在平均最短路径长度和网络直径（diameter）方面均非最优。此外，我们还证明了存在既能保持轨道内星间链路、又能实现近乎最优平均最短路径长度性能的网络构造。对于一般情景，我们表明，当网络足够密集时，可以构建出其平均最短路径长度接近一般下界的网络。

仿真结果表明，对于这两种情景，随着网络规模的扩大，我们都能找到与理论下界非常接近的拓扑结构。

Introduction

Network topology design is critical for ensuring optimal operation of satellite networks. Network operators have to design topologies to meet the stringent Quality of Service demands required for user traffic. For large satellite networks with thousands of satellite nodes, such as the proposed constellations for Starlink and Kuiper, topology design becomes even more critical for ensuring network operation can be done with as little overhead as possible, since deploying satellite systems is financially costly [1]. However, the introduction of high-bandwidth optical inter-satellite links (ISLs) for the space segment of the satellite network offers some topology design flexibility: since ISLs can be reoriented to establish a link between any two satellites within link range, the space-segment network topology can be reconfigured after deployment of the constellation. Given the freedom to choose from a large set of possible topologies, choosing the best network topology is desirable.

网络拓扑设计对于确保卫星网络的优化运行至关重要。网络运营商必须设计拓扑以满足用户流量所需的严苛服务质量（Quality of Service）要求。对于拥有数千个卫星节点的大型卫星网络，如规划中的星链（Starlink）和柯伊伯（Kuiper）星座，拓扑设计在确保网络以尽可能少的开销运行方面变得更为关键，因为部署卫星系统的财务成本极高[1]。然而，为卫星网络的空间段引入高带宽光纤星间链路（ISL）提供了一定的拓扑设计灵活性：由于星间链路可以重新定向，以在链路范围内的任意两颗卫星之间建立连接，因此空间段的网络拓扑可以在星座部署后进行重构。鉴于可以从大量可能的拓扑中进行选择，选出最佳的网络拓扑是十分必要的

Latency is a metric of paramount importance in satellite networks for users that need near real-time performance, such as those using the network for military applications or for commercial operations with strict time constraints such as high-frequency trading [2]. Many strategies exist for reducing or limiting network latency, such as routing for mitigating queueing backlog at forwarding satellite nodes [2], [3], and resource management strategies that guarantee particular quality of service criteria, including latency [4]. Even so, the topology strongly influences how routing schemes behave and how much overhead they incur; it also determines how much network capacity is available for resource management. The most direct effect a topology has on latency is the distance a packet travels.

对于需要近实时性能的用户，例如在军事应用或高频交易等有严格时间限制的商业操作中，延迟是一个至关重要的指标[2]。现有多种策略可用于减少或限制网络延迟，例如通过路由来减轻转发卫星节点的排队积压[2], [3]，以及保证包括延迟在内的特定服务质量标准的资源管理策略[4]。即便如此，拓扑结构强烈影响着路由方案的行为方式及产生的开销；它也决定了可用于资源管理的网络容量。拓扑对延迟最直接的影响是数据包传输的距离

A common metric for measuring distance is the average shortest path length (ASPL) of the network. The ASPL captures the distance a packet must travel on average through the network to reach its destination assuming a shortestpath routing scheme like Dijkstra’s Algorithm is used to choose the shortest network path. ASPL serves as a proxy for measuring latency, since each hop along the path in the network incurs delay and contributes to the latency. Other metrics exist for measuring latency, such as geographical distance and direct end-to-end latency probing, and have been well-studied in the literature [5], [6]. ASPL and its relation to average geographical path distance was studied in [7], which demonstrated there exists parameter settings for which the two metrics are equivalent. The geographical distance between satellite nodes is subject to change since LEO orbits are not geostationary. Therefore, a geographical distance-optimal topology can quickly become suboptimal for that metric, whereas the optimal ASPL topology would continue to be optimal as long as the set of visible satellites remains unchanged. In [5], delay probing is used to infer end-to-end latency caused by various sources of delay. While delay probing is appropriate for measuring latency in real-time, latency for topology design must be measured with respect to a larger timescale: probing packets traverse a satellite network on the order of milliseconds whereas topologies can only be reconfigured via ISLs on the order of minutes [8]. We therefore study the optimal design of satellite-to-satellite network topology with respect to the ASPL.

衡量距离的一个常用指标是网络的平均最短路径长度（ASPL）。

ASPL描述了假设使用像迪科斯彻（Dijkstra）算法这样的最短路径路由方案来选择网络路径时，一个数据包在网络中到达目的地平均需要经过的距离。ASPL可作为衡量延迟的代理指标，因为网络路径上的每一跳都会产生延迟并累加到总延迟中。存在其他衡量延迟的指标，如地理距离和直接的端到端延迟探测，这些已在文献中得到充分研究[5], [6]。ASPL及其与平均地理路径距离的关系在[7]中进行了研究，该研究表明在某些参数设置下，这两个指标是等价的。 由于低地球轨道（LEO）并非地球静止轨道，卫星节点间的地理距离会不断变化。因此，一个地理距离最优的拓扑很快就会在该指标下变为次优，而只要可见卫星的集合保持不变，ASPL最优的拓扑则将继续保持其最优性。 在[5]中，延迟探测被用来推断由各种延迟源引起的端到端延迟。虽然延迟探测适合实时测量延迟，但在拓扑设计中，必须在更大的时间尺度上衡量延迟：探测数据包以毫秒量级穿越卫星网络，而拓扑只能通过星间链路以分钟量级进行重构[8]。因此，我们研究面向ASPL的星对星网络拓扑优化设计。

There are several models for representing ISL networks in the literature, capturing aspects of the constellation that affect topology design, such as orbital parameters (altitude, degree of ascension), communication power budget, antenna design, and ISL setup time [1], [9], [10]. Many standard constellation designs exist such as the Walker Delta or Polar constellations, which can influence the choice of ISL topology [11]. In this paper, we assume the satellites’ positions are fixed, which is a common model in the literature [12]. We study ASPLoptimal topology design assuming each satellite node has 1 unit of traffic for every other node, and each satellite makes exactly ∆ ISL connections with other satellites. We represent the topology as a graph — with satellites as vertices and ISL connections as edges — and consider two broad topology design cases: vertex-symmetric topology design, and general regular topology design. Vertex-symmetric topologies can be expressed as a repeating motif in the network where connections between vertices follow the same pattern, such as the mesh grid [13], whereas general regular topologies need not exhibit such structure. There are distinct advantages to vertex-symmetric topologies, since the regular structure provides many alternative shortest paths between vertices and provides ease of management. But, as will be shown, imposing vertex symmetry on a network of size N can limit the ASPL performance to scale Θ( √ N), and improves to Θ(log N) without the symmetry condition. For each topology design case, we analyze the optimal ASPL topology assuming that the degree is 3 or 4, the latter a typical model in the literature and in practice [14], and the former a potentially more cost-effective alternative.

文献中有多种模型用于表示星间链路网络，这些模型捕捉了影响拓扑设计的星座各方面因素，例如轨道参数（高度、升交点经度）、通信功率预算、天线设计以及星间链路建立时间[1], [9], [10]。目前已存在如沃克三角（Walker Delta）或极地（Polar）星座等多种标准星座设计，这些设计可能影响星间链路拓扑的选择[11]。

在本文中，我们假设卫星的位置是固定的，这是文献中一种常见的模型[12]。我们研究在以下假设下的最优平均最短路径长度（ASPL-optimal）拓扑设计：每个卫星节点为其他所有节点提供单位流量，且每颗卫星恰好与其他卫星建立 Δ 条星间链路连接。

我们将此拓扑表示为一个图（graph）——其中卫星为顶点（vertices），星间链路连接为边（edges）——并考虑两种宽泛的拓扑设计情景：顶点对称（vertex-symmetric）拓扑设计与一般正则（general regular）拓扑设计。顶点对称拓扑可以表现为网络中一种重复的单元模式（motif），其中顶点间的连接遵循相同的范式，例如网格（mesh grid）结构[13]；而一般正则拓扑则无需呈现此类结构。顶点对称拓扑具有显著优势，因为其规则的结构为顶点之间提供了许多备选的最短路径，并带来了管理上的便捷性。但是，如下文所示，对一个规模为 N 的网络施加顶点对称性约束，会将其ASPL性能限制在 Θ(N​) 的量级；而若无此对称性条件，性能则可提升至 Θ(logN) 的量级。针对每种拓扑设计情景，我们都分析了当度（degree）为3或4时的最优ASPL拓扑。度为4是文献和实践中的典型模型[14]，而度为3则是一种可能更具成本效益的替代方案。

Our primary contributions in this paper are the following. We develop lower bounds for the vertex-symmetric case depending on whether the number of ISLs per satellite is even or odd valued. Next, we show that the mesh grid topology is suboptimal in both ASPL and graph diameter. We show the vertex-symmetric lower bounds are achievable for degree 3 and 4. In particular, we show that when the degree is 4 there exist topologies that meet the lower bound and are comparable in link range to that of the mesh grid. For the general regular case we develop a procedure that with high probability finds low-ASPL topologies that scale according to the general regular topology ASPL lower bound.

The remainder of the paper is organized as follows. In Section II we mathematically define the network model. In Section III we develop lower bounds for the vertex-symmetric design case when the degree is 3 and 4. In Section IV, we search for ASPL-optimal topologies for both design cases. In Section V we provide concluding remarks.

我们针对顶点对称情景，根据每颗卫星的星间链路数量为偶数或奇数，分别推导出了其性能下界。接下来，我们证明了网格拓扑在平均最短路径长度（ASPL）和图直径（graph diameter）两个指标上均为次优。我们证明了，当度为3和4时，顶点对称的下界是可达的。特别地，我们指出当度为4时，存在既能达到下界、又在链路距离（link range）上与网格拓扑相当的拓扑结构。对于一般正则情景，我们开发了一种规程（procedure），该规程能够以高概率找到低ASPL的拓扑，其性能尺度符合一般正则拓扑的ASPL下界。

本文的其余部分组织如下。第二节对网络模型进行数学定义。第三节为度为3和4时的顶点对称设计情景推导下界。第四节，我们为两种设计情景寻找ASPL最优的拓扑。第五节为本文的总结。

TL; DR

优化网络拓扑结构来最小化低地球轨道（LEO）卫星网络中的平均最短路径长度（ASPL, average shortest path length）

将卫星网络抽象为一个建立在二维环面（torus）上的图

将拓扑分成两类:

1. 顶点对称型: 每个卫星节点的连接模式都是相同的，如同一个“模体”（motif）在整个网络中重复
2. 通用正则拓扑: 放宽了对称性的严格约束，只要求每个卫星节点拥有相同数量（Δ）的连接

后续就是一系列数学建模和分析了...

1. 证明了广泛使用的网格（mesh grid）拓扑和蜂窝（honeycomb）拓扑在ASPL和网络直径方面是次优的
2. "平方根比例偏移":
   1. 针对顶点对称网络
   2. 通过在标准的网格连接基础上，为跨轨道平面的连接增加一个与 \(n_s​/n_o\) ​​成正比的“偏移量”，可以在保持轨道内链路稳定性的同时，显著提升网络性能
3. 为度为3和度为4的顶点对称网络推导出了全新的、明确的ASPL性能理论下界