Real-world packet routing networks differ in many ways from the networks which are analyzable by current-day queueing theory methods. For example the service distributions in real-world networks are constant, whereas the vast majority of queueing theory applies most powerfully to exponential service distributions.

Consequently, it is desirable to at least be able to approximate the behavior of real-world networks by networks which we know how to analyze. Towards this end, much previous research has been done showing that for many networks greater variance (in service-time distributions and other things) leads to greater congestion, and therefore we can obtain upper bounds on delays in real-world networks by computing the delay in a related network, having more variance, which we know how to analyze.

The class of networks for which greater variance leads to greater congestion is not known. This paper contributes to determining this classification by demonstrating a network for which increasing the variance in either of two very different ways leads to smaller delays.

The arguments we make in this paper are not traditional to the field of queueing theory and are much more in the spirit of discrete mathematics.





Download Full History