Contact Graph Routing¶
SABR, ION, and what ASTROLAB actually optimises
When Coverage or Latency uses ISL (CGR earliest delivery), ASTROLAB plans a store-and-forward path on the Connection Network. The buttons and COMM fields live on ISL routing. This page is the standards picture: which official algorithms that policy follows, and which limits are by design — not a Dashboard bug.
It is not a drop-in of NASA’s ION stack, and it does not put Bundle Protocol on the wire. The contact plan is the Connection Network; the payload is an MMFU file or a command.
Open Web App · product page: ISL routing
Official specifications¶
The procedure started at NASA/JPL as Contact Graph Routing (CGR) and was later issued by CCSDS as Schedule-Aware Bundle Routing (SABR). Professional discussion is in those documents and in the IETF Delay/Disruption Tolerant Networking working group — not in informal forums.
| Document | What it is | Link |
|---|---|---|
| CCSDS 734.3-B-1 Schedule-Aware Bundle Routing (Blue Book, July 2019) | The Recommended Standard. Earliest projected delivery, residual volume, route determination, overbooking left as an implementation matter. | PDF (CCSDS) · CCSDS Blue Books |
IETF draft-burleigh-dtnrg-cgr (Scott Burleigh, JPL) |
Original CGR procedure: contact plan, residual capacity, earliest projected delivery time, then fewest hops as a tie-break. | HTML · plain text |
| IETF DTN working group | Bundle Protocol and related RFCs (the packet format SABR assumes). | datatracker |
| RFC 9171 Bundle Protocol Version 7 | The DTN bundle (TTL, custody, endpoints). ASTROLAB analyses files and commands; it does not speak BP on a space link. | rfc-editor |
| NASA DTN | Agency programme page for delay-tolerant networking in flight. | NASA SCaN DTN |
| NASA ION | Reference implementation of BP + CGR/SABR (Interplanetary Overlay Network). | NASA software catalog · ION-DTN distribution |
SABR is the document to cite for “what the algorithm is allowed to optimise.” The Burleigh draft is the readable statement of the forwarding rule. ION is how a flight stack recomputes that rule at every node.
What the standard optimises — and what it does not¶
CGR/SABR computes a route per message, from the contact plan, at the time the message is ready.
The Burleigh draft’s forwarding rule is: pick the proximate node with the earliest associated projected delivery time; on a tie, the smallest network distance (hop count); on a further tie, a stable node id. SABR keeps that earliest-arrival objective and adds residual-volume checks so a contact that cannot carry the bundle is skipped.
That is not:
| Not an objective | Why it matters in ASTROLAB |
|---|---|
| Fewest hops | Hop count breaks a tie when two routes deliver at the same instant. It is not a budget. A longer path that arrives earlier is the one SABR keeps. |
| Smallest max Delivery delay | One file at 80 min and four thousand at 4 s is a valid CGR solution if that 80 min was the earliest plan for that file. |
| Joint schedule of every file | Each bundle is planned greedily. Residual volume is consumed as messages are planned. There is no multi-commodity optimum in the UI. |
| A promise that the predicted time will happen | The plan assumes the contact still has room when the file actually arrives. Queues and one radio per bus can miss the pass. |
Mean can fall while max stays high
That split is what earliest-arrival CGR is specified to do. Read mean / P50 / P90, max, and lost at scenario end as different questions. Worked cases: ISL routing.
SABR also filters routes that cannot deliver before the bundle expires (TTL). ASTROLAB’s analysis interval plays that role: a file still onboard at scenario end is lost, not counted in max. Lost is worse than a high max — it never arrived.
CGR-ETO (radio occupancy)¶
Classic CGR treats a contact as empty: the bundle leaves at contact start. CGR-ETO (Earliest Transmission Opportunity) is the backlog rule from Bezirgiannidis and Caini, the one ION 3.6+ uses. It answers when this bundle can start radiating, given what is already queued.
The booking is an interval on a radio and on a contact, not a watermark that says “this radio is free only after T”. Each physical radio keeps the stretches of time it is already radiating. Each contact keeps its own queue of those stretches. For a bundle of size S at rate R, radiation lasts S/R. The search takes the earliest start t such that:
tis at or after both the contact opening and the moment the bundle is ready[t, t + S/R)ends before the contact closes- that interval misses this contact’s queue
- that interval misses at least one free radio of the right class
Delivery is the end of radiation plus one-way light time. A Connection Network contact has no range, so light time is 0 and delivery is the end of radiation. The radio and the contact queue are busy only while radiating. Light time does not hold the transmitter.
The node that receives the file then adds its COMM Processing Latency. A relay spacecraft can forward only after it, and at a facility it is added to delivery. The file's origin does not pay it. CGR ranks routes with this delay included, so a relay or station with a long processing time can lose to a later pass. With every Processing Latency at 0 (the default), routes are unchanged.
A later booking is only its own interval. Reserving a transmission at 01:30 does not close a pass that ended at 00:40 on the same radio, and it does not mark the radio busy from now until 01:30. An earlier gap stays usable.
| Source | Role |
|---|---|
| Bezirgiannidis, Caini, et al., Contact graph routing enhancements for DTN space communications, Int. J. Satell. Commun. Network., 2015 | CGR-ETO + overbooking management, later folded into ION. DOI · earlier conference version CGR-ETO |
| Caini et al., Contact Graph Routing in DTN Space Networks, IEEE Communications Magazine, 2015 | Overview of CGR enhancements used in flight stacks. DOI |
Two radio pools¶
The class of a hop is the receiver, not the name of the button:
| Hop ends at | Pool | COMM field | Default |
|---|---|---|---|
| A spacecraft (ISL, or a command uplink to a bus) | ISL | Max. Concurrent ISL Links | 1 |
| A facility (X-band dump) | Downlink | Max. Concurrent Downlink Links | 1 |
| A spacecraft, from a Static IoT site | Uplink (receive side of the bus) | Max. Concurrent Uplinks, at Uplink Data Rate | 1 |
A missing concurrent field is one radio. Zero means that class cannot transmit. The uplink pool exists only in Static Latency; Continuous and Discrete never book it.
ISL and X-band do not block each other: a satellite can dump to ground and forward on ISL in the same step. Two radios of the same class can serve two different contacts at once. One contact stays a single queue, so a second bundle on that same contact waits for a gap in the queue even if another radio of that class is idle.
Overbooking — a later, higher-priority bundle displacing a booking that is already there — is the companion algorithm in the ETO paper. SABR Annex C leaves it to the implementation. ASTROLAB does not do it. Bundles are planned in ready-time order. Bundle Protocol priority (bulk, normal, expedited) breaks a tie only when two bundles are ready at the same instant. A later expedited file does not jump an earlier bulk file.
What actually gets reserved¶
Latency (Continuous, Discrete and Static IoT) keeps one contact plan for the whole fleet. Each file enters the MMFU of the spacecraft that produced it. When that file can leave, CGR runs from that spacecraft and reserves only the radiation interval of the next hop, size / rate, on that radio and on that contact queue. The spacecraft that receives the file asks again. A station in view is chosen when its delivery is the earliest, so the hop that is not flown is not left booked.
Discrete event assignment runs before a file exists. When an event is generated, CGR projects the delivery from every spacecraft that can acquire it, without booking anything, on the plan as it stands with every earlier file already booked. Only the earliest candidate makes the file; the others never see it in their MMFU.
Static IoT adds one node per site to that plan. The packet is born on its site, and the first CGR decision is the uplink: the spacecraft it picks is the acquirer. From there it is an ordinary file.
Routing Analysis with the CGR criterion asks the same search from its source at every time step, on an idle plan: nothing is booked, so each step is the earliest delivery of one file alone on the network.
Static Session is not CGR. A session is a live rate with no storage, so there is nothing to store and forward. It is a min-cost flow over the links that are open at that moment — Continuous session.
Coverage command is one order per event, 1 byte. Every imager is scored first without occupying a radio. The order that is sent is the one that produces the earliest look. If the geometric Direct look is as early as the CGR look, Direct wins and the unused multi-hop route is not reserved. Only the CGR order that is actually sent occupies the radio. Events run in birth order, so the next event sees that booking.
One byte at 2 Mbps is 4 µs. A command does not miss a pass because of its size. Tasking delay moves because of when the contact opens and who may hear the station.
What ION recomputes, and what the dump does now¶
ION (and SABR as flown) recomputes the best next hop at every waypoint. Downstream nodes see their own queues. Birrane, Burleigh, and Kasch, Analysis of the contact graph routing algorithm, Acta Astronautica, 2012, argue that sticking to a full source route can miss delivery when contacts or congestion change — DOI.
Continuous, Discrete and Static IoT follow that rule on the events of the contact plan, not on a fixed step:
- The file is born in the MMFU of the spacecraft that produced it.
- CGR, from that spacecraft, reserves only the next hop's radiation interval.
- On arrival, the neighbour asks CGR again. If a station is the earliest delivery, that hop is the one that is reserved.
The clock is the birth of each file, the opening and closing of each contact, and the end of each radiation. simulation_time_step_s samples the fill curve. A Continuous file closes at bytes / rate between produce-window edges. Static session is not on this clock: it checks for link changes every simulation_time_step_s and re-solves its flow only when one happens.
Moderate Source Routing (Caini / Unibo) is the same idea: carry the decision, and compute again when the file is somewhere else. Overbooking stays out.
Limits that no Dijkstra removes¶
These are physics, radios, and the scenario window. Changing the search metric does not delete them.
1. Geometry (polar gap)¶
Dump gateways at high latitude (for example Inuvik, Svalbard, Troll) are in view only on parts of each LEO rev. If no neighbour sees a selected facility before the imager’s own next pass, CGR correctly waits. Two orbital planes and a long ocean stretch can leave a file onboard for most of a revolution. That wait is the Direct polar gap, not a CGR loop.
ISL cannot beat a contact that does not exist on the Connection Network.
2. One ISL radio, FIFO¶
With Max. Concurrent ISL Links = 1, files share a single transmitter. At 250 Mbps a 100 MB hop is about 3 s of radio time; the next file on that radio waits for a gap that fits. Residual volume on the useful contact can already be gone, so CGR leaves that file on the imager. A second radio is Max. Concurrent ISL Links (or Downlink Links). Hop count does not add one.
3. Predicted arrival vs the pass that actually closed¶
CGR minimises estimated arrival. A long path can look tens of seconds better and then sit behind a neighbour whose X-band pass already closed. The file waits for that neighbour’s next contact — which can be later than staying on the imager. SABR has no rule “never worse than the local downlink.” The dump asks again at the spacecraft that holds the file, and a station in view wins when that delivery is earliest. It does not displace a booking that is already radiating (no overbooking).
4. Hop count is a tie-break¶
Fraire, Madoery, et al. (WiSEE 2022) describe a different algorithm, CGR-Hops: among routes that meet a deadline, pick the fewest hops — IEEE · arXiv. SABR does not do that, and ASTROLAB does not either.
SABR keeps the earliest delivery. If two routes deliver at the same time, the shorter one wins, then the proximate node with the smaller id. There is no Max hops field on Coverage or Latency. A saved max_route_hops value is ignored. The hop count you see on a route is a result.
5. Scenario end¶
Files still in MMFU when the interval ends are lost. Lengthening the scenario, adding a dump station, or raising ISL rate changes that count. The planner does not invent a contact after T_end.
How to read Dashboard spikes¶
| What you see | Standard reading | What to check |
|---|---|---|
| CGR mean / P50 / P90 much better, max still ~one orbit | Earliest-arrival did its job for the body; one file had no better contact (geometry, residual volume, or the source route missed a pass) | Direct max (polar gap), CN sat–GS windows, ISL Data Rate, concurrent ISL = 1 |
| Command ISL looks worse than Direct | Direct was allowed to task every acquirer, while the interesting case is “only these buses hear the station” | Who hears the GS is the same spacecraft list on Direct and on CGR |
| Direct and CGR match | Imager already sees a gateway — ISL routing | Policy, local dump |
| CGR does nothing | No spacecraft–spacecraft CN edges (buses or laser sensors), or ISL rate 0 | Connection Network access pairs — two lasers and a dump dish |
Tutorial of the mesh: Network, routing & latency. Clocks: Coverage and latency clocks.
Further professional reading¶
These are the usual citations in the satellite-DTN literature (Unibo, CONICET/Fraire, JPL, CCSDS SIS-DTN). They are not product manuals.
| Paper | Why it is here |
|---|---|
| Fraire, De Jonckère, Burleigh, Routing in the Space Internet: A contact graph routing tutorial, J. Network and Computer Applications, 2020 | Tutorial of CGR as flown. DOI |
| Caini, Firrincieli, et al., Application of Contact Graph Routing to LEO satellite DTN communications, IEEE ICC 2012 | CGR on LEO, ION testbed. DOI |
| De Cola, Caini, et al. on SABR analysis and enhancements, Int. J. Satell. Commun. Network. | Independent SABR implementation (Unibo-CGR) vs ION. DOI |
| Load-balancing enhancement to SABR, Int. J. Satell. Commun. Network., 2024 | SABR can ignore parallel equivalent channels and concentrate traffic. DOI |