Consider an open queueing system that is stable for arrival rates, 0 ≤ λ < c. Let f(λ) be some function such as the mean sojourn time of a customer. Normally, light traffic theory is concerned with limits as λ → 0, e.g., f(n)(0), n = 0, 1, …. Here we use light traffic theory to obtain derivatives of f(·) at any value of λ for which the system is stable. The derivatives, f(n)(λ), n = 0, 1, …, are obtained by perturbing a system with arrival rate, λ, with a small auxiliary arrival process. The nth derivative is obtained by looking at sample paths of the original system with k auxiliary customers thrown in, k = 0, 1, …, n. In practice, the only way to obtain f(n)(λ) for λ > 0 is by observing the effect of additional customers on the sample path of a simulation. We make this technique rigorous by showing that a certain function of the sample paths is “admissible.” The analysis suggests a method for analytically bounding the derivatives, and yields a proof that a large class of queueing functions are infinitely differentiable with respect to λ. The calculations are reminiscent of other sensitivity analyses of simulations such as (infinitesimal) perturbation analysis and the likelihood ratio method. The method described here (the “light traffic perturbation method”) shares the rigorous foundation of the likelihood ratio method and numerical evidence suggests that (at least for simple systems) it has convergence properties similar to perturbation analysis. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

Resource sharing systems, such as database management systems, utilize various types of locking to maintain consistency. Most locking mechanisms cause some resources to remain idle at certain times when there is work for them to do, inducing a decrease in the system’s capacity. This decrease of capacity is reflected in the stability condition for the locking system as compared to the system without locking. We consider the following locking system. There are N servers operating in parallel and two types of incoming customers. The first type corresponds to simple customers, i.e., customers with no locking requirements, and the second corresponds to customers that have to be processed simultaneously by all N servers. When a server is ready to serve such a customer, it has to wait until all servers are ready to serve that same customer. We determine a necessary and sufficient condition for stability of this system, which can be expressed in terms of the mean of the maximum of N random variables, each representing the amount of work due to simple customers arriving at a station between successive locking customers. For a particular case we provide an asymptotic analysis which indicates that the wasted capacity in such a system grows as $\log N$.

A network is defined as an undirected graph and a routing which consists of a collection of simple paths connecting every pair of vertices in the graph. The forwarding index of a network is the maximum number of paths passing through any vertex in the graph. Thus it corresponds to the maximum amount of forwarding done by any node in a communication network with a fixed routing. For a given number of vertices, each having a given degree constraint, we consider the problem of finding networks that minimize the forwarding index. Forwarding indexes are calculated' for cube networks and generalized de Bruijn networks. General bounds are derived which show that de Bruijn networks are asymptotically optimal. Finally, efficient techniques for building large networks with small forwarding indexes out of given component networks are presented and analyzed.

A priority queuing system m which a customer can feed back and change priority after being served is analyzed.More exactly, there are c customer types.Customer type i feeds back after service N(I) -1 times.The kth time a type / customer is m the queue it has priority level f(t, k) and requires a service time with arbitrary distribution G,k Type ~ customers enter from outside as a Poisson process w~th rate X, and can be e~ther preemptive or nonpreemptlve.A customer who has been preempted must start serwce over from the beginning w~th a new (independently chosen) service Ume.The analysis gwes mean waiting times for each customer type at each stage m its itinerary, the mean number of each customer type m the system, and other quantities of interest.It ~s also shown that bulk arrivals and branching can be included m the model without substantially changing the form of the solution.