Communication orale non publiée/Abstract (Colloques et congrès scientifiques)
Comparing Oblivious and Robust Routing Approaches
Cuvelier, Thibaut; Gourdin, Éric
2018Programme Gaspard Monge pour l'optimisation
 

Documents


Texte intégral
Oblivious routing.pdf
Postprint Éditeur (1.06 MB)
Télécharger

Tous les documents dans ORBi sont protégés par une licence d'utilisation.

Envoyer vers



Détails



Mots-clés :
Network routing; Oblivious routing; Optimisation
Résumé :
[en] Network routing is an already well-studied problem: the routers in the network know which path a packet must follow in order to reach its destination. Traffic engineering attempts to tune the routing to meet some requirements, such as avoiding congestion or a reducing end-to-end delays. Several approaches have been devised to perform these adaptations, but only few of them deal with the uncertainty in some parameters. Mostly, the uncertainty lies in the demand, the total amount of traffic that goes through the network; however, links and nodes may also fail. Robust routing approaches have been proposed to tackle this issue: indeed, they consider that traffic matrices are not know precisely but that they lie in an uncertainty space that can be analytically described [1]. Oblivious routing is the extreme case where the uncertainty space is the whole set of possible traffic matrices and the prescribed routing must be as close as p ossible to the optimum routing, whatever traffic matrix effectively occurs. It has been proved that oblivious routing achieves a polylogarithmic competitive ratio with respect to congestion [2]. Several variants of robust or oblivious routing approaches will be considered and compared on series of realistic instances, some of which are based on Orange network topologies. Future works include dealing with other sources of uncertainty (for instance, survivability to failures [3]) within a common robustness framework. [1] Sözüer, S., and Thiele, A. C. (2016). The State of Robust Optimization. In Robustness Analysis in Decision Aiding, Optimization, and Analytics. [2] Räcke, H. (2002). Minimizing congestion in general networks. In Foundations of Computer Science, 2002. [3] Li, L., Buddhikot, M. M., Chekuri, C., and Guo, K. (2005). Routing bandwidth guaranteed paths with local restoration in label switched networks. IEEE Journal on Selected Areas in Communications, 23(2), 437-449.
Disciplines :
Mathématiques
Sciences informatiques
Auteur, co-auteur :
Cuvelier, Thibaut ;  Université de Liège - ULiège > Form. doct. sc. ingé. & techno. (éléctr., électro.&info.pay)
Gourdin, Éric;  Orange Labs Network
Langue du document :
Anglais
Titre :
Comparing Oblivious and Robust Routing Approaches
Date de publication/diffusion :
21 novembre 2018
Nom de la manifestation :
Programme Gaspard Monge pour l'optimisation
Lieu de la manifestation :
Paris, France
Date de la manifestation :
from 20-11-2018 to 21-11-2018
Disponible sur ORBi :
depuis le 30 novembre 2018

Statistiques


Nombre de vues
93 (dont 5 ULiège)
Nombre de téléchargements
33 (dont 2 ULiège)

Bibliographie


Publications similaires



Contacter ORBi