Abstract:
This thesis considers a system of processor sharing queues under selfish routing, where the users choice of queue depends on their expected waiting times in each queue - in the simplest case they will seek just to minimize their expected waiting time. We assume that users have full knowledge of the state of the system when choosing their route. We introduce several update and routing rules, and seek to characterize the state dependent user equilibria induced by them. We discuss properties of both the system itself and the user equilibrium policies. We employ stochastic comparison and coupling arguments to show various monotonicity properties possessed by this system. Some of these theorems, such as that describing the monotonic relationship between service rate in a queue and the probability that a user will join that queue, hold only for systems of two queues. Other theorems, such as that describing the monotonic relationship between the service rate in a queue and the expected waiting time for a user joining that queue, hold in the context of a system of arbitrarily many queues in parallel. We also present extensive numerical work exploring the structure of fixed points of policy iteration in the system with two queues. We confirm previous findings of complex behaviour arising from policy iteration in this system. In particular, we see that policy iteration is not guaranteed to converge to a fixed point, and may instead converge to a periodic orbit. When it does converge, the fixed point policy is sometimes non-monotonic in occupancy. We implement novel routing and update rules, investigating the effect of boundary conditions, and of routing rules which are not necessarily 0-1 rules. We find that none of the boundary conditions we employ eliminates the nonmonotonicity or periodicity. Each routing rule gives rise to non-monotonic policies, but for one of them all our numerical examples converge to a fixed point, with no periodic behaviour. We go on to use a method related to backwards induction to show that with this routing rule, policy iteration in the system is indeed guaranteed to have at least one fixed point