Level crossing analysis of priority queues and a conservation identity for vacation models

The two purposes of this article are to illustrate the power and simplicity of level crossing analysis and to present a conservation identity for M/G/1 priority queues with server vacations. To illustrate the use of level crossing analysis we apply it to preemptive (resume) priority M/G/1 queues with single- and multiple-server vacations considered by Kella and Yechiali (1986) and to non-preemptive priority M/M/c queues considered by Kella and Yechiali (1985). The conservation identity presented here states that the ratios of mean waiting times in an M/G/1 queue with and without server vacation policies are independent of the service discipline for first come first served, shortest processing time, shortest processing time within generations and non-preemptive priority service disciplines.     

Stochastic analysis of a single server retrial queue with general retrial times

Retrial queueing systems are widely used in teletraffic theory and computer and communication networks. Although there has been a rapid growth in the literature on retrial queueing systems, the research on retrial queues with nonexponential retrial times is very limited. This paper is concerned with the analytical treatment of an M/G/1 retrial queue with general retrial times. Our queueing model is different from most single server retrial queueing models in several respectives. First, customers who find the server busy are queued in the orbit in accordance with an FCFS (first‐come‐first‐served) discipline and only the customer at the head of the queue is allowed for access to the server. Besides, a retrial time begins (if applicable) only when the server completes a service rather upon a service attempt failure. We carry out an extensive analysis of the queue, including a necessary and sufficient condition for the system to be stable, the steady state distribution of the server state and the orbit length, the waiting time distribution, the busy period, and other related quantities. Finally, we study the joint distribution of the server state and the orbit length in non‐stationary regime. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 561–581, 1999     

African nations as proxies in covert cyber operations

The growth of the African Internet, and services related to the Internet, has been rapid over the last decade. Following this market expansion, a variety of service providers have started to provide access. A fast-growing market puts pressure on the providers to deliver services first and only then seek to secure the networks. Over time, industrialised nations have become more able to detect and trace cyber attacks against their networks. These tracking features are constantly developing and the precision in determining the origin of an attack is increasing. A state-sponsored cyber attacker, such as intelligence agencies and electronic warfare units, will seek to avoid detection, especially when the attacks are politically sensitive intelligence-gathering and intrusion forays into foreign states' networks. One way for the attacker to create a path that links the attacks and the originating country is by actions through a proxy. The less technologically mature developing nations offer an opportunity for cyber aggression due to their lower level of security under the quick expansion of the Internet-based market. Developing countries could be used as proxies, without their knowledge and consent, through the unauthorised usage of these countries' information systems in an attempt to attack a third country by a state-sponsored offensive cyber operation. If the purpose of the cyber attack is to destabilise a targeted society and the attack succeeds, the used proxies are likely to face consequences in their relations with foreign countries, even if the proxy was unaware of the covert activity.     

An M/M/1 queue with delayed feedback

We present some results for M/M/1 queues with finite capacities with delayed feedback. The delay in the feedback to an M/M/1 queue is modelled as another M-server queue with a finite capacity. The steady state probabilities for the two dimensional Markov process {N(t), M(t)} are solved when N(t) = queue length at server 1 at t and M(t) = queue length at server 2 at t. It is shown that a matrix operation can be performed to obtain the steady state probabilities. The eigenvalues of the operator and its eigenvectors are found. The problem is solved by fitting boundary conditions to the general solution and by normalizing. A sample problem is run to show that the solution methods can be programmed and meaningful results obtained numerically.     

Waiting time analysis for a queueing system with time‐limited service and exponential timer

We consider a single‐queue with exhaustive or gated time‐limited services and server vacations, in which the length of each service period at the queue is controlled by a timer, i.e., the server serves customers until the timer expires or the queue becomes empty, whichever occurs first, and then takes vacations. The customer whose service is interrupted due to the timer expiration may be attended according to nonpreemptive or preemptive service disciplines. For the M/G/1 exhaustive/gated time‐limited service queueing system with an exponential timer and four typical preemptive/nonpreemptive service disciplines, we derive the Laplace—Stieltjes transforms and the moment formulas for waiting times and sojourn times through a unified approach, and provide some new results for these time‐limited service disciplines. © John Wiley & Sons, Inc. Naval Research Logistics 48: 638–651, 2001.     

