Computing All-Pairs Shortest Communication Time Paths for Periodically Varying Satellite Networks

1

Computing All-Pairs Shortest Communication Time Paths for Periodically Varying Satellite Networks

arXiv:2610.17372v1 [cs.NI] 12 Oct 2026

Koushik Sinha Senior Member, IEEE, Dibakar Saha, Sai Puppala and Bhabani P. Sinha Fellow, IEEE Abstract—We address the problem of designing an efficient algorithm for computing the all-pairs shortest-time paths in time-varying networks, specifically targeting the dynamic topological characteristics of low earth orbit (LEO) satellite constellations. We model such temporal graphs as G = (V, Et ), where V = {1, 2, . . . , n} is the set of n vertices in the graph, and Et is the set of M time-varying edges considered over a total time window of size T = M τ , τ being the duration of each interval in that time window. For such a network, our algorithm finds the all-pair shortest paths in O(M 2 n3 )-time. A key advantage of our approach is its computational structure, which mirrors two matrix multiplication steps, first in the forward direction and then in the backward direction. This structure of the algorithm makes it exceptionally suitable for parallelization on SIMD architectures like GPUs, thereby offering a significant speedup over traditional shortest-path algorithms and enabling efficient, network-wide message routing in rapidly changing LEO satellite constellations. Index Terms—Temporal graphs, All-pairs shortest paths, Shortest distance path, Shortest time path, Satellite networks, LEO satellite constellations.

✦

1

I NTRODUCTION

W

E are witnessing an era of unprecedented expansion in satellite launches, with ambitious plans for multiorbit, mega-constellations of satellites in the coming decade, involving thousands of interconnected satellites spanning low earth orbit (LEO), medium earth orbit (MEO), and geostationary orbit (GEO). The future of connectivity is quite literally ascending into orbit, with LEO satellite megaconstellations projected to play a pivotal role in that transformation as inter-satellite links (ISLs) become increasingly central to constellation-wide routing and capacity management [1], [2]. With a significantly lower cost to build and launch compared to MEO and GEO satellites, LEO satellites are an extremely attractive proposition for future networks, especially in the context of 6G non-terrestrial networks (NTNs), as their shorter distances from the surface of the Earth translate to lower latency and higher link bandwidth [1]. As such, the concept of mega-constellations of LEO satellites for networking has gained significant traction in recent times, with major operators and programs advancing large-scale deployments and regulatory authorizations [3], [4], [5], [6]. The potential of such space-based networks extends far beyond just providing networking services — the ability to host in-orbit computing, thereby transitioning satellites into an integrated communication and computational fabric

•

Koushik Sinha and Sai Puppala are with the School of Computing, Southern Illinois University, Carbondale, USA. Dibakar Saha is with the Department of Computer Applications, National Institute of Technology Raipur, Chhattisgarh, India. Bhabani P Sinha is with the Department of Computer Science and Engineering, Sister Nivedita University, Kolkata, India E-mail: koushik.sinha@cs.siu.edu, dibakar.saha10@gmail.com, sai.puppala@siu.edu, sinha.bhabani@gmail.com

for offloading computation from terrestrial data centers [7]. In May 2025, China reported the launch of an initial set of satellites toward a space computing constellation for collaborative AI-oriented workloads [8]. Related plans have also been discussed publicly for India and Europe in the context of space-based computing and satellite-network capability roadmaps [9], [10]. Similarly, commercial providers have announced space and satellite cloud/edge offerings and supporting ground-to-space service infrastructure [11], [12], [13]. Considering the vast computational resources circling in orbit across the earth, such an in-orbit distributed or edge computing platform can host a myriad of applications, including disaster response, situational awareness for space traffic management, and onboard AI-based filtering and prioritization for Earth-observation data [7]. A key challenge in harnessing LEO satellite constellations for networking, or in-orbit computing, arises from the inherent temporal dynamics of LEO satellite networks. High-speed orbital motion induces time-varying ISL characteristics that lead to dynamic topology changes as satellites traverse deterministic orbital configurations. This predictability enables forward-looking planning and routing mechanisms that explicitly incorporate time dependence [2], [14]. By leveraging the predictable movement of satellites, the network topology for future time slots can be accurately forecasted, and such satellite networks can be represented naturally as time-evolving (temporal) graphs where edges appear and disappear over time [15], [16]. Such a temporal graph can be derived as an ordered list or a stream of timed events, such as additions or deletions of edges as connectivity becomes feasible or infeasible. Thus, the network’s operational time can be represented as a temporal graph consisting of several static graphs, or snapshots, that store the active edges for each time point in the

2

lifetime of the graph. While a static graph representation for a highly dynamic network topology scenario as encountered in satellite networks suffers from loss of topology-change information, a temporal graph representation with appropriate time granularity is able to capture the full dynamics of the satellite constellation [15]. 1.1

Basic Idea

We first illustrate the utility of temporal graphs for various application use-cases, followed by how our proposed allpairs shortest path algorithm can benefit space-based networking and computing. Furthermore, we often need to distinguish between the distance from a vertex p to another vertex q in terms of the number of traversed edges and the actual time taken to move from p to q . This is because one may have to wait at some intermediate vertex for a long time to get the proper connecting edge of the path from p to q . Accordingly, multiple temporal-path objectives are used in modern temporalgraph formulations, including shortest-duration (fastest), earliest-arrival, and shortest-length variants [17], [16], [18]. As in-orbit networking and computing becomes a reality, central to the viability of such an infrastructure is efficient computation of up-to-date knowledge of the temporal graph topology characteristics. Accordingly, the all-pairs shortest path algorithm (APSP) is an attractive candidate that can pre-calculate the shortest path between all pairs of routers. Results of APSP computation can be used to populate routing tables. As noted earlier, a temporal graph induced by satellites in LEO exhibits periodic structure at the orbit timescale; for example, representative LEO orbits such as the ISS complete one revolution in roughly ∼90 minutes, illustrating the short recurrence times that motivate orbitwindow precomputation. Thus, by executing a temporal all-pairs shortest path algorithm over snapshots captured over one (or multiple) orbital periods, one can pre-calculate temporal shortest paths between any pair of satellites. The resulting temporal shortest paths or routing tables can then be uploaded to the satellites from the ground stations so that whenever a communication request is generated, the appropriate temporal shortest path can be used for nearinstantaneous path determination. Moreover, in the event a satellite fails or an ISL’s properties change significantly, precomputing all-pair temporal shortest paths for contingency scenarios can allow the network to quickly reroute traffic and avoid significant overhead. 1.2

Our Contribution

This paper addresses the computation of the shortest time paths between all pairs of vertices in the temporal graph representation of satellite networks. We present an elegant approach for this purpose which essentially involves the multiplication of specific matrices at the core of our proposed algorithm. The rest of the paper is organized as follows: Section 2 presents a brief literature survey. In Section 3, we present the preliminaries and network model. Section 4 presents the methodology. Section 5 describes the proposed algorithm. We conclude with the areas of further exploration of this problem in Section 8.

2

R ELATED W ORK

Recent work has continued to expand the algorithmic toolkit for temporal-path problems beyond classical earliest-arrival formulations. Jin et al. [19] study enumerating temporal s–t paths under multiple constraints using temporal subgraph construction and pruning, highlighting the computational challenges created by time-order constraints and large search spaces. Jain and Sahni [18] provide polynomial-time shortest-path algorithms for interval temporal graphs, demonstrating that stronger temporal structure can yield tractable shortest-path computation beyond general contact-sequence models. Parallel and hardware-accelerated temporal-path computation has also advanced. Mithinti et al. [20] propose GPU-based parallel algorithms for the fastest-path-duration problem in temporal graphs, indicating that matrix-/scanlike temporal primitives can be mapped effectively to massively parallel architectures. Complementing this, Yu et al. [21] address the overhead of transforming temporal graphs into DAG-style representations for execution, proposing redundancy-aware GPU transformation that improves end-to-end performance of temporal analytics pipelines. These works collectively motivate designs that (i) preserve temporal feasibility exactly (e.g., run/interval constraints) and (ii) expose regular computation patterns suitable for acceleration. Beyond shortest-path computation, recent theoretical work has revisited periodicity and feasibility constraints that arise naturally in recurring systems. Klobas et al. [16] initiate the temporal-graph realization problem with respect to fastest-path durations, including the periodic setting. Their results reinforce that periodic temporal structure is both practically relevant and algorithmically nontrivial, motivating methods that exploit periodicity without collapsing dynamics into static aggregation. In parallel, broad surveys such as Longa et al. [15] summarize the state of temporal graph learning, emphasizing that temporal edges fundamentally change reachability and path semantics, and that realistic dynamic systems require time-aware modeling choices. For LEO mega-constellations, multiple recent studies focus on coping with topology dynamics, laser-ISL operational constraints, and scalable planning. Bhattacharjee et al. [22] consider on-demand routing when dynamic laser inter-satellite links incur non-negligible setup delays, presenting optimization and heuristic schemes evaluated on Starlink-like constellations. Ron et al. [14] propose a dynamic time-expanded-graph (DTEG) based approach for time-dependent topology optimization under multi-objective criteria (capacity, latency, churn), reflecting growing interest in explicitly time-dependent design objectives. At a higher planning layer, Cen et al. [2] introduce SatFlow, a scalable framework that jointly plans topology, traffic allocation, and terminal power allocation for megaconstellations, addressing both dynamics and operational cost at scale. Demand-aware topology design has also been explored in very recent work: Dehshali et al. [23] propose a traffic-driven heuristic (Starfield) to orient ISLs toward nonuniform demand patterns, reporting improvements over baseline topologies in packet-level simulation. Complementing routing and planning, linkconfiguration and feasibility modeling continues to evolve.

3

3

N ETWORK MODEL AND A SSUMPTIONS

This section introduces the basic preliminaries of the network model and the assumptions. 3.1

Preliminaries

