Bounding Delays in Packet-Routing Networks with Light Traffic
Abstract: 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.