Any packet-routing network can be formulated as a queueing network, where each server has a constant service time and the packets are served in a first-come-first served (FCFS) order. If each server had exponentially-distributed service time, queueing theory techniques could be used to determine the expected packet delay. However, it is not known how to compute the average packet delay for all but the simplest networks with constant time servers.
It has been conjectured that to get an upper bound on expected packet delay in the constant service network, one can simply replace each constant time server with an exponential server of equal mean service time.
We prove that for a large class of networks, this conjecture is true, but that there exists a network for which it is false. This large class of networks is the Markovian queueing networks. Markovian queueing networks are important because they include many packet-routing networks where the packets are routed to random destinations.