##
We consider the problem of computing the average packet delay in a general
dynamic packet-routing network with Poisson input stream, during
steady-state.

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.