cgr#

Contact Graph Routing for time-varying satellite networks.

Overview#

CGR computes routes through scheduled communication contacts in DTN (Delay-Tolerant Networking) environments. Unlike traditional routing where links are persistent, CGR handles networks where connectivity is intermittent but predictable - such as satellite constellations, deep space networks, and scheduled terrestrial links.

The algorithm implements CCSDS Schedule-Aware Bundle Routing (SABR) using Dijkstra's shortest-path algorithm adapted for time-varying graphs where edges (contacts) have temporal validity windows.

Features#

• Contact Plans: Define scheduled communication windows between nodes
• Time-aware routing: Routes respect contact start/end times
• Propagation delay: Supports one-way light time (OWLT) for deep space
• Multiple routes: Find alternative paths for redundancy
• Bottleneck capacity: Track minimum capacity across route hops

Installation#

opam install cgr

Usage#

open Cgr

(* Define nodes *)
let earth = Node.v "EARTH"
let mars = Node.v "MARS"
let relay = Node.v "RELAY"

(* Define contacts (scheduled communication windows) *)
let contacts = [
  Contact.v ~from:earth ~to_:relay ~start:0. ~stop:100. ~rate:1_000_000. ();
  Contact.v ~from:relay ~to_:mars ~start:50. ~stop:150. ~rate:500_000.
    ~owlt:600. ();  (* 10 min light time *)
]

(* Create contact plan and find route *)
let plan = Contact_plan.of_list contacts

let () =
  match route plan ~src:earth ~dst:mars ~time:0. with
  | None -> print_endline "No route available"
  | Some route ->
      Format.printf "Route found: %a@." Route.pp route;
      Format.printf "Arrival time: %.0f seconds@." (Route.arrival_time route)

API#

Nodes#

• Node.v name - Create a node identifier
• Node.name node - Get the node's name

Contacts#

• Contact.v ~from ~to_ ~start ~stop ~rate ?owlt () - Create a contact
• Contact.is_active contact ~time - Check if contact is active
• Contact.capacity contact - Maximum bytes transmittable

Contact Plans#

• Contact_plan.of_list contacts - Create a plan from contacts
• Contact_plan.contacts_from plan node - Get outgoing contacts
• Contact_plan.active_at plan ~time - Get contacts active at time

Routing#

• route plan ~src ~dst ~time - Find best route (earliest arrival)
• routes plan ~src ~dst ~time ~max - Find multiple alternative routes

Routes#

• Route.hops route - List of contacts forming the path
• Route.arrival_time route - Earliest delivery time
• Route.capacity route - Bottleneck capacity (minimum across hops)

Algorithm#

CGR uses Dijkstra's algorithm with arrival time as the distance metric:

1. Initialize arrival time at source to query time, infinity elsewhere
2. Select unvisited node with minimum arrival time
3. For each outgoing contact from current node:
   • Skip if contact ends before we arrive
   • Compute arrival at neighbor: max(arrival, contact_start) + owlt
   • Update if this improves the neighbor's arrival time
4. Mark current node visited, repeat until destination reached

Related Work#

• ION - NASA/JPL's DTN implementation (C)
• CGR Tutorial - Fraire et al., 2020
• CCSDS SABR - Schedule-Aware Bundle Routing standard
• DtnSim - DTN network simulator

References#

• IETF Draft: Contact Graph Routing
• CCSDS 734.2-B-1: Schedule-Aware Bundle Routing
• Fraire et al., "Routing in the Space Internet: A contact graph routing tutorial", JNCA 2020

Licence#

ISC License. See LICENSE.md for details.