Analysis of an open tandem queueing network with population constraint and constant service times 1

We consider an open tandem queueing network with population constraint and constant service times. The total number of customers that may be present in the network can not exceed a given value K. Customers arriving at the queueing network when there are more than K customers are forced to wait in an external queue. The arrival process to the queueing network is assumed to be arbitrary. We show that this queueing network can be transformed into a simple network involving only two nodes. Using this simple network, we obtain an upper and lower bound on the mean waiting time. These bounds can be easily calculated. Validations against simulation data establish the tightness of these bounds.     

State space collapse and stability of queueing networks

We study the stability of subcritical multi-class queueing networks with feedback allowed and a work-conserving head-of-the-line service discipline. Assuming that the fluid limit model associated to the queueing network satisfies a state space collapse condition, we show that the queueing network is stable provided that any solution of an associated linear Skorokhod problem is attracted to the origin in finite time. We also give sufficient conditions ensuring this attraction in terms of the reflection matrix of the Skorokhod problem, by using an adequate Lyapunov function. State space collapse establishes that the fluid limit of the queue process can be expressed in terms of the fluid limit of the workload process by means of a lifting matrix.     

����ά�DZ���Jackson����ļ�����Ϊ

??For the infinite Jackson network, assume that the net input rates are greater than the service rates for some nodes. Via solving the new throughput equation, the stochastic comparable processes are obtained by coupling method, and furthermore the limits for the queueing length in all nodes are also obtained. Despite the whole network is non-ergodic, it is possible to get the maximal ergodic subnetwork.     

Tandem behavior of a telecommunication system with finite buffers and repeated calls

The tandem behavior of a telecommunication system with finite buffers and repeated calls is modeled by the performance of a finite capacityG/M/1 queueing system with general interarrival time distribution, exponentially distributed service time, the first-come-first-served queueing discipline and retrials. In this system a fraction of the units which on arrival at a node of the system find it busy, may retry to be processed, by merging with the incoming arrival units in that node, after a fixed delay time. The performance of this system in steady state is modeled by a queueing network and is approximated by a recursive algorithm based on the isolation method. The approximation outcomes are compared against those from a simulation study. Our numerical results indicate that in steady state the non-renewal superposition arrival process, the non-renewal overflow process, and the non-renewal departure process of the above system can be approximated with compatible renewal processes.     

A generalization of Norton's theorem for queueing networks

A general framework for aggregation and decomposition of product form queueing networks with state dependent routing and servicing is presented. By analogy with electrical circuit theory, the stations are grouped into clusters of subnetworks such that the process decomposes into a global process and a local process. Moreover, the local process factorizes into the subnetworks. The global process and the local processes can be analyzed separately as if they were independent. The global process describes the behaviour of the queuing network in which each cluster is aggregated into a single station, whereas the local process describes the behaviour of the subnetworks as if they are not part of the queueing network. The decomposition and aggregation method formalized in this paper allows us to first analyze the global behaviour of the queueing network and subsequently analyze the local behaviour of the subnetworks of interest or to aggregate clusters into single stations without affecting the behaviour of the rest of the queueing network. Conditions are provided such that:

- the global equilibrium distribution for aggregated clusters has a product form;

- this form can be obtained by merely monitoring the global behaviour;

- the computation of a detailed distribution, including its normalizing constant, can be decomposed into the computation of a global and a local distribution;

- the marginal distribution for the number of jobs at the stations of a cluster can be obtained by merely solving local behaviour.

As a special application, Norton's theorem for queueing networks is extended to queueing networks with state dependent routing such as due to capacity constraints at stations or at clusters of stations and state dependent servicing such as due to service delays for clusters of stations.     

The departure process of discrete-time queueing systems with Markovian type inputs

