Optimal Policies for Large Queueing Networks Through Diffusion Limits

Queueing networks are ubiquitous, serving as models of computer networks, service stations, dams, etc. Their performance depends on their structure, parameters and on the service rules. In general, finding good service rules is a difficult problem. We give some examples to motivate the study of queueing networks, and in particular large networks. We show how to approximate large networks by simpler models of diffusions. Two examples will then illustrate how the asymptotic analysis can lead to practical conclusions about service rules, when the model is not known completely---in this case, service rates of the various servers are not known. The first example shows that, when attempting to minimize the time in the system, it suffices to take a surprisingly small sample of service times of a subset of servers. The second example deals with the issue of fairness towards servers, and yields a rule which does not depend on the values of service rates, and is easy to implement as well as robust with respect to some model assumptions (joint work with Rami Atar and Yair Shaki).