Operator calculus approach to minimal paths: Precomputed routing in a store and forward satellite constellation

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 combinatorial 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.