Mor Harchol-Balter and David Wolfe
EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-94-841
November 1994
http://www2.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://www2.eecs.berkeley.edu/Pubs/TechRpts/1994/5747.html}, Number = {UCB/CSD-94-841}, Abstract = {Let <i>N</i> 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 <i>NC,FCFS</i> (respectively, <i>NE,FCFS</i>) to be queueing network <i>N</i> where each server has a constant (respectively, exponentially distributed) service time with the same mean as the corresponding server in <i>N</i>, and the packets are served in a First-Come-First-Served order. <p>It has long been conjectured that for all networks <i>N</i>, the average packet delay in <i>NC,FCFS</i> is upper bounded by the average packet delay in <i>NE,FCFS</i>. In this paper, we present a counterexample to this conjecture.} }
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://www2.eecs.berkeley.edu/Pubs/TechRpts/1994/5747.html %F Harchol-Balter:CSD-94-841