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 Probabilités et statistiques
IECL - Institut Élie Cartan de Lorraine
4 TRIO - Real time and interoperability
Inria Nancy - Grand Est, LORIA - NSS - Department of Networks, Systems and Services
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.
Type de document :
Communication dans un congrès
IEEE. IEEE Globecom2012, Dec 2012, Anaheim, California, United States. IEEE Xplore, 2012
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00745161
Contributeur : Ye-Qiong Song <>
Soumis le : mercredi 24 octobre 2012 - 17:05:01
Dernière modification le : jeudi 11 janvier 2018 - 06:26:22
Document(s) archivé(s) le : vendredi 25 janvier 2013 - 03:50:40

Fichier

OCSAndFGlobecom.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00745161, version 1

Collections

Citation

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. IEEE Globecom2012, Dec 2012, Anaheim, California, United States. IEEE Xplore, 2012. 〈hal-00745161〉

Partager

Métriques

Consultations de la notice

417

Téléchargements de fichiers

198