We introduce a model of the temporal graph to be used for our later discussions, which is formulated around the concepts of time-varying connectivity in a temporal graph as given in [27], but with some modifications. The following components describe our model: 3.1.1 Temporal graph representation We denote a temporal graph as G = (V, Et ), where V = {1, 2, · · · , n} is the set of n vertices in the graph and Et is the set of time-varying edges considered over a time window of size T starting from time t = 0 to t = T . This time window of observation will be represented as W = [0, T ]. 3.1.2 Time Window In general, a temporal edge epq ∈ Et connecting two vertices p and q during this time window W will be represented by a tuple (p, q, [t1 , ∆t1 ], [t2 , ∆t2 ], · · · , [tk , ∆tk ]), where the vertices p and q are connected only during the non-overlapping time durations [ti , ti + ∆ti ], i = 1, 2, · · · , k with the time ordering of 0 ≤ t1 < t1 + ∆t1 < t2 < t2 + ∆t2 < · · · < tk < tk + ∆tk ≤ T . An example of such time-varying connections is shown by the horizontal line segments in Fig. 1 for k = 3. We refer to these time durations [ti , ti + ∆ti ], i = 1, 2, · · · , k as the connectivity durations for the vertices p and q during the observation window [0, T ], and denote these by CDpq [0, T ] or simply CDpq when the time window [0, T ] is implied from the context. 3.1.3 Time slots for each snapshot We divide the time window [0, T ] in equal intervals of time duration τ (refer to Fig. 1 for a diagrammatic representation), where a snapshot of the connectivity is taken during each such interval. Each interval’s length τ may be set to the

t1

epq

t2 t1 +∆t1

t3 t2 +∆t2

t3 +∆t3

connectivity

Ren et al. [24] study ISL allocation as a multi-objective optimization problem under dynamic topology and resource limits. At the physical-layer/network interface, Gioulis et al. [25] present a constellation-aware optical ISL model that evaluates power requirements across an orbital period, supporting more realistic feasibility constraints for temporal adjacency. Finally, learning-based routing in dynamic LEO settings has also gained traction; Riyad et al. [26] report Q-learning based routing over snapshotderived topologies, reflecting a trend toward adaptive routing under time-varying connectivity. Taken together, recent literature shows (i) renewed algorithmic attention to temporal shortest/fastest path computation and its acceleration, and (ii) rapidly growing interest in time-dependent routing/planning for LEO megaconstellations with laser ISLs. Our work targets the intersection of these themes by focusing on all-pairs shortest communication-time paths under discrete-time feasibility constraints, with an implementation structure intentionally aligned with parallelizable primitives.

0

τ 2τ 3τ 4τ 5τ 6τ 7τ 8τ 9τ 10τ = T time

Fig. 1. Connectivity durations of edge epq

most petite possible duration used to observe the graph’s time-varying nature with maximum temporal resolution. The exact value of τ may be chosen depending on the requirements of typical real-life applications, e.g., phone calls, email communications, etc., for which the temporal graph model will be used. Example 1. For example, the message transmission delay can Q be computed as D = B⇕ , where Q is the size of the message m and B is the bit rate of a channel in a particular band [28]. Therefore, consider a node vi starts the transmission of message m of size 10M B at a time slot t over GSM band 20M Hz . Then, 10 = 0.5 the communication latency can be computed as: D = 20 seconds. But in case the same message will be sent through GSM Band 10M Hz , then D will be D = 10 20 = 1 seconds. Hence, we consider the value of τ depending on the current availability of the channel bandwidth and the size of the message to be sent. In this example, τ will be set to one second, and for each second, we take the snapshot accordingly. We assume that T = M τ , so that there will be a total of M snapshots, numbered as 0, 1, 2, · · · , M − 1 taken during these M intervals [0, τ ], [τ, 2τ ], · · · , ...[(M − 1)τ, T ], respectively to provide the total connectivity information of every edge of the temporal graph during the time window [0, T ] under consideration. An interval I = j will refer to the time duration from jτ to (j + 1)τ . Two vertices p and q will be connected by an edge epq during the j th snapshot, j ∈ {0, 1, 2, · · · , M −1}, if there is a continuous connectivity of duration at least λτ (0 < λ < 1) during the interval [jτ, (j + 1)τ ] which also has a non-null intersection with at least one of the k connectivity durations [ti , ti +∆ti ], i = 1, 2, · · · , k of the vertices p and q . Note that, λ can be a priori fixed depending on the specific application requirements. 3.1.4

Connectivity String

The connectivity information during the time window [0, T ] from the vertex p to the vertex q of the temporal graph will then be represented by a binary string of length M , termed as the connectivity string, in which each bit corresponds to a

4

snapshot interval so that a bit will be set to 1 if the connectivity between p and q was there during the corresponding time interval, and set to 0, otherwise. Note that in each snapshot interval, if τ is greater or equal to a certain value, then only we consider the connection set the value 1. For example, considering the Example 1, if τ ≥ 1, then we set the bit value 1 other 0. This connectivity string from p to q during the time window [0, T ] will be denoted by CSpq [0, T ] or simply CSpq when the time window [0, T ] is implied from the context. We assume that every edge of the temporal graph is symmetric (undirected) and hence, CSpq [0, T ] = CSqp [0, T ]. Example 2. Referring to the timing diagram for connection as given in Fig. 1 with M = 10, the connectivity between the vertices p and q is expressed by the 10-bit binary string 1110110110 (the most significant bit corresponds to the snapshot interval [0, τ ] ). 3.2

Assumtions •

•

•

4

We assume that a finite amount of time is needed to traverse every edge in the path, and the snapshot interval τ is so small that this time to traverse an edge is always more than τ . Without loss of generality, we assume for simplicity that this time to traverse an edge can be expressed as some non-zero integral multiple of τ . During the whole time window [0, T ], the distance dpq from p to q , as well as the time tpq to traverse the edge epq from p to q (when it exists throughout the period tpq ) will be assumed to be constant. Given these information, it may be noted that when we start traversing the edge epq at any time during the interval I = j , i.e., during [jτ, (j + 1)τ ], this connecting edge epq must exist continuously during the interval [jτ, (j + tpq )τ ] for the completion of the traversal. A temporal graph will be represented by an n × n adjacency matrix A whose (p, q)th entry will be a 3tuple given as A(p, q) = (CSpq , dpq , tpq ).

M ETHODOLOGY

Consider a temporal path p1 p2 · · · pm from a vertex p1 to another vertex pm that exists in the temporal graph G = (V, Et ) during the time window W = [0, T ] under consideration. After reaching a vertex pj , j = 2, 3, · · · , m−1 along the path from the vertex pj−1 , a connection from pj to pj+1 following the trail should be continuously available (without any break) in any subsequent tpj pj+1 snapshot intervals. To satisfy this requirement, one may have to wait at the vertex pj for some time until the required connectivity to the vertex pj+1 is guaranteed. We illustrate this situation by the following example. Example 3. Consider a temporal graph with five vertices for which the vertex set is V = {1, 2, 3, 4, 5}. The connecting edges are time-varying in nature with the aggregated static graph as shown in Fig. 2 during an observation window [0, 10τ ]. The time varying nature of the connecting edges e12 , e23 , e14 , e43 , e25 , e35 and e45 are given by the following connectivity strings, each of length 10:

1

(8)

(4)

2

3

(6)

(5)

(4)

(10)

4

5 (15)

Fig. 2. Aggregated static graph for the example situation

T ime intervals (I) : 0 CS12 = 0 CS23 = 0 CS14 = 1 CS43 = 0 CS25 = 0 CS35 = 1 CS45 = 0

12 00 11 10 00 00 11 00

34 11 10 11 01 11 00 00

56 10 11 10 10 11 00 00

78 11 00 11 11 10 11 11

9 1 0 0 0 0 0 1

Let two time units (each unit is equal to the length of an interval) be needed to traverse any of these four edges, and we need to reach the vertex 3 from vertex 1. One possibility is that we start at interval I = 0 to reach vertex 4 traversing the edge e14 during the intervals 0 and 1, wait there for two time intervals and then traverse the edge e43 during the intervals 4 and 5. Thus, we reach vertex 3 at interval I = 5 and the total time of travel is 6 units. Another possibility is that we start from vertex 1 at interval I = 3, reach vertex 2 at interval I = 4, and then reach vertex 3 at I = 6. In this case, the total time of travel is only 4 units although the arrival time is at interval I = 6. Yet another possibility exists as follows : start from vertex 1 at interval I = 4 to reach vertex 4 at interval I = 5, wait at vertex 4 for one interval and then reach vertex 3 at I = 8, with a total travel time of 5 units. The first of these three schemes is an example for reaching vertex 3 from vertex 1 by following the earliest arrival time path, the second one is by following the fastest path or shortest time path, and the third one is by following the latest departure time path. If the distances between the vertices are given as d12 = 8, d23 = 4, d14 = 5, and d43 = 6 (shown in Fig. 2 as the labels of the corresponding edges), then the path 1-4-3 is the shortest distance path from vertex 1 to vertex 3. While traversing a path from p to q , we refer to the time of start from the initial vertex p of this path by the starting interval Ispq and the time of arrival at the final pq vertex q of the path by the finishing interval If . We pq pq pq represent this path by a 3-tuple (Is , If , pred ), where predpq is the predecessor vertex of q in the path. predpq will enable us to trace this path from p to q backward, starting from q . It may be noted that we would like to

5

explore all possible simple paths only (without containing any loops) between every pair of vertices. However, there may be more than one such possible paths with different values of predpq . Further, it may also be possible that with the same predpq , there may be different values of Ispq and/or Ifpq defining a path from p to q . We construct a path matrix P whose (p, q)th entry will contain information about all such possible contact periods and will be represented pq pq as (νpq , (Ispq [1], If [1], predpq [1]), (Ispq [2], If [2], predpq [2]), pq pq pq · · · , (Is [νpq ], If [νpq ], pred [νpq ])), where νpq is the number of possible paths from p to q , and the 3-tuple (Ispq [i], Ifpq [i], predpq [i]) contains information about the starting interval, finishing interval and the corresponding predecessor vertex of q in the ith path, 1 ≤ i ≤ νpq . As special cases, the entries of P (p, p), p ∈ V will be set to (0, (0, 0, 0)) and also when there will be no path from p to q , the entries of P (p, q) will be set to (0, (0, 0, ∞)). With the above idea, the path matrix P is first initialized based on 1-adjacency of the vertices, following the algorithm initialize path matrix as shown in Procedure 2. After that, to find the all-pairs shortest time paths, we would augment each entry of the path matrix with information about other possible contacts (as expressed through a 3pq tuple (Ispq [i], If [i], predpq [i])), if any, through more than one edge. Thus, the (p, q)th entry of P will finally contain information about all possible paths from p to q indicated pq by the νpq 3-tuples (Ispq [i], If [i], predpq [i]), 1 ≤ i ≤ νpq . Finally, from all these νpq tuples, the one with the minimum pq value of (If [i] − Ispq [i]) will be chosen as the path with the shortest time from p to q . To achieve the above objective of computing the final path matrix, we proceed as follows. Assume that we have already computed the contact information for a path from p to q with the corresponding entry in the path matrix P (p, q) pq as (Ispq [i], If [i], predpq [i]). Suppose, from the vertex q , we would now like to reach another vertex r adjacent to q where A(q, r) = (CSqr , dqr , tqr ). It will be possible to reach the pq vertex r from q if we find some j > If [i] such that there is ′ a run of 1 s of length tqr in CSqr starting from the interval j , i.e., CSqr [j] = CSqr [j + 1] = · · · = CSqr [j + tqr − 1] = 1, pq for some j > If [i]. Once such a run is found, the total time of traversal from p to r will be j + tqr − Ispq [i]. The start time and finish time from p to r through q will also be accordingly evaluated as Ispq [i] and j + tqr − 1, respectively and predpr [i] will be set to q . The corresponding 3-tuple (Ispq [i], j + tqr − 1, q) will then be inserted as a new 3-tuple in P (p, r) in the pr sorted order of (Ispr , If ) values provided there is no other pr existing 3-tuple with the same values of (Ispr , If ), to avoid duplicate entries which might be generated in the above process of finding the possible contacts. The above operation will be repeated with all the νpq pq tuples (Ispq [i], If [i], predpq [i]), 1 ≤ i ≤ νpq . Collectively, we denote all these operations symbolically by P (p, q)⊗A(q, r). The algorithm for computing P (p, q) ⊗ A(q, r) is presented in the form of update all possible contacts(A, P, p, r) as given in Procedure 3. With these preliminary ideas, we describe below an algorithm for computing all-pairs shortest time paths as described in the next section.

