Stability of Processor Sharing Networks

Friday, June 26, 2015 - 2:45pm - 3:45pm
Keller 3-180
Maury Bramson (University of Minnesota, Twin Cities)
In the processor sharing discipline, all jobs at a station simultaneously receive the same rate of work at a given time. Processor sharing is one of the most widely used disciplines, and is a natural abstraction of the round robin discipline for allocating time to queued jobs at a computer server.

Processor sharing has been widely studied in the context of queueing networks. A standard result states that, irrespective of the network topology, when the input is Poisson and the system is subcritical, the corresponding Markov process is positive recurrent and its equilibrium distribution has an explicit “product” form. Importantly, this result holds for general service time distributions at the different stations.

Much less is known about the behavior of processor sharing for renewal input, rather than Poisson input. The equilibrium distribution is no longer explicit, and even the obvious conjecture, that subcritical networks must be positive recurrent, is undemonstrated in general.

Here, this conjecture is discussed in the context of ongoing work by the speaker. It is relatively simple to show positive recurrence for a large family of input and service distributions. With a substantial amount of effort, the speaker believes he can show positive recurrence for “most” distributions.