This paper proposes a unified matrix-analytic approach to characterize the output processes of general discrete-time lossless/lossy queueing systems in which time is synchronized/slotted into fixed length intervals called slots. The arrival process can be continuous- or discrete-time Markovian processes. It can be either renewal or non-renewal. The service of a customer commences at the beginning of a slot, consumes a random number of slots, and completes at the end of a later slot. The service times are independent and follow a common and general distribution. Systems with and without server vacations are both treated in this paper. These queueing systems have potential applications in asynchronous transfer mode (ATM) networks, packet radio networks, etc. Since the output process of a node in a queueing network becomes an input process to some node at the next stage, the results of this paper can be used to facilitate end-to-end performance analysis which has attracted more and more attention in the literature. This revised version was published online in June 2006 with corrections to the Cover Date.     

A Markov Renewal Based Model for Wireless Networks

We propose a queueing network model which can be used for the integration of the mobility and teletraffic aspects that are characteristic of wireless networks. In the general case, the model is an open network of infinite server queues where customers arrive according to a non-homogeneous Poisson process. The movement of a customer in the network is described by a Markov renewal process. Moreover, customers have attributes, such as a teletraffic state, that are driven by continuous time Markov chains and, therefore, change as they move through the network. We investigate the transient and limit number of customers in disjoint sets of nodes and attributes. These turn out to be independent Poisson random variables. We also calculate the covariances of the number of customers in two sets of nodes and attributes at different time epochs. Moreover, we conclude that the arrival process per attribute to a node is the sum of independent Poisson cluster processes and derive its univariate probability generating function. In addition, the arrival process to an outside node of the network is a non-homogeneous Poisson process. We illustrate the applications of the queueing network model and the results derived in a particular wireless network.     

Generalized steiner problem in series-parallel networks

The generalized Steiner problem (GSP) is concerned with the determination of a minimum cost subnetwork of a given network where some (not necessarily all) vertices satisfy certain pairwise (vertex or edge) connectivity requirements. The GSP has applications to the design of water and electricity supply networks, communication networks and other large-scale systems where connectivity requirements ensure the communication between the selected vertices when some vertices and/or edges can become inoperational due to scheduled maintenance, error, or overload. The GSP is known to be NP-complete. In this paper we show that if the subnetwork is required to be respectively biconnected and edge-biconnected, and the underlying network is series-parallel, both problems can be solved in linear time.     

Generalized steiner problem in outerplanar networks

The generalized Steiner problem (GSP) is concerned with the determination of a minimum cost subnetwork of a given network where some (not necessarily all) vertices satisfy certain pairwise (vertex or edge) connectivity requirements.The GSP has applications to the design of water and electricity supply networks, communication networks and other large-scale systems where connectivity requirements ensure the communication between the selected vertices when some vertices and/or edges can become inoperational due to scheduled maintenance, error, or overload.The GSP is known to beNP-complete. In this paper we show that if the subnetwork is required to be biconnected or respectively edge-biconnected, and the underlying network is outerplanar, the GSP can be solved in linear time.     

Jitter analysis of an MMPP-2 tagged stream in the presence of an MMPP-2 background stream

We first consider a single-server queue that serves a tagged MMPP-2 stream and a background MMPP-2 stream in a FIFO manner. The service time is exponentially distributed. For this queueing system, we obtain the CDF of the tagged inter-departure time, from which we can calculate the jitter, defined as a percentile of the inter-departure time. The formulation is exact, but the solution is obtained numerically, which introduces an error that has been found to be negligible. Subsequently, we consider a tandem queueing network consisting of N tandem queues, which is traversed by the MMPP-2 tagged stream, and where each queue also serves a local MMPP-2 background stream. For this queueing network, we obtain an upper bound on the CDF of the inter-departure time from the Nth queue using a heavy traffic approximation, and we verify it by simulation.     

Analysis of G/D/1 Queueing Systems with Inputs Satisfying Large Deviation Principle under Weak* Topology

The large deviation principle (LDP) which has been effectively used in queueing analysis is the sample path LDP, the LDP in a function space endowed with the uniform topology. Chang [5] has shown that in the discrete-time G/D/1 queueing system under the FIFO discipline, the departure process satisfies the sample path LDP if so does the arrival process. In this paper, we consider arrival processes satisfying the LDP in a space of measures endowed with the weak^* topology (Lynch and Sethuraman [12]) which holds under a weaker condition. It is shown that in the queueing system mentioned above, the departure processes still satisfies the sample path LDP. Our result thus covers arrival processes which can be ruled out in the work of Chang [5]. The result is then applied to obtain the exponential decay rate of the queue length probability in an intree network as was obtained by Chang [5], who considered the arrival process satisfying the sample path LDP.     

