5th International ICST Conference on Performance Evaluation Methodologies and Tools

Research Article

Selfish routing revisited: degeneracy, evolution and stochastic fluctuations

Download126 downloads
  • @INPROCEEDINGS{10.4108/icst.valuetools.2011.245732,
        author={Panayotis Mertikopoulos and Aris Moustakas},
        title={Selfish routing revisited: degeneracy, evolution and stochastic fluctuations},
        proceedings={5th International ICST Conference on Performance Evaluation Methodologies and Tools},
        publisher={ICST},
        proceedings_a={VALUETOOLS},
        year={2012},
        month={6},
        keywords={Congestion model Wardrop equilibrium replicator dynamics stochastic differential equations},
        doi={10.4108/icst.valuetools.2011.245732}
    }
    
  • Panayotis Mertikopoulos
    Aris Moustakas
    Year: 2012
    Selfish routing revisited: degeneracy, evolution and stochastic fluctuations
    VALUETOOLS
    ICST
    DOI: 10.4108/icst.valuetools.2011.245732
Panayotis Mertikopoulos1,*, Aris Moustakas1
  • 1: University of Athens
*Contact email: pmertik@phys.uoa.gr

Abstract

We study the traffic routing problem in networks whose agents try to minimize their latencies by employing a distributed learning rule inspired by the replicator dynamics of evolutionary game theory. The stable states of these dynamics coincide with the network's (Wardrop) equilibrium points and we find that they form a convex polytope whose dimension is determined by the network's degeneracy index (an important concept which measures the overlap of the agents' paths). Still, despite this abundance of stable states, we find that (almost) every solution trajectory converges to an equilibrium point at an exponential rate.

On the other hand, a major challenge occurs when network latencies fluctuate unpredictably due to random exogenous factors. In that case, we show that the time-average of the traffic flows of sufficiently patient agents is still concentrated in a neighborhood of evolutionarily stable equilibria and we estimate analytically the corresponding stationary distribution and convergence times.