Perturbation analysis and control of two-class stochastic fluid models for communication networks

This paper uses stochastic fluid models (SFMs) for the control and optimization (rather than performance analysis) of communication network nodes processing two classes of traffic: one is uncontrolled and the other is subject to threshold-based buffer control. We derive gradient estimators for packet loss and workload related performance metrics with respect to threshold parameters. These estimators are shown to be unbiased and directly observable from a sample path without any knowledge of underlying stochastic characteristics of the traffic processes. This renders them computable in online environments and easily implementable for network management and control. We further demonstrate their use in buffer control problems where our SFM-based estimators are evaluated based on data from an actual system.     

Infinitesimal perturbation analysis of a queueing system with bursty traffic

We study aG/G/1 queueing system with a bursty arrival process. Based on a general model for such a bursty process, we derive infinitesimal perturbation analysis (IPA) derivative estimators of the mean system time with respect to various parameters of interest. The cases of both complete and partial state information are considered. To ensure unbiasedness and strong consistency of the estimators, different sample path representations are developed such that sample functions are continuous with respect to the particular parameter of interest. Some of these representations are applicable to a wider class of gradient estimation problems where sample path discontinuities arise. Simulation results are included to compare the convergence rates and variance properties of the different IPA estimators developed.     

On-line Optimal Control of a Class of Discrete Event Systems with Real-Time Constraints

We consider Discrete Event Systems (DES) involving tasks with real-time constraints and seek to control processing times so as to minimize a cost function subject to each task meeting its own constraint. It has been shown that the off-line version of this problem can be efficiently solved by the Critical Task Decomposition Algorithm (CTDA) (Mao et al., IEEE Trans Mobile Comput 6(6):678–688, 2007). In the on-line version, random task characteristics (e.g., arrival times) are not known in advance. To bypass this difficulty, worst-case analysis may be used. This, however, does not make use of probability distributions and results in an overly conservative solution. In this paper, we develop a new approach which does not rely on worst-case analysis but provides a “best solution in probability” efficiently obtained by estimating the probability distribution of sample-path-optimal solutions. We introduce a condition termed “non-singularity” under which the best solution in probability leads to the on-line optimal control. Numerical examples are included to illustrate our results and show substantial performance improvements over worst-case analysis.     

Perturbation Analysis and Optimization of Multiclass Multiobjective Stochastic Flow Models

Stochastic Flow Models (SFMs) are stochastic hybrid systems that abstract the dynamics of many complex discrete event systems and provide the basis for their control and optimization. SFMs have been used to date to study systems with a single user class or some multiclass settings in which performance metrics are not class-dependent. In this paper, we develop a SFM framework for multiple classes and class-dependent performance objectives, where competing classes employ threshold control policies and service is provided on a First Come First Serve (FCFS) basis. In this framework, we analyze new phenomena that result from the interaction of the different classes and give rise to a new class of “induced” events that capture delays in the SFM dynamics. We derive Infinitesimal Perturbation Analysis (IPA) estimators for derivatives of various class-dependent objectives, and use them as the basis for on-line optimization algorithms that apply to the underlying discrete event system (not the SFM). This allows us to contrast system-centric and user-centric objectives, thus putting the resource contention problem in a game framework. The unbiasedness of IPA estimators is established and numerical results are provided to illustrate the effectiveness of our method for the case where there are no constraints on the controllable thresholds and to demonstrate the gap between the results of system-centric optimization and user-centric optimization.     

Optimal Control of Two-Stage Discrete Event Systems with Real-Time Constraints

We consider discrete event systems (DES) involving tasks with real-time constraints and seek to control processing times so as to minimize a cost function subject to each task meeting its own constraint. When tasks are processed over a single stage, it has been shown that there are structural properties of the optimal sample path that lead to very efficient solutions of such problems. When tasks are processed over multiple stages and are subject to end-to-end real-time constraints, these properties no longer hold and no obvious extensions are known. We consider a two-stage problem with homogeneous cost functions over all tasks at each stage and derive several new optimality properties. These properties lead to the idea of introducing “virtual” deadlines at the first stage, thus partially decoupling the stages so that the known efficient solutions for single-stage problems can be used. We prove that the solution obtained by an iterative virtual deadline algorithm (VDA) converges to the global optimal solution of the two-stage problem and illustrate the efficiency of the VDA through numerical examples.

Perturbation Analysis of Multiclass Stochastic Fluid Models

We use a stochastic fluid model (SFM) to capture the operation of finite-capacity queueing systems with multiple customer classes. We derive gradient estimators for class-dependent loss and workload related performance metrics with respect to any one of several threshold parameters used for buffer control. These estimators are shown to be unbiased and directly observable from a sample path without any knowledge of underlying stochastic characteristics of the traffic processes. This renders them computable in on-line environments and easily implementable in settings such as communication networks.     

Optimal control of batteries with fully and partially available rechargeability

Motivated by the increasing dependence of many systems on battery energy, we study the problem of optimally controlling how to discharge and recharge a non-ideal battery so as to maximize the work it can perform over a given time period and still maintain a desired final energy level. Modeling a battery as a dynamic system, we adopt a Kinetic Battery Model (KBM) and formulate a finite-horizon optimal control problem when recharging is always feasible under the constraint that discharging and recharging cannot occur at the same time. The solution is shown to be of bang–bang type with the property that the battery is always in recharging mode during the last part of the interval. When the length of the time horizon exceeds a critical value, we also show that the optimal policy includes chattering. Numerical results are included to illustrate our analysis. We then extend the problem to settings where recharging is only occasionally feasible and show that it can be reduced to a nonlinear optimization problem which can be solved at least numerically.     

Optimal Control of Multi-Stage Discrete Event Systems With Real-Time Constraints

We consider discrete event systems involving tasks with real-time constraints and seek to control processing times so as to minimize a cost function subject to each task meeting its own constraint. When tasks are processed over a single stage, it has been shown that there are structural properties of the optimal state trajectory that lead to very efficient solutions of such problems. When tasks are processed over multiple stages and are subject to end-to-end real-time constraints, these properties no longer hold and no obvious extensions are known. We consider such a multi-stage problem with not only stage-dependent but also task-dependent cost functions over all tasks at each stage and derive several new optimality properties. These properties lead to the idea of introducing ldquovirtualrdquo deadlines at each stage except the last one, thus partially decoupling the stages so that the known efficient solutions for single-stage problems can be used. We prove that a sequence of solutions to single-stage problems with virtual deadlines updated at each step converges to the global optimal solution of the multi-stage problem. This leads to a virtual deadline algorithm (VDA) which is scalable in the number of processed tasks. We illustrate the scalability and efficiency of the VDA through numerical examples.     

An event domain formalism for sample path perturbation analysis of discrete event dynamic systems

We present a state-space representation of a general discrete event dynamic system (DEDS) model on the basis of a natural event domain, which replaces time. Perturbation analysis of a sample path Of a DEDS is then formalized using some fundamental concepts introduced to establish conditions for its validity. A set of simple perturbation equations is then derived under these conditions, so that performance gradients with respect to parameters are estimated from observation of real or simulated data on a single sample path.     

Optimal scheduling of two competing queues with blocking

Consideration is given to the problem of optimal scheduling for two queues for service at a single station, where the queues have finite capacities and the service rate is class-dependent. The cost structure is linear in the number of holding customers in the queues, combined with blocking costs incurred whenever arrivals encounter a full queue. The authors derive the optimal policy minimizing this criterion when the blocking cost is larger than the holding cost for each queue. Then they show that the optimal policy is of the switching type. Numerical results are included to support the analytical findings