Importance sampling for Jackson networks with customer impatience until the end of service

Importance sampling is a technique that is commonly used to speed up Monte Carlo simulation of rare events. The standard approach, which simulates the system using an a priori fixed change of measure, has been shown to fail in even the simplest network settings. Estimating probabilities associated with rare events has been a topic of great importance in queuing theory, and in applied probability at large. In this paper, we estimate the probability of two rare events known as total population overflow and individual buffer overflow in an open Jackson network in which the customers should receive the needed service in a definite deadline. we use parallel computing in implementing the estimator. Moreover, we consider the effect of various network parameters on aforementioned overflow probabilities, and we have also shown that how these parameters affect the probability of missing the deadline.     

Optimal scheduling with deadline constraints in tree networks

The problem of scheduling time-critical messages over a tree network is considered. Messages arrive at any of the nodes and have to reach the root node before their deadlines expire, else they are considered lost. The network is assumed to be operating in discrete time and the messages need one time unit for transmission from one node to the next along its path. The arrival and deadline processes are arbitrary. The policy which transmits messages with smallest extinction (arrival+deadline) time at every link is shown to minimize the number of lost messages over all time intervals and for every sample path     

Aperiodic servers in a deadline scheduling environment

A real-time system may have tasks with soft deadlines, as well as hard deadlines. While earliest-deadline-first scheduling is effective for hard-deadline tasks, applying it to soft-deadline tasks may waste schedulable processor capacity or sacrifice average response time. Better average response time may be obtained, while still guaranteeing hard deadlines, with an aperiodic server. Three scheduling algorithms for aperiodic servers are described, and schedulability tests are derived for them. A simulation provides performance data for these three algorithms on random aperiodic tasks. The performances of the deadline aperiodic servers are compared with those of several alternatives, including background service, a deadline polling server, and rate-monotonic servers, and with estimates based on the M/M/1 queueing model. This adds to the evidence in support of deadline scheduling,versus fixed priority scheduling.     

基于排队网络的多优先级MapReduce作业调度算法

MapReduce是一个能够对大规模数据进行分布式处理的框架,目前被各个领域广泛应用。在提供MapReduce服务的集群中,如何保证不同优先级用户的截止时间限定是MapReduce作业调度问题的一个挑战。针对这一问题,提出了一个基于排队网络的多优先级作业调度算法（MPSA）。首先分析和归纳了基于MapReduce模型的算法,提出了三种常见模式,采用Jackson排队网络对基于MapReduce模型的算法建立了数学模型,应用该网络模型可以求出不同优先级队列对资源的需求;随后使用AR(1)模型进行预测,使算法可以动态地适应不同的用户访问量;利用二分查找算法,分步计算出不同优先级在map阶段和reduce阶段分配的槽位数;最后实现了在MapReduce模型中应用的实时调度算法。实验结果表明,与传统的FIFO和公平调度算法相比,本文提出的算法在用户到达率和任务规模变化的情况下,可以更加有效地满足不同优先级用户的截止时间限定。     

Aperiodic task scheduling for Hard-Real-Time systems

A real-time system consists of both aperiodic and periodic tasks. Periodic tasks have regular arrival times and hard deadlines. Aperiodic tasks have irregular arrival times and either soft or hard deadlines. In this article, we present a new algorithm, the Sporadic Server algorithm, which greatly improves response times for soft deadline aperiodic tasks and can guarantee hard deadlines for both periodic and aperiodic tasks. The operation of the Sporadic Server algorithm, its performance, and schedulability analysis are discussed and compared with previously published aperiodic service algorithms.     

Optimal importance sampling for Markovian systems with applications to tandem queues

Importance sampling is a change-of-measure technique for speeding up the simulation of rare events in stochastic systems. In this paper we establish a number of properties characterizing optimal importance sampling measures for Markovian systems. We use these properties to develop a new method for computing the optimal measure and give specific results for a tandem queueing system. Optimal measures, though as diffcult to compute as the rare event probability itself, give useful insight into the characteristics of importance sampling measures. Our approach has no immediate computational advantage over other methods, but it suggests a number of heuristic approximations which may lead to computationally attractive methods.     

Performance evaluation of product form cellular mobile communications networks

This paper proposes and analyzes a queueing network model of a cellular mobile communications network including the multiway connection. This model is formulated as a queueing network with multiple call classes and state-dependent transition rates. As the performance measure a handover blocking probability is evaluated based on the product form equilibrium distribution and the constraint matrix whose elements consist of the mean arrival and service rates for individual cells. As a numerical example, an eight-cell cellular system is considered and blocking probabilities for a two-way handover between neighbouring cells are calculated for several network loads and constraint matrices. Since results represent the characteristics depending on individual cells or neighbouring cells, it can be emphasized that this model is useful for the control of QoS taking account of the spatial traffic.     

Parameter estimation for product-form distributions of queueing networks

Basic parameters of a queueing network are its routing matrix, arrival flow rate, and service rates at network nodes. To estimate these parameters, one has to solve a system of balance equations. In turn, a product-form limiting distribution of the number of customers at the network nodes is defined through loading factors. Therefore, in the paper we propose to estimate loading factors through estimates of the limiting distribution based on observations of the number of customers at the nodes. This makes it possible to avoid solving a system of balance equations. This algorithm is realized for Jackson networks: classical, in a random environment, with blocked transitions.     

