Network Storage Analysis via Semiring Geometry

William Bernardoni, Robert Kassouf-Short, Robert Cardona, Brian Heller, Justin Curry, David I. Spivak, Juan A. Fraire2024 · DOI

TL;DR

This paper introduces a novel semiring-based framework to model and analyze storage requirements in Delay Tolerant Networks (DTNs), specifically for space communication scenarios. By leveraging the algebraic properties of semirings, the authors provide a method to determine optimal storage strategies for maximizing transmission durations, a crucial aspect for building a robust Solar System Internet.

What Problem Does This Paper Address?

Current Delay Tolerant Networking (DTN) routing protocols primarily focus on the "store-and-forward" aspect of data transmission, optimizing how data is routed through a network. However, they often overlook a critical component: the storage needs of the nodes (satellites, ground stations, etc.). As we envision a Solar System Internet (SSI) with numerous interconnected devices, accurately predicting and managing storage is essential for efficient communication, impacting satellite size, mass, and power consumption. This paper addresses this gap by developing a mathematical framework that explicitly incorporates storage considerations into routing analysis.

Methods

The core of this paper lies in the application of semiring geometry to model DTN communication. The authors introduce specialized semirings that capture the behavior of:

  • Contact windows: Time intervals during which communication between nodes is possible.
  • Delays: The time it takes for data to traverse a link.
  • Storage: The capacity of a node to buffer data.

They define "contact window" matrices and "storage" matrices, and then explore their compositions using semiring operations (addition and multiplication). This allows them to represent complex communication paths and their associated storage requirements as algebraic objects. The paper then leverages the algebraic path problem and the concept of Kleene star on these semiring matrices to determine optimal transmission durations and the minimal storage needed to achieve them. They also introduce "nevadas" as a canonical form to represent complex communication paths using a fixed number of parameters.

Datasets

The authors describe an experimental setup based on a simulated LunaNet communications architecture. This scenario includes:

  • 6 satellites.
  • 3 ground stations (Deep Space Network - DSN: Goldstone, Madrid, Canberra).
  • 3 potential Lunar Exploration Ground Stations (LEGS) sites (White Sands, Wallops, Dongara).
  • 3 representative lunar ground stations (one near the South Pole, two on the far side).

Contact plan data and distance information were extracted using the Satellite Orbital Analysis Program (SOAP).

Key Insights and Ideas

  • Semirings as a Unified Framework: Semirings provide a powerful and unified algebraic language to model diverse aspects of DTN communication, including contact windows, delays, and storage.
  • Storage is Key for Maximizing Transmission Duration: While routing focuses on efficient forwarding, optimizing storage is crucial for achieving the longest possible data transmission durations, especially in scenarios with limited bandwidth or intermittent connectivity.
  • "Nevadas" Simplify Complex Paths: The concept of "nevadas" offers a compact way to represent the geometric shape of communication windows resulting from complex paths, reducing the representation to just five numbers.
  • Asymmetries in Communication: Even with symmetric contact availability, the interplay of delays and storage can lead to significant asymmetries in communication capabilities between nodes.
  • Computational Tractability: The developed semiring models allow for efficient computation, enabling the analysis of complex contact graphs and the determination of optimal storage strategies.

Key Results

  • The paper demonstrates that their semiring models can be used to analyze simulated satellite networks.
  • They show how to determine the maximum transmission duration and the corresponding minimal storage required for a given path.
  • For a specific simulated link between IOAGSouth2 satellite and LunarRoverNear, they found a maximum transmission duration of 15.8 hours requiring 6.15 hours of storage. Without storage, a transmission duration of 10.32 hours was achievable.
  • The analysis revealed asymmetries in communication, where increasing storage benefited one direction of communication but not the other.
  • The computational analysis of a 15x15 contact matrix (288 contacts) stabilized at the 7th cumulant and took 22.013 seconds.

Limitations and Future Work

Limitations: * Constant Bandwidth Assumption: The current model assumes constant bandwidth across all links, simplifying the problem. Adapting to variable bandwidths would require more complex tropical polynomial equations. * Constant One-Way Light Time: The experimental setup assumed constant one-way light times for contacts. For longer simulations or more dynamic scenarios, contact windows might need subdivision. * Idealized Contacts: The model treats contacts as ideal opportunities for communication, not accounting for practical constraints like satellite realignment that might make certain windows unusable.

Future Work: * Routing Decisions: Integrating the semiring models with existing algorithms for making routing decisions in DTNs. * Network Substructures: Identifying network substructures and optimal decompositions using the semiring framework. * Generalizing to Other Networks: Applying the semiring models to non-satellite networks, such as terrestrial networks or fused satellite-internet topologies. * Algebraic Geometry over Semirings: Developing a deeper understanding of algebraic geometry over semirings to optimize satellite topology design and solve polynomial equations related to network parameters. * Eigenvectors and Eigenvalues: Exploring the implications of eigenvectors and eigenvalues of semiring matrices for network analysis, potentially leading to concepts like "Delay Tolerant Katz centrality." * Categorical Constructions: Investigating further categorical constructions related to pixel array work and semiring structures.

Summary updated

Abstract

The long-term goal of space networking studies is to provide the foundation needed to support a Solar System Internet (SSI). We anticipate that such an SSI would be composed of science and exploration satellites, ground stations, routing satellites, and ultimately humans and robots on the surfaces of different planets throughout our solar system. Interplanetary communications networks will need to handle the delays, disruptions, and disconnections inherent to space communications. The architecture of Delay Tolerant Networking (DTN) provides protocols and strategies to support these communications plans. At its core, DTN relies on a store-carry-forward approach to provide robust communications in the presence of delays and disruptions.In the past, routing models in DTN have focused on the forwarding aspects of store-carry-forward. Methods such as Contact Graph Routing, Contact Multigraph Routing, and Probabilistic Routing Protocol using the History of Encounters and Transitivity (PRoPHET) provide solutions for how to choose where to forward bundles through a network. However, these routing models often function bundle-by-bundle allowing them to set aside storage needs for each node. In order to bring our vision of a SSI to reality, we will need to be able to predict and incorporate storage needs that satellites and rovers will require. Modeling and predicting storage needs is the first step to being able to optimize storage needs and also optimize communication footprints on the size, mass, and power needs of future satellites.In this paper, we introduce a novel semiring model for contact-based routing protocols that includes a means of determining storage needs. Through proper analysis of the semiring structure, we show how to determine optimal storage structures in satellite networks. In addition, we run our analysis on simulated satellite networks to demonstrate the potential for working with these semiring models in a computational framework. We conclude by indicating future directions for semiring analysis is space communications.
BibTeX
@misc{bernardoni2024network,
  author = {William Bernardoni and Robert Kassouf-Short and Robert Cardona and Brian Heller and Justin Curry and David I. Spivak and Juan A. Fraire},
  title = {{Network Storage Analysis via Semiring Geometry}},
  year = {2024},
  doi = {10.1109/aero58975.2024.10521207},
}

Loading related content...

Figure