Decomposition of Queueing Networks with Dependent Service and Negative Customers

Queueing networks with negative customers (G-networks) and dependent service at different nodes are studied. Every customer arriving at the network is defined by a set of random parameters: his route over the network (a sequence of nodes visited by the customers), route length, and volume and service length of the customer at every stage of the route. For G-networks, which are the analogs of BCMP-networks, the multidimensional stationary distribution of the network state probabilities is shown to be representable in product form.     

G-networks with resets

Gelenbe networks (G-networks) are product form queuing networks which, in addition to ordinary customers, contain unusual entities such as “negative customers” which eliminate normal customers and “triggers” which move other customers from some queue to another. These models have generated much interest in the literature since the early 1990s. The present paper discusses a novel model for a reliable system composed of N unreliable systems, which can hinder or enhance each other’s reliability. Each of the N systems also tests other systems at random; it is able to reset another system if it is itself in working condition and discovers that the other system has failed, so that the global reliability of the system is enhanced. This paper shows how an extension of G-networks that includes novel “reset” customers can be used to model this behavior. We then show that a general G-network model with resets has product form, and prove existence and uniqueness of its solution.     

Queueing Networks with Dynamic Routing and Dynamic Stochastic Bypass of Nodes

We consider open exponential networks with routing matrices that depend on a network state. A customer entering a node is either independently of other customers queued with probability that depends on the network state or instantly bypasses the node with complementary probability. After bypassing a node, customers are routed according to a stochastic matrix that depends on the network state and may differ from the routing matrix. Under certain restrictions on parameters of the model, we establish a sufficient ergodicity condition and find the final stationary distribution.     

Product from solutions for multiserver centres with concurrent classes of customers

The MultiServer centre with Concurrent Classes of Customers (MSCCC) is a service centre consisting of B parallel identical exponential servers. The customers requesting service at the MSCCC centre belong to K groups. Customers arriving at the MSCCC centre are queued in the order of their arrival. A customer from group k will go into service at the MSCCC centre provided that one or more of the B servers is free and that at most n − 1 other group k customers are in service at the MSCCC centre.

The MSCCC centre can be applied to model systems where customers simultaneously occupy two resources. The system resources are partitioned into K primary and B secondary resources. A customer of group k can access primary resource k if it already is in possession of a secondary resource and if at most n − 1 other group k customers are using primary resource k.

This paper defines the MSCCC centre and presents several examples of computer (sub)systems that can be modelled using the MSCCC centre. The MSCCC centre is shown to satisfy local balance: therefore a multiclass queuing network consisting of BCMP and MSCCC centres has a product form solution. The joint probability distribution (JPD) for a queuing network consisting of several BCMP centres and one MSCCC centre is derived. Aggregation techniques are next used to reduce the JPD to a computationally tractable form. A Mean Value Analysis algorithm is presented for calculating the closed and open chain performance measures at the MSCCC centre.     

Event-based optimization of admission control in open queueing networks

In this paper, we use the event-based optimization framework to study the admission control problem in an open Jackson network. The external arriving customers are controlled by an admission controller. The controller makes decision only at the epoch when an event of customer arrival happens. Every customer in the network obtains a fixed reward for each service completion and pays a cost with a fixed rate during its sojourn time (including waiting time and service time). The complete information of the system state is not available for the controller. The controller can observe only the number of total customers in the network. Based on the property of closed form solution of Jackson networks, we prove that the system performance is monotonic with respect to the admission probabilities and the optimal control policy has a threshold form. That is, when the number of total customers is smaller than a threshold, all of the arriving customers are admitted; otherwise, all are rejected. The sufficient condition and necessary condition of optimal policy are also derived. Furthermore, we develop an iterative algorithm to find the optimal policy. The algorithm can be executed based on a single sample path, which makes the algorithm online implementable. Simulation experiments are conducted to demonstrate the effectiveness of our approach.     

Response times in a two-node queueing network with feedback

The study presented in this paper is motivated by the performance analysis of response times in distributed information systems, where transactions are handled by iterative server and database actions. We model system response times as sojourn times in a two-node open queueing network with a processor sharing (PS) node and a first-come-first-served (FCFS) node. External customers arrive at the PS node according to a Poisson process. After departing from the PS node a customer proceeds to the FCFS node with probability p, and with probability 1−p the customer departs from the system. After a visit to the FCFS node, customers are fed back to the PS node. The service requirements at both nodes are exponentially distributed. The model is a Jackson network, admitting a product-from solution for the joint number of customers at the nodes, immediately leading to a closed-form expression for the mean sojourn times in steady-state. The variance of the sojourn times, however, does not admit an exact expression—the complexity is caused by the possibility of overtaking. In this paper we propose a methodology for deriving simple, explicit and fast-to-evaluate approximations for the variance of the sojourn times. Numerical results demonstrate that the approximations are very accurate in most model instances.     

