  Motivated by timeouts in Internet services, we consider networks of infinite
server queues in which routing decisions are based on deadlines. Specifically,
at each node in the network, the total service time equals the minimum of
several independent service times (e.g. the minimum of the amount of time
required to complete a transaction and a deadline). Furthermore, routing
decisions depend on which of the independent service times achieves the minimum
(e.g. exceeding a deadline will require the customer to be routed so they can
re-attempt the transaction). Because current routing decisions are dependent on
past service times, much of the existing theory on product-form queueing
networks does not apply. In spite of this, we are able to show that such
networks have product-form equilibrium distributions. We verify our analytic
characterization with a simulation of a simple network. We also discuss
extensions of this work to more general settings.
