1
CRT: Collision-Tolerant Residence Time for Deterministic Transmission in LEO Satellite Networks
arXiv:2605.03382v1 [cs.NI] 5 May 2026
Siqi Yang, Zonghui Li, Chaoqun You, Yue Gao, Fellow, IEEE
Abstract—Low-Earth Orbit (LEO) satellite networks are a key enabler for the 6G Non-Terrestrial Network (NTN) architecture. However, supporting time-sensitive services in LEO networks is challenging due to highly dynamic topologies and the difficulty of maintaining precise global time synchronization. Existing Time-Sensitive Networking (TSN) mechanisms largely rely on static topologies and strict synchronization, which makes them ill-suited to dynamic LEO environments. To address this issue, we propose CRT, a deterministic transmission framework tailored for LEO networks. CRT regulates per-hop residence time using local clocks, thereby compensating for link-delay variations without requiring strict global synchronization. To handle asynchronous collisions, CRT adopts a collision-tolerant scheduling strategy that maximizes the number of schedulable flows while bounding collision-induced jitter. We formalize the corresponding scheduling problem and show that it is NP-hard. We further develop CRT-Fast, an efficient heuristic algorithm. It combines iterative layering with path continuity to control collision intensity and improve path stability under topology changes. Simulations on Iridium and Starlink constellations show that the proposed method achieves lower delay jitter and high schedulability under heavy traffic loads. Index Terms—LEO Satellite Networks, 6G NTN, TimeSensitive Networking, Deterministic Transmission, Scheduling
I. I NTRODUCTION Low-Earth-Orbit (LEO) satellite networks are gaining attention for global connectivity due to their broad coverage and high availability. Driven by the miniaturization of hardware and reduced launch expenditures, massive LEO constellations, such as Starlink [1], Iridium [2], and OneWeb [3], are proliferating to bridge the digital divide in isolated and underserved regions. Concurrently, the transition toward 6G frameworks [4], [5] has imposed increasingly stringent requirements on LEO infrastructures. Time-critical services such as tele-surgery, autonomous transport, and industrial automation require strictly bounded latency and near-zero packet loss. To fulfill these exacting requirements, LEO networks must facilitate the deterministic transmission of data flows [6], [7]. Nevertheless, the inherent volatility of LEO constellations presents a formidable obstacle to achieving deterministic S. Yang, C. You and Y. Gao are with the Institue of Space Internet, Fudan University, Shanghai 200438, China, and the College of Computer Science and Artificial Intelligence, Fudan University, Shanghai 200438, China (email: [email protected], [email protected], [email protected]). Z. Li is with Beijing Key Lab of Traffic Data Analysis and Mining, School of Computer Science and technology, Beijing Jiaotong University, Beijing 100044, China (email: [email protected]). The corresponding authors are Z. Li and C. You.
communication. The high-velocity orbital motion of satellites results in transient link unavailability and frequent handovers [8]–[10]. Consequently, both Inter-Satellite Links (ISLs) and Ground-Satellite Links (GSLs) suffer from fluctuating propagation delays and intermittent connectivity. Such instability complicates the precise scheduling of time-sensitive traffic and undermines deterministic service guarantees. This leads to a fundamental challenge: maintaining deterministic performance within a highly fluid topology. This challenge must be addressed before LEO networks can support mission-critical time-sensitive services. Deterministic networking technologies have recently garnered considerable interest [11]–[13]. Distinguishing itself from traditional best-effort routing that calculates paths on a hop-by-hop basis in real time, these technologies emphasize the pre-establishment of end-to-end (e2e) routes and the advance reservation of network resources. Time-Sensitive Networking (TSN) [14], [15], standardized by the IEEE 802.1 working group, has emerged as a primary technical framework for providing such guarantees. The TSN framework integrates gate-controlled scheduling, time synchronization, preemption, and seamless redundancy. This allows Ethernet to support deterministic delivery for delay-critical traffic while maintaining compatibility with besteffort services. Rooted in the Time-Triggered (TT) communication paradigm [16], TSN aligns end systems and switches through precise time synchronization before executing transmissions at predefined instants. Network-wide synchronization is typically managed via IEEE 802.1AS [17], which builds upon the IEEE 1588 precision clock protocol [18]. Furthermore, IEEE 802.1Qbv [19] introduces the Time-Aware Shaper, utilizing Gate Control Lists (GCLs) to regulate packet forwarding at high-precision intervals. However, satellite links differ significantly from terrestrial TSN environments due to continuous and rapid propagationdelay variations, which can reach tens of milliseconds [20] and induce substantial jitter. Furthermore, attaining nanosecondlevel time synchronization across multi-satellite LEO systems is exceptionally difficult. Discrepancies in propagation delay can cause signal misalignment and simultaneous interference, hindering both synchronous reception and accurate peer-delay estimation. Factors such as orbital perturbations and the nonspherical geometry of the Earth further aggravate synchronization errors [21]. Consequently, terrestrial deterministic methods, which rely on stable topologies and negligible sync errors, may become suboptimal or entirely ineffective when
2
deployed in LEO constellations. To address these limitations, we propose CRT, a novel scheduling mechanism for deterministic transmission in LEO satellite networks. CRT addresses two fundamental challenges: (1) delay jitter caused by highly dynamic satellite topologies, and (2) limited time synchronization among local clocks in LEO satellites. To address them, CRT combines three key strategies. First, instead of relying on globally synchronized transmission instants, CRT computes the residence time of each data flow at every switch node based on local timestamps. In this way, it stabilizes the e2e delay without requiring precise global synchronization. Second, recognizing that strict nonoverlapping routing limits network capacity, CRT adopts a collision-tolerant strategy. It maximizes flow schedulability while minimizing link overlap. By calculating the WorstCase Delay (WCD) caused by asynchronous collisions, CRT ensures that the resulting jitter remains bounded within the deadline margin. Third, to cope with topology dynamics, CRT introduces a seamless handover mechanism based on implicit backup paths and path continuity, thereby mitigating packet loss during topology changes. CRT enables deterministic transmission with high schedulability in dynamic LEO environments without requiring precise global synchronization. The major contributions of this paper are summarized as follows: • Deterministic transmission mechanism without global synchronization. We propose CRT, a residence-timebased deterministic transmission framework for LEO satellite networks. By regulating per-hop residence time using local timestamps, CRT compensates for linkinduced dynamics without relying on strict global clock synchronization. • Collision-tolerant scheduling model with bounded jitter. We analyze the impact of asynchronous clock drift on shared-link transmissions and show that collisions among flows from distinct sources are unavoidable in unsynchronized LEO environments. Based on this observation, we formulate the CRT scheduling problem, which maximizes schedulability while minimizing the overlap degree to bound collision-induced jitter under deadline and resource constraints. We further show that this problem is NP-hard. • Practical heuristic scheduling algorithm. To solve the CRT scheduling problem efficiently, we develop CRTFast, a heuristic algorithm that combines iterative layering with path continuity. CRT-Fast controls collision intensity during flow scheduling while improving stability across time slots. • Comprehensive evaluation on representative LEO constellations. We conduct extensive simulations on Iridium and Starlink constellations. The results show that CRT-Fast achieves better schedulability, lower jitter, stronger path stability under topology dynamics, and good scalability compared with baseline methods. II. BACKGROUND To facilitate the understanding of the proposed CRT mechanism, we first introduce the basic terminology and the deter-
ministic transmission principles in TT networks. 𝑓𝑖 end device 𝑣0
global time synchronization
switch 𝑣1
∅𝑖, 𝑣0,𝑣1 sending point
𝑣𝑗
𝑣𝑗+1
∅𝑖, 𝑣𝑗 ,𝑣𝑗+1
𝑣𝑛−1
end device 𝑣𝑛 t
𝑑𝑙𝑖𝑛𝑘,𝑖, 𝑣𝑛−1,𝑣𝑛
Fig. 1: Example of a deterministic data flow path in TT networks.
A. Network Topology and Dataflow The physical topology is represented as an undirected graph G(V, E), where V consists of end systems and switches, and E represents the physical communication links. Each physical link defines two directed dataflow links. We define the set of directed links L as: L = {[u, v], [v, u] | {u, v} ∈ E}.
(1)
A dataflow path p is defined by a sequence of directed links from a sender to a receiver. For example, as illustrated in Fig. 1, the path from sender v0 to receiver vn is: p = ⟨[v0 , v1 ], [v1 , v2 ], . . . , [vn−1 , vn ]⟩.
(2)
A TT flow fi is a periodic data stream characterized by its period Ti and frame length Li . In a standard synchronized network, the transmission of fi on a specific link [u, v] is triggered at a precise, pre-scheduled time instant, known as the offset, denoted by ϕi,[u,v] . B. Deterministic Transmission TT networks depend on global time synchronization, which establishes a unified temporal reference for deterministic transmission. TT schedulers typically use linear constraint models that incorporate factors such as e2e delay bounds, conflict-free transmission requirements, and buffer constraints. The goal is to determine precise sending instants for TT flows at both end devices and intermediate switches. The computed schedules are compiled into static schedule tables [22], which are then deployed to the devices. As a result, each device transmits TT flow frames strictly according to the specified time instants. For example, consider the n-th departure time of flow fi from vertex vj to vertex vj+1 , which is specified as: tdepart = n · Ti + ϕi,[vj ,vj+1 ] ,
(3)
where Ti is the period, and ϕi,[vj ,vj+1 ] denotes the scheduled offset on the link. Alongside TT flows, the network accommodates non-TT traffic. IEEE 802.1Qbv [19] introduces guard bands to prevent transmission conflicts. These bands precede each TT transmission. They allow non-TT frames to complete transmission before TT frames begin. However, this guard band is set to the maximum frame length of non-TT traffic, leading to
3
end device 𝑣0
𝑓𝑖
satellite 𝑣1
satellite 𝑣𝑗
satellite 𝑣𝑗+1
satellite 𝑣𝑛−1
∆𝑡𝑖,𝑣1
∆𝑡𝑖,𝑣𝑗
∆𝑡𝑖,𝑣𝑗+1
∆𝑡𝑖,𝑣𝑛−1
end device 𝑣𝑛
t
𝑑𝑙𝑖𝑛𝑘,𝑖, 𝑣𝑗 ,𝑣𝑗+1
𝑑𝑙𝑖𝑛𝑘,𝑖, 𝑣0 ,𝑣1
𝑑𝑙𝑖𝑛𝑘,𝑖, 𝑣𝑛−1 ,𝑣𝑛
Fig. 2: The Residence-Time Mechanism.
potential bandwidth waste. IEEE 802.1Qbu [23] introduces a preemption mechanism to address this. It allows TT frames to interrupt ongoing non-TT transmissions. This mechanism reduces the guard band to 127 bytes, which corresponds to the maximum non-preemptible frame length. Based on this, we assume that TT frames can be transmitted immediately at their scheduled departure times. There is no delay due to ongoing transmissions. As a result, the arrival time of flow fi at vn is determined as follows: Arri,vn = ϕi,[vn−1 ,vn ] + dlink,i,[vn−1 ,vn ] ,
(4)
where dlink,i,[vn−1 ,vn ] denotes the link delay on [vn−1 , vn ]. This delay is dynamically measured using the peer delay mechanism defined in IEEE 1588 [18]. Accordingly, the e2e delay of flow fi from v0 to vn is given by: Delayie2e = Arri,vn − ϕi,[v0 ,v1 ] .
(5)
However, maintaining consistent transmission schedules in TT networks requires system-wide time synchronization. The synchronization accuracy is denoted by µ. It represents the maximum allowable time offset between any two synchronized devices. As a result, the e2e delay jitter of flow fi falls within the range Delayie2e ± µ. This characterizes the deterministic latency guarantee offered by TT networks. While TT-based networks provide high predictability under static, well-synchronized conditions, their underlying assumptions are often violated in the LEO environment. Their reliance on fixed schedule tables, global time alignment, and rigid transmission instants makes them ill-suited for topologies characterized by frequent connectivity shifts and uncertain propagation delays. These constraints emphasize the urgent need for a more resilient and adaptive scheduling paradigm. III. T HE R ESIDENCE T IME M ECHANISM AND C OLLISION C HALLENGES A. Residence Time Mechanism To address the challenges of dynamic topologies and asynchrony, we propose the Residence Time mechanism. As shown in Fig. 2, the proposed mechanism differs from traditional methods relying on the global time synchronization, it stabilizes the e2e delay by regulating the per-hop residence time according to local clocks. Let ∆ti,v denote the allocated residence time of flow fi at node v before it is transmitted to the next hop.
Under this mechanism, the e2e delay of flow fi from sender v0 to receiver vn is defined as: Delayie2e =
n−1 X
dlink,i,[vj ,vj+1 ] +
j=0
n−1 X
∆ti,vj .
(6)
j=1
Specifically, when a data frame of flow fi reaches vertex vj from vj−1 , the vertex records its arrival timestamp Arri,vj using the local clock and schedules it for forwarding at Arri,vj + ∆ti,vj . Since this mechanism triggers transmission based on local time rather than the global time synchronization, it functions as a local time-triggered system. Consequently, it remains fully compatible with the guard band strategy of IEEE 802.1Qbv and the preemption strategy of IEEE 802.1Qbu. By utilizing these standards, the switch ensures that TT flows are protected from interference by Non-TT traffic (e.g., BestEffort), maintaining isolation without global synchronization.
B. Collision Challenges and the CRT Scheduling Problem While the residence-time mechanism can stabilize the e2e delay, it cannot by itself eliminate contention among TT flows. In an asynchronous LEO environment, TT packets may still be blocked by other TT packets on shared links. This is because, unlike the globally synchronized case where the relative transmission offsets between flows remain fixed, different source nodes operate in different local clock domains. When flows from different sources traverse a common link, relative clock drift gradually shifts their transmission windows over time. As a result, even flows that are initially nonoverlapping may eventually interfere with each other. This challenge is formalized in the following theorem. Theorem 1 (Flow Drift). Consider two periodic flows fi , fj ∈ F originating from different source nodes and sharing a common link [vk , vl ]. Let their initial transmission offsets on this link be ϕi and ϕj , respectively, and let the relative clock drift rate between their source clock domains be s > 0. If no explicit synchronization is enforced, then the relative phase difference between the two flows varies over time. Consequently, there exists a finite time after which their transmission windows overlap, causing a collision. Proof. Let the initial phase difference be ∆ϕ0 = |ϕi − ϕj |.
4
Due to the relative clock drift s, the phase difference evolves over time as ∆ϕ(t) = |∆ϕ0 − st|. Let C denote the transmission duration of a TT frame on the shared link. A collision occurs when the phase difference becomes smaller than the transmission window, i.e., ∆ϕ(t) < C. Solving this inequality gives ∆ϕ0 − C . s Therefore, for any non-zero relative clock drift s > 0, there exists a finite time t such that the transmission windows of fi and fj overlap, which causes a collision. t>
Collisions among TT flows introduce additional queuing jitter, which can undermine deterministic transmission guarantees. To address this issue, CRT adopts a collision-tolerant scheduling strategy. Since flows generated by the same source are serialized at the ingress, effective collisions only occur among flows originating from different source nodes. We formulate an optimization problem that maximizes schedulability while minimizing the maximum overlap degree, thereby bounding the resulting jitter. Based on this idea, we define the CRT scheduling problem as follows. Definition 1 (CRT Scheduling Problem). Given a timevarying network topology sequence G and a set of timesensitive flows F , the CRT scheduling problem is to determine a scheduled subset of flows F ′ ⊆ F, together with their routing paths P and per-hop residence times ∆t, such that: 1) the number of scheduled flows |F ′ | is maximized; 2) subject to (1), the maximum overlap degree is minimized, where the overlap degree of a link counts only flows originating from distinct source nodes; 3) all scheduled flows satisfy the e2e deadline, residencetime, and resource constraints. Theorem 2. The CRT scheduling problem in Definition 1 is NP-hard. Proof. We prove this by reduction from the Edge-Disjoint Paths (EDP) problem [24], which is NP-complete in directed graphs. Consider the following decision problem of CRT scheduling: given a topology sequence G, a flow set F , an integer threshold Q, and an overlap bound K, determine whether there exists a feasible schedule such that at least Q flows are scheduled and the maximum overlap degree is at most K. We reduce an arbitrary EDP instance to a restricted static instance of this decision problem. Given a directed graph G = (V, E) and a set of source-destination pairs (si , di ), we construct a static CRT instance as follows: 1) Topology: Use a single static snapshot identical to G. 2) Flows: For each source-destination pair (si , di ) in the EDP instance, we introduce a private virtual source node ŝi and connect it to the original source node si by a dedicated edge (ŝi , si ) that is not shared by any other
flow. We then define the corresponding flow fi to start from ŝi and terminate at di . 3) Relaxation: Set link capacities, deadlines, buffer limits, and residence-time bounds sufficiently large so that they never restrict feasibility. 4) Decision parameters: Set Q = |F | and K = 1. Then, there exists a feasible CRT schedule admitting at least Q flows with maximum overlap degree at most K = 1 if and only if there exists a set of pairwise edge-disjoint paths for all source-destination pairs in the EDP instance. Indeed, admitting at least Q = |F| flows means all flows must be scheduled. Since the maximum overlap degree is at most 1, no two scheduled flows can share any link, thus the resulting paths are pairwise edge-disjoint. Conversely, any solution to the EDP instance directly yields a feasible CRT schedule for all flows with maximum overlap degree at most 1. Therefore, this restricted decision version of CRT scheduling is NP-hard. Since the optimization problem in Definition 1 is at least as hard as this restricted version, the CRT scheduling problem is NP-hard. IV. S CHEDULING FOR CRT D ETERMINISTIC T RANSMISSION A. Scheduling Model
𝒇𝒊 𝒇𝒋 𝒔𝒊
𝒔𝒋
𝒅𝒊
𝒅𝒋
Fig. 3: TT scheduling model in LEO satellite network. As depicted in Fig. 3, the network architecture comprises access devices and a LEO satellite system. The terminal devices handle the sending and receiving of each TT flow, while the LEO satellite network manages the scheduling process. A summary of the important notations and definitions used throughout the paper is provided in Table I, aiding in the comprehension of the proposed models and algorithms. We consider a LEO satellite constellation consisting of M orbital planes with N satellites per plane. The network connectivity relies on ISLs. Due to the periodic nature of satellite orbits, the dynamic topology is discretized into a sequence of time slots T = {1, . . . , m}. Within each time slot τ , the topology is modeled as a static directed graph Gτ = (V, Lτ ), where V denotes the set of satellites and Lτ denotes the set of ISLs. The network transmits TT flows requiring strictly deterministic service. We formally define a TT flow fi ∈ F as a tuple: fi = {Ti , Li , si , di , Di },
(7)
5
TABLE I: Notations and Definitions Notation T τ Gτ Lτ Be dτprop,e dproc,v F fi Ti Li Di Ci,e Cmax,e pτi nτe W CDeτ (nτe ) ∆tτi,v textra Ditarget yi xτi,p δe,p
Description The set of discrete time slots The index of a time slot The network topology graph in time slot τ The set of directed ISLs in time slot τ The bandwidth capacity of link e The propagation delay of link e in time slot τ The fixed processing delay at node v The set of TT flows The i-th TT flow The transmission period of fi The frame length of fi The e2e deadline of fi The transmission time of fi on link e (Li /Be ) The maximum transmission time of a TT frame on link e The routing path of flow fi in time slot τ The overlap degree on link e The worst-case delay caused by collisions on link e The allocated residence time of fi at node v The dynamic regulatory time to absorb jitter The scheduled deterministic e2e latency Binary schedule variable (1 if fi is scheduled) Binary path variable (1 if fi uses path p) Binary indicator (1 if link e is on path p)
where Ti is the transmission period, Li is the frame length, Di is the maximum allowable e2e deadline. si and di represent the source and destination satellites corresponding to the sender and receiver terminal devices. The packet transmission time on a link e with bandwidth Be is denoted as Ci,e = Li /Be . Given the time-varying topology, the routing path of flow fi in time slot τ is denoted as pτi . It consists of a sequence of links: pτi = [[v0 , v1 ], [v1 , v2 ], . . . , [vn−1 , vn ]] .
(8)
The physical delay on an ISL consists of transmission delay and propagation delay. For flow fi on link e, the link delay is: dτlink,i,e = dτprop,e + Ci,e .
(9)
The e2e latency assigned by the residence-time mechanism is: X e∈pτi
dτlink,i,e +
X
∆tτi,v = Ditarget ,
∀fi ∈ F, ∀τ ∈ T .
v∈pτi
(10) This equality defines the e2e delay Ditarget before accounting for collision-induced jitter. The residence time ∆tτi,v at node v is the control variable: ∆tτi,v = dproc,v + tτextra,i,v ,
(11)
where dproc,v is the processing delay of node v, it mainly results from analyzing the frame header and performing frame verification, which is considered a fixed constant. tτextra,i,v is the additional residence time required by the scheduler at node v. This residence time is dynamically adjusted by the scheduler to stabilize the e2e delay and compensate for variations in link delays across time slots.
B. Collision-Induced Jitter Analysis In a network-wide traffic scenario without reliance on global time synchronization, two main challenges arise: conflicts between TT and non-TT traffic, and conflicts among TT traffic flows themselves. The first issue is addressed through the residence-time mechanism combined with standard TSN features. Specifically, TT packets avoid blocking from nonTT packets via IEEE 802.1Qbu frame preemption or IEEE 802.1Qbv guard-band mechanisms. However, blocking from other TT packets persists. In an asynchronous environment, data flows originating from different sources operate in independent time domains. As these flows converge on a shared inter-satellite link e, their relative arrival times drift. Consequently, packets from different flows may arrive simultaneously, leading to resource contention. We define the overlap degree nτe as the number of scheduled flows originating from distinct source nodes and traversing link e in time slot τ . nτe = |{si | fi ∈ F, e ∈ pτi , fi is scheduled in slot τ }| . (12) 1) Overlap and Network Calculus Modeling: To rigorously quantify the physical jitter caused by these collisions, we must identify the effective interference. Crucially, TT flows originating from the same source node are inherently serialized at the ingress interface and do not collide with each other. Collisions only occur between flows from different sources. For a target flow fi on link e, the set of effective competing τ flows is denoted as Oi,e = {fj | e ∈ pτj , sj ̸= si }. The number τ τ of effective interfering flows is ki,e = |Oi,e |. We employ network calculus to derive the WCD. In the worst-case asynchronous scenario, packets from all flows in τ Oi,e may arrive simultaneously at the switch egress port. The aggregate arrival curve α(t) for these interfering flows is bounded by their collective burst size: X α(t) = Lj + ρagg · t, (13) τ fj ∈Oi,e
P where Lj is the packet length and ρagg = fj ∈Oτ (Lj /Tj ) i,e represents the aggregate average arrival rate. Since TT flows are served strictly by the physical link bandwidth Be , the service curve β(t) is linear: β(t) = Be · t.
(14)
2) Jitter Bound Derivation: The delay bound is defined as the maximum horizontal deviation between α(t) and β(t). For a packet of flow fi , the WCD occurs when it is processed last among the contending burst. We define the link-level worstcase jitter on link e in time slot τ , denoted as W CDeτ (nτe ), as: P τ Lj X fj ∈Oi,e τ τ = Cj,e , (15) W CDe (ne ) = Be τ fj ∈Oi,e
where Cj,e = Lj /Be is the transmission time. To ensure a strictly deterministic upper bound independent of specific flow lengths in the set, we simplify this as: W CDeτ (nτe ) ≤ (nτe − 1) · Cmax,e ,
(16)
6
where nτe is the overlap degree, i.e., the number of distinctsource flows on link e, and Cmax,e is the maximum possible transmission time of any TT frame on link e. This W CDeτ (nτe ) represents the unavoidable collisioninduced jitter contributed by by link e in slot τ . Although this jitter is not part of the target e2e delay enforced by the residence-time mechanism, it consumes the available deadline margin. Therefore, jitter along routing path P the cumulative target τ τ pτi must satisfy . Cone∈pτi W CDe (ne ) ≤ Di − Di τ sequently, minimizing the overlap degree ne is critical for deterministic transmission.
b) Priority 2 (P2 ): Minimize Collision Intensity: Subject to maintaining the optimal schedulability J1⋆ , denoting the optimal value of Eq. (22), we minimize the maximum overlap degree across all links. To linearize the Min-Max objective (min max nτe ), we introduce an auxiliary integer variable z. The second-stage objective is min J2 ≜ z, subject to nτe ≤ z, and
yi = J1⋆ .
(24) (25)
fi ∈F
The optimization goal is to maximize the schedulability while minimizing the overlap degree, so as to suppress collision-induced jitter. We define two sets of binary decision variables: if flow fi uses path p ∈ Piτ in slot τ, otherwise.
( 1, yi = 0,
∀τ ∈ T , ∀e ∈ Lτ , X
C. Optimization Framework
( 1, xτi,p = 0,
(23)
if flow fi is scheduled, if flow fi is unscheduled.
(17)
(18)
In summary, the overall objective can be expressed as a lexicographic optimization: lex max J1 (y), −J2 (x) . (26) x,y
2) Maximum Delay Constraint: Since the target e2e delay Ditarget serves as a baseline and does not account for asynchronous collisions, a safety margin must be reserved for collision-induced jitter. Therefore, the sum of the baseline delay and the cumulative WCD along the path must not exceed the deadline: X Ditarget + W CDeτ (nτe ) ≤ Di , ∀fi ∈ F, ∀τ ∈ T . (27) e∈pτi
Here, e∈pτ W CDeτ (nτe ) represents the maximum collisioni induced jitter caused by link overlaps along the path. 3) Baseline Latency Consistency Constraint: The residence-time mechanism assigns a baseline e2e latency Ditarget for each scheduled flow. Eq. (10) enforces this baseline delay, while the actual packet delay may additionally include bounded collision-induced jitter. 4) Path Uniqueness Constraint: To ensure routing consistency, each scheduled flow is assigned exactly one path per time slot: X xτi,p = yi , ∀fi ∈ F, ∀τ ∈ T . (28) P
Let δe,p be a binary parameter, where δe,p = 1 if link e belongs to path p, and 0 otherwise. Let Vsrc denote the set of source nodes associated with the flow set F. To express the source-level overlap degree in terms of the path selection variables, we introduce an auxiliary binary variable ( 1, if source s occupies link e in slot τ, τ us,e = (19) 0, otherwise, for all s ∈ Vsrc , e ∈ Lτ , and τ ∈ T . Here, source s occupies link e if at least one scheduled flow originating from s traverses e in slot τ . Then, the overlap degree on link e in slot τ can be written as X nτe = uτs,e , ∀e ∈ Lτ , ∀τ ∈ T . (20) s∈Vsrc
To link uτs,e with the path selection variables, we impose uτsi ,e ≥ xτi,p · δe,p , ∀fi ∈ F, ∀p ∈ Piτ , ∀e ∈ Lτ , ∀τ ∈ T .
(21)
1) Objective Function: we formulate a hierarchical optimization problem with priority order P1 ≻ P2 . a) Priority 1 (P1 ): Maximize Schedulability: Our primary goal is to maximize the total number of scheduled TT flows. The objective function is: max J1 ≜
X fi ∈F
yi .
(22)
p∈Piτ
5) Bandwidth Constraint: The aggregated bandwidth of all scheduled TT flows traversing a specific link must not exceed the link’s bandwidth capacity. X X Li ≤ Be , ∀e ∈ Lτ , ∀τ ∈ T . (29) xτi,p · δe,p · Ti τ i∈F p∈Pi
6) Buffer Capacity Constraint: Satellites employ a storeand-forward strategy, where insufficient buffer capacity in any time slot τ inevitably leads to packet loss. Although dedicated buffer spaces can be allocated for TT traffic to isolate it from non-TT traffic interference, contention persists among concurrent TT flows occupying the shared TT-specific buffer space within each time slot. To prevent buffer overflow, we impose an upper bound on the residence time at each hop: max ∆tτi,v ≤ Tbuf f er ,
∀fi ∈ F, ∀v ∈ pτi ,
(30)
max where Tbuf f er represents the maximum duration a packet can be buffered at a switch port.
7
Time slot
Time slot
Fig. 4: Example of Cross-Time-Slot Transmission.
7) Minimum Residence Time Constraint: Physically, a packet cannot be processed faster than the hardware limit. Therefore, the allocated residence time must be lower-bounded by the processing delay, regardless of whether collisions occur, ∆tτi,vj ≥ dproc ,
∀fi ∈ F, ∀vj ∈ pτi .
(31)
V. A LGORITHM D ESIGN A. Heuristic Strategy: Iterative Layering Since the formulated CRT scheduling problem is NP-Hard, we propose a heuristic algorithm CRT-Fast. Unlike simple greedy approaches that schedule flows strictly one-by-one, CRT-Fast adopts a layer-by-layer superposition strategy. The core idea is to decompose the complex global optimization into a sequence of simpler sub-problems. In each layer, we solve a constrained version of the ”Maximum Independent Set” problem: finding the maximum subset of remaining flows that can be added to the network without conflicting with each other and without violating the deadlines of already scheduled flows. This strategy naturally controls the collision intensity: Layer 1: We select the maximum set of edge-disjoint flows. These form the base layer (ne = 1, W CD = 0). • Layer k: We select the next batch of edge-disjoint flows and superimpose them onto the existing schedule. This increases the overlap degree ne by at most 1 per layer, ensuring the interference grows gradually and predictably. • Temporal Consistency: When scheduling flow fi in slot τ , we prioritize reusing the path pτi −1 from the previous slot. If pτi −1 remains valid in the current topology and satisfies constraints, we select it immediately. This avoids unnecessary path switching during topology handovers.
1) Implicit Backup Path: Unlike traditional fault tolerance schemes that reserve dedicated redundant resources, which would increase collision intensity nτe and worsen jitter, we adopt an efficient implicit backup approach. As illustrated in Fig. 4, for a flow fi in the current time slot τ : The primary path is the optimal path selected for slot τ . The backup path is essentially the pre-calculated primary path for the next time slot τ + 1. Since the backup path is intended for the future, it does not actively consume bandwidth or contribute to the overlap degree (nτe ) in the current slot, thus preserving the low-jitter performance of our collision-tolerant mechanism. 2) Switching Mechanism and Path Continuity: During the transition phase near the end of slot τ , if the primary link becomes unstable or disconnects, the switch immediately redirects packets to the backup path. This ensures continuous data flow. To support this mechanism efficiently, our scheduling strategy enforces a principle of path continuity. When scheduling for a new time slot τ , the system prioritizes keeping the path unchanged from the previous slot (pτ = pτ −1 ) whenever the topology allows. This reduces the frequency of switching paths and the risk of transient congestion caused by path changes.
•
B. Handling Dynamic Topology: Seamless Handover While the discretized time-slot model (Gτ ) effectively handles intra-slot stability, LEO networks face critical challenges during the transition between time slots. As satellites move, ISLs may break, causing packet loss if the flow path is not updated instantaneously. To mitigate this, we propose a seamless handover strategy based on path lookahead, which acts as a guiding principle for our scheduling algorithm.
C. Algorithm Description Main Framework (Alg. 1): The main algorithm manages the lifecycle of the scheduling process. It maintains a set of unscheduled flows and the global network state (overlap counters nτe ). The process consists of two phases: 1) Iterative Superposition: In each iteration, Alg. 1 calls the subroutine Alg. 2 to identify the best set of flows for the current layer. If a non-empty set is returned, these flows are committed to the schedule, and the per-link source sets together with the corresponding overlap counters are updated accordingly. This loop continues until no more flows can be scheduled. 2) Deterministic Parameter Calculation: Once the slot-level paths of a flow are finalized, the post-processing stage computes a common target delay and the corresponding per-hop residence times over its active time slots. Specifically, algorithm first evaluates the path delay in each slot and sets the common baseline target delay to the maximum among them. It then computes the slot-dependent slack as the difference between this common baseline
8
Algorithm 1: CRT-Fast algorithm
Algorithm 2: Subroutine: FindMaxFeasibleIS
Input: Gτ , Flow set F, Candidate path sets {Piτ } Output: Scheduled Paths P, Residence Times ∆t /* 1. Initialization */ 1 Initialize P ← ∅, Unscheduled Set U ← F τ τ 2 Initialize Global Link Counters ne ← 0 for all e ∈ L τ 3 Initialize SrcOnLink[e] ← ∅, ∀e ∈ L /* 2. Layer-by-Layer Scheduling */ 4 while U ̸= ∅ do 5 Slayer ← FindMaxFeasibleIS(U, P, nτe , SrcOnLink, Pτ −1 ) 6 if Slayer == ∅ then 7 break // Network saturated, stop iteration 8 end /* Commit Layer and Update Global State */ 9 foreach (fi , p) ∈ Slayer do 10 P[fi ] ← p 11 Remove fi from U 12 foreach e ∈ p do 13 if si ∈ / SrcOnLink[e] then 14 SrcOnLink[e] ← SrcOnLink[e] ∪ {si } 15 nτe [e] ← nτe [e] + 1 16 end 17 end 18 end 19 end /* 3. Post-Processing: Cross-Slot Residence-Time Allocation */ 20 foreach fi ∈ P do // Compute the path delay in each slot 21 foreach τ ∈ Ti do 22 p ← P[fi , τ ]P P τ + v∈p dproc,v 23 Dfτ ixed,i ← e∈p Pdlink,i,e τ τ 24 W CDtotal,i ← e∈p (ne − 1)Cmax,e 25 end // Common baseline delay over all slots 26 Ditarget ← maxτ ∈Ti Dfτ ixed,i // Allocate slot-dependent slack to each hop 27 foreach τ ∈ Ti do 28 p ← P[fi , τ ] 29 Slackiτ ← Ditarget − Dfτ ixed,i τ 30 if Ditarget + W CDtotal,i > Di then 31 mark fi infeasible 32 break 33 end 34 foreach v ∈ p do Slackτ 35 tτextra,i,v ← |p| i // |p| = |{v | v ∈ pτi }| τ τ 36 ∆ti,v ← dproc,v + textra,i,v 37 end 38 end 39 end 40 return P, ∆t
Input: Unscheduled U, Scheduled P, Global Counters nτe , Per-Link Source Sets SrcOnLink, Previous Paths Pτ −1 Output: Layer Subset Slayer Slayer , LL ← ∅ Initialize LinkCounts[e] ← 0, ∀e ∈ Gτ τ 3 Initialize T mpSrc[e] ← ∅, ∀e ∈ G /* 1. Conflict Degree Calculation */ 4 foreach fi ∈ U do S 5 foreach e ∈ p∈P τ [1:K] p do i 6 if si ∈ / T mpSrc[e] then 7 T mpSrc[e] ← T mpSrc[e] ∪ {si } 8 LinkCounts[e] ← LinkCounts[e] + 1 9 end 10 end 11 end 12 foreach fi ∈ U do P 13 (cdi , p⋆i ) ← minp∈Piτ [1:K] e∈p (LinkCounts[e] − 1) 14 end 15 Sort U by cdi ↑ (Di tie) /* 2. Greedy Selection */ 16 foreach fi ∈ U do 17 pbest ← ∅; p ← Pτ −1 [fi ] 18 if p ̸= ∅ and IsPathValid(p, Gτ ) and p ∩ LL = ∅ and CheckGlobalFeasibility(fi , p, P ∪ Slayer , nτe , SrcOnLink) then 19 pbest ← p 20 end 21 if pbest = ∅ then 22 p ← p⋆i 23 if p ̸= ∅ and p ∩ LL = ∅ and CheckGlobalFeasibility(fi , p, P ∪ Slayer , nτe , SrcOnLink) then 24 pbest ← p 25 end 26 end 27 if pbest = ∅ then 28 foreach p ∈ Piτ [1:K] do 29 if p = p⋆i or p ∩ LL ̸= ∅ or CheckGlobalFeasibility(fi , p, P ∪ Slayer , nτe , SrcOnLink)==False then 30 continue 31 end 32 pbest ← p; break 33 end 34 end 35 if pbest ̸= ∅ then 36 Add (fi , pbest ) to Slayer 37 LL ← LL ∪ {e | e ∈ pbest } 38 end 39 end 40 return Slayer 1
2
greedy rule to mitigate collision-induced jitter. and the current slot’s delay, and evenly distributes the slack across all hops on the selected path to obtain the final residence times. CheckGlobalFeasibility validates local path and resource feasibility during path selection, while the exact cross-slot residence-time allocation is finalized in this post-processing stage. Finding Feasible Independent Set (Alg. 2): This subroutine constructs the current layer Slayer using a minimum-conflict
1) Conflict-degree ordering. For each unscheduled flow fi , we estimate link popularity via LinkCounts[e], i.e., the number of unscheduled flows whose candidate paths traverse linkPe. For any candidate path p, its conflict score is pc(p) = e∈p (LinkCounts[e]−1). We define the flow conflict degree as cd(fi ) = minp∈Piτ pc(p) and record p⋆i = arg min pc(p). Flows are processed in ascending cd(·) (deadline Di breaks ties). For consistency with the overlap definition, the link popularity used in conflict-
9
degree estimation is accumulated at the source level, i.e., multiple flows from the same source contribute only once to a given link. 2) Path continuity. To support seamless handover (Sec. V-B), we first reuse the previous-slot path pprev if it remains valid, layer-conflict-free, and globally feasible. 3) Low-conflict path selection. If pprev is not eligible, we try p⋆i first; otherwise we scan the remaining candidates and select the first path that satisfies (i) intra-layer edge-disjointness and (ii) CheckGlobalFeasibility under updated nτe . The procedure CheckGlobalFeasibility tentatively inserts a candidate path p of flow fi into the current partial schedule P ∪ Slayer and updates the overlap counters according to distinct source nodes. It then checks whether the candidate flow and all already scheduled flows sharing at least one link with p remain feasible. In particular, it recomputes the cumulative WCD, derives the corresponding target delay Ditarget = Di − W CDtotal , and verifies that the resulting slack is non-negative and that the per-hop residence times satisfy max the buffer bound Tbuf f er 4) Overlap accounting. When computing WCD, only interference from distinct sources is counted due to source serialization. D. Complexity Analysis The computational complexity of CRT-Fast is determined by the iterative layering process executed across |T | discrete time slots. In the worst-case scenario characterized by dense conflicts, each layer admits only a single flow, resulting in |F | iterations per slot. Within each iteration, computing conflict degrees requires aggregating link popularity over the K candidate paths and evaluating the minimum path-conflict score for each flow, which costs O(|F |·K·Lpath +|F| log |F |). Subsequently, the path selection evaluates up to K candidates per flow, and the bottleneck remains CheckGlobalFeasibility, which may validate against up to O(|F|) previously scheduled flows along a path of length Lpath . Therefore, the overall worst-case time complexity is bounded by O(|T | · |F |2 · K · Lpath ). Although the path continuity strategy significantly reduces the average execution time by avoiding redundant searches in stable topologies, this polynomial worst-case bound guarantees that the algorithm remains scalable for largescale LEO satellite networks with thousands of flows. VI. P ERFORMANCE E VALUATION In this section, we evaluate the performance of the proposed CRT-Fast algorithm on a simulated LEO satellite network. A. Experimental Setup Simulation Environment: The simulations were conducted using the Iridium and the Starlink constellation. The Iridium constellation is a representative polar-orbit satellite network consisting of 6 orbit planes with 11 satellites per plane, while the Starlink constellation consists of 1,584 satellites in 72
orbits. The dynamic network topology is discretized into a sequence of m = 10 time slots, with each slot duration set to 10 seconds. To reflect a realistic multi-service network scenario, we assume the deterministic traffic operates within a dedicated network slice. Accordingly, the ISLs are configured with a bandwidth of 100 Mbps reserved specifically for TT flows. Traffic Generation and Candidate Paths: TT flows are generated by randomly selecting source-destination pairs from the satellite nodes. Each flow has a fixed frame size of 1,500 Bytes and a fixed period of 10 ms. The deadline is defined as Di = min(αdphy , dphy + ∆buf , Dmax ), i i where dphy is the shortest-path propagation delay. We set i (α, ∆buf , Dmax ) = (1.5, 30 ms, 100 ms) for Iridium and (2.0, 80 ms, 500 ms) for Starlink. Candidate paths are generated using Yen’s K-shortest simple paths algorithm [25], with K = 5. Baseline Algorithms: To validate the effectiveness of CRTFast, we compare it against four representative baselines: • DSTMR [26]: It combines spatio-temporal routing with conservative resource reservation under the same parameter setting as CRT-Fast. • Strict Non-Overlapping: A conservative lower-bound baseline for schedulability. It enforces a strict nonoverlapping constraint (nτe ≤ 1) and rejects any flow that cannot find a conflict-free path. • Shortest Path First (SPF): A static-routing baseline. It selects the single shortest path for each flow. • Load-Aware Greedy (LAG): A representative dynamicrouting greedy baseline. It sequentially schedules flows by selecting the path with the minimum current congestion cost (Best-Fit). All algorithms are evaluated on the same topology snapshots and TT flow sets. Each experiment is repeated over 5 independent runs with different random seeds, and all reported results are averaged across runs. B. Performance Analysis Schedulability Evaluation: Fig. 5 shows the average scheduling success rate as the traffic load increases on Iridium. CRT-Fast consistently achieves the highest schedulability, maintaining 100% admission at light loads and 94.5% under the heaviest tested load. In contrast, the Strict NonOverlapping drops rapidly as the load increases, because fully conflict-free routing severely limits the feasible solution space. SPF performs reasonably well at light loads but degrades more quickly at higher loads due to its rigid shortest-path selection. LAG improves over SPF by using dynamic routing to alleviate local congestion, but it still performs worse than CRT-Fast, especially in the high-load regime. The DSTMR degrades even faster because its conservative reservation-based routing exhausts available resources early under increasing load. The results show that CRT-Fast improves schedulability more effectively than strict conflict avoidance, rigid shortest-path routing, greedy dynamic routing, or conservative reservationbased scheduling.
10
& 5 7 ) D V W / $ * 6 3 ) ' 6 7 0 5 6 W U L F W
1 X P E H U R I 7 7 ) O R Z V
& 5 7 ) D V W ' 6 7 0 5 / $ * 6 3 )
/ L Q N ' H O D \ - L W W H U P V
6 F K H G X O D E L O L W \ 5 D W H
7 L P H 6 O R W / H Q J W K V
& 5 7 ) D V W / $ * 6 3 )
/ L Q N 2 Y H U O D S ' H J U H H
Fig. 8: Distribution of link-induced jitter under conflict-free scheduling.
& 5 7 ) D V W / $ * 6 3 )
/ L Q N 2 Y H U O D S ' H J U H H
(a) Iridium
(b) Starlink
& 5 7 ) D V W / $ * 6 3 )
1 X P E H U R I 7 7 ) O R Z V (a) Iridium
: & ' - L W W H U P V
: & ' - L W W H U P V
Fig. 6: CDF of link overlap degrees (ne ).
& 5 7 ) D V W / $ * 6 3 )
1 X P E H U R I 5 H V F K H G X O H G ) O R Z V
& ' )
& ' )
Fig. 5: Average flow scheduling success rate.
6 3 ) / $ * & 5 7 ) D V W
7 L P H 6 O R W , Q G H [
Fig. 9: Path stability analysis under dynamic LEO topology handovers.
1 X P E H U R I 7 7 ) O R Z V (b) Starlink
Fig. 7: Distribution of collision-induced jitter. Conflict Mitigation and Jitter Analysis: Fig. 6 and Fig. 7 examine the relationship between link overlap and collisioninduced jitter. Taking Iridium as an example (Fig. 6a), CRTFast yields the most concentrated overlap distribution: more than 85% of links remain at ne = 1, and the maximum overlap is limited to 3. In comparison, SPF and LAG exhibit longer tails, with overlap degrees reaching 5 and 4, respectively. This indicates that CRT-Fast is more effective at suppressing local collision intensity. Fig. 7a shows that the jitter distribution follows the same trend. Because the WCD grows with the overlap degree, the tighter overlap control achieved by CRTFast leads to lower median jitter and smaller variance. These results confirm that iterative layering can reduce collisioninduced jitter while preserving high schedulability. Since Strict Non-Overlapping enforces fully conflict-free routing, its overlap degree and collision-induced jitter are identically zero. Link-Induced Jitter Analysis: To isolate link-delayinduced jitter from collision-induced jitter, we construct a conflict-free traffic setting with 200 TT flows in the Iridium constellation, where no two flows share transmission links in the same slot. Under this setting, the accumulated WCD is zero, and the remaining delay variation is caused mainly by
dynamic link delays and route changes across slots. As shown in Fig. 8, CRT-Fast keeps the link-induced jitter nearly zero across all tested slot lengths, while others exhibit substantially larger jitter and wider distributions. Path Stability under LEO Handovers: To evaluate robustness against topology dynamics, we simulated 11 consecutive time slots with 400 flows on Iridium. In each slot, 3% of links were randomly disconnected and 15% experienced delay perturbations. We measure stability by the number of rescheduled flows. As shown in Fig. 9, CRT-Fast requires the fewest path updates on average, with 57.3 rescheduled flows per slot. The shaded region indicates ±1 standard deviation. This improvement is mainly due to the path continuity mechanism, which first attempts to reuse the previous-slot path whenever it remains valid. In contrast, LAG and SPF independently reoptimize routing in each slot, making them more sensitive to local topology changes. CRT-Fast reduces rescheduling by about 38.7% compared with LAG and 62.7% compared with SPF, indicating stronger path stability under frequent LEO handovers. End-to-End Delay Performance: Fig. 10 reports the normalized e2e delay of scheduled flows on Iridium. Compared with SPF and LAG, CRT-Fast exhibits a slightly wider delay range. This increase does not indicate degraded feasibility, rather, it reflects that CRT-Fast admits more hard-to-schedule flows that require longer paths or traverse more congested regions of the network. In contrast, SPF and LAG tend to reject such flows earlier, which leads to a lower average delay among only the schedulable flows. Despite the marginal
1 X P E H U R I 7 7 ) O R Z V
6 F K H G X O D E L O L W \ 7 L P H F R V W
.
.
.
.
.
.
.
1 X P E H U R I ) O R Z V
.
. .
7 L P H F R V W V
& 5 7 ) D V W / $ * 6 3 )
6 F K H G X O D E L O L W \
1 R U P D O L ] H G ' H O D \ ' H O D \ ' H D G O L Q H
11
Fig. 12: Scalability performance of the CRT-Fast.
Fig. 10: Normalized End-to-End Delay Performance.
6 F K H G X O D E L O L W \ 7 L P H F R V W
' H D G O L Q H P V (a) Iridium
6 F K H G X O D E L O L W \ 7 L P H F R V W
7 L P H F R V W V
6 F K H G X O D E L O L W \
7 L P H F R V W V
6 F K H G X O D E L O L W \
VII. R ELATED W ORK
' H D G O L Q H P V (b) Starlink
Fig. 11: Performance of CRT-Fast with different e2e deadline.
increase in normalized delay, all flows scheduled by CRTFast remain within their deadlines. These results indicate that CRT-Fast improves schedulability while effectively utilizing the available delay slack. Impact of End-to-End Deadline on Scheduling: We fix the number of flows at 1,000 and vary the e2e deadline in both Iridium and Starlink constellations. As shown in Fig. 11a for Iridium and Fig. 11b for Starlink, schedulability is improved as the deadline becomes more relaxed. In Iridium, the scheduling success rate increases from 32.4% at 32 ms to 98.0% at 128 ms, and reaches 100% at 320 ms and above. In Starlink, it increases from 63.8% at 320 ms to 98.3% at 512 ms, and reaches 100% at 576 ms and above. These results show that tighter deadlines significantly restrict feasible routing and residence-time allocation, while more relaxed deadlines provide greater scheduling flexibility. Scalability Analysis: We stress-test CRT-Fast on Starlink by increasing the number of flows from 1,000 to 10,000. As shown in Fig. 12, CRT-Fast maintains strong schedulability over a wide range of large-scale traffic loads, achieving 98.2% at 1,000 flows and still admitting 66.7% of flows at 10,000. This result demonstrates that the proposed collision-tolerant scheduling framework remains effective even in very large and dense LEO scheduling scenarios. Meanwhile, the algorithm successfully scales to all tested problem sizes, showing that CRT-Fast can handle large candidate sets and complex topology-constrained scheduling instances on a megaconstellation.
Terrestrial deterministic transmission: Deterministic transmission in terrestrial networks has been studied primarily in the context of TSN. Early work formulates routing and scheduling for time-triggered traffic as constraint-solving problems, such as SMT, ILP, or related optimization models, in order to compute feasible or optimal schedules [27], [28]. To improve support for traffic with timing guarantees, IEEE 802.1Qch introduces Cyclic Queueing and Forwarding (CQF) [29], and subsequent studies further refine CQF-based mechanisms for better delay control and resource utilization [30], [31]. More recently, learning-based methods such as DeepScheduler and TTDeep explore deep reinforcement learning to accelerate scheduling and improve schedulability without relying entirely on handcrafted rules [32], [33]. Although these methods are effective in wired TSN environments, they are generally developed under two assumptions: accurate network-wide time synchronization and relatively stable topologies. These assumptions are difficult to satisfy in LEO satellite networks, where links are timevarying, handovers are frequent, and path availability changes continuously. Therefore, terrestrial deterministic transmission techniques cannot be directly applied to LEO scenarios. Deterministic transmission in LEO satellite networks: Existing studies on time-sensitive transmission in LEO satellite networks mainly focus on delay reduction, routing adaptation, and reliability enhancement. For example, CPF [34] and TSNMCQ [35] improve queueing and forwarding mechanisms to provide bounded service delay for time-sensitive flows. Other studies investigate delay-aware routing strategies for dynamic satellite topologies [36], [37]. To improve robustness under topology variations and link failures, FastTS [38] introduces a fault-tolerant heuristic scheduling strategy, while Lai et al. [39] develop a resilient routing mechanism that improves route restoration under topology fluctuations. Above all, the existing LEO-oriented approaches still leave two issues insufficiently addressed. First, they mainly focus on delay reduction or routing robustness, but explicitly controlling collision-induced delay jitter. Second, they usually do not model the effect of imperfect time synchronization across different source clock domains, which is a fundamental challenge in asynchronous LEO environments. In contrast, our work jointly considers topology dynamics, asynchronous collisions,
12
and imperfect synchronization, and develops a residencetime-based collision-tolerant scheduling framework to provide bounded jitter and deterministic transmission. VIII. C ONCLUSION We studied deterministic transmission in asynchronous LEO satellite networks and proposed CRT, a deterministic transmission framework that operates without requiring global time synchronization. By introducing a residence-time mechanism based on local clocks, CRT compensates for linkdelay variations caused by topology dynamics and stabilizes the e2e delay. To address inevitable asynchronous collisions among flows from different sources, we further developed a collision-tolerant scheduling model that improves schedulability while bounding collision-induced jitter under deadline and resource constraints. We showed that the scheduling problem is NP-hard and CRT-Fast, an efficient heuristic algorithm that combines iterative layering with path continuity. Simulations on Iridium and Starlink constellations show that CRT-Fast achieves better schedulability, lower jitter, and stronger path stability than compared baselines. CRT provides a scalable solution for time-sensitive services in dynamic LEO satellite networks. R EFERENCES [1] F. Michel, M. Trevisan, D. Giordano, and O. Bonaventure, “A first look at starlink performance,” in Proceedings of the 22nd ACM Internet Measurement Conference, 2022, pp. 130–136. [2] S. R. Pratt, R. A. Raines, C. E. Fossa, and M. A. Temple, “An operational and performance overview of the IRIDIUM low earth orbit satellite system,” IEEE Communications Surveys, vol. 2, no. 2, pp. 2–10, 1999. [3] Y. Henri, “The oneweb satellite system,” in Handbook of Small Satellites: Technology, Design, Manufacture, Applications, Economics and Regulation, 2020, pp. 1091–1100. [4] P. Popovski, F. Chiariotti, K. Huang, A. E. Kalør, M. Kountouris, N. Pappas, and B. Soret, “A perspective on time toward wireless 6G,” Proceedings of the IEEE, vol. 110, no. 8, pp. 1116–1146, 2022. [5] H. Yu, T. Taleb, K. Samdanis, and J. Song, “Toward supporting holographic services over deterministic 6G integrated terrestrial and nonterrestrial networks,” IEEE Network, vol. 38, no. 1, pp. 262–271, 2023. [6] Z. Wang, H. Yao, T. Mai, Z. Li, and C. P. Chen, “Learning-driven swarm intelligence: Enabling deterministic flows scheduling in LEO satellite networks,” IEEE Transactions on Mobile Computing, 2024. [7] H. Sun, H. Zhang, H. Ma, and V. C. Leung, “Joint scheduling, computing, and load balancing for time sensitive traffic in sdn-enabled spaceair-ground integrated 6G networks: A federated reinforcement learning approach,” IEEE Transactions on Mobile Computing, 2025. [8] Z. Xiao, J. Yang, T. Mao, C. Xu, R. Zhang, Z. Han, and X.-G. Xia, “LEO satellite access network (LEO-SAN) toward 6G: Challenges and approaches,” IEEE Wireless Communications, vol. 31, no. 2, pp. 89–96, 2022. [9] S. Ma, Y. C. Chou, H. Zhao, L. Chen, X. Ma, and J. Liu, “Network characteristics of LEO satellite constellations: A starlink-based measurement from end users,” in Proceedings of the IEEE INFOCOM 2023-IEEE Conference on Computer Communications, 2023, pp. 1–10. [10] X. Cao and X. Zhang, “Satcp: Link-layer informed TCP adaptation for highly dynamic LEO satellite networks,” in Proceedings of the IEEE INFOCOM 2023 -IEEE Conference on Computer Communications, 2023, pp. 1–10. [11] W. Tian, C. Gu, M. Guo, S. He, J. Kang, D. Niyato, and J. Chen, “Largescale deterministic networks: Architecture, enabling technologies, case study, and future directions,” IEEE Network, vol. 38, no. 4, pp. 284–291, 2024. [12] S. Wang, B. Wu, C. Zhang, Y. Huang, T. Huang, and Y. Liu, “Largescale deterministic IP networks on CENI,” in Proceedings of the IEEE INFOCOM 2021-IEEE Conference on Computer Communications Workshops, 2021, pp. 1–6.
[13] Y. Hu, B. Guo, C. Yang, and Z. Han, “Time-deterministic networking for satellite-based internet-of-things services: Architecture, key technologies, and future directions,” IEEE Network, 2024. [14] N. Finn, “Introduction to time-sensitive networking,” IEEE Communications Standards Magazine, vol. 2, no. 2, pp. 22–28, 2018. [15] A. Nasrallah, A. S. Thyagaturu, Z. Alharbi, C. Wang, X. Shao, M. Reisslein, and H. ElBakoury, “Ultra-low latency (ULL) networks: The IEEE TSN and IETF detnet standards and related 5G ull research,” IEEE Communications Surveys & Tutorials, vol. 21, no. 1, pp. 88–145, 2018. [16] H. Kopetz and G. Bauer, “The time-triggered architecture,” Proceedings of the IEEE, vol. 91, no. 1, pp. 112–126, 2003. [17] IEEE Std 802.1AS, “IEEE Standard for Local and Metropolitan Area Networks—Timing and Synchronization for Time-Sensitive Applications,” 2020. [18] IEEE Std 1588, “IEEE Standard for a Precision Clock Synchronization Protocol for Networked Measurement and Control Systems,” Jun. 2020. [19] IEEE Std 802.1Qbv, “IEEE Standard for Local and Metropolitan Area Networks—Bridges and Bridged Networks—Amendment 25: Enhancements for Scheduled Traffic,” Mar. 2016. [20] J. Pan, J. Zhao, and L. Cai, “Measuring a low-earth-orbit satellite network,” in Proceedings of the IEEE 34th Annual International Symposium on Personal, Indoor and Mobile Radio Communications, 2023, pp. 1–6. [21] X. Chen and Z. Luo, “Asynchronous interference mitigation for leo multi-satellite cooperative systems,” IEEE Transactions on Wireless Communications, 2024. [22] Z. Li, H. Wan, Y. Deng, X. Zhao, Y. Gao, X. Song, and M. Gu, “Time-triggered switch-memory-switch architecture for time-sensitive networking switches,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 39, no. 1, pp. 185–198, 2018. [23] IEEE Std 802.1Qbu, “IEEE Standard for Local and Metropolitan Area Networks—Bridges and Bridged Networks—Amendment 26: Frame Preemption,” 2016. [24] J. Vygen, “Np-completeness of some edge-disjoint paths problems,” Discrete Applied Mathematics, vol. 61, no. 1, pp. 83–90, 1995. [25] J. Y. Yen, “Finding the k shortest loopless paths in a network,” management Science, vol. 17, no. 11, pp. 712–716, 1971. [26] X. Jiang, Y. Huang, J. Li, H. He, S. Chen, F. Yang, and J. Yang, “Spatio-temporal routing, redundant coding and multipath scheduling for deterministic satellite network transmission,” IEEE Transactions on Communications, vol. 71, no. 5, pp. 2860–2875, 2023. [27] A. A. Atallah, G. B. Hamad, and O. A. Mohamed, “Routing and scheduling of time-triggered traffic in time-sensitive networks,” IEEE Transactions on Industrial Informatics, vol. 16, no. 7, pp. 4525–4534, 2020. [28] E. Schweissguth, P. Danielis, D. Timmermann, H. Parzyjegla, and G. Mühl, “ILP-based joint routing and scheduling for time-triggered networks,” in Proceedings of the 25th International Conference on RealTime Networks and Systems, 2017, pp. 8–17. [29] IEEE Std 802.1Qch, “IEEE Standard for Local and Metropolitan Area Networks—Bridges and Bridged Networks—Amendment: Cyclic Queuing and Forwarding,” 2017. [30] D. Yang, Z. Cheng, W. Zhang, H. Zhang, and X. Shen, “Burstaware time-triggered flow scheduling with enhanced multi-CQF in timesensitive networks,” IEEE/ACM Transactions on Networking, vol. 31, no. 6, pp. 2809–2824, 2023. [31] J. Yan, W. Quan, X. Jiang, and Z. Sun, “Injection time planning: Making CQF practical in time-sensitive networking,” in Proceedings of the IEEE INFOCOM 2020 -IEEE Conference on Computer Communications, 2020, pp. 616–625. [32] X. He, X. Zhuge, F. Dang, W. Xu, and Z. Yang, “Deepscheduler: Enabling flow-aware scheduling in time-sensitive networking,” in Proceedings of the IEEE INFOCOM 2023 -IEEE Conference on Computer Communications, 2023, pp. 1–10. [33] H. Jia, Y. Jiang, C. Zhong, H. Wan, and X. Zhao, “Ttdeep: Timetriggered scheduling for real-time ethernet via deep reinforcement learning,” in Proceedings of the IEEE Global Communications Conference, 2021, pp. 1–6. [34] F. Wang, D. Wu, W. He, Z. Li, Q. Zhang, and H. Yao, “CPF: Bridging time-sensitive networks into large-scale LEO satellite networks,” in Proceedings of the International Wireless Communications and Mobile Computing, 2023, pp. 1–6. [35] X. Ma, S. Li, Z. Guan, J. Li, H. Sun, Y. Wang, and H. Guo, “Timesensitive networking mechanism aided by multilevel cyclic queues in LEO satellite networks,” Electronics, vol. 12, no. 6, p. 1357, 2023.
13
[36] F. Dong, Y. Zhang, G. Liu, H. Yu, and C. Sun, “Delay-sensitive service provisioning in software-defined low-earth-orbit satellite networks,” Electronics, vol. 12, no. 16, p. 3474, 2023. [37] S. Geng, S. Liu, Z. Fang, and S. Gao, “An optimal delay routing algorithm considering delay variation in the LEO satellite communication network,” Computer Networks, vol. 173, p. 107166, 2020. [38] G. Peng, S. Wang, T. Huang, F. Li, K. Zhao, Y. Huang, and Z. Xiong, “FastTS: Enabling fault-tolerant and time-sensitive scheduling in spaceterrestrial integrated networks,” IEEE Journal on Selected Areas in Communications, vol. 42, no. 12, pp. 3551–3565, 2024. [39] Z. Lai, H. Li, Y. Wang, Q. Wu, Y. Deng, J. Liu, Y. Li, and J. Wu, “Achieving resilient and performance-guaranteed routing in spaceterrestrial integrated networks,” in Proceedings of the IEEE INFOCOM 2023 -IEEE Conference on Computer Communications, 2023, pp. 1–10.