SAMOVAR UMR 5157

  • Accueil
  • Accueil
  • Accueil
  • Accueil

CNRS

Rechercher




Accueil > Équipes > METHODES > Séminaires Méthodes > Séminaires METHODES > Séminaires 2012 METHODES

"Routing in Equilibrium"

par Timothy G. Griffin, University of Cambridge

le 21 juin à 14h00 en Amphi 11

Abstract :

Some path problems cannot be modelled using semirings because the
associated algebraic structure is not distributive. Rather than
attempting to compute globally optimal paths with such structures, it
may be sufficient in some cases to find locally optimal paths --- paths
that represent a stable local equilibrium.

For example, this is the type
of routing system that has evolved to connect Internet Service Providers
(ISPs) where link weights implement bilateral commercial relationships
between them.

Previous work has shown that routing equilibria can be
computed for some non-distributive algebras using algorithms in the
Bellman-Ford family. However, no polynomial time bound was known for
such algorithms.

In this talk, we show that routing equilibria can be
computed using Dijkstra’s algorithm for one class of non-distributive
structures. This provides the first polynomial time algorithm for
computing locally optimal solutions to path problems.

This is joint work with João Luís Sobrinho
(http://www.lx.it.pt/ jls/)
presented at the 19th International Symposium on Mathematical Theory of
Networks and Systems (MTNS 2010).
You can find the paper here :
This is joint work with João Luís Sobrinho
http://www.cl.cam.ac.uk/ tgg22/publications/routing_in_equilibrium_mtns_2010.pdf


Contact : Ana Rosa Cavalli
Professeur
Directrice du département Logiciels-Réseaux
INSTITUT TELECOM/ TELECOM SudParis
9 rue Charles Fourier, 91011 Evry Cedex
http://www.telecom-sudparis.eu/fr_accueil.html