Approximation for the departure process of a queue in a network

A simple renewal process is identified to approximate the complex departure process of a queue often found in queueing network models. The arrival process to the queue is the superposition or merging of several independent component-renewal processes that are approximations of departure processes from other queues and external arrival processes; there is a single server with exponential service times, and the waiting space is infinite. The departure process of this queue is of interest because it is the arrival process to other queues in the network. The approximation proposed is a hybrid; the mean and variance of the approximating departure intervals is a weighted average of those determined by basic methods in Whitt [41] with the weighting function empirically determined using simulation. Tandem queueing systems with superposition arrival processes and exponential service times are used to evaluate the approximation. The departure process of the first queue in the tandem is approximated by a renewal process, the tandem system is replaced by two independent queues, and the second queue is solved analytically. When compared to simulation estimates, the average absolute error in hybrid approximations of the expected number in the second queue is 6%, a significant improvement over 22–41% in the basic methods.     

Approximations for heavily loaded G/GI/n + GI queues

Motivated by applications to service systems, we develop simple engineering approximation formulas for the steady‐state performance of heavily loaded G/GI/n+GI multiserver queues, which can have non‐Poisson and nonrenewal arrivals and non‐exponential service‐time and patience‐time distributions. The formulas are based on recently established Gaussian many‐server heavy‐traffic limits in the efficiency‐driven (ED) regime, where the traffic intensity is fixed at ρ > 1, but the approximations also apply to systems in the quality‐and‐ED regime, where ρ > 1 but ρ is close to 1. Good performance across a wide range of parameters is obtained by making heuristic refinements, the main one being truncation of the queue length and waiting time approximations to nonnegative values. Simulation experiments show that the proposed approximations are effective for large‐scale queuing systems for a significant range of the traffic intensity ρ and the abandonment rate θ, roughly for ρ > 1.02 and θ > 2.0. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 187–217, 2016     

Workload distribution of discrete‐time parallel queues with two servers

We study discrete‐time, parallel queues with two identical servers. Customers arrive randomly at the system and join the queue with the shortest workload that is defined as the total service time required for the server to complete all the customers in the queue. The arrivals are assumed to follow a geometric distribution and the service times are assumed to have a general distribution. It is a no‐jockeying queue. The two‐dimensional state space is truncated into a banded array. The resulting modified queue is studied using the method of probability generating function (pgf) The workload distribution in steady state is obtained in form of pgf. A special case where the service time is a deterministic constant is further investigated. Numerical examples are illustrated. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 440–454, 2000     

Using a birth‐and‐death process to estimate the steady‐state distribution of a periodic queue

If the number of customers in a queueing system as a function of time has a proper limiting steady‐state distribution, then that steady‐state distribution can be estimated from system data by fitting a general stationary birth‐and‐death (BD) process model to the data and solving for its steady‐state distribution using the familiar local‐balance steady‐state equation for BD processes, even if the actual process is not a BD process. We show that this indirect way to estimate the steady‐state distribution can be effective for periodic queues, because the fitted birth and death rates often have special structure allowing them to be estimated efficiently by fitting parametric functions with only a few parameters, for example, 2. We focus on the multiserver M_t/GI/s queue with a nonhomogeneous Poisson arrival process having a periodic time‐varying rate function. We establish properties of its steady‐state distribution and fitted BD rates. We also show that the fitted BD rates can be a useful diagnostic tool to see if an M_t/GI/s model is appropriate for a complex queueing system. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 664–685, 2015     

The single server queue in discrete time-numerical analysis I

