Adaptive Routing with Stale Information
Simon Fischer, Berthold Vöcking
We investigate adaptive routing policies for large networks in which
agents reroute traffic based on old information. It is a well known and
practically relevant problem that old information can lead to undesirable
oscillation effects resulting in poor performance. We investigate how
adaptive routing policies should be designed such that these effects
can be avoided.
In our theoretical model, the network is represented by a general graph
with latency functions on the edges. Traffic is managed by a large number
of agents each of which is responsible for a negligible amount of traffic.
Initially the agents' routing paths are chosen in an arbitrary fashion.
From time to time each agent revises her routing strategy by sampling
another path and switching with positive probability to this path if it
promises smaller latencies. As the information on which the agent bases
her decision might be stale, however, this does not necessarily lead to
an improvement. The points of time at which agents revise their strategy
are generated by a Poisson distribution. Stale information is modelled
in form of a bulletin board that is updated periodically and lists the
latencies on all edges.
We analyze such a distributed routing process in the so-called fluid
limit, that is, we use differential equations describing the fractions
of traffic on different paths over time. In our model, we can show the
following effects. Simple routing policies that always switch to the
better alternative lead to oscillation, regardless at which frequency the
bulletin board is updated. Oscillation effects can be avoided, however,
when using smooth adaption policies that do not always switch to better
alternatives but only with a probability depending on the advantage
in the latency. In fact, such policies have dynamics that converge to
a fixed point corresponding to a Nash equilibrium for the underlying
routing game, provided the update periods are not too large.
In addition, we also analyze the speed of convergence towards approximate
equilibria of two specific variants of smooth adaptive routing policies,
e.g., for a replication policy adopted from evolutionary game theory.