An open exponential queuing network with limited waiting spaces and losses: A method of approximate analysis

Open exponential queuing networks are considered where each node in a network represents several exponential servers with a joint waiting space (a buffer) of limited capacity. A customer arriving to a node with fully occupied buffer is lost. An assumption is made that the input flow to each node formed as a mixture of the external Poisson flow and the flows coming from other nodes is a Poisson flow. Under this assumption, a method of computing network parameters is presented which is based on solving iteratively a system of nonlinear equations for the unknown nodal flow rates. A method based on Markov chain techniques is presented to find the approximate value of the average conditional sojourn time in the network for customers which completed their service process in the network and for customers which were lost eventually. It is demonstrated for two types of a network (a complete 5-node graph and a 5-node tandem-type system) that the network parameters obtained by the derived analytic method are close to those obtained by the Monte Carlo simulation method.     

Exponential queuing system with negative customers and bunker for ousted customers

Consideration was given to the queuing system with Poisson flows of incoming positive and negative customers. For the positive customers, there is an infinite-capacity buffer. The arriving negative customer knocks out a positive customer queued in the buffer and moves it to an infinite-capacity buffer of ousted customers (bunker). If the buffer is empty, then the negative customer discharges the system without affecting it. After servicing the current customer, the server receives a customer from the buffer or, if the buffer is empty, the bunker. The customers arriving from both the buffer and bunker are distributed exponentially with the same parameter. Relations for calculation of the stationary distributions of the queues in the buffer and bunker were obtained.     

Stationary probability distribution for states of G-networks with constrained sojourn time

We consider an exponential queueing network that differs from a Gelenbe network (with the usual positive and so-called negative customers), first, in that the sojourn time of customers at the network nodes is bounded by a random value whose conditional distribution for a fixed number of customers in a node is exponential. Second, we significantly relax the conditions on possible values of parameters for incoming Poisson flows of positive and negative customers in Gelenbe’s theorem. Claims serviced at the nodes and customers leaving the nodes at the end of their sojourn time can stay positive, become negative, or leave the network according to different routing matrices. We prove a theorem that generalizes Gelenbe’s theorem.     

G-networks with synchronised arrivals

We consider G-networks in which customers arrive simultaneously in several queues. We denote this new signal as synchronised arrivals. Under some conditions on the arrivals on the boundary of the state space, and the ergodicity condition, we prove that these networks have a product-form steady-state distribution. We show the link between this new signal and the positive signals introduced by Chao, Miyazawa and Pinedo.     

An initiative for a classified bibliography on G-networks

In the last two decades, researchers have really been embracing the idea of G-networks with negative arrivals and the relevant product form solution including nonlinear traffic equations, which is the unified model for queueing networks and neural networks. This paper reports the initiative to collect and classify a bibliography on G-networks.     

大数据环境下精准客户定位的社交网络分析

大数据为企业进行精准营销提供了重要支撑,精准营销能提升营销效果,提高客户满意度,精准营销的前提是客户识别与选择。通过分析网络个体与群体特征,社交网络分析能够定位核心价值客户。首先对社交网络的中心性进行分析,探讨社交网络节点地位与营销效果的关系,运用社群识别方法,对社交网络进行分群,提出并用MapReduce实现了针对大规模社交网络的社群划分RMCL方法。在此基础上,构建了客户影响度与客户影响因子等指标,并结合中心度指标,定位社群的核心节点,并采用分类回归树方法,研究了社交网络结构与客户消费响应关系,并确定了变量重要性,为企业采取客户差异化营销组合策略提供指导。     

Insensitivity in processor-sharing networks

We consider an open network of processor-sharing nodes with state-dependent service capacities, i.e., the speed of each node may depend on the number of customers at any node. We demonstrate that the stationary distribution of the network state is insensitive to the distribution of service times if and only if the service capacities are balanced, i.e., the considered network is a Whittle network. The stationary distribution then has a closed-form expression and the expected sojourn time of a customer at any node is proportional to its required quantity of service. These results are extended to the cases of closed networks and state-dependent arrival rates and routing. Two simple examples illustrate the practical interest of these results in the context of communication networks.     

Network routing control with G-networks

The aim of this paper is to detail a control scheme for packet computer networks whose purpose is to minimise a quality-of-service oriented performance metric by re-routing the traffic. The model is based on G-networks with triggered customer movement to represent traffic re-routing, and on a gradient descent based optimisation algorithm. The model and the algorithm are presented and we show that the gradient descent algorithm is of computational complexity O(N³) where N is the number of nodes in the packet network. Via the use of multiple classes of normal traffic and multiple classes of triggers, our approach allows one not only to evaluate the effect of the control, but also to incorporate the overhead that the control traffic will induce, and the consequences of the delays or possible losses of the control traffic. Similarly, these effects will naturally be incorporated when one considers both the impact of the control traffic on the cost function, and the details of this control traffic in the control algorithm itself.     