This is the first of a sequence of papers dealing with the computational aspects of the transient behavior of queues in discrete time It is shown that for a substantial class of queues of practical interest, a wealth of numerical information may be obtained by relatively unsophisticated methods This approach should prove useful in the analysis of unstable queues which operate over a limited time interval, but is by no means limited to such queues Mathematically the service unit is modeled in terms of a multivariate Markov chain, whose particular structure is used in iterative computation. Many important queue features may then be derived from the n-step transition probabilities of this chain.     

Robust preallocated preferential defense

The problem is to protect a set of T identical targets that may come under attack by A identical weapons. The targets are to be defended by D identical interceptors, which must be preallocated to defend selected targets. The attacker is aware of the number of interceptors, but is ignorant of their allocation. The size of the attack is chosen by the attacker from within a specified range. The robust strategies developed in this article do not require the defender to assume an attack size. Rather, the defender chooses a strategy which is good over a wide range of attack sizes, though not necessarily best for any particular attack size. The attacker, knowing that the defender is adopting a robust strategy, chooses the optimal attack strategy for the number of weapons he chooses to expend. The expected number of survivors is a function of the robust defense strategy and optimal attack strategy against this robust defense.     

A note on sojourn times in M/G/1 queues with instantaneous,bernoulli feedback

Queueing systems which include the possibility for a customer to return to the same server for additional service are called queueing systems with feedback. Such systems occur in computer networks for example. In these systems a chosen customer will wait in the queue, be serviced and then, with probability p, return to wait again, be serviced again and continue this process until, with probability (1 – p) = q, it departs the system never to return. The time of waiting plus service time, the nth time the customer goes through, we will call his nth sojourn time. The (random) sum of these sojourn times we will call the total sojourn time (abbreviated, sojourn time when there is no confusion which sojourn time we are talking about). In this paper we study the total sojourn time in a queueing system with feedback. We give the details for M/G/1 queues in which the decision to feedback or not is a Bernoulli process. While the details of the computations can be more difficult, the structure of the sojourn time process is unchanged for the M/G/1 queue with a more general decision process as will be shown. We assume the reader is familiar with Disney, McNickle and Simon [1].     

Algorithmic and approximation analyses of the shorter queue model

A system of two parallel queues where the arrivals from a single stream of customers join the shorter queue is considered. Arrivals form a homogeneous Poisson stream and the service times in each of the two queues are independent exponential variates. By treating one of the queues as bounded, the steady-state probability vector for the system can be expressed in a modified matrix-geometric form and can be computed efficiently. Computational procedures for the sojourn time distribution and characteristics of the departure stream are developed. Some numerical results are presented, and based on these results an efficient approximation scheme for the model is developed which can be readily extended to systems with more than two parallel queues.     

级联失效下非对称依赖网络鲁棒性研究

研究级联失效下网络化信息物理系统的鲁棒性具有重要的现实意义.针对具有单向依赖关系的信息物理系统构建双层非对称依赖网络模型,综合依赖失效和过载失效设计级联失效模型,提出一种更贴近实际的非对称攻击方式,并给出一种资源限制下的节点容量分配方式.针对无标度子网构成的非对称依赖网络进行了仿真实验,结果表明:网络鲁棒性与子网络平均...     

Optimal control of entry to an M/Ek/1 queue serving several classes of customers

The individual and social optimum control policies for entry to an M/M//1 queue serving several classes of customers have been shown to be control-limit policies. The technique of policy iteration provides the social optimum policy for such a queue in a straightforward manner. In this article, the problem of finding the optimal control policy for the M/E_k/1 system is solved, thereby expanding the potential applicability of the solutions developed. The Markovian nature of the queueing system is preserved by considering the service as having k sequential phases, each with independent, identically distributed, exponential service times, through which a customer must pass to be serviced. The optimal policy derived by policy iteration for such a system is likely to be difficult to use because it requires knowledge of the number of phases rather than customers in the system when an arrival occurs. To circumvent this difficulty, a heuristic is used to find a good usable (implementable) solution. In addition, a mixed-integer program is developed which yields the optimal implementable solution when solved.     

