Diffusion approximations for multiclass queueing networks under preemptive priority service discipline

We prove a heavy traffic limit theorem to justify diffusion approximations for multiclass queueing networks under preemptive priority service discipline and provide effective stochastic dynamical models for the systems. Such queueing networks appear typically in high-speed integrated services packet networks about telecommunication system. In the network, there is a number of packet traffic types. Each type needs a number of job classes （stages） of processing and each type of jobs is assigned the same priority rank at every station where it possibly receives service. Moreover, there is no inter-routing among different traffic types throughout the entire network.

RELATIONS BETWEEN PERFORMANCE POTENTIALS AND INFINITESIMAL REALIZATION FACTORS IN CLOSED QUEUEING NETWORKS

In this paper,the concept of the infinitesimal realization factor is extended to the parameter dependent performance functions in closed queueing networks.Then the concepts of realization matrix (its elements are called realization factors) and performance potential are introduced,and the relations between infinitesimal realization factors and these two quantities are discussed.This provides a united framework for both IPA and non IPA approaches.Finally,another physical meaning of the service rate is given.

Open Queueing Network Model of Shanghai Public Transportation Problem

In this paper, the open queueing network model is proposed for solving the problem of public transportation in cities. The vertices of the networks(i.e., the bus stops) are determined by means of the fuzzy clustering method. The arcs (i.e., the paths of the public transportation) can be set up by using the shortest path model in the time sense or the 0 1 integer programming method.Applying the statistics method, we can calculate the parameters(such as the passenger flow's distribution, passenger flow's transition probability, mean waiting time for the bus etc. ) of the public transportation network. In this paper, we suggest to divide the network into two or three stages to implement the public transportation system in the form of ``frog jumping' fast transfer and ``permeation' fast dispersion.Combining the computer simulation and the evaluation of the achievement and effect of public transportation system, we modify the model so as to solve the public transportation problem better.

Variability Analysis for a Two-station Queueing Network in Heavy Traffic with Arrival Processes Driven by Queues

The law of the iterated logarithm(LIL)for the performance measures of a two-station queueing network with arrivals modulated by independent queues is developed by a strong approximation method.For convenience,two arrival processes modulated by queues comprise the external system,all others are belong to the internal system.It is well known that the exogenous arrival has a great influence on the asymptotic variability of performance measures in queues.For the considered queueing network in heavy traffic,we get all the LILs for the queue length,workload,busy time,idle time and departure processes,and present them by some simple functions of the primitive data.The LILs tell us some interesting insights,such as,the LILs of busy and idle times are zero and they reflect a small variability around their fluid approximations,the LIL of departure has nothing to do with the arrival process,both of the two phenomena well explain the service station’s situation of being busy all the time.The external system shows us a distinguishing effect on the performance measures:an underloaded(overloaded,critically loaded)external system affects the internal system through its arrival(departure,arrival and departure together).In addition,we also get the strong approximation of the network as an auxiliary result.

COOPERATIVE DYNAMICS OF LOYAL CUSTOMERS IN QUEUEING NETWORKS

We consider queueing networks （QN＇s） with feedback loops roamed by ＂intelligent＂ agents, able to select their routing on the basis of their measured waiting times at the QN nodes. This is an idealized model to discuss the dynamics of customers who stay loyal to a service supplier, provided their service time remains below a critical threshold. For these QN＇s, we show that the traffic flows may exhibit collective patterns typically encountered in multi-agent systems. In simple network topologies, the emergent cooperative behaviors manifest themselves via stable macroscopic temporal oscillations, synchronization of the queue contents and stabilization by noise phenomena. For a wide range of control parameters, the underlying presence of the law of large numbers enables us to use deterministic evolution laws to analytically characterize the cooperative evolution of our multi-agent systems. In particular, we study the case where the servers are sporadically subject, to failures altering their ordinary behavior.

A Simple Proof for the Stability of Global FIFO Queueing Networks

We study the stability of multiclass queueing networks under the global FIFO （first in first out） service discipline, which was established by Bramson in 2001. For these networks, the service priority of a customer is determined by his entrance time. Using fluid models, we describe the entrance time of the most senior customer in the networks at time t, which is the key to simplify the proof for the stability of the global FIFO queueing networks.

Fuzzy Scheduling of Coupled Customers toa Queueing Network with Parallel Servers

In this paper we consider a queueing network consisting of two parallel servers and threearrival streams generated by independent Poisson sources. Each server has its own queue and receivescustomers from its own arrival stream. A third arrival stream consists of customers which place resourcedemands on both servers, which are handled separately by each server once the request is made. Eachservice time is independent and exponentially distributed. Each customer in the system pays a holdingcost per unit time. The objective is to dynamically determine the optimal scheduling policy to the thirdstream of conupled customers. based on the state of the system, so as to minimize the average cost. Thismodel is new, and has Policy implications for computer or communication networks. A fuzzy approachis presented to solve this problem. Simulation shows that the approach is efficient and promising.

