Performance Evaluation

A. Experiment setup

We conduct experiments on the first orbital shell of Starlink and Kuiper respectively. Same as the experiment setup in III-C, we use +Grid to interconnect satellites and use the shortest path routing algorithm. Dataset A includes 8 GSes currently deployed by Amazon around the world (except GS in Stockholm which is not well covered by these constellations) [4]. These 8 GSes are distributed in North America, Asia, Europe, Oceania and America. The distance between these GS pairs is long, which is very suitable for using emerging LEO SNs to achieve low-latency communication. Dataset B, including 31 GSes distributed in the United States, Canada, Europe, Oceania and South America, is selected from the stations currently deployed and planned to be deployed by Starlink with the restriction that the distance between each two of them is more than 500km. For dataset A, we choose the case that there is communication demand between any GS pair, i.e., there are altogether 28 GS pairs, since these stations are almost separated by intercontinental and ocean. A recent study has shown LEO SNs can provide lower latency communications than any possible terrestrial optical fiber networks over distances greater than 3000km [28]. For dataset B, we then randomly select 126 GS pairs with their distance of more than 3000km and assume that there is communication demand between them. We use StarPerf [34] to simulate these constellations for 6000 seconds which exceeds their orbital period. We use python to implement four algorithms and conduct numerical simulation. To evaluate the packet delivery ratio between different GS pairs, we run the OSPF protocol under different satellite-ground topologies based on the network simulation tool mininet. We set the HELLO INTERVAL in OSPF to 0.2s and 5s. Although 0.2s is too frequent in the real environment, some studies have proposed prediction-based OSPF protocol especially for SNs [39], [48]. We simulate these optimized OSPF by reducing the HELLO INTERVAL.

好的，这是根据您提供的文本整理的实验相关配置表格。

实验配置汇总

Configuration	Setting
卫星星座	分别采用 Starlink 和 Kuiper 的第一个轨道壳层 (first orbital shell)
星间链路 (ISL) 拓扑	采用 +Grid 模型来互联卫星
核心路由算法	在仿真中计算路径时，采用最短路径路由算法 (shortest path routing)
数据集	数据集 A: \<br> • 来源: 亚马逊 (Amazon) 在全球部署的8个地面站(GS) [4]。 \<br> • 分布: 遍布北美、亚洲、欧洲、大洋洲和美洲，多为洲际和跨洋长距离。 \<br> • 通信对: 任意两个GS间都有通信需求，共计28个GS对。\<br>\<br>数据集 B: \<br> • 来源: 从Starlink已部署和计划部署的站点中选取31个GS。 \<br> • 约束: 任意两个GS之间的距离大于500km。 \<br> • 通信对: 随机选取126个距离大于3000km的GS对。
仿真工具	• 主要星座与算法仿真: StarPerf [34]。\<br> • 分组投递率测试: Mininet 网络模拟器。
仿真时长	6000秒 (超过了两个星座的轨道周期)。
算法实现	使用 Python 实现了文中所对比的四种算法。
网络可达性测试设置	• 协议: 在Mininet中运行 OSPF 协议来评估分组投递率。\<br> • 核心参数: 将OSPF的 HELLO INTERVAL 分别设置为 0.2秒 和 5秒。\<br> • 说明: 设置0.2秒是为了模拟针对卫星网络优化的、基于预测的OSPF协议 [39], [48]。

B. Experiment results

Satellite-Ground topology change interval of GS pairs. Figure 7(a) and (b) shows the distribution of satellite-ground topology change interval between 28 GS pairs and (c) and (d) shows the interval distribution between 126 GS pairs when using these four algorithms under Starlink and Kuiper. We observe LRST and CSGI attain longer topology change intervals than other two algorithms, and CSGI attains longer intervals than LRST in around 60 percent cases. In terms of the average topology change times between all GS pairs, CSGI reduces by 15% in Starlink and 33% in Kuiper, compared to LRST. The decrease of topology change times will reduce the recalculation of routing, thereby reducing the route calculation and communication overhead, and reducing the network convergence time. In addition, the satellite-ground topology change frequency of LRST is less in Kuiper, compared to Starlink. This is caused by the parameters of the constellation itself. Kuiper has higher orbital height and lower minimum elevation angle, thus its satellites have longer connection time with the GS. In light of this, we set different topology change interval threshold θ T for the two constellations, 150ms for Starlink and 250ms for Kuiper separately, to decrease the topology change frequency.

