The throughput of irreducible closed Markovian queueing networks: Functional bounds, asymptotic loss, efficiency, and the Harrison–Wein conjectures

Let N be the population of an irreducible closed Markovian queueing network, and denote by α^u(N) the throughput of a scheduling policy u. The policy u is said to be efficient if limN→+∞ α*(N), where α* is the capacity of a bottleneck station. The quantity J(u):= limN→∞N(α* − α^u(N)/α* is called the asymptotic loss of u. The policy u is said to be asymptotically optimal if J(u) is as small as it can be. For multi-station irreducible closed Markovian networks, we obtain functional bounds on the throughput which are of the form αN/(N + υ). The coefficients α and υ are obtained by solving two linear program (LPs), which consist of L(L + 3)/2 variables, where L is the number of buffers in the system. We are thus able to establish efficiency, as well as provide upper and lower bounds on asymptotic loss, through LP procedures. For balanced systems where all stations are equally loaded, we are able to provide reduced dimensional LP which consist of just S(S + 1)/2 variables, where S is the number of stations in the system. We also show that the lower bound on asymptotic loss produced by the reduced dimensional LP can capture interactions between multiple bottlenecks in heavy traffic, and that it always dominates a bound obtainable by extending a conjecture of Harrison and Wein (HW) from two station systems to multi-station systems. Employing these bounds on two station systems, we prove that a certain policy developed by HW is efficient. This buffer priority policy was conjectured by them to be asymptotically optimal. They also conjectured a finite valued formula for the asymptotic loss of every buffer priority policy. This latter conjecture is not true in its full generality since there exists a certain buffer priority policy for a certain two station system which is not efficient, and consequently has infinite asymptotic loss. However, we provide credence to the conjectures by establishing that for balanced systems, the conjectured asymptotic loss of the HW-policy is a lower bound on the asymptotic loss of all policies, while the conjectured formula for the asymptotic loss applied to the exact opposite of the HW-policy is an upper bound on the asymptotic loss for all nonidling policies. The latter result is established under an additional condition identified by us which guarantees the finiteness of the asymptotic loss, and thus also the efficiency, of every nonidling scheduling policy.