Wardrop Equilibrium in Discrete-Time Selfish Routing with Time-Varying Bounded Delays
This paper presents a multi-commodity, discrete-
time, distributed and non-cooperative routing algorithm, which is
proved to converge to an equilibrium in the presence of
heterogeneous, unknown, time-varying but bounded delays.
Under mild assumptions on the latency functions which describe
the cost associated to the network paths, two algorithms are
proposed: the former assumes that each commodity relies only on
measurements of the latencies associated to its own paths; the
latter assumes that each commodity has (at least indirectly) access
to the measures of the latencies of all the network paths. Both
algorithms are proven to drive the system state to an invariant set
which approximates and contains the Wardrop equilibrium,
defined as a network state in which no traffic flow over the
network paths can improve its routing unilaterally, with the latter
achieving a better reconstruction of the Wardrop equilibrium.
Numerical simulations show the effectiveness of the proposed
approach.