An Overview for Markov Decision Processes in Queues and Networks <s> Objective six: Dynamic control of queueing networks with useful information <s> In a distributed computing system made up of different types of processors each processor in the system may have different performance and reliability characteristics. In order to take advantage of this diversity of processing power, a modular distributed program should have its modules assigned in such a way that the applicable system performance index, such as execution time or cost, is optimized. This paper describes an algorithm for making an optimal module to processor assignment for a given performance criteria. We first propose a computational model to characterize distributed programs, consisting of tasks and an operational precedence relationship. This model alows us to describe probabilistic branching as well as concurrent execution in a distributed program. The computational model along with a set of seven program descriptors completely specifies a model for dynamic execution of a program on a distributed system. The optimal task to processor assignment is found by an algorithm based on results in Markov decision theory. The algorithm given in this paper is completely general and applicable to N-processor systems. <s> BIB001 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Objective six: Dynamic control of queueing networks with useful information <s> In this paper we consider a queueing system having n exponential servers, each with its own queue and service rate. Customers arrive according to a Poisson process with rate λ, and upon arrival each customer must be routed to some server's queue. No jockeying amongst the queues is allowed and each server serves its queue according to a first-come-first-served discipline. Each server i , 1 ≦ i ≦ n , provides service with a state-dependent rate μ ( i ) ( k ), k = 0, 1, …. In addition, at every queue i , there is a deterministic holding cost which occurs at rate h ( i ) ( k ) while there are k customers at the queue. An admissible routing policy is a policy that assigns each arriving customer to one of the queues. A decision at time t may be randomized and dependent on the queue lengths and decisions till time t . An optimal routing policy is an admissible policy that minimizes the long-run average holding cost. In this study, we bound the optimal cost from below, by considering an ideal system, where each server optimally selects a given proportion of customers, irrespective of other servers' selections. From this ideal system we construct a class of admissible routing policies, the overflow routing class , that approximates the ideal situation for each server. Finally, we evaluate the policies and compare them to the lower bound. <s> BIB002 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Objective six: Dynamic control of queueing networks with useful information <s> Abstract In distributed systems, load balancing can improve efficiency by migrating jobs from heavily loaded to lightly loaded sites. In this paper we present a method for optimal load allocation in a static environment. A queueing network model is used to evaluate response time, and mathematical programming techniques are used to find the load allocation that minimizes average response time. The method is not proposed as a substitute for dynamic, heuristic load balance policies; rather, it is perceived as a useful tool for resource allocation and capacity planning in distributed systems and as a promising complement to dynamic policies in hybrid load balance strategies. The method can handle very general classes of problems, including distinct classes of jobs, multitasking within each job, and jobs with spawned tasks. Several examples illustrating these applications are reported. <s> BIB003 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Objective six: Dynamic control of queueing networks with useful information <s> We consider a discrete-time Markov decision process with a partially ordered state space and two feasible control actions in each state. Our goal is to find general conditions, which are satisfied in a broad class of applications to control of queues, under which an optimal control policy is monotonic. An advantage of our approach is that it easily extends to problems with both information and action delays, which are common in applications to high-speed communication networks, among others. The transition probabilities are stochastically monotone and the one-stage reward submodular. We further assume that transitions from different states are coupled, in the sense that the state after a transition is distributed as a deterministic function of the current state and two random variables, one of which is controllable and the other uncontrollable. Finally, we make a monotonicity assumption about the sample-path effect of a pairwise switch of the actions in consecutive stages. Using induction on the horizon length, we demonstrate that optimal policies for the finite- and infinite-horizon discounted problems are monotonic. We apply these results to a single queueing facility with control of arrivals and/or services, under very general conditions. In this case, our results imply that an optimal control policy has threshold form. Finally, we show how monotonicity of an optimal policy extends in a natural way to problems with information and/or action delay, including delays of more than one time unit. Specifically, we show that, if a problem without delay satisfies our sufficient conditions for monotonicity of an optimal policy, then the same problem with information and/or action delay also has monotonic (e.g., threshold) optimal policies. <s> BIB004 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Objective six: Dynamic control of queueing networks with useful information <s> Considers discrete-time versions of two classical problems in the optimal control of admission to a queueing system: (i) optimal routing of arrivals to two parallel queues and (ii) optimal acceptance/rejection of arrivals to a single queue. The authors extend the formulation of these problems to permit a k step delay in the observation of the queue lengths by the controller. For geometric inter-arrival times and geometric service times the problems are formulated as controlled Markov chains with expected total discounted cost as the minimization objective. For problem (i) the authors show that when k=1, the optimal policy is to allocate an arrival to the queue with the smaller expected queue length (JSEQ: Join the Shortest Expected Queue). The authors also show that for this problem, for k/spl ges/2, JSEQ is not optimal. For problem (ii) the authors show that when k=1, the optimal policy is a threshold policy. There are, however, two thresholds m/sub 0//spl ges/m/sub 1/>0, such that m/sub 0/ is used when the previous action was to reject, and m/sub 1/ is used when the previous action was to accept. > <s> BIB005 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Objective six: Dynamic control of queueing networks with useful information <s> Load balancing problems for multiclass jobs in distributed/parallel computer systems with general network configurations are considered. We construct a general model of such a distributed/parallel computer system. The system consists of heterogeneous host computers/processors (nodes) which are interconnected by a generally configured communication/interconnection network wherein there are several classes of jobs, each of which has its distinct delay function at each host and each communication link. This model is used to formulate the multiclass job load balancing problem as a nonlinear optimization problem in which the goal is to minimize the mean response time of a job. A number of simple and intuitive theoretical results on the solution of the optimization problem are derived. On the basis of these results, we propose an effective load balancing algorithm for balancing the load over an entire distributed/parallel system. The proposed algorithm has two attractive features. One is that the algorithm can be implemented in a decentralized fashion. Another feature is simple and straightforward structure. Models of nodes, communication networks, and a numerical example are illustrated. The proposed algorithm is compared with a well-known standard steepest-descent algorithm, the FD algorithm. By using numerical experiments, we show that the proposed algorithm has much faster convergence in terms of computational time than the FD algorithm. <s> BIB006 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Objective six: Dynamic control of queueing networks with useful information <s> We consider a system of parallel queues with dedicated arrival streams. At each decision epoch a decision-maker can move customers from one queue to another. The cost for moving customers consists of a fixed cost and a linear, variable cost dependent on the number of customers moved. There are also linear holding costs that may depend on the queue in which customers are stored. Under very mild assumptions, we develop stability (and instability) conditions for this system via a fluid model. Under the assumption of stability, we consider minimizing the long-run average cost. In the case of two-servers the optimal control policy is shown to prefer to store customers in the lowest cost queue. When the inter-arrival and service times are assumed to be exponential, we use a Markov decision process formulation to show that for a fixed number of customers in the system, there exists a level S such that whenever customers are moved from the high cost queue to the low cost queue, the number of customers moved brings the number of customers in the low cost queue to S. These results lead to the development of a heuristic for the model with more than two servers. <s> BIB007 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Objective six: Dynamic control of queueing networks with useful information <s> While vacation processes are considered to be ordinary behavior for servers, the study of queueing networks with server vacations is limited, interesting, and challenging. In this paper, we provide a unified and effective method of functional analysis for the study of a supermarket model with server multiple vacations. Firstly, we analyze a supermarket model of N identical servers with server multiple vacations, and set up an infinite-dimensional system of differential (or mean-field) equations, which is satisfied by the expected fraction vector, in terms of a technique of tailed equations. Secondly, as N??? we use the operator semigroup to provide a mean-field limit for the sequence of Markov processes, which asymptotically approaches a single trajectory identified by the unique and global solution to the infinite-dimensional system of limiting differential equations. Thirdly, we provide an effective algorithm for computing the fixed point of the infinite-dimensional system of limiting differential equations, and use the fixed point to give performance analysis of this supermarket model, including the mean of stationary queue length in any server and the expected sojourn time that any arriving customer spends in this system. Finally, we use some numerical examples to analyze how the performance measures depend on some crucial factors of this supermarket model. Note that the method of this paper will be useful and effective for performance analysis of complicated supermarket models with respect to resource management in practical areas such as computer networks, manufacturing systems and transportation networks. <s> BIB008 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Objective six: Dynamic control of queueing networks with useful information <s> In this paper, we provide a key generalization of the supermarket model both from the impatient customers and from a doubly dynamic control, which may also be related to the size-based scheduling through the centered management of the customer resource as well as the total service ability. We first use an infinite-dimensional Markov process to express the states of this supermarket model, and set up an infinite-dimensional system of differential equations satisfied by the expected fraction vector. Then we use the operator semigroup to provide a mean-field limit for the sequence of infinite-dimensional Markov processes, which asymptotically approaches a single trajectory identified by the unique and global solution to the infinite-dimensional system of limiting differential equations. Finally, we provide an effective and efficient algorithm for computing the fixed point of the infinite-dimensional system of limiting differential equations, and use the fixed point to give performance analysis of this supermarket model. Also, some numerical examples are given to demonstrate how the performance measures depend on some crucial parameters of this supermarket model. We believe that the mean-field method developed in this paper will be useful and effective for analyzing more complicated supermarket models in many practical areas. <s> BIB009 </s> An Overview for Markov Decision Processes in Queues and Networks <s> Objective six: Dynamic control of queueing networks with useful information <s> Big networks express various large-scale networks in many practical areas such as computer networks, internet of things, cloud computation, manufacturing systems, transportation networks, and healthcare systems. This paper analyzes such big networks, and applies the mean-field theory and the nonlinear Markov processes to set up a broad class of nonlinear continuous-time block-structured Markov processes, which can be applied to deal with many practical stochastic systems. Firstly, a nonlinear Markov process is derived from a large number of interacting big networks with symmetric interactions, each of which is described as a continuous-time block-structured Markov process. Secondly, some effective algorithms are given for computing the fixed points of the nonlinear Markov process by means of the UL-type RG-factorization. Finally, the Birkhoff center, the Lyapunov functions and the relative entropy are used to analyze stability or metastability of the big network, and several interesting open problems are proposed with detailed interpretation. We believe that the results given in this paper can be useful and effective in the study of big networks. <s> BIB010
In the queueing networks, the useful information plays a key role in dynamic control of queueing networks. Readers may refer to Kuri and Kumar BIB005 , Altman and Stidham BIB004 , Honhon and Seshadri  and Rosberg and Kermani BIB002 . Load balancing is an interesting research direction in queueing networks with simply observable information, e.g., see Down and Lewis BIB007 , Chou and Abraham BIB001 , e Silva and Gerla BIB003 , Li and Kameda BIB006 , Li et al. BIB008 BIB009 and Li and Lui BIB010 .