In Network of Queues, M/M/1 Can Outperform M/D/1
Mor Harchol-Balter and David Wolfe
EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-94-841
November 1994
http://www.eecs.berkeley.edu/Pubs/TechRpts/1994/CSD-94-841.pdf
Let N be an open queueing network where the servers have generally distributed service times (with possibly different means) and the outside arrivals to the servers are Poisson. Define NC,FCFS (respectively, NE,FCFS) to be queueing network N where each server has a constant (respectively, exponentially distributed) service time with the same mean as the corresponding server in N, and the packets are served in a First-Come-First-Served order.
It has long been conjectured that for all networks N, the average packet delay in NC,FCFS is upper bounded by the average packet delay in NE,FCFS. In this paper, we present a counterexample to this conjecture.
BibTeX citation:
@techreport{Harchol-Balter:CSD-94-841,
Author = {Harchol-Balter, Mor and Wolfe, David},
Title = {In Network of Queues, M/M/1 Can Outperform M/D/1},
Institution = {EECS Department, University of California, Berkeley},
Year = {1994},
Month = {Nov},
URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1994/5747.html},
Number = {UCB/CSD-94-841}
}
EndNote citation:
%0 Report %A Harchol-Balter, Mor %A Wolfe, David %T In Network of Queues, M/M/1 Can Outperform M/D/1 %I EECS Department, University of California, Berkeley %D 1994 %@ UCB/CSD-94-841 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/1994/5747.html %F Harchol-Balter:CSD-94-841