Degree of Queue Imbalance
Abstract
In this paper, we argue that heavy-traffic delay optimality is a coarse metric that does not necessarily imply good delay performance. Specifically, we show that any load balancing scheme is heavy-traffic delay optimal as long as it satisfies a fairly weak condition. This condition only requires that in the long-term the dispatcher favors, even slightly, shorter queues over longer queues. Hence, the empirical delay performance of heavy-traffic delay optimal schemes can range from very good (that of join-shortest-queue) to very bad (arbitrarily close to the performance of random routing).
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Jun 12, 2018
- Source ID
- 10.1145/3292040.3219665
Entities
People
- Fei Wu
- Jian Tan
- Kannan Srinivasan
- Ness Shroff
- Xingyu Zhou
Organizations
- National Science Foundation
- Office of Naval Research
- Ohio State University