Marginal queue length approximations for a two-layered network with correlated queues

We consider an extension of the classical machine-repair model, where we assume that the machines, apart from receiving service from the repairman, also serve queues of products. The extended model can be viewed as a layered queueing network, where the first layer consists of the queues of products and the second layer is the ordinary machine-repair model. As the repair time of one machine may affect the time the other machine is not able to process products, the downtimes of the machines are correlated. This correlation leads to dependence between the queues of products in the first layer. Analysis of these queue length distributions is hard, as the exact dependence structure for the downtimes, or the queue lengths, is not known. Therefore, we obtain an approximation for the complete marginal queue length distribution of any queue in the first layer, by viewing such a queue as a single server queue with correlated server downtimes. Under an explicit assumption on the form of the downtime dependence, we obtain exact results for the queue length distribution for that single server queue. We use these exact results to approximate the machine-repair model. We do so by computing the downtime correlation for the latter model and by subsequently using this information to fine-tune the parameters we introduced to the single server queue. As a result, we immediately obtain an approximation for the queue length distributions of products in the machine-repair model, which we show to be highly accurate by extensive numerical experiments.     

State-dependent Coupling of Quasireversible Nodes

The seminal paper of Jackson began a chain of research on queueing networks with product-form stationary distributions which continues strongly to this day. Hard on the heels of the early results on queueing networks followed a series of papers which discussed the relationship between product-form stationary distributions and the quasireversibility of network nodes. More recently, the definition of quasireversibility and the coupling mechanism between nodes have been extended so that they apply to some of the later product-form queueing networks incorporating negative customers, signals, and batch movements.In parallel with this research, it has been shown that some special queueing networks can have arrival and service parameters which depend upon the network state, rather than just the node state, and still retain a generalised product-form stationary distribution.In this paper we begin by offering an alternative proof of a product-form result of Chao and Miyazawa and then build on this proof by postulating a state-dependent coupling mechanism for a quasireversible network. Our main theorem is that the resultant network has a generalised product form stationary distribution. We conclude the paper with some examples.     

Decomposition approximation of queueing-network control models with tree structures

We devise a decomposition approximation method for a general branching queueing network with service-rate controls. The decomposition method, which reduces and simplifies computation routines considerably, results from the conditions for monotone optimal control policies in induction arguments. We first isolate each branch of connected queues as a subnetwork and then link the subnetworks through branching nodes to approximate the optimal control policies for the global network. The numerical results for a wide class of cost models show that the approximated optimal policies from the decomposed problems are sufficiently close to the optimal policies of the global problem.     

Near optimal control of queueing networks over a finite time horizon

We propose a method for the control of multi-class queueing networks over a finite time horizon. We approximate the multi-class queueing network by a fluid network and formulate a fluid optimization problem which we solve as a separated continuous linear program. The optimal fluid solution partitions the time horizon to intervals in which constant fluid flow rates are maintained. We then use a policy by which the queueing network tracks the fluid solution. To that end we model the deviations between the queuing and the fluid network in each of the intervals by a multi-class queueing network with some infinite virtual queues. We then keep these deviations stable by an adaptation of a maximum pressure policy. We show that this method is asymptotically optimal when the number of items that is processed and the processing speed increase. We illustrate these results through a simple example of a three stage re-entrant line. Research supported in part by Israel Science Foundation Grant 249/02 and 454/05 and by European Network of Excellence Euro-NGI.     

Solving a vehicle routing problem by balancing the vehicles time utilization

Various vehicle routing problems (VRP) appear in the literature due to their important applications in the area of transportation and distribution.A VRP is characterized by the constraints that the involved factors must satisfy and by an optimality goal.In this paper, we develop a heuristic algorithm that

