Bounding Delays in Packet-Routing Networks with Light Traffic

Mor Harchol-Balter

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-95-885

, 1995

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1995/CSD-95-885.pdf

If N is a queueing network and cs is the mean service time at server s of N, define NC,FCFS (respectively, NE,FCFS) to be the queueing network N where the service time at server s is a constant cs (respectively, an independent exponentially distributed random variable with mean cs) and the packets are served in a first-come-first-served order. Recently, Harchol-Balter and Wolfe introduced the problem of determining the class S of queueing networks N for which NC,FCFS has smaller average delay than NE,FCFS. This problem has applications to bounding delays in packet-routing networks. In this paper we consider the same problem, only restricted to the case of light traffic. We define SLight to be the set of queueing networks N for which NC,FCFS has smaller average delay than NE,FCFS in the case of light traffic. We discover a sufficient criterion to determine whether a network N belongs to SLight, where this criterion is extremely simple and easy to check. Using this criterion we are able to show that many networks belong to SLight that were previously not known to belong to S. The significance of this result is that it suggests that many more networks are contained in S than has already been shown.

BibTeX citation:

@techreport{Harchol-Balter:CSD-95-885,
    Author= {Harchol-Balter, Mor},
    Title= {Bounding Delays in Packet-Routing Networks with Light Traffic},
    Year= {1995},
    Month= {Oct},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1995/5753.html},
    Number= {UCB/CSD-95-885},
    Abstract= {If <i>N</i> is a queueing network and <i>cs</i> is the mean service time at server <i>s</i> of <i>N</i>, define <i>NC,FCFS</i> (respectively, <i>NE,FCFS</i>) to be the queueing network <i>N</i> where the service time at server <i>s</i> is a constant <i>cs</i> (respectively, an independent exponentially distributed random variable with mean <i>cs</i>) and the packets are served in a first-come-first-served order. <p>Recently, Harchol-Balter and Wolfe introduced the problem of determining the class <i>S</i> of queueing networks <i>N</i> for which <i>NC,FCFS</i> has smaller average delay than <i>NE,FCFS</i>. This problem has applications to bounding delays in packet-routing networks. <p>In this paper we consider the same problem, only restricted to the case of light traffic. We define <i>SLight</i> to be the set of queueing networks <i>N</i> for which <i>NC,FCFS</i> has smaller average delay than <i>NE,FCFS</i> in the case of light traffic. We discover a sufficient criterion to determine whether a network <i>N</i> belongs to <i>SLight</i>, where this criterion is extremely simple and easy to check. Using this criterion we are able to show that many networks belong to <i>SLight</i> that were previously not known to belong to <i>S</i>. The significance of this result is that it suggests that many more networks are contained in <i>S</i> than has already been shown.},
}

EndNote citation:

%0 Report
%A Harchol-Balter, Mor 
%T Bounding Delays in Packet-Routing Networks with Light Traffic
%I EECS Department, University of California, Berkeley
%D 1995
%@ UCB/CSD-95-885
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1995/5753.html
%F Harchol-Balter:CSD-95-885