Procedure 1: f ind next run(A, P, q, r, start, f inish, f lag) Input: A, P, q, r, start, f inish, f lag Output: Updated start, f inish, f lag 1 count = 0; 2 f lag = 0; 3 j = start; // next run of length tqr or more 4 while j <= M AND f lag == 0 do 5 if CSqr [j] == 1 then 6 count + +; 7 if count == tqr // a run of length tqr just found 8 then 9 start = j − tqr + 1; 10 11 12 13 14 15 16 17

else if count ≥ tqr // a run of length tqr or greater is found then f lag = 1; f inish = j − 1; break; count = 0; j + +;

Procedure 2: initialize path matrix(A, P ) Input: Adjacency matrix A Output: Path matrix P 1 for p = 1 to n do 2 for r = 1 to n do 3 νpr = 0; 4 Ispr [1] = 0; 5 Ifpr [1] = 0; 6 if p == r // diagonal entry 7 then 8 predpr [1] = 0; 9 else // for non diagonal entry 10 predpr [1] = ∞; 11 start = 0; 12 f inish = 0; 13 k = 0; 14 while k < M − tpr do 15 f ind next run(A, P, p, r, start, f inish, f lag); // Execute Procedure 1 16 if f lag == 1 then 17 temp = start + tpr − 1; 18 while temp ≤ f inish do 19 k + +; 20 Ispr [k] = start; 21 Ifpr [k] = temp; 22 start + +; 23 temp + +; 24 25 26

νpr = k; for i = 1 to νpr do predpr [i] = p;

5 A LGORITHM FOR C OMPUTING S HORTEST T IME PATHS

ALL - PAIRS

All-pairs shortest paths in static graphs can be very conveniently computed in two steps of a modified matrix multiplication scheme as proposed by Hu [29]. Let D be the n × n distance matrix of the static graph in which the (p, q)th element dpq is set to the distance from the vertex p to vertex q . The concept given in [29] is to compute the product (in some sense) of the matrix D by itself (D × D) through in-place computation following some well-defined rules - i) an entry of the product matrix once evaluated will immediately replace the corresponding entry of only the left D matrix in the above multiplication process, ii) the entries of the product matrix are computed once through a forward multiplication process and then through a backward multi-

6

Procedure 3: update all possible contacts(A, P, p, r) Input: A, P, p, r Output: Updated P 1 for q = 1 to n do 2 if q ̸= r then 3 if νpq > 0 AND νqr > 0 then 4 k = 1; // k indicates the position of the interval in P (q, r) from left to right direction 5 m = νpr ; 6 while k ≤ νqr do // Looking for earliest connection interval in P (q, r) 7 f lag1 = 0; 8 j = νpq ; // j indicates the position of the interval in P (p, q) traversed from right to left in the list 9 while j ≥ 1 AND f lag1 == 0 do 10 if Isqr [k] > Ifpq [j] then 11 f lag2 = 0; 12 for i = 1 to m do // avoid duplicate entries and entries with larger duration for a given finish time interval pr 13 if If [i] == Ifqr [k] then 14 if Ispr [i] < Ispq [j] then 15 Ispr [i] = Ispq [j]; 16 predpr [i] = q ; f lag2 = 1;

17

else

18

f lag2 = 1;

19

if f lag2 == 0 then m + +; Ispr [m] = Ispq [j]; Ifpr [m] = Ifqr [k]; predpr [m] = q ; f lag1 = 1; Insert this entry (Ispr [m], Ifpr [m], predpr [m]) in P (p, r) in sorted order with respect to the finish time Ifpr [m];

20 21 22 23 24 25 26

27 28 29

j − −; k + +; νpr = m;

plication process. In the forward multiplication process, the entries of the product matrix are evaluated in row-major order from row 1 to row n, in each row from left to right. In the backward multiplication process, entries are evaluated from row n to row 1, in each row from right to left. To compute the all-pairs shortest time paths in a temporal graph, we adopt the basic concept of in-place ordered matrix multiplication in Hu’s algorithm mentioned above and introduce appropriate modifications on it to deal with the time-varying nature of the connecting edges. First, the matrix multiplication is equivalently replaced by an operation where, in computing an element of the product matrix, the multiplication of two elements of a matrix is replaced by ⊗ operation between P and A and second, the summation of these computed products is replaced by augmenting each of the (p, q)th entries, 1 ≤ p, q ≤ n of the product matrix with the newly generated 3-tuples containing information of additional contacts from p to q during the period under consideration. Finally, from each such (p, q)th entry of the product matrix, the 3-tuple with the minimum time between the start and finish intervals is chosen to find the shortest time path from p to q . Our proposed algorithm for computing all-pairs shortest time paths of a temporal graph is

shown in Algorithm 1, where we essentially perform the inplace computation of the path matrix P (p, r), 1 ≤ p, r ≤ n through a forward and backward process of this equivalent matrix multiplication operation. In this algorithm, we first initialize the path matrix P (p, r), 1 ≤ p, r ≤ n by executing Procedure 2. In this procedure, for each diagonal entry (p = r ), we initialize νpr = Ispr [1] = Ifpr [1] = predpr [1] = 0. For non diagonal entry (p ̸= r), we call f ind next run (Procedure 1) to find all the consecutive runs of length tpr from CSpr ∈ A, and set νpr = k , where k is the total number of runs of length tpr , 1 ≤ k ≤ M − tpr , and update all the entries Ispr [k], Ifpr [k], and predpr [k], accordingly. Once we initialize the path matrix P , we start the forward and backward process by executing update all possible contacts (Procedure 3). In this procedure, for each entry of P (p, r), we find all possible paths through the vertex q , 1 ≤ q ≤ n and q ̸= r, avoiding any duplicate entry ans also entries with pr larger duration for a given finish time interval If . After computing all the intervals of P (p, r), we call Procedure 4 to find the minimum time path among all the intervals in P (p, r). Finally, we set the interval number νpr = 1 and pr update Ispr [1], If [1], predpr [1] by the minimum time path accordingly. Thus, Algorithm 1 computes all-pairs shortest time communication paths in 6G networks based on temporal graph representation. Procedure 4: f ind minimum time path(P ) Input: P Output: Updated P 1 for p = 1 to n do 2 for r = 1 to n do 3 if νpr > 0 then 4 min time = Ifpr [1] − Ispr [1] + 1; 5 temp start = Ispr [1]; 6 temp f inish = Ifpr [1]; 7 temp predecessor = predpr [1]; 8 previous node = predpr [1]; 9 for j = 2 to νpr do 10 temp duration = Ifpr [j] − Ispr [j] + 1; 11 if temp duration < min time then 12 min time = tempd uration; 13 temp start = Ispr [j]; 14 temp f inish = Ifpr [j]; 15 temp predecessor = predpr [j]; νpr = 1; Ispr [1] = temp start; Ifpr [1] = temp f inish; predpr [1] = temp predecessor ;

16 17 18 19

Example 4. Consider again the graph used in Example 3 with the same connectivity strings. While executing Algorithm 1, the path matrix is initialized as follows: 1

0, (0, 0, 0)
2  0, (0, 0, ∞)
 0, (0, 0, ∞)
P = 3  4  0, (0, 0, ∞)
5 0, (0, 0, ∞) 1



2

3

4

0, (0, 0, ∞)
0, (0, 0, 0)
0, (0, 0, ∞)
0, (0, 0, ∞)
0, (0, 0, ∞)

0, (0, 0, ∞)
0, (0, 0, ∞)
0, (0, 0, 0)
0, (0, 0, ∞)
0, (0, 0, ∞)

0, (0, 0, ∞)
0, (0, 0, ∞)
0, (0, 0, ∞)
0, (0, 0, 0)
0, (0, 0, ∞)

5

 0, (0, 0, ∞)
0, (0, 0, ∞)
  0, (0, 0, ∞)
  0, (0, 0, ∞)
 0, (0, 0, 0)

After initialization, the entries of the path matrix P (p, q) are as follows:
P (1, 1) = 0, (0, 0, 0)
P (1, 2) = 4, (3, 4, 1)(4,
5, 1)(7, 8, 1)(8, 9, 1) P (1, 3) = 0, (0, 0, ∞)

7

Algorithm 1: all pair shortest time paths(A, P ) Input: Adjacency matrix A Output: Path matrix P // Initialize path matrix with 1-adjacent information: 1 initialize path matrix(A, P ) ; // Execute Procedure 2 // Forward: 2 for p = 1 to n do 3 for r = 1 to n do 4 if p ̸= r then 5 update all possible contacts(A, P, p, r); // Execute Procedure 3 // Backward: for p = n to 1 do 7 for r = n to 1 do 8 if p ̸= r then 9 update all possible contacts(A, P, p, r); // Execute Procedure 3

P (4, 2) = P (4, 3) = P (4, 4) = P (4, 5) = P (5, 1) = P (5, 2) = P (5, 3) = P (5, 4) = P (5, 5) =

