Before revision:  We first show that these performance metrics can be evaluated with a complexity that is polynomial in the system size when we allow for some controlled asymmetry, in the sense that the network contains a fixed number of parts wherein all queues are `exchangeable ' . This in turn allows us to derive stochastic bounds for a larger class of networks which satisfy less restrictive symmetry assumptions.
After revision:  We first show that these performance metrics can be evaluated with a complexity that is polynomial in the system size when we allow for some controlled asymmetry, in the sense that the network contains a fixed number of parts , so that queues are exchangeable within each part and asymmetric across different parts . This in turn allows us to derive stochastic bounds for a larger class of networks which satisfy less restrictive symmetry assumptions.