PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Lack of Periodicity of Walker Satellite Constellation Routing Tables

Chang-Sik Choi, François Baccelli

arXiv:2609.36566v1cs.ITcs.NImath.DSmath.IT

TL;DR

Prior analyses established a periodicity dichotomy for Walker constellation motion, but its implications for routing tables had not been established. This paper models deterministic, time-invariant routing tables as observations of the constellation flow and proves that their behavior follows the flow’s rational-versus-irrational speed-ratio dichotomy. In the irrational case, long-run route statistics can be evaluated as ensemble averages, providing a basis for metrics that disregard temporal fluctuations and initial conditions.

  • Problem

    Earlier work established periodicity properties of Walker constellation motion, but whether routing tables inherit that dichotomy remained uninvestigated.

    Source: §I · p. 1

  • Method

    The paper models deterministic, time-invariant routing tables, including relay labels and beamforming angles, as observables of the torus flow and uses an injectivity result to transfer its dichotomy.

    Source: §I · pp. 1–2, C. Routing Rules as Observables · p. 3

  • Results

    For rational speed ratios, routing tables have the flow’s period; for irrational ratios, they are non-periodic and their long-run averages converge to computable ensemble averages.

    Source: §I · p. 2, §V · p. 9

  • Takeaways & Limitations

    In the irrational case, ensemble averages provide universal route metrics that disregard temporal fluctuations and initial conditions.

    Source: §V · p. 9

    An irrational flow does not make every observable non-periodic; constant observables and observables depending only on Earth phase can remain periodic.

    Source: A. General Properties of Observables · p. 4

Abstract

from arXiv · show

In a referential that rotates with Earth, the dynamics of the configurations of satellites in a Delta Walker constellation can be analyzed as a dynamical system as a function of a translation on the torus. This paper extends this type of analysis to routing over a Walker constellation, leveraging fixed ground relays. It considers any deterministic, time-invariant routing rule on such a collection of satellites and relays. The main object of interest is the routing table associated with this rule, which specifies, for all source-destination pairs, a route made of satellites and relays between them, for instance the shortest, together with angular information on next hop at each step of the route, which is essential for beamforming in this context. The main result is that, for each such routing rule, the routing table inherits the dichotomy of the torus flow: when the ratio of the Earth-spin and satellite angular speeds is rational, the routing table process is periodic with the same period as the constellation. When it is irrational, the table is non periodic but admits ergodic long-run averages which can be computed as ensemble averages w.r.t. an explicit invariant measure. Simulations with mixed satellite--gateway greedy routing illustrate these findings in terms of both temporal and spectral properties of the Walker routing table time series. The paper also discusses how to define metrics that cope with such non periodic fluctuations when present. This is illustrated by a comparison of the round-trip times between two far away cities as offered by a Walker constellation using greedy routing on one side, and by the currently available terrestrial fiber on the other side. It is shown how ergodicity can be used to make this comparison between the time varying instantaneous round trip times of the constellation and the constant round trip time of the fiber network meaningful.

I. INTRODUCTION

The paper extends the known periodicity dichotomy of Walker constellation motion to routing tables, addressing whether routing processes inherit the constellation’s temporal structure. It establishes periodicity or non-periodicity according to the Earth-to-satellite speed ratio and uses long-run averages to compare time-varying constellation delays with terrestrial delays.

I. INTRODUCTION

  • The paper addresses a gap in routing research: prior schemes design specific rules, while their assumed exact topology periodicity was not examined; static stochastic-geometric models also miss temporal evolution for users on rotating Earth.Source: §I · p. 1
  • The paper formalizes mixed satellite–ground routing as observables of constellation flow, using shortest-path and greedy routing as admissible examples.Source: §I · p. 1
  • For irrational speed ratios, routing tables are non-periodic, while their long-term averages converge to computable limits for every initial constellation phase.For rational ratios, every routing process is periodic with a period dividing the constellation period; the routing table itself has exactly the constellation period.Source: §I · p. 2
  • A routing-table entry that includes relay labels, look angles, and angle rates determines the torus phase outside a null set, enabling the periodicity result for every deterministic, time-invariant rule.Source: §I · pp. 1–2
  • Discrete-event simulation and spectral analysis illustrate periodic routing tables in the rational case and non-periodicity with matching time and ensemble averages in the irrational case.Source: §I · p. 2
  • In the ergodic case, long-term average round-trip propagation delays between distant cities provide a basis for comparing time-varying constellation delays with terrestrial delays.Source: §I · p. 2

A. Constellation Flow

