Mor Harchol-Balter and David Wolfe

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-94-821
July 1994

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1994/CSD-94-821.pdf

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.

BibTeX citation:

@techreport{Harchol-Balter:CSD-94-821,
    Author = {Harchol-Balter, Mor and Wolfe, David},
    Title = {Greater Variance Does Not Necessarily Imply Greater Average Delay},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1994},
    Month = {Jul},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1994/5491.html},
    Number = {UCB/CSD-94-821},
    Abstract = {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. <p>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. <p>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. <p>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.}
}

EndNote citation:

%0 Report
%A Harchol-Balter, Mor
%A Wolfe, David
%T Greater Variance Does Not Necessarily Imply Greater Average Delay
%I EECS Department, University of California, Berkeley
%D 1994
%@ UCB/CSD-94-821
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1994/5491.html
%F Harchol-Balter:CSD-94-821