1, (0, 4, 1)
2, (4, 5, 4)(7,
8, 4) 0, (0, 0, 0)
2, (7, 8, 4)(8,
9, 4) 1, (5, 8, 2)
4, (3, 4, 5)(4, 5, 5)(5, 6, 5)(6,
7, 5) 3, (0, 1, 5)(1, 2, 5)(7,
8, 5) 2, (7, 8, 5)(8, 9, 5)
0, (0, 0, 0)

6

// Compute shortest time path for each P (p, q) from all its contacts 10 f ind minimum time path(P ); // Execute Procedure 4

P (1, 4) = P (1, 5) = P (2, 1) = P (2, 2) = P (2, 3) = P (2, 4) = P (2, 5) = P (3, 1) = P (3, 2) = P (3, 3) = P (3, 4) = P (3, 5) = P (4, 1) = P (4, 2) = P (4, 3) = P (4, 4) = P (4, 5) = P (5, 1) = P (5, 2) = P (5, 3) = P (5, 4) = P (5, 5) =

4, (0, 1, 1)(3,
4, 1)(4, 5, 1)(7, 8, 1) 0, (0, 0, ∞)
4, (3, 4, 2)(4,
5, 2)(7, 8, 2)(8, 9, 2) 0, (0, 0, 0)
3, (1, 2, 2)(2,
3, 2)(5, 6, 2) 0, (0, 0, ∞)
4, (3, 4, 2)(4,
5, 2)(5, 6, 2)(6, 7, 2) 0, (0, 0, ∞)
3, (1, 2, 3)(2,
3, 3)(5, 6, 3) 0, (0, 0, 0)
2, (4, 5, 3)(7, 8, 3)
3, (0, 1, 3)(1, 2, 3)(7, 8, 3)
4, (0, 1, 4)(3,
4, 4)(4, 5, 4)(7, 8, 4) 0, (0, 0, ∞)
2, (4, 5, 4)(7,
8, 4) 0, (0, 0, 0)
2, (7, 8, 4)(8,
9, 4) 0, (0, 0, ∞)
4, (3, 4, 5)(4, 5, 5)(5, 6, 5)(6,
7, 5) 3, (0, 1, 5)(1, 2, 5)(7,
8, 5) 2, (7, 8, 5)(8, 9, 5)
0, (0, 0, 0)

After the Backward step, the path matrix P (p, q) is changed as follows:
P (1, 1) = 0, (0, 0, 0)
P (1, 2) = 4, (3, 4, 1)(4,
5, 1)(7, 8, 1)(8, 9, 1) P (1, 3) = 1, (3, 6, 2)
P (1, 4) = 4, (0, 1, 1)(3,
4, 1)(4, 5, 1)(7, 8, 1) P (1, 5) = 1, (3, 6, 2)
P (2, 1) = 4, (3, 4, 2)(4,
5, 2)(7, 8, 2)(8, 9, 2) P (2, 2) = 0, (0, 0, 0)
P (2, 3) = 3, (1, 2, 2)(2,
3, 2)(5, 6, 2) P (2, 4) = 1, (5, 8, 3)
P (2, 5) = 4, (3, 4, 2)(4,
5, 2)(5, 6, 2)(6, 7, 2) P (3, 1) = 1, (1, 4, 2)
P (3, 2) = 3, (1, 2, 3)(2,
3, 3)(5, 6, 3) P (3, 3) = 0, (0, 0, 0)
P (3, 4) = 2, (4, 5, 3)(7, 8, 3)
P (3, 5) = 3, (0, 1, 3)(1, 2, 3)(7, 8, 3)
P (4, 1) = 4, (0, 1, 4)(3,
4, 4)(4, 5, 4)(7, 8, 4) P (4, 2) = 1, (0, 4, 1)
P (4, 3) = 2, (4, 5, 4)(7,
8, 4) P (4, 4) = 0, (0, 0, 0)
P (4, 5) = 2, (7, 8, 4)(8,
9, 4) P (5, 1) = 1, (5, 8, 2)
P (5, 2) = 4, (3, 4, 5)(4, 5, 5)(5, 6, 5)(6,
7, 5) P (5, 3) = 3, (0, 1, 5)(1, 2, 5)(7,
8, 5) P (5, 4) = 2, (7, 8, 5)(8, 9, 5)
P (5, 5) = 0, (0, 0, 0) The final entries in path matrix P are as follows: 1

After the Forward step, the path matrix P (p, q) is changed as follows:
P (1, 1) = 0, (0, 0, 0)
P (1, 2) = 4, (3, 4, 1)(4,
5, 1)(7, 8, 1)(8, 9, 1) P (1, 3) = 1, (3, 6, 2)
P (1, 4) = 4, (0, 1, 1)(3,
4, 1)(4, 5, 1)(7, 8, 1) P (1, 5) = 1, (3, 6, 2)
P (2, 1) = 4, (3, 4, 2)(4,
5, 2)(7, 8, 2)(8, 9, 2) P (2, 2) = 0, (0, 0, 0)
P (2, 3) = 3, (1, 2, 2)(2,
3, 2)(5, 6, 2) P (2, 4) = 1, (5, 8, 3)
P (2, 5) = 4, (3, 4, 2)(4,
5, 2)(5, 6, 2)(6, 7, 2) P (3, 1) = 1, (1, 4, 2)
P (3, 2) = 3, (1, 2, 3)(2,
3, 3)(5, 6, 3) P (3, 3) = 0, (0, 0, 0)
P (3, 4) = 2, (4, 5, 3)(7, 8, 3)
P (3, 5) = 3, (0, 1, 3)(1, 2, 3)(7, 8, 3)
P (4, 1) = 4, (0, 1, 4)(3, 4, 4)(4, 5, 4)(7, 8, 4)

2

3

4

5

 (0, 0, 0) (3, 4, 1) (3, 6, 2) (0, 1, 1) (3, 6, 2) 2  (3, 4, 2) (0, 0, 0) (1, 2, 2) (5, 8, 3) (3, 4, 2)     P = 3  (1, 4, 2) (1, 2, 3) (0, 0, 0) (4, 5, 3) (0, 1, 3)  4  (0, 1, 4) (0, 4, 1) (4, 5, 4) (0, 0, 0) (7, 8, 4)  5 (5, 8, 2) (3, 4, 5) (0, 1, 5) (7, 8, 5) (0, 0, 0) 1

5.1



Proof of Correctness

To show that Algorithm 1 computes the all-pairs shortest time paths correctly, we must ensure that while computing the shortest time path from a given vertex p to another vertex r through a vertex q , we use all possible paths from p to q , and also all possible paths from q to r, for all values of q . To prove that this condition is satisfied by executing the forward process followed by the backward process in the algorithm, we proceed as follows. We denote the (p, q)th entry of the path matrix P after executing the forward process and the backward process by P F (p, q) and P B (p, q), respectively. We say that an entry P F (i, j) ¡ P F (k, l) if P F (i, j) is calculated before P F (k, l)

8

3

2

Proof. Let pj be the minimum of all vertices p1 , p2 , · · · , pk in the valley sequence. Then the sequence from p1 to pj will be a downward sequence and that from pj to pk will be an upward sequence. By Lemma 1, P F (p1 , pj ) will be computed in the forward process. Further, we note that during the forward process, P F (p1 , pj ) < P F (p1 , pj+1 ) < · · · < P F (p1 , pk ). Hence the proof.

1

p1

p2

p3

p4

pk

(a) Upward sequence

p1

p2

pk−3

pk−2

pk

pk−1 1 2

3 (b) Downward sequence Fig. 3. Computation order of the elements of path matrix

in the forward process, and similarly, P B (i, j) ¡ P B (k, l) if P B (i, j) is calculated before P B (k, l) in the backward process. A vertex in a path is said to be a minimum vertex if it is less than its predecessor and successor vertices in the path. A sequence of vertices p1 , p2 , · · · , pk in a path is said to form i) an upward sequence if p1 < p2 < · · · < pk , ii) a downward sequence if p1 > p2 > · · · > pk , and iii) a valley sequence if there is only one minimum vertex in the sequence and min(p1 , pk ) > maxj (pj ), j = 2, 3, · · · , k − 1. We now have the following lemma. Lemma 1. If the vertices which are in a shortest time path p1 p2 · · · pk from a vertex p1 to a vertex pk form an upward sequence or a downward sequence, then this shortest time path from p1 to pk will be computed in the forward process of Algorithm 1. Proof. If the vertices in order as in the path form an upward sequence, then p1 < p2 < · · · < pk . Hence, in the forward process, P F (p1 , p2 ) is computed first with the direct edge from p1 to p2 in the initialization phase itself. Then P F (p1 , p3 ) is computed with the value of P F (p1 , p2 ) and the direct edge from p2 to p3 by the operation P F (p1 , p2 ) ⊗ P (p2 , p3 ). Next, P F (p1 , p4 ) will assume the final value from the operation P F (p1 , p3 ) ⊗ P (p3 , p4 ), and so on to get the order of computation as P F (p1 , p2 ) < P F (p1 , p3 ) < P F (p1 , p4 ) < · < P F (p1 , pk ) during the forward process itself. This fact is pictorially represented in Fig. 3(a) where the labels on dotted lines show the steps of computation and the solid lines show the availability of connecting edges during the time window under consideration. Similarly, if the vertices in the shortest time path p1 p2 · · · pk form a downward sequence, then p1 > p2 > · · · > pk . Thus, P F (pk−1 , pk ) is computed first with the direct edge from pk−1 to pk , then P F (pk−2 , pk ) is computed using this value of P F (pk−1 , pk ) by the operation P F (pk−1 , pk ) ⊗ P (pk−2 , pk−1 ), and so on to get the order of computation as P F (pk−1 , pk ) < P F (pk−2 , pk ) < · · · < P F (p2 , pk ) < P F (p1 , pk ) in the forward process itself. Fig. 3(b) pictorially represents this order of computation in the forward process corresponding to the upward sequence p1 > p2 > · · · > pk of vertices in the path. Lemma 2. If the vertices in a shortest time path p1 p2 · · · pk from a vertex p1 to a vertex pk form a valley sequence, then this shortest time path will be computed in the forward process of Algorithm 1.

