Description
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.