A unified game-theoretic methodology for the
joint load sharing, routing and congestion control problem
Anastasios A. Economides
Ph.D. Thesis, University of Southern California, 1990
This was the first research to formulate, model and solve routing (load balancing, load sharing)
problems in computer and communication networks both as Nash games
(IEEE ITS 1990,and
IEEE Infocom 1991)
and as Stackelberg games (Allerton 1990)
In this dissertation, we introduce a unified game-theoretic methodology for the multi-objective joint load sharing, routing and congestion control problem in distributed systems. We further propose
stochastic learning automata algorithms for decentralized asynchronous dynamic computation of the solution.
First, we define and model the problem on the path flow space using queueing and state space models.
Then we develop three methodologies for both the quasi-static and the dynamic causes of the problem:
(i) Team optimization methodology, when the classes of jobs cooperate for the socially optimum,
(ii) Nash game methodology, when the classes of jobs compete among themselves and each class tries
to operate optimally for its own jobs, and (iii) Stackelberg game methodology, when some classes of
jobs have more power than others, for example priority classes.
For each methodology, we formulate the problem as a Nonlinear Programming, an Optimal Control,
a Dynamic Programming, a Nonlinear Complementarity and a Variational Inequality problem.
We state conditions for existence/uniqueness of the solution, and derive the optimality conditions
for the quasi-static problem using the Karush-Kuhn-Tucker theorem, and for the dynamic
problem using Pontryagin's maximum principle.
We apply the proposed methodologies to Datagram, Virtual Circuit and Integrated Services
Networks and develop several new queueing models and performance measures, for each network type.
We explicitly solve several examples and evaluate the system performance via simulation.
Finally, we propose decentralized asynchronous dynamic load sharing, routing and congestion control using Stochastic Learning Automata. We introduce new classes of Stochastic Learning Automata algorithms and use them as decision makers in the distributed system. We explicitly illustrate their operation with an example for dynamic virtual circuit routing and demonstrate via simulation improved system performance.