In the Earth-fixed frame, a Walker constellation is represented by a linear flow on a two-dimensional torus whose speeds are set by Earth rotation and satellite orbital motion. Its periodicity depends on the rationality of their speed ratio.

A. Constellation Flow

  • The Earth-fixed orbit and satellite phases evolve linearly on a torus, with the Earth’s sidereal rotation rate and satellites’ orbital angular speed setting the flow.Source: A. Constellation Flow · p. 2
  • The labelled constellation tracks satellite lattice sites as phases wrap around the torus, permuting labels so the labelled configuration is a well-defined function on the phase space.Source: A. Constellation Flow · p. 2
  • Alternatively, satellites can retain time-zero marks; this removes relabelling, and the results also hold using a full two-dimensional torus and its uniform measure.Source: A. Constellation Flow · p. 2
  • When the speed ratio is rational, the flow is periodic; when irrational, it is minimal and uniquely ergodic with the uniform invariant measure.Source: A. Constellation Flow · pp. 2–3

B. Ground Nodes and LOS Graph

The paper models satellites, gateways, and terminals through a time-varying line-of-sight graph, then treats routing tables as observations of the constellation flow. The table records relay identities and beamforming information along each route.

B. Ground Nodes and LOS Graph

  • The line-of-sight graph connects visible ground–satellite pairs and satellites with unobstructed inter-satellite paths, using Euclidean edge lengths; ground nodes have no direct edges between them.The analysis assumes enough satellites and gateways, and moderate enough ground-node latitudes, for the graph to remain connected at all times.Source: B. Ground Nodes and LOS Graph · p. 3

C. Routing Rules as Observables

  • An admissible mixed-relay rule is a deterministic, measurable, time-invariant function of the constellation configuration, selecting routes through satellite and gateway relays.Source: C. Routing Rules as Observables · p. 3
  • Each routing-table hop records the next relay’s label or gateway mark, its look angles, and the time derivatives of those angles.Source: C. Routing Rules as Observables · p. 3
  • The routing table is an observable of the torus flow: the current phase determines the trajectory and therefore the angle derivatives, while dropping angle information recovers the label-only route.Source: C. Routing Rules as Observables · p. 3

1) Shortest-Path Routing:

Shortest-path routing is constructed from the time-varying line-of-sight graph using tropical (min, +) operations. A fixed ordering resolves ties, making the resulting rule admissible.

1) Shortest-Path Routing:

  • The symmetric min-plus matrix of line-of-sight relay distances yields all shortest-path lengths through tropical powers, and terminal-to-relay distances extend those paths to terminals.Source: 1) Shortest-Path Routing · p. 3
  • When multiple shortest routes tie, selecting the least route under a fixed total ordering makes route selection measurable and the shortest-path strategy admissible.Source: 1) Shortest-Path Routing · p. 3

2) Greedy routing:

The greedy rule forwards over visible satellites and gateways to reduce central angle to the destination. A deterministic tie-break and outage route make the rule defined for every configuration.

2) Greedy routing:

  • At each step, forwarding selects the visible node closest to the destination in central angle among those that strictly reduce that angle.Ties are resolved deterministically.Source: 2) Greedy routing · pp. 3–4
  • If a greedy step reaches a node with no further neighbor, the rule returns a designated outage route.This completion ensures the rule is defined for every configuration.Source: 2) Greedy routing · p. 4

III. MAIN RESULTS

For observables of the constellation flow, rational speed ratio yields periodicity, while irrational ratio supports long-run averages under stated integrability conditions. Irrationality alone does not ensure that an observable is non-periodic.

A. General Properties of Observables

  • For rational ρ, every observable has period T⋆, and any minimal period divides T⋆, though it may be a proper divisor when the observable is not injective along the orbit.The constellation flow’s period is therefore a period of its observables, but observable non-injectivity can shorten the minimal period.Source: A. General Properties of Observables · p. 4
  • For irrational ρ, time averages of integrable observables converge to their ensemble averages for almost every initial phase.When the observable is bounded and the closure of its discontinuity set is Q-null, this convergence holds for every initial phase.Source: A. General Properties of Observables · p. 4
  • Irrational ρ does not preclude periodic observables: constants and observables depending only on θ̄t are periodic.Non-periodicity must be established from the observable’s properties rather than inferred from the flow’s irrationality alone.Source: A. General Properties of Observables · p. 4

B. The Routing Table as a Factor and a Measurable Conjugate of the Flow

A routing table is a measurable observable of the constellation flow, and its ground-anchored entries can recover the phase outside a null exceptional set. Route labels alone do not provide this phase-recovering factor structure.