复杂客户网络拓扑性质研究

运用复杂网络的理论来研究客户网络的建立和发展复杂客户网络,通过对复杂客户网的小世界和无标度性质的分析来证实客户网络是一个复杂网络。并具备点分布、平均路径长度、聚集数等拓扑性质,研究结论对于企业赢得客户和保持客户规模具有指导意义。     

新颖的离散时间队列系统模型(英文)

带有正负顾客的连续时间单台服务器的队列系统得到了深入研究且已应用于多agent服务系统和计算机网络系统,而带有正负顾客的离散时间Geo/Geo/1队列研究在最近才出现。在拓展离散时间单台服务器Geo/Geo/1队列的基础上,提出了一个具有正负几何到达顾客的离散时间单台服务器GI/M/1队列模型,分析了队列静态长度分布和在RCH与RCE情况下的等待时间长度分布。     

An M/G/1 retrial G-queue with non-exhaustive random vacations and an unreliable server

This paper deals with an M/G/1 retrial queue with negative customers and non-exhaustive random vacations subject to the server breakdowns and repairs. Arrivals of both positive customers and negative customers are two independent Poisson processes. A breakdown at the busy server is represented by the arrival of a negative customer which causes the customer being in service to be lost. The server takes a vacation of random length after an exponential time when the server is up. We develop a new method to discuss the stable condition by finding absorb distribution and using the stable condition of a classical M/G/1 queue. By applying the supplementary variable method, we obtain the steady-state solutions for both queueing measures and reliability quantities. Moreover, we investigate the stochastic decomposition law. We also analyse the busy period of the system. Some special cases of interest are discussed and some known results have been derived. Finally, an application to cellular mobile networks is provided and the effects of various parameters on the system performance are analysed numerically.     

Discrete time tandem networks of queues: Effects of different regulation schemes for simultaneous events

We consider tandem networks of discrete time Bernoulli servers with state dependent service rates and a state dependent Bernoulli arrival stream at the first node of the tandem. We investigate the effects of different regulation schemes for simultaneous events (e.g. joint arrivals and departures at some node, or joint departures at different nodes) on the performance behaviour of the network. The most serious effects occur with respect to arrival theorems which describe the distribution of the other customers present in the network and seen by an arriving customer, or observed by a customer during a jump inside the network. We prove necessary and sufficient conditions on the regulation scheme for a customer to observe always the time stationary behaviour of the network during his jumps. It turns out that we have to distinguish between local and global control for the regulation of simultaneous jumps. For different arrival schemes we compute the joint sojourn time distribution for a customer traversing the tandem. As a consequence we identify from this a regulation scheme which is known in the literature, where Little’s formula cannot be applied directly.     

Critical purchasing incidents in e-business

This research utilized the critical incident technique (CIT) to identify factors influencing customer satisfaction and retention of customers participating in e-commerce transactions. Customers were asked in telephone interviews to discuss both particularly satisfying and dissatisfying (or critical) incidents they had experienced when using web sites to conduct transactions. Each customer also provided demographic information, rated their satisfaction with the experience and ecommerce provider, and was asked how often they purchased products from the provider prior to and after the incident. Analysis revealed 662 citations by customers of items contributing to either positive or negative experiences. Exploratory text-mining analysis revealed that the majority of positive items pertained to the transaction (38%), product (25%), or website (23%), and to customer support (35%) or the transaction for negative items (30%). Approximately 86% of customers citing positive items said they were very likely to use the e-commerce site again, compared to 22% of customers citing negative items. Customer support and user experience both seemed to play an important mediating role on the criticality of negative incidents. Over 70% of first time users and customers who said customer support ignored or refused their requests for assistance said they were unlikely to return to the site, compared to 20% when customer support was said to be responsive. Correlation analysis confirmed that negative incidents tended to be more critical than positive ones, and more so for first time customers.     

A discrete-time retrial queue with negative customers and unreliable server

This paper treats a discrete-time single-server retrial queue with geometrical arrivals of both positive and negative customers in which the server is subject to breakdowns and repairs. Positive customers who find sever busy or down are obliged to leave the service area and join the retrial orbit. They request service again after some random time. If the server is found idle or busy, the arrival of a negative customer will break the server down and simultaneously kill the positive customer under service if any. But the negative customer has no effect on the system if the server is down. The failed server is sent to repair immediately and after repair it is assumed as good as new. We analyze the Markov chain underlying the queueing system and obtain its ergodicity condition. The generating functions of the number of customers in the orbit and in the system are also obtained along with the marginal distributions of the orbit size when the server is idle, busy or down. Finally, some numerical examples show the influence of the parameters on some crucial performance characteristics of the system.