Petri Nets—A Versatile Modeling Structure

Petri Nets (PNs) are an effective structure for modeling and analyzing asynchronous systems with concurrent and parallel activities. A Petri net models the static properties of a discrete event system concentrating on two basic concepts: events and conditions. Most of the theoretical work on Petri nets is a formal definition of Petri nets structures, which consist of a set of places, representing conditions, a set of transitions, representing events, an input function and an output function. For practical purposes, a graphical representation is more useful. Two types of nodes portray places and transitions. A circle is a place and a bar is a transition. There is no inherent measure of time in a classical Petri net. To approach time-based evaluation of system performances, Timed Petri Nets (TPNs) were introduced. Modeling the notion of time is not straightforward. There are several possibilities for introducing time in PNs, among them timed transitions and timed places. This paper reviews several published examples where Petri Nets were used in different circumstances such as estimating expected utilization of processing resources at steady state in open queueing networks, verifying computerized simulations and batch planning in textile industry.

ON OPTIMAL LOCAL BUFFER ALLOCATION IN FLEXIBLE MANUFACTURING SYSTEMS

An optimal design problem of local buffer allocation in the FMS is discussed in order to maximize a reward earned from processed jobs at all workstations. Structural properties of the optimal design problem are analyzed for the model with two job routing policies. Based on these properties, approaches to optimal solutions are given.

On the Strong Approximation for a Simple Reentrant Line in Light Traffic Under First-buffer First-served Service Discipline

For a 2-station and 3-class reentrant line under first-buffer first-served(FBFS)service discipline in light traffic,we firstly construct the strong approximations for performance measures including the queue length,workload,busy time and idle time processes.Based on the obtained strong approximations,we use a strong approximation method to find all the law of the iterated logarithms(LILs)for the above four performance measures,which are expressed as some functions of system parameters:means and variances of interarrival and service times,and characterize the fluctuations around their fluid approximations.

HPSIN: a new hybrid P2P spatial indexing network

Geographic information system （GIS） is increasingly managing very large sets of data, hence a centralized data index may not always provide the most scalable solution. Recently, the peer to peer （P2P） networks have become very popular for sharing information in a totally decentralized manner. In this paper, a new hybrid P2P spatial indexing network （HPSIN） is proposed, which combines distributed quad-tree with distributed Hash table （DHT） based Chord network to maintain both query efficiency and system load balance. In addition, a simple theoretical model based on opened queueing network for HPSIN is established. Assuming each peer as M/M/1 queueing processor in the model, fundamental characteristics of the system is captured, and expression of average query delay is obtained in close form. The theoretical analysis and numerical computing results show that there exists an optimum point of tradeoff between efficiency and load balance. By setting a proper value of start index level ls for different network scale and query rate, HPSIN will achieve the minimum overall query delay, therefore, can adapt to different P2P application environments.

Stability of Kumar-Seidman Networks Under Longest Queue First Policy

This paper is concerned with the stability of multiclass queueing networks of 2 stations and4 buffers under the longest queue first served discipline(LQFS).For this network,the service priority of a customer is determined by the length of the queue that customer resides in at that time.The main result includes two parts.Firstly,the corresponding fluid model is established,and then it is shown that the queueing networks under LQFS are stable whenever the traffic intensity is strictly less than one for each station.

Study on I/O response time bounds of networked storage systems

In order to predict and improve the performance of networked storage systems,this paper explored the rela-tionship between the system I/O response time and its per-formance factors by quantitative analytical method.Through analyzing data flow in networked RAID storage system,we established its analytical model utilizing closed queueing networks and studied the performance bounds of the system I/O response time.Experimental results show that the theo-retical bounds are found to be in agreement with the actual performance bounds of the networked RAID storage system and reflect the dynamic trend of its actual performance.Furthermore,it concludes that the CPU processing power and cache hit rate of the central storage server are the key factors affecting the I/O response time as the concurrent jobs are lower,while the network bandwidth and cache hit rate of the central storage server become the key factors as the concurrent jobs go higher.

Analysis of a New Type of Production System

Previous work studied a production system including multiple stations (or workshops) consisting of an entry station, a set of workstations, an exit station, and a central station, which could be arranged in any configuration. The central station was introduced into the production system to relax the environment. In this paper, the central station is eliminated. The entry station and all workstations have limited local buffers. A workstation can choose either a buffer or a kanban mechanism to control its work-in-process (WIP). The production system was modeled as a queueing network with blocking in a general configuration. A symmetrical decomposition approach was developed to analyze the production system. The simulation result shows that the decomposition approach works well. Comparison of the new production systems with modified production systems having a common buffer shows that the key for implementing just-in-time production systems is to reduce the uncertainty.