Evaluation¶

LEOPath evaluation focuses on path optimality, stability, and state size under dynamic constellations.

Metrics¶

• Delivery: how many ground-station pairs were physically deliverable in a snapshot, and how many the algorithm actually delivered.
• Stretch: hop and distance ratio against a shortest-path baseline, reported on two bases (see below).
• Churn: next-hop changes between consecutive snapshots.
• Memory footprint: forwarding state size per satellite.
• Compute time: wall-clock time to compute routing state per time step.

Why these metrics:

• Delivery gives stretch a denominator. Without it, an algorithm that fails on the hard pairs is rewarded, because only its successes reach the average.
• Stretch captures the path-optimality cost of reduced state.
• Churn indicates update frequency and control-plane overhead.
• Memory footprint reflects routing-table scalability.
• Compute time is a rough proxy for algorithmic complexity on the host, not a measure of on-board forwarding cost.

Reachability and the stretch baseline¶

Reachability is decided from the topology before any algorithm runs, so every algorithm is scored over the same pairs. Each ordered ground-station pair in a snapshot falls into one of five buckets, reported as delivery_* columns:

A ground station is reachable through any satellite above its horizon, not only its nearest one. The baseline for stretch is therefore the best end-to-end route to any of them, which makes it identical for every algorithm and independent of what any algorithm does.

Falling short of that baseline has two separate causes, so stretch is one headline figure and two factors that multiply to it:

  end-to-end  =  egress choice   x   forwarding

  stretch_dist_shared    stretch_dist_egress    stretch_dist_forwarding
  stretch_hop_shared     stretch_hop_egress     stretch_hop_forwarding

The egress factor exists because "nearest to the ground station" and "best for this particular source" are different questions:

     S = source
      \
       \                  e2    ..... a longer route, but the station
        \                /  \          did not attach here
         \______________/    ~~~~ g
                             /
                       e1 ~~/    nearest to g, so the address names it
                      /
        ............./  the best route from S

Under gs_addressing: visibility every satellite minimises over all visible egresses, so the egress factor is 1.000 and the headline equals the forwarding factor. Under attachment the address fixes the egress, so a poor choice and a poor path become two distinct causes that one number cannot separate. Reporting only the headline would make a change of destination model look like a regression in forwarding that never happened.

delivery_non_optimal_egress_rate counts how often an algorithm delivered through an egress other than the optimal one, which is the discrete version of the same thing. Plain link-state scores 1.000000 on all three by construction, so it doubles as a correctness check on the metric itself.

Attachment addressing gives a ground station one ground link, and it would be an uneven comparison if topological routing were held to that link while link-state kept every visible one. Link-state therefore also accepts gs_addressing: attachment, which routes it to the same single satellite. Its forwarding factor stays at 1.000 (still a shortest path, just to a fixed egress), while its egress factor now carries the same attachment cost topological routing pays. In the failure sweep that variant is link_state_attach: set it beside the *_attach topological variants to compare forwarding like for like, and keep link_state as the any-egress optimum that every algorithm is scored against.

aux_gs_renumberings counts the stations whose advertised addresses changed in a snapshot, which is what the directory has to be told. Under visibility it stays at zero, because the address never moves.

The multihoming experiment varies gs_attachment_count over K=1, 2 and 4 and crosses it with gs_address_policy (see Routing Algorithms); in the failure sweep those runs are the *_addr_* variants. Under attachment addressing every flow runs a fixed-address walk, with its source and destination addresses set when the flow is allocated and never changed by a transit satellite. Stretch for these walks uses the same lower bound as every other variant, source at its nearest attachment and destination at any satellite it can see, so a K=1 run reproduces the single-attachment numbers exactly. The columns to read:

• fixed_address_forwarding is 1 when a snapshot ran the fixed-address walk. Topological runs with an exception policy still use the older walk, in which every satellite minimises over all K attachments, and report 0; keep them apart from the fixed-address rows.
• aux_gs_current_address_changes counts stations that moved their current address.
• aux_flow_updates and aux_flow_update_messages are what those moves cost. Every station has a flow to every other station in the evaluation, so one renumbering sends G-1 updates.
• delivery_switched_egress_rate stays at 0 on fixed-address walks. It's the check that no packet left the constellation at a satellite its address didn't name.

Every run also reports one-way propagation delay over the paths it delivered: delay_ms for the path taken, GSL legs included, delay_best_ms for the same lower bound the shared stretch uses, and delay_extra_ms for the gap between them, each as a per-snapshot distribution. It's path length divided by the speed of light, so it says what a routing choice costs in milliseconds; queueing, processing and transmission delay aren't modelled. The sweep summaries pool them as delay_ms, delay_extra_ms and delay_extra_p95_ms.

The independent attachment policy lets one satellite serve several stations; exclusive allows each satellite one station at most, a deliberately pessimistic case. The CSV also reports assignment shortfall, unconstrained conflicts and address-set additions and removals.

Optional metrics to add later:

• Stability window: time between next-hop changes.

Constellations¶