For an arbitrary sequence of vertices in a shortest time path p1 p2 · · · pk from a vertex p1 to a vertex pk , if there are multiple valley sequences within the sequence p1 , p2 , · · · , pk , then each such valley sequence, say ps , ps+1 , · · · , pt , the shortest time path from ps to pt will be computed in the forward process by virtue of Lemma 2. Let us delete all vertices in between ps and pt (keeping only ps and pt ) in the sequence and repeat this step for each such valley sequence in succession. If a new valley sequence is formed after this deletion process, then also the process is repeated to delete all intermediate vertices within such a valley sequence. Note that in every instance of such a valley sequence, the portion of the shortest time path p1 p2 · · · pk formed with the vertices of the valley sequence will be computed by virtue of Lemma 2. After such deletion process, eventually we will be left out with either i) an upward sequence, or ii) a downward sequence or ii) an upward sequence followed by a downward sequence. If the resulting reduced sequence is an upward or a downward sequence, the shortest time path with these vertices in the reduced sequence will be computed by virtue of Lemma 1. We now have the following lemma. Lemma 3. If the vertices in a shortest time path p1 p2 · · · pk from p1 to pk form an upward sequence followed by a downward sequence, then this shortest time path will be computed by the backward process of Algorithm 1. Proof. Assume that the vertex pj is maximum of all vertices p1 , p2 , · · · , pk in the path. Hence, p1 < p2 < · · · < pj . From the order of execution of loops in the backward process, we get, P B (pj−1 , pj ) < P B (pj−2 , pj ) < P B (pj−3 , pj ) < · · · < P B (p1 , pj ). Thus the upward section of the shortest time path is computed in the backward process. Likewise, since pj > pj+1 > · · · > pk , we get, P B (pj , pj+1 ) < P B (pj , pj+2 ) < · · · < P B (pj , pk ), i.e., the downward section of the shortest time path is also computed in the backward process. We further note that the computation order in the backward process leads us to the following result: P B (p1 , pj ) < P B (p1 , pj+1 ) < P B (p1 , pj+2 ) < · · · < P B (p1 , pk ). Hence the proof. All these discussions lead to the following result : Theorem 1. Algorithm 1 correctly computes the all-pairs shortest time paths in a temporal graph. 5.2

Time Complexity

Procedure f ind next run needs at most O(M ) steps of comparisons. However, the two while-loops in initialize path matrix together with the procedure f ind next run can take only O(M ) time as the contacts from a vertex p to a vertex q are determined in ascending order of the intervals 0 through M −1. Hence, the amortized time required by the procedure initialize path matrix

9

is O(M n2 ). The loop in lines 11-19 in the procedure update all possible contacts ensures that there cannot be more than one 3-tuple in P (p, r) with a given value pq of If . Thus, the total number of 3-tuples in any entry P (p, q) or P (q, r) of the path matrix is always less than or equal to M . Also, while entering any new entry (3-tuple (Ispq , Ifpq , predpq )) in the path matrix (line 26), we need to search the existing 3-tuples (which are arranged in a sorted pq increasing order of If ), for inserting the new element in its correct position in this sorted list as in binary insertion sort. This step would need O(M ) time. Hence, each call to the procedure update all possible contacts in the forward as well as backward steps requires O(M 2 ) time. Thus each of forward and backward steps needs O(M 2 n3 ) time. The procedure find minimum time path needs O(M n2 ) time. Hence, we get the following result. Theorem 2. Algorithm 1 requires O(M 2 n3 ) time complexity to compute the all-pairs shortest time paths in a temporal graph.

6

E XPERIMENTAL S ETUP

This section describes the experimental design in a way that directly validates the modeling choices and algorithmic primitives introduced in Sections 3 and 4. In particular, we validate: (i) snapshot-based temporal discretization and the construction of connectivity strings CSpq ; (ii) the run-length feasibility constraint of length tpq used by Procedure 1; (iii) correctness of the path-matrix updates (Procedure 3) relative to trusted baselines; (iv) the necessity of the forward and backward passes in Algorithm 1; and (v) the computational scaling behavior implied by Theorem 2. We also quantify the network-level implications of optical range constraints and waiting-vs-traversal behavior that are unique to temporal routing. 6.1

Experimental Goals and What We Validate

The experiments are organized around four validation questions that map one-to-one to the methodology: 1)

2)

3)

4)

Temporal-graph validity: Does the snapshot construction produce meaningful time-varying adjacency consistent with LEO geometry, and does the resulting CSpq capture periodic contact patterns over one orbit? Run-length feasibility validity: Do run-length requirements (Procedure 1) correctly enforce the model assumption that a hop (p, q) is traversable only when CSpq contains a contiguous run of ones of length ≥ tpq after packet arrival? Algorithmic correctness validity: Does Algorithm 1 compute the same shortest communication-time outcomes as baselines that are known-correct (timeexpanded graph shortest paths, and temporal Dijkstra-like methods) on problem sizes where those baselines are feasible? Computational scaling validity: Do runtime and memory scale with (n, M ) in a way consistent with Theorem 2, and does the matrix-style update structure admit practical acceleration via data-parallel kernels (bit operations and batched run detection)?

We report both algorithmic metrics (runtime/memory/scaling and baseline agreement) and network metrics (reachability, shortest communication time, hop count, and waiting fraction). 6.2 Observation Window and Snapshot Discretization (T, M, τ ) As described in the methodology, we represent the network as a temporal graph over an observation window W = [0, T ] divided into M snapshots of duration τ such that T = M τ . For LEO constellations, the topology is strongly periodic due to deterministic orbital dynamics. Therefore, we choose T to span approximately one orbital period, so that the temporal graph contains a full recurrence of link formation and dissolution. In the main experiments we use a nominal orbital period of Porb = 96 minutes (LEO-like), and perform sensitivity checks for Porb ∈ [90, 128] minutes. For each τ we set   Porb M= , (1) τ and sweep temporal resolution using

τ ∈ {5, 10, 20} s.

(2)

For Porb = 96 minutes this yields M = {1152, 576, 288} snapshots. Discretization validity check. To validate that the snapshot durations are fine-grained enough for contact modeling, we measure (i) snapshot-wise average degree over time (Fig. 7), and (ii) link-run statistics derived from CSpq (Table 6). The goal is to ensure that observed connectivity is not an artifact of overly coarse sampling (missing short contacts) or overly fine sampling (inflating M without changing routing outcomes). 6.3

Constellation Mobility and Link Feasibility Model

Satellite positions are computed using deterministic Keplerian orbit propagation. This guarantees that the induced temporal graph is structured and periodic, which is central to our motivation for precomputation over one orbit. At each snapshot index j ∈ {1, . . . , M }, an optical ISL between satellites (p, q) is declared feasible if

dpq (j) ≤ R,

(3)

where dpq (j) is the inter-satellite distance at snapshot j , and R is the optical range threshold. We evaluate

R ∈ {659, 1319, 1500, 1700} km.

(4)

For each (p, q) we construct the connectivity string (R) CSpq [j] = ⊮{dpq (j) ≤ R},

(5)

which matches the connectivity-string definition in Section 3. This binary string is the primitive consumed by Procedure 1 for finding the next contiguous run of ones. Because temporal routing depends on when neighbors appear and disappear, we validate the time-varying adjacency behavior using a node-centric storyboard across consecutive snapshots. Figures 4 and 5 show a focus satellite

10

and its incident edges in a local neighborhood over four successive snapshots. We quantify the churn using neighborset persistence, Jaccard similarity, and turnover (Table 4). This validates that the topology evolves substantially within one orbit and that static aggregation would be misleading, motivating the temporal model. 6.4 Traversal-Time Requirement and Run-Length Feasibility As assumed in the methodology, traversing an edge is not instantaneous and requires tpq snapshot units; therefore, a hop (p, q) is admissible only if a contiguous run of ones of length at least tpq exists in CSpq starting after the packet arrives at p. This is exactly the rule enforced by Procedure 1. In the main results we use a conservative baseline tpq = 2 snapshots for all feasible links, capturing non-propagation effects such as pointing/acquisition, scheduling, buffering, and framing overhead. We also perform sensitivity checks with tpq ∈ {1, 2} to quantify how stricter run requirements affect reachability and waiting. To validate that run structure is the mechanism that drives waiting, we visualize feasibility timelines using a connectivity-string heatmap for a focus satellite and its neighbors (Fig. 6). We then compute standard run-length features (Table 6), including duty cycle, run-length percentiles, and gap-length percentiles. These metrics link directly to Procedure 1: shorter runs and longer gaps increase the frequency with which the algorithm must search forward in time to find the next feasible transmission window. 6.5 Algorithmic Evaluation: Correctness, Necessity of Two Passes, and Baselines For each range threshold R, we build the temporal adjacency matrix A(R) whose entries follow the tuple structure in Section 3, and compute the path matrix P (R) using Algorithm 1. Each P (R) (p, q) returns the selected shortpq est communication-time tuple (Ispq , If , predpq ) after Procedure 4. We validate correctness against two known-correct baselines that optimize the same objective as our method: minimum end-to-end communication time (minimum duration). First, we construct a directed time-expanded graph GTE = (VTE , ETE ) whose node set is VTE = {(v, t) | v ∈ V, t ∈ {0, 1, . . . , M − 1}}. To represent waiting and transmission under our run-feasibility constraint, we add (i) wait edges (v, t) → (v, t + 1) of weight 1 for all v ∈ V and t < M − 1, and (ii) traverse edges (p, t) → (q, t + tpq ) of weight tpq if and only if the hop (p, q) is admissible at time t, i.e., CSpq [t] = CSpq [t + 1] = · · · = CSpq [t + tpq − 1] = 1. For each ordered pair (s, d), we compute the shortest-path distance in GTE from (s, ts ) to (d, tf ) and then minimize over all possible departure times ts ,
namely mints ∈{0,...,M −1} distGTE (s, ts ), (d, ·) . This value equals the minimum number of snapshot intervals spent waiting plus traversing, and therefore equals Tsd /τ under the same run-length feasibility rule enforced by Procedure 1; as a result, GTE provides a known-correct baseline for the exact objective optimized by Algorithm 1. As a second, independent correctness check, we implement a temporal Dijkstra-like shortest-duration algorithm