On optimal lateness and tardiness scheduling in real-time systems

We address lateness and tardiness scheduling policies for real-time systems. It is well-known that preemptive Earliest Deadline First (EDF) minimizes the worst lateness and tardiness of a finite set of tasks with known arrival times, service times and deadlines to the finishing time, on a uniprocessor. We extend this result significantly, to include an arbitrary (possibly infinite) number of tasks with arbitrary arrival and service times, and deadlines, and to show thatEDF

1. minimizes the lateness and tardiness of the tasks that are in the system at an arbitrary time.
2. minimizes lateness within a busy interval, for an arbitrary, possibly infinite number of tasks.
3. maximizes the time to the first missed deadline, and
4. minimizes the length of time during which there is at least one missed deadline in the system.

We also show that a combination ofEDF and Shortest Remaining Processing Time First (SRPTF) policy minimizes maximum latenesses in a vector sense (as defined tin the paper) and minimizes the number of tasks that miss their deadline at the time the first missed deadline occurs. For non-preemptive non-idling polices, we establish new, similar results in a stochastic sense. We attempt extending our findings to multiprocessor systems. We demonstrate that under the assumptions of arbitrary distributions of arrival times, service times and deadlines, our results no longer hold true. When a further assumption of unit-length service times and integer-valued arrival times is introduced, we are able to re-establish the results in the multiprocessor case.     

Nonstationary analysis of circuit-switched communication networks

Circuit-switched communication networks have been analyzed extensively in the stationary case, i.e. where the arrival and/or service rates are independent of time. In this paper, we study a circuit-switched network where the rates of external arrivals at the network are time-dependent functions. The circuit-switched network is modelled as a nonstationary queueing network with population constraints, which is analyzed approximately in order to obtain the blocking probability functions. Using this method we model two circuit-switched networks, namely, a traffic-groomed tandem optical network and a single-orbit LEO satellite network.     

工程项目未按期完工概率估算的新型数值模拟算法

考虑到生产力波动、现场条件改变等不确定性因素的影响,工程项目的进度管理一般采用计划评审技术(program evaluation and review technique,PERT)网络模型,并以未按期完工概率作为重要的进度风险分析指标.针对工程项目的未按期完工概率估算,基于区域分解法,提出一种新型的数值模拟算法.针对PERT网络中的任一路径,将该路径的工期超出目标工期的事件定义为基本事件,从而将项目的未按期完工事件表示为所有基本事件的并集.所提出算法通过估计基本事件间的交集程度,对基本事件的概率求和进行折减,从而估算项目的未按期完工概率.通过算例验证,所提出模拟算法具有较好的估算准确度,且与蒙特卡罗方法相比有明显的计算效率提升.     

A quick simulation method for excessive backlogs in networks ofqueues

Excessive backlogs in stable open Jackson networks are studied. Although these events occur rarely, they can be critical, since they can impair the functioning of the network. The use of simulation to estimate their probability is attempted. Since a direct simulation of a rare event takes a very long time, a method is discussed for changing the network to speed up the simulation, using a heuristic method. It is shown by examples that the method can be several orders of magnitude faster than direct simulations     

Deadline-based connection setup in wavelength-routed WDM networks

This article addresses the ubiquitous topic of quality of service (QoS) aware connection provisioning in wavelength-routed WDM optical networks. The impact of the connection setup time of an optical connection has not been adequately addressed in the open literature. As such, this paper presents a novel approach that uses the optical connection setup time as a service differentiator during connection provisioning. The proposed approach utilizes the Earliest Deadline First (EDF) queueing algorithm to achieve deadline-based connection setup management with the deadline being the setup time requirement of an optical connection. The proposed EDF-based approach would allow the network operator to improve the QoS perceived by the end clients. Performance of this novel scheme is analyzed by accurately calculating various parameters, such as the fraction of connections provisioned on-time (i.e. prior to deadline expiration) and the average time it takes to successfully setup a connection. In addition, the presented approach is validated by a simulation that analyzes the performance of the proposed connection setup scheme in the specific context of the National Science Foundation Network (NSFNET). The obtained results show that a deadline-based setup strategy can minimize blocking probability while achieving QoS differentiation.     

A closed-form solution on a level-dependent Markovian arrival process with queueing application

Abstract This paper reports a closed-form solution of the arrival events for a particular level-dependent Markovian arrival process (MAP). We apply the Baker–Hausdorff Lemma to the matrix expression of the number of arrival events in (0, t]. The successful derivation depends on the fact that the matrices representing the MAP have a specific structure. We report the results of numerical experiments indicating that the closed-form solution is less time-consuming than the uniformization technique for large values of t. As an application, we consider a finite-capacity, multi-server queueing model with impatient customers for possible use in automatic call distribution (ACD) systems. Our primary interest lies in performance measures related to customer waiting time, and we demonstrate how the closed-form solution is applicable to performance analysis.     