• Starlink (synthetic)
• Kuiper (synthetic)
• OneWeb (synthetic)
• Telesat (synthetic)
• Dense LEO (synthetic, stress case)
• The individual shells of Starlink Gen1, Kuiper and Starlink Gen2 as filed with the FCC, one config each under leopath/config/shells/ (see Configuration). A constellation reaches tens of thousands of satellites only by adding shells, and each shell runs as its own 6G-RUPA layer, so per-shell runs measure what a satellite holds at that scale.

All of them model the geometry an operator filed, not the constellation as it flies on a given day. The two can differ a lot: on 29 September 2026 most of Starlink flew 80-90 km below its filings, in different plane counts (scripts/celestrak_shell_geometry.py measures that from a CelesTrak snapshot).

Algorithms¶

• Topological routing
• Link-state baseline
• Predictive link-state
• Explicit-path routing

ISL scenarios¶

• ring: intra-plane only
• grid: intra-plane + inter-plane (+grid), four terminals per satellite; a Walker star builds it as a cylinder
• grid_seam: +grid with the wrap from the last plane to the first removed, a stress test on delta shells
• brick_a, brick_b: three terminals per satellite, cross-plane (a) or in-plane (b) links staggered on (plane + slot) parity; see ISL Topology

Failure injection¶

Pass --failure-type to the harness and it removes links or satellites from every snapshot before any routing algorithm runs. The pattern depends only on --failure-seed and the failure parameters, never on the algorithm, so two algorithms run with the same seed route over exactly the same broken network.

Random failures don't flicker from one minute to the next. Each link or satellite follows its own on/off process and, once down, stays down for a while: 10 minutes on average for a link and 60 for a satellite, which --failure-mean-duration-minutes overrides. --failure-rate is the long-run fraction of time an element spends down, and a run starts from that steady state instead of from a healthy network.

Voids¶

Picture the +Grid as a sheet that wraps around in both directions, with orbital planes as columns and positions within a plane as rows. A void punches a hole in it:

    plane:  0   1   2   3   4   5   6
    row 0   o---o---o---o---o---o---o
            |   |   |   |   |   |   |
    row 1   o---o---X   X   X   X---o
            |   |               |   |
    row 2   o---o---X   X   X   X---o      X = failed satellite (4x4 void)
            |   |               |   |
    row 3   o---o---X   X   X   X---o
            |   |               |   |
    row 4   o---o---X   X   X   X---o
            |   |   |   |   |   |   |
    row 5   o---o---o---o---o---o---o

It models a regional loss, such as a batch of neighbouring satellites taken out together. Topological forwarding finds voids awkward because its distance estimate still points straight through the hole, so a packet approaching from the far side reaches the edge and finds no neighbour any closer to the destination.

Cuts¶

    plane:  0   1   2 | 3   4   5 | (wraps to 0)
    row 0   o---o---o | o---o---o |
            |   |   | | |   |   | |
    row 1   o---o---o | o---o---o |      | = every inter-plane link removed
            |   |   | | |   |   | |
    row 2   o---o---o | o---o---o |

Removing the links across one boundary would only turn the torus into a cylinder, so the cut takes out two boundaries half the constellation apart. That leaves two halves with no link between them, while every satellite keeps working. A pair stays deliverable only when the destination ground station sees some satellite on the source's side, and the delivery metric counts only those pairs. It's the hardest condition for topological forwarding, since the geometry still believes the halves are joined.

Polar deactivation only matters where satellites climb above the threshold. Starlink and Kuiper stay below 60°, so at 60° and 75° it removes nothing from them and only Telesat and OneWeb are affected.

Who knows about a failure¶

Every algorithm routes over the post-failure graph of the snapshot it's in. For link-state that's close to reality at one-minute snapshots, because flooding converges within seconds. Topological routing is the exception: its pivot geometry would pick up every failure in the constellation at once, which a satellite deriving that geometry from ephemerides couldn't do. --geometry-source nominal builds the geometry from the failure-free graph while next hops still use only live neighbours, and observed, the default, keeps the global view as an upper bound.

Failure metrics¶

failure_isls_removed and failure_satellites_down describe each snapshot's damage, and failure_events counts failures that appeared or cleared since the previous snapshot. The first snapshot counts every failure present, since none has been announced yet.

When a deliverable pair isn't delivered, delivery_failure_* records why, and the causes add up to delivery_forwarding_failure:

Links slower than their geometry¶

--isl-delay-spread s gives every ISL a fixed extra delay of up to s times its geometric delay, drawn per link as 1 + s * U(0, 1) from --isl-delay-seed, so every algorithm meets the same slow links. The factor only adds delay, since light can't cross a link faster than its length allows; think of it as processing, pointing or hardware differences the geometry doesn't know about. Routing, link-state and the metrics all see the slowed links, but a geometry_source: derived estimator doesn't, which is the point: it measures what assuming ideal Walker geometry costs when the real network disagrees. The graph has one weight per link, so delays differ between links but not between the two directions of one link. In the sweep runner, pass it to every job with EXTRA_ARGS="--isl-delay-spread 0.3".

Evaluation checklist¶

• Fix ground-station set and simulation horizon for all runs.
• Run ring and grid for every constellation.
• Use identical time steps for churn comparisons.
• Record algorithm_params alongside metrics.
• Report stretch (hop + distance), churn, and forwarding state size.