Sensitivity analysis and control of queueing systems with real-time constraints and discontinuous performance measures

This work is devoted to the study of a class of queueing networks with certain properties, namely those with discontinuous performance measures. An important subclass consists of networks with real-time constraints, where jobs must arrive at their destination within given deadlines, otherwise they are considered lost. Performance in such networks is measured by the probability a job is lost. For a network of K parallel links with a probabilistic routing scheme, consider the problem of optimal routing. Assuming the availability of a closed-form expression for the probability of loss across each link, the problem is solved under general conditions and properties of the optimal flow allocation are given. However, an analytical expression often cannot be derived, in which case other optimization approaches are necessary. One alternative is to use approximate analysis. Two suboptimal heuristic routing schemes are presented and compared. A second alternative involves implementing an on-line gradient-based stochastic optimization algorithm. Such algorithms require performance gradient estimates with respect to the control parameter. The methods of Perturbation Analysis (PA) and the Likelihood Ratio (LR) have been developed to supply the derivative estimates required. Smoothed Perturbation Analysis (SPA) is a specific PA approach suited to gradient estimation problems with discontinuous sample performance functions. SPA overcomes the normal difficulty of discontinuities by defining alternative sample performance functions that are conditioned forms of the original sample functions, such that the discontinuities are smoothed out. Here, a new SPA approach is developed that extends the applicability of SPA to cover additional performance measures including the probability of loss in real-time networks. New SPA gradient estimators are presented for this and other problematic performance measures such as the probability an arriving customer finds an idle server and the network occupancy as seen by an arrival to a tandem network. The convergence rate of SPA and LR gradient estimators are compared experimentally. Furthermore, the effectiveness of SPA gradient estimation in on-line stochastic optimization problems is demonstrated by coupling an SPA algorithm with a sampling-controlled stochastic version of Gallager\u27s algorithm for the routing problem described above