Diffusion approximation of open queueing networks with critical traffic levels

We consider an open Jackson network with a critical traffic level. The vector queueing process at the network nodes is shown to converge, with appropriate normalization, to a diffusion process with a reflecting boundary.Translated from Kibernetika, No. 4, pp. 90–96, July–August, 1989.     

Routing Messages with Release Time and Deadline Constraint

The problem of determining whether a set of real-time messages can be routed in a network is considered. Each message has five parameters-origin node, destination node, length, release time, and deadline. The complexity of the problem is considered under various restrictions of four parameters-origin node, destination node, release time, and deadline. It is shown that if the network is a arbitrary directed graph, the problem is NP-complete even when all four parameters are fixed; i.e., the messages have identical values in all four parameters. Motivated by the complexity of the problem, we consider a simple network-a unidirectional ring. For nonpreemptive transmission, it is shown that the problem is solvable in polynomial time if three of the four parameters are fixed, but becomes NP-complete if only two of them are fixed. The same kind of complexity results hold for preemptive transmission, except for the following two cases: (1) identical origin nodes and release times and (2) identical destination nodes and deadlines. The complexity of these two cases remains open. The issue of whether there is an optimal on-line algorithm is also considered. It is shown that no such algorithm can exist unless all of the remaining three parameters are fixed.     

Optimal control of parallel queues with impatient customers

We consider a queueing system with a number of identical exponential servers. Each server has its own queue with unlimited capacity. The service discipline in each queue is first-come-first-served (FCFS). Customers arrive according to a state-dependent Poisson process with an arrival rate which is a non-increasing function of the number of customers in the system. Upon arrival, a customer must join a server’s queue according to a stationary state-dependent policy, where the state is taken to be the number of customers in servers’ queues. No jockeying among queues is allowed. Each arriving customer is limited to a generally distributed patience time after which it must depart the system and is considered lost. Two models of customer behavior are considered: deadlines until the beginning of service and deadlines until the end of service. We seek an optimal policy to assign an arriving customer to a server’s queue. We show that, when the distribution of customer impatience satisfies certain property, the policy of joining shortest queue (SQ) stochastically minimizes the number of lost customers during any finite interval in the long run. This property is shown to always hold for the case of deterministic customer impatience.     

Simulation of queueing network with time varying arrival rates

Queueing models are important in the analysis of many aspects of system or human behaviour. In such widely divergent fields as administrative processes, health services, traffic control, production control, computer communication networks, time sharing, and architecture, queueing analysis is indisposable for better understanding and ultimately synthesis of the system.However straight mathematical analysis is difficult, as the difference equations describing a queueing network are non-linear and of infinite dimensional. Due to this difficulty, time varying cases are seldomly included in the study of analytic solutions of queueing systems. In existing literature, the mean arrival rates are assumed independent of time. This assumption is of dubious validity as the arrival rate in actual operations varies with a twenty four hours period. While one can assume further that at every instant in time, the equilibrium condition for constant arrival rate is reached for the current arrival rate, it has never been verified that such is the case.An alternative approach is to reduce the queueing problem to finite dimensional and to simulate it on computer as is proposed in the present paper. The basic assumptions are (1) time-varying random arrival rate with Poisson statistics and (2) exponentially distributed service time. An algorithm and flow diagram for doing this is given. With the simulation techniques developed in this paper, we can study the dynamics of varying arrival rate. Simulation of a simple network shows that as the arrival rate approaches capacity, the divergence between simulated results and previous analytical results for the equilibrium condition become increasingly large. A conclusion is therefore that except for systems with very light loading, analytical results based on constant arrival rate are not accurate. Simulation is necessary if one is to obtain a true picture of the system.     

The overflow process from a state-dependent queue

The interoverflow time distribution is explicitly obtained as a power series for a finite-state queueing system with general state-dependent arrival and service rates. This can be expressed as a hyper-exponential distribution in closed form for specific constant, linear and quadratic arrival and service rates. Further, we obtain an explicit formula for the rth moment of the overflow process. We also analyse the inverse problem of finding the arrival and service rates from the given spectral data. Numerical illustrations are presented.     

Buffer Management for Colored Packets with Deadlines

We consider buffer management of unit packets with deadlines for a multi-port device with reconfiguration overhead. The goal is to maximize the throughput of the device, i.e., the number of packets delivered by their deadline. For a single port or with free reconfiguration, the problem reduces to the well-known packets scheduling problem, where the celebrated earliest-deadline-first (EDF) strategy is optimal 1-competitive. However, EDF is not 1-competitive when there is a reconfiguration overhead. We design an online algorithm that achieves a competitive ratio of 1−o(1) when the ratio between the minimum laxity of the packets and the number of ports tends to infinity. This is one of the rare cases where one can design an almost 1-competitive algorithm. One ingredient of our analysis, which may be interesting on its own right, is a perturbation theorem on EDF for the classical packets scheduling problem. Specifically, we show that a small perturbation in the release and deadline times cannot significantly degrade the optimal throughput. This implies that EDF is robust in the sense that its throughput is close to the optimum even when the deadlines are not precisely known.