B. The Routing Table as a Factor and a Measurable Conjugate of the Flow

  • The routing table’s finite entries form a measurable map between standard Borel spaces, making it an observable of the flow.Each entry contains a finite sequence of next-hop labels and bounded look-angle and angle-rate components.Source: B. The Routing Table as a Factor and a… · p. 4
  • A ground-anchored table entry determines the phase outside the finite zenith set D, where the observable map is injective and Q(D)=0.The routing table flow can then be represented by conjugating the constellation flow through the observable map.Source: B. The Routing Table as a Factor and a… · p. 4
  • The relay label and look angles locate the first-hop satellite, while angle rates resolve the ascending-versus-descending ambiguity needed to recover phase.The label and recovered orbital coordinates then determine the torus phase modulo its periods.Source: B. The Routing Table as a Factor and a… · pp. 4–5
  • The exceptional zenith set D differs from the table’s discontinuity set: label wraps and relay handovers leave the table well defined and need no exclusion.The discontinuity set is a finite union of closed curves and is Q-null.Source: B. The Routing Table as a Factor and a… · p. 5
  • A label-only route is an observable but not a factor or measurable conjugate, because distinct phases can share a route and exit its phase cell at different times.Route sequences take only finitely many values; the full table’s relay labels and angular information supply the richer phase-recovering observable.Source: B. The Routing Table as a Factor and a… · p. 5

C. Consequences

The routing-table process inherits the constellation flow’s rational-periodic versus irrational-nonperiodic dichotomy, while irrational routing tables still have computable long-run averages. The table is measurably conjugate to the flow under the stated ground-node condition, with practical implications for constellation design.

C. Consequences

  • Off a Q-null set, the routing-table process is a measure-preserving dynamical system measurably conjugate to the constellation flow.The routing map is injective on S \ D, permitting the inverse used in the conjugacy.Source: C. Consequences · p. 5
  • For rational speed ratios, the full routing table has minimal period exactly T⋆; for irrational ratios, it is non-periodic when it contains a ground-node entry.No user terminal has a periodic beamforming table in the irrational case.Source: C. Consequences · p. 5
  • In the rational case, the label-only route can have a proper-divisor period, unlike the full routing table’s exact constellation period.The paper distinguishes this coarse route observable from the finer routing table.Source: C. Consequences · p. 5
  • Without ground stations or ground users, satellite-only routing is oblivious to Earth’s rotation, so the ground-node condition is substantive.Source: C. Consequences · p. 6
  • For irrational ratios, every initial phase gives long-run averages of bounded route functionals equal to their ensemble averages under the routing map’s push-forward of Q.The functionals include hop count, end-to-end length, and number of ground relays.Source: C. Consequences · p. 6
  • Because almost every altitude chosen from a continuum yields an irrational speed ratio, non-periodic routing tables are the almost-sure design outcome absent deliberate resonance.The paper also notes that orbital-model departures can further undermine the periodic model.Source: C. Consequences · p. 6
  • Non-periodicity here does not mean randomness: the routing-table process has zero entropy, with its future fully determined by the current phase.The paper relates this to the line spectrum measured in its simulations.Source: C. Consequences · p. 6

IV. NUMERICAL VALIDATION

The numerical-validation section supplements the routing-table dynamics analysis with simulations and spectral analysis. It also uses ensemble averages to define a fluctuation-oblivious round-trip-delay metric and compare it with terrestrial fiber.

IV. NUMERICAL VALIDATION

  • The section provides numerical evidence to complement the dynamical-system analysis of routing tables.Source: §IV · p. 6
  • Discrete-event simulation and spectral analysis examine routing-table periodicity in rational and irrational regimes.The stated targets are exact periodicity at the constellation period in the rational case and non-periodicity with equal time and ensemble averages in the irrational case.Source: §IV · p. 6
  • The section defines an ensemble-average round-trip-delay metric between two cities and compares it with the terrestrial counterpart.The metric is intended to be oblivious to delay fluctuations.Source: §IV · p. 6

A. Setting

The simulations use greedy routing in a Walker constellation and examine convergence of route-function time averages to ensemble averages. The reported convergence is close across all tested initial phases, while finite simulation windows cannot certify an irrational speed ratio.

A. Setting

  • The simulation uses a 24-orbit, 15-satellite-per-orbit Walker constellation and greedy forwarding among line-of-sight satellites and gateways toward a nearly antipodal destination.The route ends when the current satellite sees the destination; the greedy rule returned a route at every sampled phase.Source: A. Setting · p. 6
  • Finite-precision parameters make the simulated speed ratio rational, with a 3824-sidereal-day period, so the 32-day observation window only approximates an irrational flow.No finite record can distinguish an irrational ratio from a rational one with a sufficiently long period.Source: A. Setting · pp. 6–7