• (i)partitions suitably a distribution network into subnetworks. A single depot complies with every subnetwork, where a fleet of identical vehicles will start their itinerary. The nodes of the corresponding subnetwork are demand nodes that require a onetime visit by one only vehicle.
• (ii)Determine the routes of k vehicles, k=2,3,…, for every subnetwork so to minimize the visiting time of the corresponding demand nodes. Consequently the method computes the necessary vehicle number for each subnetwork so as to complete promptly the visiting requirement of all the demand nodes of the whole network. The main strategy of the algorithm for designing the vehicle routes consists of balancing the time utilization of the used vehicles. The paper is integrated by an application of the presented algorithm to the center of the city of Thessaloniki.

     

MARKOV SKELETON PROCESS IN PERT NETWORKS

In this article, we investigate Programming Evaluation and Review Technique networks with independently and generally distributed activity durations. For any path in this network, we select all the activities related to this path such that the completion time of the sub-network （only consisting of all the related activities） is equal to the completion time of this path. We use the elapsed time as the supplementary variables and model this sub-network as a Markov skeleton process, the state space is related to the subnetwork structure. Then use the backward equation to compute the distribution of the sub-network＇s completion time, which is an important rule in project management and scheduling.     

Heavy traffic approximations of large deviations of feedforward queueing networks

We consider a multi-class feedforward queueing network with first come first serve queueing discipline and deterministic services and routing. The large deviation asymptotics of tail probabilities of the distribution of the workload vector can be characterized by convex path space minimization problems with non-linear constraints. So far there exists no numerical algorithm which could solve such minimization problems in a general way. When the queueing network is heavily loaded it can be approximated by a reflected Brownian motion. The large deviation asymptotics of tail probabilities of the distribution of this heavy traffic limit can again be characterized by convex path space minimization problems with non-linear constraints. However, due to their less complicated structure there exist algorithms to solve such minimization problems. In this paper we show that, as the network tends to a heavy traffic limit, the solution of the large deviation minimization problems of the network approaches the solution of the corresponding minimization problems of a reflected Brownian motion. Stated otherwise, we show that large deviation and heavy traffic asymptotics can be interchanged. We prove this result in the case when the network is initially empty. Without proof we state the corresponding result in the stationary case. We present an illuminating example with two queues. This revised version was published online in June 2006 with corrections to the Cover Date.     

Queueing networks with dependent nodes and concurrent movements

Classical queueing network processes are useful for modeling the movement of discrete units in a network in which the nodes operate independently, the routing of units is independent of the congestion, only one unit moves at a time and its equilibrium distribution is a well-understood product form. Actual networks, however, typically have dependent nodes and concurrent movement of units. Imagine the dependencies associated with the network movements of telephone calls, manufacturing material, computer data packets, messages in a parallel-processing simulation, etc. A second generation of queueing network processes is beginning to evolve for modeling such “intelligent” networks with dependent nodes and concurrent movements. This paper describes the following fundamental processes that have been developed in this regard:

? A basic queueing network process for dependent nodes and single-unit movements. Examples include the classical Jackson, BCMP, Kelly and Kelly-Whittle networks and networks with interacting subpopulations.

? Reversible queueing network processes for dependent nodes and concurrent movements. An example is a multivariate, compound birth-death process.

? Miscellaneous partially balanced queueing networks. Examples include extensions of the basic network processes and weakly coupled and quasi-reversible networks.

     

Deadlock properties of queueing networks with finite capacities and multiple routing chains

Blocking in queueing network models with finite capacities can lead to deadlock situations. In this paper, deadlock properties are investigated in queueing networks with multiple routing chains. The necessary and sufficient conditions for deadlockfree queueing networks with blocking are provided. An optimization algorithm is presented for finding deadlock-free capacity assignments with the least total capacity. The optimization algorithm maps the queueing network into a directed graph and obtains the deadlock freedom conditions from a specified subset of cycles in the directed graph. In certain network topologies, the number of deadlock freedom conditions can be large, thus, making any optimization computationally expensive. For a special class of topologies, so-calledtandem networks, it is shown that a minimal capacity assignment can be directly obtained without running an optimization algorithm. Here, the solution to the minimal capacity assignment takes advantage of the regular topology of tandem networks.This work was supported by the National Science Foundation under Grant No. CCR-90-11981.