Analysis of a finite‐buffer bulk‐service queue with discrete‐Markovian arrival process: D‐MAP/Ga,b/1/N

Discrete‐time queues with D‐MAP arrival process are more useful in modeling and performance analysis of telecommunication networks based on the ATM environment. This paper analyzes a finite‐buffer discrete‐time queue with general bulk‐service rule, wherein the arrival process is D‐MAP and service times are arbitrarily and independently distributed. The distributions of buffer contents at various epochs (departure, random, and prearrival) have been obtained using imbedded Markov chain and supplementary variable methods. Finally, some performance measures such as loss probability and average delay are discussed. Numerical results are also presented in some cases. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 345–363, 2003.     

Designing safety space in a supply chain to handle system‐wide disruptions

In some supply chains serious disruptions are system wide. This happens during periods of severe weather, as when storms cause shuttle tankers serving oil platforms in the North Sea to stop movements of crude oil, barges are frozen in the Mississippi, or all airplanes are grounded after a blizzard. Other notable instances of system‐wide disruption happened after the attack on the World Trade Center when all aircraft were grounded and the natural gas and crude‐oil pipelines were tangled by hurricanes in 2005. We model a situation where shutting down supply facilities is very difficult and expensive because of excessive inventory buildup from an inability to move out the production. We present a planning model that balances the cost of spare capacity versus shutting down production when planning for disruptions. The model uses an assignment model embedded in a simulation. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Scheduling policies for an antiterrorist surveillance system

This article concerns scheduling policies in a surveillance system aimed at detecting a terrorist attack in time. Terrorist suspects arriving at a public area are subject to continuous monitoring, while a surveillance team takes their biometric signatures and compares them with records stored in a terrorist database. Because the surveillance team can screen only one terrorist suspect at a time, the team faces a dynamic scheduling problem among the suspects. We build a model consisting of an M/G/1 queue with two types of customers—red and white—to study this problem. Both types of customers are impatient but the reneging time distributions are different. The server only receives a reward by serving a red customer and can use the time a customer has spent in the queue to deduce its likely type. In a few special cases, a simple service rule—such as first‐come‐first‐serve—is optimal. We explain why the problem is in general difficult and we develop a heuristic policy motivated by the fact that terrorist attacks tend to be rare events. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

Optimal patrol to uncover threats in time when detection is imperfect

Consider a patrol problem, where a patroller traverses a graph through edges to detect potential attacks at nodes. An attack takes a random amount of time to complete. The patroller takes one time unit to move to and inspect an adjacent node, and will detect an ongoing attack with some probability. If an attack completes before it is detected, a cost is incurred. The attack time distribution, the cost due to a successful attack, and the detection probability all depend on the attack node. The patroller seeks a patrol policy that minimizes the expected cost incurred when, and if, an attack eventually happens. We consider two cases. A random attacker chooses where to attack according to predetermined probabilities, while a strategic attacker chooses where to attack to incur the maximal expected cost. In each case, computing the optimal solution, although possible, quickly becomes intractable for problems of practical sizes. Our main contribution is to develop efficient index policies—based on Lagrangian relaxation methodology, and also on approximate dynamic programming—which typically achieve within 1% of optimality with computation time orders of magnitude less than what is required to compute the optimal policy for problems of practical sizes. © 2014 Wiley Periodicals, Inc. Naval Research Logistics, 61: 557–576, 2014     

无标度网络上的队列资源重分配策略

在实际的通信系统中,由于物理条件的限制,每个节点都具有有限长度的队列。研究了在有限队列资源的条件下,队列资源对无标度数据流动力学的影响。提出了一种队列资源重分配策略,策略中节点的队列长度与节点的介数成正比。仿真结果表明,在无标度网络中使用最短路径路由的条件下,所提出的重分配策略可以有效地改进网络的容量。同时对有限队列资源条件下的网络容量进行了理论分析。