B. Ensemble and Time Averages

  • Below 1.6 × 10−4: after 30 days, every tested phase’s relative gap from the ensemble average is under this threshold for route length and hop count.The ensemble estimates are 21,963 km and 6.006 hops, with Monte Carlo standard error 2 × 10−5.Source: B. Ensemble and Time Averages · p. 7, Figure 2 · p. 7
  • The observed average-gap decay is consistent with torus equidistribution, and unique ergodicity supports convergence for every initial phase rather than almost every phase.The passage contrasts the observed decay with discrepancy-based T^-1 decay up to logarithmic factors for almost every ratio; T^-1/2 is presented as a conservative guide.Source: B. Ensemble and Time Averages · p. 7

C. An Ergodic Theory Based Round-Trip Delay Metric

The section uses long-run delay averages to compare time-varying satellite routing with terrestrial propagation, then tests the periodicity dichotomy through first-hop look angles. Rational configurations show recurrence at the constellation period, while irrational configurations do not.

C. An Ergodic Theory Based Round-Trip Delay Metric

  • The delay metric is the ensemble average, which equals the convergent time average for every initial phase; processing and queueing delays are excluded.The example uses greedy routing between a source near Seoul and a destination near Paris in the irrational configuration.Source: C. An Ergodic Theory Based Round-Trip… · p. 7
  • 72.1 ms is the common long-run greedy Seoul–Paris delay, below 88.0 ms for ideal geodesic fiber and 247 ms for measured Internet round-trip time.Instantaneous delay varies from 68.3 to 79.9 ms; the long-run average applies for every initial phase and observation starting time.Source: Figure 3 · p. 7, C. An Ergodic Theory Based Round-Trip… · p. 7

D. Periodicity–Lack of Periodicity of the Look Angles

  • For the rational repeat-ground-track configuration, route labels recur with minimal period T⋆; routes with physical-vehicle marks have a period that is a multiple of T⋆.Here T⋆ is one third of a sidereal day.Source: D. Periodicity–Lack of Periodicity of… · p. 8
  • In the irrational configuration, tested lag mismatches stay above 1.8 rad; satellite handovers create order-one look-angle jumps that the dense orbit encounters.The mismatch supremum is the period detector: it vanishes exactly when a lag is a period of the entry.Source: D. Periodicity–Lack of Periodicity of… · p. 8, Figure 4 · p. 8

E. Spectral Validation

The spectral analysis tests whether first-hop elevation peaks share a common fundamental over finite records. It finds a period matching T⋆ in the rational configuration, while the conclusion reiterates the periodicity dichotomy and the role of long-run ensemble averages.

E. Spectral Validation

  • The test samples first-hop elevation over 8 sidereal days, tests dominant peaks against candidate common fundamentals across longer records, then fits two frequencies if needed.The analysis uses 10-second sampling and a Hann window.Source: E. Spectral Validation · p. 8
  • In the rational configuration, all 16 peaks fit integer multiples of 34.8173 µHz, yielding a 7.978 h period that agrees with T⋆.The maximum deviation from integer multiples falls from 2.3×10^-4 over 8 days to 0.2×10^-4 over 32 days.Source: E. Spectral Validation · p. 8, Figure 5 · p. 9
  • In the irrational configuration, peak deviations do not shrink with record length, and no integer relation between two fitted frequencies is found within coefficient magnitude 74.The two spectra look similar; the distinction comes from testing frequency relations.Source: E. Spectral Validation · pp. 8–9, Figure 5 · p. 9
  • Spectral conclusions are limited to retained peaks, tested coefficient range, and achieved frequency resolution; finite records cannot exclude a rational ratio with a sufficiently long period.A scalar observable may retain only some flow frequencies, so its periodicity alone does not establish periodicity of the full table.Source: E. Spectral Validation · p. 9

V. CONCLUSION

  • The routing table is periodic with the flow period for rational speed ratios and non-periodic for irrational ratios, whose long-run route statistics are ensemble averages under the invariant measure.These averages provide metrics insensitive to temporal fluctuations and initial conditions.Source: §V · p. 9
  • In non-periodic designs, finite predictive routing instructions are valid only for a bounded duration, leaving recomputation frequency and broadcast volume unresolved.The conclusion also identifies extensions beyond single-altitude Walker constellations as future work.Source: §V · p. 9

Related papers

Loading 2609.36566v1…