Mor Harchol-Balter and David Wolfe

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-94-821

, 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. <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.

---

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},
    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