Bounding Delays in Packet-Routing Networks with Light Traffic
Mor Harchol‐Balter · 1995
If N is a queueing network and cs is the mean service time at server s of N , define N C,FCFS (respectively, N E,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 N C,FCFS has smaller average delay than N E,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 N C,FCFS has smaller average delay than N E,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...