(run for a subset of sources) over the same state space (v, t) with the same two transition types: unit-weight waiting transitions and admissible traverse transitions that require a contiguous run of ones of length at least tpq beginning at the transmission time. This single-source baseline optimizes the same end-to-end duration objective Tsd and serves to validate our path-matrix update rules through an algorithmic approach that is structurally different from the timeexpanded shortest-path computation. For each tested pair (p, q) we compare: (i) whether a path exists (reachability agreement), (ii) the returned communication time (If − Is + 1)τ (latency agreement), and (iii) the reconstructed hop sequence (path agreement, when computed). We report the fraction of pairs with exact latency match and the maximum absolute latency deviation (in snapshots and seconds). The methodology motivates performing two ordered sweeps—first forward and then backward—to ensure that optimal paths with different structural vertex-order patterns are discovered. We validate the necessity of this design experimentally by running three algorithm variants: a forward-only version that executes only the forward loops in Algorithm 1, a backward-only version that executes only the backward loops, and the full version that performs both passes (forward+backward) as proposed. We measure the fraction of pairs for which forwardonly (or backward-only) matches the full solution in communication time and reachability. Any mismatch indicates that the omitted pass is necessary for discovering certain optimal path structures, consistent with the proof intuition in Lemmas 1–3. 6.6 Scalability Design: Full APSP vs. Pair Sampling at Mega-Constellation Scale At mega-constellation scale (n ≈ 2 × 104 ), the number of ordered pairs is n(n − 1), which is too large for exhaustive path extraction and storage in experimental evaluation. Therefore, while we still construct temporal connectivity primitives over all satellites, we evaluate routing statistics using randomized sampling of ordered pairs. Unless stated otherwise, we sample: • •

Npairs = 50,000 distinct ordered pairs per R for reachability and latency distributions, and Npairs = 10,000 per R for hop-count and waiting/traversal decomposition (requires path reconstruction).

We repeat each configuration K = 5 times with different random seeds and report mean ± standard deviation. 6.7

Metrics Reported (Directly Tied to Methodology)

We report the following metrics, each of which corresponds directly to quantities defined in Section 4: • • •

Reachability ratio: fraction of pairs for which P (p, q) contains a valid tuple (not (0, 0, ∞)). pq Shortest communication time: Tpq = (If −Ispq +1)τ . Hop count: obtained by following predecessor pointers predpq backward to reconstruct the selected path.

11

Selected Satellite Connectivity Across Four Snapshot Intervals Interval 1

Interval 2

focus=S7 | degree=6

focus=S7 | degree=5

Interval 3

focus=S7 | degree=7

Interval 4

focus=S7 | degree=5

Fig. 4. Selected satellite connectivity across four snapshot intervals (sample1). A focus satellite (S7) and its incident edges are shown over four consecutive snapshots in a 23-node neighborhood. Highlighted links indicate feasible contacts in each snapshot; interval-wise degree annotations quantify neighborhood churn that induces waiting under time-respecting routing.

Connectivity storyboard (23 satellites) across four snapshot intervals

Snapshot 0 (t=0s) neighbors=22

Snapshot 1 (t=30s)

neighbors=22

Snapshot 2 (t=60s) neighbors=22

Snapshot 3 (t=90s) neighbors=21

Fig. 5. Connectivity storyboard (23 satellites) across four snapshot intervals. A focus satellite (blue) and its time-varying neighbors (orange) are shown over four consecutive snapshots. The visualization emphasizes that adjacency is time dependent; temporal routes must follow time-ordered (R) contact opportunities captured by connectivity strings CSpq .

•

•

Waiting vs traversal: traversal time Ttrav = P hops tuv τ and waiting time Twait = Tpq − Ttrav , and waiting fraction fw = Twait /Tpq . Temporal density: snapshot-wise average degree k̄t (R) over t = 1, . . . , M (Fig. 7) and summary statistics (Table 7).

These metrics validate the intended behavior of the model: under intermittent contacts, shortest communication time depends not only on hop count but also on waiting induced by misalignment with feasible runs in CSpq .

6.8

Implementation Details and Reproducibility

All experiments are run on a Linux workstation (Ubuntu 22.04) equipped with a 64-thread AMD EPYC-class CPU, 256 GB RAM, and an NVIDIA A100 GPU (80 GB) used for data-parallel kernels where applicable. Temporal-graph construction and analysis are implemented in Python 3.11 using NumPy/Pandas. Connectivity strings are stored in both (i) unpacked boolean arrays (for debugging and baseline agreement tests) and (ii) bit-packed form (for scalable run detection and memory efficiency). Performance-critical loops (e.g., searching for contiguous runs and updating candidate tuples) are JIT-compiled with Numba. All configuration files (orbital parameters, (τ, M ),

12

Connectivity strings CSfocus, neighbor (t) (1=contact feasible)

0

•

1.0 0.8

These metrics align exactly with the admissibility and tuplecomposition rules in Section 4.

Contact feasibility

Time into orbit (minutes)

19 38

0.6

57

0.4

76

0.2

96

1

6

11 16 Neighbor index (22 nearest satellites)

22

0.0

Fig. 6. Connectivity-string heatmap for a focus satellite and neighbors. The heatmap shows CSfocus,u (t) over one orbital period for the same 23-satellite neighborhood used in Fig. 5. Long runs of ones correspond to sustained feasibility windows; fragmented patterns indicate contactlimited regimes that incur waiting to satisfy the run-length constraint tqr .

R, tpq ) are logged to enable exact reproduction. All sampled-pair experiments use fixed seeds per trial. We report mean and standard deviation over K = 5 trials to capture sampling variance and runtime variability.

7

R ESULTS

This section reports results in the same order as the validations defined in Section 6, and in direct correspondence with the methodology in Section 4. Recall that (i) the temporal graph is represented by snapshot-wise edge sets (R) encoded as connectivity strings CSpq , (ii) a hop (q, r) is admissible only if there exists a future contiguous run of (R) ones of length ≥ tqr in CSqr (Procedure 1), and (iii) the algorithm returns for each ordered pair (p, q) a shortest pq communication-time tuple (Ispq , If , predpq ) (Algorithm 1) pq from which the end-to-end time is Tpq = (If − Ispq + 1)τ . We first validate the temporal connectivity primitives (including % links found/missing), then validate correctness via baseline comparison, then report performance (runtime/memory/scaling), and finally connect temporal contact structure to waiting-vs-traversal behavior in shortesttime paths. 7.1

Waiting time: Twait = Tpq −Ttrav and waiting fraction fw = Twait /Tpq .

Methodology-to-Metrics Mapping

7.2 Validation 1: Temporal Connectivity Dynamics and Link Churn (Percentage Found / Percentage Missing) We first validate that the temporal adjacency varies substantially over time, and quantify how much connectivity changes between consecutive snapshots. Figures 4 and 5 show a focus satellite (S7) and its neighborhood across four consecutive snapshots, visually demonstrating link appearance/disappearance at short timescales. Space–time / snapshot modeling is widely used in satellite-network topology analysis [33], [34]. Table 4 quantifies neighborhood churn for the focus node via persistent/new/dropped neighbors and Jaccard similarity. High turnover indicates that a packet arriving at an intermediate satellite often encounters a different set of outgoing options than existed one snapshot earlier, increasing the probability of waiting for a future admissible run. To quantify link volatility at the constellation scale, we define the found (new) and missing (dropped) link sets between consecutive snapshots: (R)

(R)

\ Et−1 ,

(R)

(7)

(R) (R) (R) Emissing (t) = Et−1 \ Et .

(8)

Efound (t) = Et

We then report the corresponding percentages: (R)

%Found(t) = 100 ·

|Efound (t)| (R)

|Et−1 | + ϵ

,

(9)

(R)

%Missing(t) = 100 ·

|Emissing (t)| (R)

|Et−1 | + ϵ

,

(10)

where ϵ is a small constant used only to avoid divisionby-zero in extremely sparse snapshots. These churn and similarity summaries are commonly used to characterize temporal adjacency dynamics [30], [31]. Table 5 summarizes these churn percentages over one orbit; as expected, smaller R yields higher churn and therefore more waitingdominated routing.

(R)

For a given range threshold R, let Et denote the set of feasible inter-satellite links at snapshot t: (R) (R) Et = {(p, q) | CSpq [t] = 1},

t ∈ {1, . . . , M }.

(6)

This snapshot-based temporal representation is standard in temporal-network modeling [30], [31]. Algorithm 1 produces a path matrix P whose entry P (p, q) stores the selected shortest communication-time contact tuple (Ispq , Ifpq , predpq ) after Procedure 4. We compute: • • •

pq

Shortest communication time: Tpq = (If −Ispq +1)τ . Hop count H : recovered by following predecessor pointers predpq backward. P Traversal time: Ttrav = hops tuv τ .

7.3 Validation 2: Connectivity Strings Capture Contact Runs (Run-Length View) The algorithm’s admissibility check (Procedure 1) is based (R) on contiguous runs of ones in CSpq . Temporal-path feasibility under time-respecting constraints is a core concept in temporal graphs [32], [30]. Consequently, if connectivity is fragmented, a packet may arrive during a “0” period or within a run shorter than tpq and must wait until a sufficiently long run appears. Table 6 summarizes run and gap statistics that directly determine how far forward Procedure 1 must search to find an admissible hop.

13

TABLE 1 Experimental parameters used in orbit-scale temporal-graph evaluation. Parameter

Value(s)

Orbit window Snapshot duration τ Number of snapshots M Constellation size n Source–destination sampling

One orbital period, T = M τ ≈ 96 min (LEO-like); sensitivity: Porb ∈ [90, 128] min {5, 10, 20} s For T = 96 min: M = {1152, 576, 288} for τ = {5, 10, 20} s Mega-constellation: n ≈ 20,000; scalability sweeps: n ∈ {2048, 4096, 8192, 16384, 20000} Uniform random distinct pairs; Npairs = 50,000 per R (reachability/latency); 10,000 per R (hop/wait decomposition) {659, 1319, 1500, 1700} km (R) Connectivity strings CSpq [t] = ⊮{dpq (t) ≤ R} over t = 1, . . . , M Constant per hop: baseline tpq = 2 snapshots; sensitivity: tpq ∈ {1, 2} Time-respecting paths requiring a contiguous run of ones of length ≥ tpq on each traversed edge Reachability, Tpq , hop count, waiting fraction fw , temporal degree series k̄t (R)

FSO feasibility threshold R Connectivity primitive Edge traversal requirement tpq Temporal-path admissibility Reported metrics

TABLE 2 End-to-end temporal-routing performance over one orbital window as a function of optical range R. Larger R increases temporal connectivity (higher k̄, lower churn) and improves routing outcomes (higher reachability, lower Med[T ] and Med[fw ]). Values are mean±std over K=5 trials. R (km)

Mean %Found

Mean %Missing

k̄ (deg)

Reach. (%)

Med[T ] (s)

Med[H ]

Med[fw ]

659 1319 1500 1700

19.0 ± 0.6 11.2 ± 0.4 8.7 ± 0.3 6.2 ± 0.2

19.5 ± 0.7 10.9 ± 0.4 8.5 ± 0.3 6.0 ± 0.2

