Skip to Main content Skip to Navigation
Conference papers

Operator Calculus Approach to Minimal Paths: Precomputed routing in a Store and Forward Satellite Constellation

Hugo Cruz-Sanchez 1 Stacey Staples 2 René Schott 3, 4 Ye-Qiong Song 1
1 MADYNES - Management of dynamic networks and services
Inria Nancy - Grand Est, LORIA - NSS - Department of Networks, Systems and Services
3 TRIO - Real time and interoperability
LORIA - NSS - Department of Networks, Systems and Services, Inria Nancy - Grand Est
Abstract : An innovative minimal paths algorithm based on operator calculus in graded semigroup algebras is described. Classical approaches to routing problems invariably require construction of trees and the use of heuristics to prevent com- binatorial explosion. The operator calculus approach presented herein, however, allows such explicit tree constructions to be avoided. Moreover, the implicit tree structures underlying the problem are pruned automatically by the inherent properties of the semigroup algebras used in this approach. The operator calculus algorithm proposed here is applied to the problem of precomputed routing in a store-and-forward (S&F) satellite constellation, which provides message communication services by relaying messages between satellites through gateways on the ground. The minimum end-to-end delay paths obtained are compared with the best existing heuristics-based results. The best existing results were obtained from a greedy algorithm designed to explore only a portion of the solution space in order to avoid combinatorial explosion and memory overload. In all test cases, the operator calculus is shown to return paths whose minimum end-to-end delay is either equal to or less than that of the best existing result. In some cases, in which the tree pruning algorithm did not find a solution, the operator calculus does. These results correspond to a one-single constraint case considering the end-to- end delay as the cost of the links, if the case of multi constraints is considered (e.g. bandwidth, rapidity,. . . ) the operator calculus approach can be similarly used.
Document type :
Conference papers
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download
Contributor : Ye-Qiong Song Connect in order to contact the contributor
Submitted on : Wednesday, October 24, 2012 - 5:05:01 PM
Last modification on : Saturday, October 16, 2021 - 11:26:08 AM
Long-term archiving on: : Friday, January 25, 2013 - 3:50:40 AM


Files produced by the author(s)


  • HAL Id : hal-00745161, version 1



Hugo Cruz-Sanchez, Stacey Staples, René Schott, Ye-Qiong Song. Operator Calculus Approach to Minimal Paths: Precomputed routing in a Store and Forward Satellite Constellation. IEEE Globecom2012, IEEE, Dec 2012, Anaheim, California, United States. ⟨hal-00745161⟩



Record views


Files downloads