地面站对的星地拓扑变化间隔。 图7(a)和(b)展示了在Starlink和Kuiper星座下，使用四种算法时28个地面站（GS）对之间的星地拓扑变化间隔分布，(c)和(d)则展示了126个GS对的间隔分布。

我们观察到， LRST和CSGI获得了比另外两种算法更长的拓扑变化间隔 ，并且在约60%的情况下，CSGI的间隔比LRST更长。

就所有GS对的平均拓扑变化次数而言，与LRST相比，CSGI在Starlink中减少了15%，在Kuiper中减少了33%。 拓扑变化次数的减少将降低路由的重算频率，从而减少路由计算和通信开销，并缩短网络收敛时间。

此外， 与Starlink相比，LRST在Kuiper星座下的星地拓扑变化频率更低 。这是由星座本身的参数决定的。Kuiper具有更高的轨道高度和更低的最小仰角，因此其卫星与地面站的连接时间更长。

鉴于此，我们为这两个星座设置了不同的拓扑变化间隔阈值 \(\theta_T\)，分别为Starlink的150毫秒和Kuiper的250毫秒，以降低拓扑变化频率。

Network reachability. Figure 8 shows the average packet delivery ratio between GS pairs under four satellite-ground interconnection algorithms. The packet delivery ratio of NSD and NSH is both less than 40% when HELLO INTERVAL is set to 5s. Even the HELLO INTERVAL is reduced to 0.2s, their packet delivery ratio is less than 90%. LRST is the optimal scheme to make the satellite-ground topology stable for a single station, as it always selects the satellite with the longest service time. Therefore, it has natural advantages in network reachability. However, through wisely coordinating the establishment of GSLs among GSes, our algorithm CSGI further improves the network reachability which is higher than that of LRST in all cases we test. The packet delivery ratio of CSGI reaches 95.97% and 92.91% under Kuiper and Starlink respectively when HELLO INTERVAL is set to 0.2s. Similarly, the packet delivery ratio of these four algorithms under Kuiper is higher than that under Starlink.

网络可达性。 图8展示了四种星地互联算法下GS对之间的平均分组投递率。当HELLO间隔设置为5秒时，NSD和NSH的分组投递率均低于40%。即便将HELLO间隔缩短至0.2秒，它们的投递率也低于90%。

对于 单个站点而言，LRST是使星地拓扑最稳定的方案，因为它总是选择服务时间最长的卫星 。因此，它在网络可达性方面具有天然优势。

然而，通过 巧妙地协调各GS间的地星链路（GSLs）建立，我们的CSGI算法进一步提升了网络可达性，在我们测试的所有案例中均高于LRST 。当HELLO间隔为0.2秒时，CSGI在Kuiper和Starlink下的分组投递率分别达到了95.97%和92.91%。类似地，这四种算法在Kuiper下的分组投递率均高于Starlink下的表现。

HELLO_INTERVAL是什么

"HELLO INTERVAL" 是一个路由协议（如此处的OSPF）中用于探测网络链路状态的核心时间参数

(1) OSPF (开放最短路径优先协议): 这是一种非常主流的内部网关路由协议

网络中的路由器运行OSPF协议，互相“沟通”，最终目的是计算出到达网络中任何一个角落的“最短路径”，然后指导数据包如何转发

(2) HELLO 报文 (Hello Packet): 为了让OSPF正常工作，相互连接的路由器之间需要一种机制

• 发现邻居: “你好，我是路由器A，我在这个链路上，你听得到吗？”
• 维持邻居关系: 持续地发送“心跳包”，告诉对方“我还活着，链路一切正常”