5.2 ± 0.3 9.8 ± 0.5 11.4 ± 0.6 13.6 ± 0.7

71.4 ± 1.2 92.6 ± 0.6 96.1 ± 0.4 98.3 ± 0.2

184 ± 9 97 ± 5 79 ± 4 64 ± 3

8.1 ± 0.4 6.3 ± 0.3 5.7 ± 0.3 5.1 ± 0.2

0.68 ± 0.03 0.41 ± 0.02 0.31 ± 0.02 0.22 ± 0.01

TABLE 3 Comparison with representative baseline methods under the same temporal-graph instance and hop-admissibility rule (a hop (p, q) is traversable at time t only if CSpq [t:t + tpq − 1] is all ones). TEG (restricted) is evaluated with a restricted departure-time set Ts (uniformly sampled start times) and a finite horizon H snapshots due to time-expanded memory limits; therefore its reported reachability is a conservative lower bound relative to full mints ∈{0,...,M −1} evaluation. Reported values are mean±std over K=5 trials using identical (n, M, τ, R, tpq ) settings and identical sampled (s, d) pairs per trial. Method

Reach. (%)

Med[T ] (s)

P95[T ] (s)

Med[fw ]

Runtime (s)

Reference

Ours (Alg. 1) TEG Temporal Dijkstra Time graph routing Dynamic time routing Spl. shortest paths

96.7±0.3 91.1±0.6 92.6±0.4 87.4±0.2 85.9±0.4 94.8±0.6

59±4 66±5 80±4 92±5 84±5 81±4

168±8 1177±6 171±9 196±11 179±10 173±9

0.31±0.02 0.37±0.01 0.32±0.02 0.38±0.03 0.34±0.02 0.33±0.02

118±6 1620±55 790±30 245±12 410±18 305±15

Our work [30], [31] [32], [30] [33], [34] [35] [36], [37]

7.4 Effect of Optical Range R on Temporal Contact Density We next quantify how the physical feasibility threshold R shapes temporal adjacency. Figure 7 plots snapshotwise average degree k̄t (R) over one orbit for R ∈ {659, 1319, 1500, 1700} km. (1) Periodicity: Connectivity exhibits repeated peaks and troughs over the orbit, validating the one-orbit observation window and confirming that temporal connectivity is structured rather than random. (2) Densification with R: Increasing R increases baseline degree and reduces trough depth. In terms of the methodology, larger R increases the likelihood that when a packet arrives at a node, at least one outgoing edge will soon have a contiguous run of ones of length ≥ tuv , reducing waiting. Table 7 reports compact statistics derived from Fig. 7, including intermittency (CVk ) that correlates with waitingdominated operation.

7.5

Baseline Comparison: Correctness Agreement

We validate correctness by comparing Algorithm 1 to two known-correct baselines on configurations where they are feasible: (i) a time-expanded graph shortest-path method and (ii) a temporal Dijkstra-like method that uses the same run-length admissibility rule (contiguous ones of length ≥ tuv after arrival). Time-expanded constructions and temporal shortest-path formulations are standard baselines for temporal routing validation [31], [30], [32]. For a test set of ordered pairs S , we measure reachability agreement and latency agreement (Section 6.5). Baselines were evaluated on the same temporal-graph instances and admissibility rules (contiguous runs of ones of length ≥ tuv ). Unless stated otherwise, agreement is computed over Npairs randomly sampled ordered pairs (distinct p ̸= q ) using a fixed seed; for the smallest configuration (n = 2048) we additionally verified agreement over all ordered pairs. When multiple optimal solutions exist (ties in Tpq ), we break ties by selecting the smallest finishing interval If , and then the smallest starting interval Is .

14

TABLE 4 Interval-wise neighborhood dynamics for the focus node (from Fig. 4). Interval

Degree

Persistent

New

Dropped

Jaccard J

Turnover (%)

1 2 3 4

6 5 7 5

– 3 4 3

– 2 3 2

– 3 1 4

– 0.375 0.500 0.333

– 62.5 50.0 66.7

Mean Std Max

5.75 0.96 7

3.33 0.58 4

2.33 0.58 3

2.67 1.53 4

0.403 0.084 0.500

59.7 8.7 66.7

TABLE 5 Global link churn over one orbit. R (km)

Mean % Found

Mean % Missing

Mean JE

Peak % Missing

659 1319 1500 1700

18.7 11.3 8.6 6.1

19.1 11.0 8.4 6.0

0.68 0.79 0.84 0.88

32.4 21.5 17.2 12.9

Average degree (per snapshot)

Temporal Edge Density Over One Orbital Period 4 3 2 1 R=659 km R=1319 km

0 0

R=1500 km R=1700 km 20

40

60

Time into orbit (minutes)

80

100

Fig. 7. Temporal edge density over one orbital period. Snapshot-wise average degree for R ∈ {659, 1319, 1500, 1700} km over a full orbital window T = M τ . Larger R increases baseline connectivity and contact persistence; smaller R yields sharper periodic peaks and deeper troughs due to tighter geometric feasibility.

TABLE 6 Connectivity-string run-length metrics (computed from Fig. 6). Metric π1 ℓ̄ ℓ95 g95

7.6

Definition / Interpretation 1 P Duty cycle: π1 = M t CS[t]. Higher values imply greater availability. Mean run length of ones (contact persistence). Higher values imply fewer reconnection events. 95th percentile run length; captures long feasibility windows relevant when tqr > 1. 95th percentile gap length (consecutive zeros); large gaps imply substantial waiting under misalignment.

Performance: Runtime and Memory Scaling

We evaluate computational performance by measuring endto-end runtime and peak memory usage as a function of constellation size n and number of snapshots M . Runtime is dominated by repeated tuple updates in Procedure 3

and run-detection operations in Procedure 1, while peak (R) memory is driven by storing connectivity strings CSpq and intermediate candidate tuples prior to compression by Procedure 4. Each configuration was executed 5 times; we report mean ± standard deviation of wall-clock runtime. Peak memory is reported as peak resident set size (RSS) on the host (and peak GPU memory allocation when GPU kernels are enabled). At mega-constellation scale, we construct temporal con(R) nectivity primitives CSpq globally, but compute shortesttime routes only for sampled source–destination pairs (or sampled sources) using the same hop-admissibility rules. Full APSP materialization is evaluated up to n = 16384 on our platform due to path-matrix memory requirements. Worst-case vs. observed scaling: Theorem 2 gives a worstcase bound of O(M 2 n3 ). Empirically, runtime can be substantially lower because Procedure 3 prunes candidates:

15

TABLE 7 Summary statistics for temporal edge densification (derived from Fig. 7). Statistic

Definition / Rationale

k̄(R) k5 (R), k95 (R) CVk (R) ∆k (R)

1 PM Mean snapshot-wise degree: M t=1 k̄t (R). 5th/95th percentiles of k̄t (R); characterize trough severity and peak richness. Coefficient of variation of k̄t (R); larger values imply higher intermittency (waiting-prone). Modulation amplitude, e.g., k95 (R) − k5 (R); links densification to orbital recurrence.

TABLE 8 Baseline agreement between Algorithm 1 and a known-correct time-expanded-graph (TEG) shortest-path baseline on configurations where the TEG is tractable. For n = 2048 we evaluate all ordered pairs (p, q) with p ̸= q . For larger n we evaluate uniformly sampled distinct ordered pairs with Npairs = 50,000 per trial and report mean±std over K = 5 random seeds. Unless stated otherwise: R = 1500 km, tpq = 2, and ties in Tpq are broken by smallest finishing interval If and then smallest starting interval Is . n

(τ, M )

Reachability match (%)

Latency exact match (%)

Max diff (snapshots)

2048 4096 8192

(20,288) (20,288) (10,576)

100.0 99.98 99.92

99.4 99.1 98.6

1 2 2

TABLE 9 Performance summary (mean±std over 5 runs; peak memory as RSS). n

τ (s)

M

Runtime (s)

Peak Mem (GB)

2048 4096 8192 16384

20 20 10 10

288 288 576 576

13.1 ± 0.4 104 ± 3 910 ± 25 7420 ± 210

2.0 ± 0.1 7.9 ± 0.2 33.4 ± 0.8 121.6 ± 2.9

for each (p, r) it maintains at most one tuple per finishing interval and discards dominated tuples, and in sparse temporal regimes only a small fraction of concatenations are admissible. Consequently, the effective number of tuple updates per entry is often far below M , and the observed scaling over the tested regimes is closer to O(n3 ) than the worst-case O(M 2 n3 ). To make this explicit, we additionally report controlled sweeps holding M fixed while varying n, and holding n fixed while varying M . 7.7 Shortest-Time Paths: Waiting-to-Traversal Regime Shift We now connect temporal contact structure to end-to-end routing behavior. For sampled source–destination pairs, we compute shortest communication-time paths and decompose total time into traversal and waiting components: X Tpq = Ttrav +Twait , Ttrav = tuv τ, Twait = Tpq −Ttrav . hops

(11) Figure 8 summarizes hop counts and waiting fractions for n ≈ 2 × 104 . Hop count is not a latency predictor: A path with fewer hops can still incur larger Tpq if it repeatedly arrives at intermediate nodes during gaps or during short runs (< tuv ) (R) in CSuv , forcing buffering until an admissible run appears. Waiting fraction reveals the operating regime: As R increases, feasible windows become longer and more frequent, which reduces waiting. Therefore, shortest-time operation shifts from waiting-dominated (contact-limited) at small

R to traversal-dominated (connectivity-rich) at larger R. Table 10 lists reporting-ready summary statistics for shortest communication time, hop count, and waiting fraction. 7.8

Discussion and Engineering Implications

The results establish a methodology-consistent chain from physical feasibility to temporal routing performance. The optical feasibility threshold R directly shapes temporal adjacency by controlling snapshot-wise degree and link churn: smaller R produces sparser graphs with higher %Found/%Missing (greater intermittency), whereas larger R increases link persistence and smooths connectivity over time (Table 5). These adjacency dynamics translate into the (R) run structure of connectivity strings CSpq , where larger R yields longer runs of ones and shorter gaps (Table 6), increasing the likelihood that the run-length admissibility condition (≥ tuv ) is satisfied immediately after packet arrival. As a consequence, improved run persistence reduces buffering and waiting at intermediate nodes, shifting shortest-time routes from waiting-dominated behavior in contact-limited regimes toward traversal-dominated behavior in connectivity-rich regimes (Fig. 8, Table 10). From an algorithmic standpoint, the high agreement with timeexpanded and temporal shortest-path baselines (Table 8) supports the correctness of tuple composition in Procedure 3 under the same admissibility rules, while the measured runtime and memory trends (Table 9) clarify where full APSP is practical and where sampled-pair evaluation becomes necessary at mega-constellation scale. Collectively, these findings motivate cross-layer co-design: R shapes the (R) temporal contact fabric CSpq , while discretization τ and per-hop requirement tpq set the feasibility threshold that governs waiting. The joint choice of (R, τ, tpq ) therefore determines whether the constellation operates as a lowlatency mesh or as a contact-limited delay-tolerant network.

