Heiner Ackermann, Simon Fischer, Martin Hoefer, Marcel Schöngens
We consider a dynamic load balancing scenario in which users
allocate resources in a non-cooperative and selfish fashion. The
perceived performance of a resource for a user decreases with the
number of users that allocate the resource. In our dynamic,
concurrent model, users may reallocate resources in a round-based
fashion. As opposed to various settings analyzed in the literature,
we assume that users have quality of service (QoS) demands. A user
has zero utility when falling short of a certain minimum performance
threshold and having positive utility otherwise.
Whereas various load-balancing protocols have been proposed for the
setting without quality of service requirements, we consider
protocols that satisfy an additional locality constraint: The
behavior of a user depends merely on the state of the resource it
currently allocates. This property is particularly useful in
scenarios where the state of other resources is not readily
accessible. For instance, if resources represent channels in a
mobile network, then accessing channel information may require
time-intensive measurements.
We consider several variants of the model, where the quality of
service demands may depend on the user, the resource, or both.
For all cases we present protocols for which the dynamics converge to a
state in which all users are satisfied. More importantly, the time
to reach such a state scales nicely. It is only logarithmic in the
number of users, which makes our protocols applicable in large-scale
systems.
| Download: |
|