这个 “心跳包” 就是 HELLO 报文

PS: 很显然这个 Hello_INTERVAL 是一个 trade-off

调整HELLO间隔，就是在“网络开销”和“收敛速度”之间做权衡

• INTERVAL 降低:
  • Cons: 能更快地发现链路故障
  • Pros: 网络开销太大, 更频繁的“心跳包”会占用更多的带宽和路由器CPU资源
• INTERVAL 升高:
  • 类比上面，反之即可

PDR (Packet Delivery Ratio)

分组投递率 是衡量网络性能的一个核心指标，它表示在网络通信中，成功从发送端传输到接收端的数据包（分组）占总发送数据包的比例

分组投递率 (PDR)= \(\frac{发送端发出的分组总数量}{接收端成功接收的分组数量​}\) × 100%

End-to-end latency and jitter. The average maximum hops between all GS pairs, i.e., the optimization objective in formula (1), and the average hops between GS pairs are shown in Table I. We use the hop count to reflect the endto-end latency, and use the difference between the average maximum hops and the average hops to reflect the jitter. We can observe that the average maximum hops and the average hops are similar when using NSH, NSD and LRST, and are much higher than those using CSGI. For example, the average maximum hops using CSGI is about 35% lower than the optimal results of the other three algorithms under Starlink and Kuiper in both datasets. Further, CSGI outperforms these algorithms with about 19% reduction of the one-way latency on average in all cases. We can also observe that the difference between the average maximum hops and the average hops of CSGI is much lower than that of other three algorithms. The average jitter (difference between the maximum and minimum latency between GS pair) of CSGI is only about 30% of other algorithms on average. We randomly select several GS pairs and plot their average one-way latency, minimum latency, and maximum latency under Starlink and Kuiper, as shown in Figure 9. Since the results of NSH and NSD are similar to LRST, only the results of LRST and CSGI are showed. Taking the GS pair of Bahrain and Ohio as an example, the one-way latency between them fluctuates in the range of under 50ms to 125ms using LRST, while it stabilizes at about 50ms using CSGI. The average latency between them using CSGI is almost half of that using LRST.

From experiment results above, CSGI reduces the topology change times and improves the network reachability, compared with the optimal results of related algorithms. While maintaining the highest packet delivery ratio, CSGI also outperforms other algorithms with about 35% reduction of the average maximum hops, 19% reduction of the average end-to-end latency and 70% reduction of the average jitter.

端到端时延与抖动。 表I展示了所有GS对之间的平均最大跳数（即公式(1)中的优化目标）和平均跳数。我们使用跳数来反映端到端时延，并使用平均最大跳数与平均跳数之差来反映抖动。

我们可以观察到，使用NSH、NSD和LRST时的平均最大跳数与平均跳数相近，但远高于使用CSGI时的数值。例如，在两个数据集中，CSGI在Starlink和Kuiper下的平均最大跳数均比其他三种算法的最优结果低约35%。此外，在所有案例中，CSGI的单向时延平均降低了约19%，性能优于其他算法。

我们还可以观察到，CSGI的平均最大跳数与平均跳数之差远小于其他三种算法。CSGI的平均抖动（GS对间最大与最小时延之差）平均仅为其他算法的约30%。如图9所示，我们随机选取了几个GS对，并绘制了它们在Starlink和Kuiper下的平均单向时延、最小时延和最大时延

由于NSH和NSD的结果与LRST相似，图中仅展示了LRST和CSGI的结果。以巴林和俄亥俄这对GS为例，使用LRST时，它们之间的单向时延在低于50毫秒到125毫秒的范围内波动，而使用CSGI时，则稳定在约50毫秒。它们之间使用CSGI的平均时延几乎是使用LRST时的一半

综上实验结果，与相关算法的最优结果相比，CSGI减少了拓扑变化次数并提升了网络可达性。在保持最高分组投递率的同时，CSGI在其他指标上也表现更优，平均最大跳数减少约35%，平均端到端时延降低约19%，平均抖动减小约70%