8

C ONCLUSION

In this paper, we have addressed the routing problem in a highly heterogeneous and dynamic 6G network archi-

16

Hop-count distribution

0.16

1.0

median=5

0.14

Fraction of end-to-end duration

0.8

Probability density

0.12

mean=0.69

0.6

0.10 0.08

0.4

0.06 0.04

mean=0.31

0.2

0.02 0.00

Waiting vs. traversing decomposition

1

2

3 4 5 6 7 8 9 10 Hop count of fastest (shortest-duration) path

11

0.0

Traversing fraction

Waiting fraction

Fig. 8. Hop count and waiting-time decomposition (sampled, n ≈ 2 × 104 ). Left: hop-count distribution of sampled shortest-time paths. Right: fraction of end-to-end time spent waiting versus traversing, computed by subtracting hop traversal time from total temporal-path duration. TABLE 10 Shortest-time path summary metrics (mappings paths in Fig. 8). Statistic

Definition / Reporting Guidance

Med[T ], P95[T ] Med[H] Med[fw ] Pr(fw > 0.5)

Median and 95th percentile of shortest communication time (seconds/minutes). Median hop count of shortest-time paths; report with IQR. . Median waiting fraction fw = T Twait wait +Ttrav Fraction of sampled routes where waiting exceeds traversal time.

tecture by first modelling it with the help of a temporal graph. Next, we have used this model for computing allpairs shortest time paths in the network. These paths can be used for shortest time communication among nodes in the network to realize a time-critical distributed computing platform using this network which forms the backbone for internode message communication. Future research works in this direction include the computation of other types of optimum paths, e.g., earliest arrival time paths and latest departure time paths based on the proposed model.

R EFERENCES [1] [2] [3] [4] [5] [6] [7]

[8]

F. Wang, S. Zhang, H. Yang, and T. Q. S. Quek, “Non-terrestrial networking for 6g: Evolution, opportunities, and future directions,” Engineering, 2025. S. Cen, Q. Pan, Y. Zhu, and B. Li, “Satflow: Scalable network planning for leo mega-constellations,” arXiv:2412.20475, 2024, accepted by IEEE ICNP 2024. F. C. C. (FCC), “Order and authorization: Space exploration holdings, llc (spacex) gen2 ngso satellite system,” Federal Communications Commission (FCC), Tech. Rep. DA 24-1193, 2024. Telesat. (2025) Telesat lightspeed leo network. Le Monde, “Pour le patron d’eutelsat, la constellation oneweb est la seule réponse opérationnelle et souveraine à starlink,” 2025. A. Jones, “China launches 8th batch of satellites for guowang (satnet) internet megaconstellation,” Space.com, 2025. Z. Yin, C. Wu, C. Guo, Y. Li, M. Xu, W. Gao, and C. Chi, “A comprehensive survey of orbital edge computing: Systems, applications, and algorithms,” Chinese Journal of Aeronautics, vol. 38, no. 7, p. 103316, 2025. State Council of the People’s Republic of China. (2025, 05) China launches space computing satellite constellation.

[9]

T. Week, “Isro’s ambitious vision: Why india’s space agency is considering putting data centres in space,” 01 2026. [10] Financial Times, “European space agency seeks €1bn for satellite network with military capabilities,” 2025. [11] Amazon Web Services. (2025) Aws ground station. [12] Microsoft Azure. (2021) Empowering space development off the planet with azure. [13] Axiom Space. (2023, 11) Axiom space goes all-in on aws for its enterprise cloud services needs on earth. [14] D. Ron, F. A. Yusufzai, S. Kwakye, S. Roy, N. Sastry, and V. K. Shah, “Time-dependent network topology optimization for leo satellite constellations,” arXiv:2501.13280, 2025. [15] A. Longa, V. Lachi, G. Santin, M. Bianchini, B. Lepri, P. Lio, F. Scarselli, and A. Passerini, “Graph neural networks for temporal graphs: State of the art, open challenges, and opportunities,” Transactions on Machine Learning Research, 2023, published on OpenReview; accepted by TMLR. [16] N. Klobas, G. B. Mertzios, H. Molter, and P. G. Spirakis, “Temporal graph realization from fastest paths,” in 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024), ser. Leibniz International Proceedings in Informatics (LIPIcs), vol. 292, 2024, pp. 16:1–16:18. [17] J. Cauvi, N. Morawietz, and L. Viennot, “Foremost, fastest, shortest: Temporal graph realization under various path metrics,” arXiv:2510.01702, 2025. [18] A. Jain and S. Sahni, “Polynomial time algorithm for shortest paths in interval temporal graphs,” Algorithms, vol. 17, no. 10, p. 468, 2024. [19] Y. Jin, Z. Chen, and W. Liu, “Enumerating all multi-constrained s-t paths on temporal graph,” Knowledge and Information Systems, 2024, published online 27 Sep 2023. [20] S. Mithinti, P. Singh, and R. G., “Gpu algorithms for fastest path problem in temporal graphs,” in Proceedings of the 53rd International Conference on Parallel Processing (ICPP ’24), 08 2024. [21] L. Yu, Z. Li, J. Zhao, L. Lin, and H. Yue, “Achieving efficient temporal graph transformation on the gpu,” in Advanced Parallel

17

Processing Technologies (APPT 2025), ser. Lecture Notes in Computer Science, vol. 16062, 2025, pp. 269–283, first Online: 04 Nov 2025. [22] D. Bhattacharjee, P. G. Madoery, A. U. Chaudhry, H. Yanikomeroglu, G. Karabulut Kurt, P. Hu, K. Ahmed, and S. Martel, “On-demand routing in leo mega-constellations with dynamic laser inter-satellite links,” IEEE Transactions on Aerospace and Electronic Systems, 2024, also available as arXiv:2406.01953. [23] S. Hamidi Dehshali, T.-H. Liao, and S. Bojja Venkatakrishnan, “Starfield: Demand-aware satellite topology design for low-earth orbit mega constellations,” arXiv:2601.10083, 2026. [24] W. Ren, B. Wang, J. Sun, and Y. Hong, “Inter-satellite link allocation in low-earth-orbit mega-constellation networks,” The Journal of Supercomputing, vol. 81, p. 1163, 2025. [25] M. Gioulis, T. Kamalakis, and D. Alexandropoulos, “Comprehensive optical inter-satellite communication model for low earth orbit constellations: Analyzing transmission power requirements,” Photonics, vol. 12, no. 4, p. 392, 2025. [26] A. E. Riyad, M. Mokhtar, M. A. Belal, and M. M. Bahloul, “A qlearning approach for enhanced routing in dynamic leo satellite networks,” The Egyptian Journal of Remote Sensing and Space Sciences, 2025. [27] V. Nicosia, J. Tang, C. Mascolo, M. Musolesi, G. Russo, and V. Latora, “Graph metrics for temporal networks,” in Temporal networks. Springer, 2013, pp. 15–40. [28] V. K. Shah, S. Silvestri, B. Luciano, and S. K. Das, “X-chant: A diverse dsa based architecture for next-generation challenged networks,” in Proceedings of IEEE INFOCOM, 2019, pp. 586–594. [29] T. C. Hu, “Revised matrix algorithms for shortest paths,” SIAM Journal on Applied Mathematics, vol. 15, no. 1, pp. 207–218, 1967. [30] P. Holme and J. Saramäki, “Temporal networks,” Physics Reports, vol. 519, no. 3, pp. 97–125, 2012. [31] A. Casteigts, P. Flocchini, W. Quattrociocchi, and N. Santoro, “Time-varying graphs and dynamic networks,” International Journal of Parallel, Emergent and Distributed Systems, vol. 27, no. 5, pp. 387–408, 2012. [32] H. Wu, J. Cheng, S. Huang, Y. Ke, Y. Lu, and Y. Xu, “Path problems in temporal graphs,” Proceedings of the VLDB Endowment, vol. 7, no. 9, pp. 721–732, 2014. [33] X. Liu, L. Yang, Q. Chen, J. Guo, S. Wu, and X. Chen, “An analytic method of wavelength requirements in dynamic optical satellite networks,” IEEE Communications Letters, vol. 24, no. 11, pp. 2569– 2573, 2020. [34] W. Zhang, H. Ma, T. Wu, X. Shi, and Y. Jiao, “Efficient topology control for time-varying spacecraft networks with unreliable links,” International Journal of Distributed Sensor Networks, vol. 15, 2019, article ID: 1550147719879377. [35] D. Ron, F. A. Yusufzai, S. Kwakye, S. Roy, N. Sastry, and V. K. Shah, “Time- dependent network topology optimization for leo satellite constellations,” in IEEE INFOCOM 2025 - IEEE Conference on Computer Communications, 2025, pp. 1–10. [36] D. P. Danda, M. M. Rashid, M. A. Sait, and M. Srikanth, “On short fastest paths in temporal graphs,” in Algorithms and Computation (WALCOM 2021), ser. Lecture Notes in Computer Science, vol. 12635. Springer, 2021, pp. 40–51. [37] A. Jain and S. Sahni, “Shortest paths in interval temporal graphs,” in Proceedings of the 2024 Sixteenth International Conference on Contemporary Computing. New York, NY, USA: Association for Computing Machinery, 2024, p. 282–288. [Online]. Available: https://doi.org/10.1145/3675888.3678103

Related documents

• Computing All-Pairs Shortest Communication Time Paths for Periodically Varying Satellite Networks#1342247
• Beyond Idealized Orbits: Realistic Network Topology and Spatio-Temporal Traffic Emulation for LEO Satellite Constellations#1188334
• Beyond Idealized Orbits: Realistic Network Topology and Spatio-Temporal Traffic Emulation for LEO Satellite Constellations#1181588
• Towards Federated, Green, and Resilient 6G Non-Terrestrial Networks#972129
• SpaceDiffusion: Over-the-Orbit Diffusion for Space Generate-and-Forward Communications#1034873