Improved Contact Graph Routing in Delay Tolerant Networks with Capacity and Buffer Constraints

This paper proposes an improved Contact Graph Routing algorithm for Delay Tolerant Networks that incorporates contact splitting and edge pruning to proactively enforce capacity and buffer constraints during route search, thereby ensuring optimal delivery times and reducing collisions compared to traditional reactive methods.

The Gist

Imagine a vast, high-speed postal system operating in space, where thousands of satellites are constantly moving around the Earth. This is the world of Delay Tolerant Networks (DTNs). Unlike the internet on Earth, where you can usually send a message and it arrives instantly, space is different. Satellites move fast, signals take time to travel, and sometimes two satellites are on opposite sides of the Earth and can't "see" each other.

In this environment, messages (called bundles) can't always be sent immediately. They have to be stored on a satellite, carried as it flies, and forwarded only when it passes another satellite that can take the message closer to its destination. This is the "Store, Carry, and Forward" principle.

The Problem: The Traffic Jam in the Sky

The paper focuses on a specific routing method called Contact Graph Routing (CGR). Think of CGR as a GPS for these space messages. It looks at a schedule of when satellites can talk to each other (called "contacts") and plots the fastest path.

However, the old version of this GPS had two major blind spots:

1. The "One-Size-Fits-All" Pipe (Capacity): The old GPS assumed that if a satellite has a 10-minute window to talk to another, it has the full 10 minutes available for any message. It didn't realize that if a giant package arrived 2 minutes before your message, it might have used up the last 2 minutes of that window. The old GPS would plan a route, only for the message to get stuck at the next satellite because the "pipe" was already full.
2. The Overfilled Backpack (Buffer): Satellites have limited memory (buffers) to hold messages while they wait for the next hop. The old GPS didn't check if a satellite's backpack was already full. It would send a message there, and the satellite would have to drop it or panic and find a new route at the last second.

The Result: Messages got stuck, took much longer to arrive, or had to be rerouted constantly, wasting precious energy and time.

The Solution: The "Smart Planner"

The authors propose a new, smarter version of the GPS that checks the capacity and buffer limits before it even picks a route. They call this FEAP-CB (Feasible Earliest-Arrival Path with Capacity and Buffer constraints).

They use two clever tricks to make this happen:

1. Contact Splitting (Cutting the Cake)

Imagine a contact (a communication window) is a long loaf of bread.

• Old Way: You see a 10-inch loaf. You plan to send a message that needs 2 inches. You assume the whole loaf is free.
• New Way (Contact Splitting): The system realizes another message already took the first 3 inches. It "splits" the loaf. Now, the GPS sees two pieces: a 3-inch piece that is gone, and a 7-inch piece that is available.
• Why it helps: The GPS never plans a route that tries to use the missing 3 inches. It only plans routes using the available 7 inches. This prevents the message from ever getting stuck because the "pipe" is full.

2. Edge Pruning (Closing the Doors)

Imagine a satellite node as a train station with a waiting room (the buffer).

• Old Way: The GPS sends a train to the station, assuming the waiting room has space.
• New Way (Edge Pruning): The system looks at a "forecast" of the waiting room. It sees that at 2:00 PM, the room will be packed.
  • If a message arrives at 1:55 PM and has to wait until 2:05 PM, the system knows the room will overflow.
  • So, it "prunes" (cuts off) the connection between the arriving train and the next departing train. It effectively closes that specific door in the map, telling the GPS: "Do not go this way; you will get stuck in a full waiting room."

The Magic of "Safety Margins"

The paper also mentions a "Safety Margin." Imagine you are the main dispatcher (the Source). You are very smart and know the whole schedule. But sometimes, a satellite in the middle of the journey might have a glitch (like a power outage) and have to make a quick decision on its own.

To help these "middlemen," the dispatcher intentionally leaves some extra space in the schedule and some empty space in the backpacks. These are reserved spots that the main dispatcher doesn't use. If a middle satellite gets stuck, it can use these reserved spots to reroute the message without causing a crash.

The Results: A Smoother Journey

The authors tested this new method against the old one using simulations of satellite constellations (groups of satellites orbiting Earth).

• Faster Delivery: Messages arrived much faster because they didn't get stuck waiting for a full pipe or a full backpack.
• Fewer Detours: The old system had to reroute messages constantly when it hit a wall. The new system avoided the walls entirely by planning around them from the start.
• Efficiency: Even though the new system had to do a bit more math to "split" the contacts, the overall network ran much more smoothly.

In a Nutshell

Think of the old routing system as a driver who ignores traffic reports and red lights, only to get stuck in a jam and have to turn around. The new system is like a driver with a live, predictive traffic app that knows exactly when a road will be blocked or a parking spot will be full, and it plots a course that avoids those problems entirely before the car even starts moving.

This ensures that in the complex, high-stakes world of space communication, your data gets to the moon (or Mars) as quickly and safely as possible.

Technical Summary

Here is a detailed technical summary of the paper "Improved Contact Graph Routing in Delay Tolerant Networks with Capacity and Buffer Constraints."

1. Problem Statement

Satellite networks, particularly those in Low Earth Orbit (LEO) and cislunar environments, face significant challenges due to intermittent connectivity, long propagation delays, and limited resources (link capacity and node buffer memory). While Delay Tolerant Networks (DTN) and the Bundle Protocol (BP) address connectivity issues via the "store, carry, and forward" paradigm, routing remains complex.

