### Bounding Delays in Packet-Routing Networks with Light Traffic

**Authors:**

Harchol-Balter, Mor
**Technical Report Identifier:** CSD-95-885
**October 1995**

CSD-95-885.pdf

CSD-95-885.ps

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