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

, 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},
    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