Worst-Case Efficiency Analyses of Queueing Disciplines

Tim Roughgarden
Stanford University

A robust protocol should perform well for a variety of mixtures of users. We quantify this idea of robustness by examining the equilibrium efficiency loss exhibited by a protocol under a worst-case choice of user preferences. We apply this idea to the design of queueing disciplines with heterogeneous users, in particular compare the worst-case equilibrium efficiency loss of a FIFO queue to one employing Shenker's Fair Share discipline. Joint work with Damon Mosk-Aoyama.

Back to Workshop III: Beyond Internet MRA: Networks of Networks