The paper identifies critical limitations in the current state-of-the-art routing algorithm, Contact Graph Routing (CGR):

• Reactive Management: Standard CGR performs capacity and buffer checks after a route is selected (during the forwarding phase). This leads to "overbooking," where a calculated route fails because a contact is already full or a node's buffer is full.
• Simplified Models: CGR often uses a "linear volume" assumption, which fails to account for the precise temporal usage of contact capacity.
• Consequences: Reactive management causes packet collisions, necessitates expensive rerouting (often back to the source), increases average delivery time, and wastes limited satellite resources.

The core problem is to find the Feasible Earliest-Arrival Path (FEAP) that respects both contact-capacity constraints (no overbooking of link volume) and node-buffer constraints (no overflow of storage) before the route is finalized.

2. Methodology

The authors propose a proactive, global routing solution that integrates capacity and buffer management directly into the route search phase. The approach modifies the standard Contact Graph Routing (CGR) algorithm to operate on a Feasible Contact Graph rather than a simple connectivity graph.

Key Technical Components:

1. Contact Splitting:

   • For Capacity: When a bundle is routed, the specific portion of a contact's time window consumed by that bundle is "erased" from the Contact Plan (CP). The original contact is split into two (or shortened), creating new vertices in the graph that represent only the remaining available capacity. This prevents future bundles from being routed over already occupied time slots.
   • For Buffer: Similar splitting is applied temporarily to prevent a bundle from arriving at a node during a time window where the buffer is forecasted to be full.

2. Edge Pruning:

   • Even if individual contacts are available, a sequence of contacts (a path) might cause a buffer overflow at an intermediate node (e.g., a bundle arrives before a buffer clears).
   • The algorithm identifies "problematic contact successions" where the arrival time at a node precedes the start of an overflow period, but the departure time would occur during the overflow.
   • These specific edges (connections between contacts) are pruned (removed) from the graph during the search, ensuring no path containing a buffer violation is ever considered.

3. Forecast Buffer Tables:

   • The system maintains dynamic tables tracking the residual buffer capacity ($\bar{B}_n(t)$) for every node over time.
   • When a route is validated, these tables are updated to reflect the "booked" load of the new bundle. This allows the source node to simulate future buffer states and avoid routes that would cause overflow.

4. Safety Margins:

   • To handle unpredictable disruptions (e.g., antenna errors) where intermediate nodes must reroute without global knowledge, the system reserves a portion of capacity and buffer space as a "safety margin." This ensures intermediate nodes have resources to reroute bundles if the primary plan fails.

3. Key Contributions

• Formalization of FEAP-CB: The authors define the optimization problem as the Feasible Earliest-Arrival Path with Capacity and Buffer constraints (FEAP-CB).
• Proactive Constraint Enforcement: Unlike standard CGR which reacts to errors, this method guarantees that the computed route is valid regarding capacity and buffer limits before transmission begins.
• Mathematical Proof of Optimality: The paper provides a rigorous proof (via Lemmas 1–4) demonstrating that the proposed graph modifications (splitting and pruning) create a feasible graph $(V_c, E_c)$ where the set of schedulable paths exactly coincides with the set of feasible routes ($P_f$). Consequently, running Dijkstra's algorithm on this modified graph guarantees the optimal (earliest arrival) solution among all valid routes.
• Source-Routing Extension: The solution is implemented within a Source-Routing (SR) framework, where the complete route is encoded in the bundle at the source, reducing the computational burden on intermediate nodes.

4. Simulation Results

The authors evaluated their solution against a standard Source-Routing CGR (SR-CGR) benchmark using MATLAB simulations of Walker-delta satellite constellations (4, 8, and 16 satellites).

• Delivery Time: The proposed method significantly reduced the average time bundles spent in the network, especially under high traffic loads and low data rates. The gap widened as the number of bundles increased, whereas the benchmark suffered from frequent delays due to rerouting.
• Rerouting Events:
  • Benchmark: Experienced a high number of rerouting events (both at intermediate nodes and back to the source) due to capacity and buffer collisions.
  • Proposed Method: Achieved zero rerouting events due to capacity or buffer failures in the ideal simulation scenario, as all routes were pre-validated.
• Buffer Efficiency: Under limited buffer constraints (e.g., 50 bundles capacity), the proposed method achieved performance comparable to an infinite buffer system. In contrast, the benchmark showed a massive increase in delivery time (up to 2000% degradation) when buffers were small.
• Complexity: The "Contact Splitting" operation slightly increased the size of the Contact Plan (CP). However, simulations showed this increase was negligible (e.g., <1% under low load, ~10% under extreme high load), indicating that the computational overhead is acceptable given the performance gains.

5. Significance

This work bridges a critical gap in DTN routing for satellite communications. By shifting from reactive to proactive resource management, the proposed algorithm:

1. Maximizes Resource Efficiency: It eliminates the waste of bandwidth and buffer space caused by failed transmissions and rerouting.
2. Ensures Deterministic Performance: It provides theoretical guarantees for optimal delivery time within the constraints, which is vital for time-sensitive space missions (e.g., Artemis program, Mars relay).
3. Scalability: The approach is shown to be effective across different constellation sizes, making it suitable for future mega-constellations.

Limitations & Future Work: The current solution assumes a centralized controller with perfect, global knowledge of the network state and no random disruptions. Future work aims to explore distributed implementations, traffic-level optimization (rather than per-bundle), and robustness against imperfect or delayed information.