Waiting-time approximations for service systems with star pollingsequence and mixed service strategies

A conservation-law-based approximation for the mean waiting times in priority service systems with a mixture of exhaustive, gated, one-limited service strategies and star polling sequence is presented. The authors generalize previous results presented by Manfield (1985) for a similar system with one-limited service at the low-priority stations. For service systems with one-limited stations the proposed approximation is a low or medium traffic approximation. However, for systems with a mixture of gated and exhaustive services the approximation is very accurate for the whole range of admissible traffic intensities     

Exact Results for Nonsymmetric Token Ring Systems

This paper derives exact results for a token ring system with exhaustive or gated service. There areNnodes on the ring and control is passed sequentially from one to the next. Messages with random lengths arrive at each node and are placed on the ring when the control arrives at that node. Exhaustive service means that the queue at a node is empty before the token is released and gated means that only those messages in the queue at the arrival of the token are served at that cycle. Generating function recursions for the terminal service time (the total sojourn time of a token at a node) and, from this, joint cycle and intervisit times are derived. Using known results relating the marginal generating functions of the waiting time and the cycle and intervisit time, it is shown that theNmean waiting times at the nodes require the solution ofN(N - 1)and N²equations for the exhaustive and gated cases, respectively. The arrival processes are assumed to be Poisson with different rates and the service processes are general and different at each node. In addition the token overhead is allowed to have an arbitrary but independent distribution at each node. Explicit, simply programmed equations are given. It is shown, arguing from the form of the equations, that there is a conservation law in effect in this system. If the nodal mean waiting times are weighted by the relative intensity, defined here as the intensity weighted mean, then the sum takes on a particularly simple form and is independent of the placement of the nodes on the ring. When the service means at each node are equal, this quantity is just the system mean waiting time.     

A single-server queue with vacations and gated time-limited service

An M/G/1 queue with server vacations and gated time-limited service is analyzed. At each visit, the server serves the queue up to a fixed amount of time. When the time expires or after all candidate customers have been served, whichever occurs first, the server takes a vacation. The service policy is gated, since only those customers present at the beginning of a server visit (poling instant) are candidates for service during that visit; subsequent arrivals are deferred until the next visit. A functional equation which characterizes the amount of work, U_p, at a polling instant is derived. To solve the equation, a numerical technique is utilized in which the complementary cumulative function for U_p is closely approximated by a weighted sum of Laguerre functions with unknown coefficients. The equation is then transformed into a set of linear equations from which the coefficients can be computed. By the stochastic decomposition and Poisson-arrivals-see-time-averages properties, the average customer response time can be related to the average amount of work found by an arrival. Several numerical examples are included. The model studied is applicable to communication and computer systems where timers are used to allocate service to customers     

Delay analysis of various service disciplines in symmetric tokenpassing networks

An approach to the delay analysis of various service disciplines in symmetric token passing networks is presented. It is shown that exact or approximate accurate expressions for the average packet delay of different service disciplines can be directly derived by the delay expression of the exhaustive service system. This can be accomplished by inflating, by an appropriate factor, the packet size of the discipline whose performance is analyzed and then using the inflated packet in the delay expression of the exhaustive service system. The method is applied to the analysis of the limited service and TTS disciplines, and its accuracy is verified by simulation results. The advantages of the analytic method presented are its generality, higher accuracy over previous analytic methods, and insensitivity to network latency and other system parameters     

Polling systems with simultaneous arrivals

The authors analyze polling systems with multiple types of simultaneous arrivals, namely, batches of customers may arrive at the different queues at an arrival epoch. The authors consider cyclic polling systems with N queues, general service time distribution in each queue, and general switchover times. For both the exhaustive and the gated service disciplines the authors derive the necessary equations for computing the N expected waiting time figures. A pseudo conservation law for these system is also derived. The authors compare several special cases of the correlated arrivals polling system, discuss the computational aspects of the numerical method, and examine the applicability of the analysis to other polling systems     

Polling systems with server timeouts and their application to tokenpassing networks

Polling systems have long been the subject of study and are of particular interest in the analysis of high-speed communications networks. There are many options for the scheduling policies that can be used at each polling station (exhaustive, gated, customer limited, etc.). In addition, one can impose an upper bound on the total service time delivered to customers at a station per server visit. In the most common case the upper bound is a constant for each polling station, and the resulting system model is not Markovian even when service times and interarrival times are exponential. In the paper, a comprehensive solution is developed for the major scheduling policies with time limits for each polling station. The approach is based on studying the embedded Markov chain defined at the sequence of epochs when the server arrives at each polling station. The computation of transition probabilities for the embedded chain requires transient analysis of the Markov process describing the system evolution between epochs. Uniformization methods are used to develop efficient algorithms for the transition probabilities and for system performance measures. Example problems are solved using the techniques developed to illustrate the utility of the results     

On the Analysis of the Bluetooth Time Division Duplex Mechanism

Efficient communication in Bluetooth networks requires design of intra and inter-piconet scheduling algorithms, and therefore, numerous algorithms have been proposed. However, due to complexities of the Bluetooth MAC, the performance of these algorithms has been analyzed mostly via simulation. We present analytic results regarding the exhaustive, gated, and limited (pure round robin) scheduling algorithms in piconets with bidirectional and unidirectional traffic. We show that a piconet operated according to the limited scheduling algorithm is equivalent to a 1-limited polling system and present exact results regarding symmetric piconets with bidirectional traffic. Then, the difficulties in analyzing the performance of the exhaustive and gated algorithms in a piconet with bidirectional traffic are demonstrated. In addition, we present exact analytic results for piconets with unidirectional traffic. We show that, surprisingly, in symmetrical piconets with only uplink traffic, the mean waiting time is the same for the exhaustive and limited algorithms. This observation results from the differences between piconets and traditional polling systems and can be extended for time-division-duplex systems with arbitrary packet lengths. Furthermore, we show that the mean waiting time in a piconet with only uplink traffic is significantly higher than its corresponding value in a piconet with only downlink traffic. Finally, we numerically compare the exact results to approximate results, presented in the past.     

A discrete time two-level mixed service parallel polling model

We present a discrete time single-server two-level mixed service polling systems with two queue types, one center queue and N normal queues. Two-level means the center queue will be successive served after each normal queue. In the first level, server visits between the center queue and the normal queue. In the second level, normal queues are polled by a cyclic order. Mixed service means the service discipline are exhaustive for center queue, and parallel 1-limited for normal queues. We propose an imbedded Markov chain framework to drive the closed-form expressions for the mean cycle time, mean queue length, and mean waiting time. Numerical examples demonstrate that theoretical and simulation results are identical the new system efficiently differentiates priorities.     

Serving two correlated queues with a synchronous server underexhaustive service discipline and nonzero switchover time

A system composed of two queues that accepts correlated inputs and receives services from a synchronous server is studied. An exhaustive service discipline is adopted in serving a queue. Nonzero switchover time for the server to change service from one queue to the other is assumed. A closed-form expression for mean waiting time is obtained. The validity of the analysis if verified using the results of a computer simulation     

Modeling Bluetooth piconet performance

The performance of a single Bluetooth piconet is analyzed using the theory of M/G/1 queues with vacations. Analytical results for probability distributions of packet access time and service cycle time are derived. Two scheduling policies are modeled and compared: exhaustive service was found to perform better, but limited service does not incur the risk of starvation. A hybrid scheme known as k-limited scheduling is shown to provide a reasonable tradeoff between performance and fairness. Results were confirmed through simulations.     

Performance Analysis of a Discrete‐Time Two‐Phase Queueing System

This paper introduces the modeling and analysis of a discrete‐time, two‐phase queueing system for both exhaustive batch service and gated batch service. Packets arrive at the system according to a Bernoulli process and receive batch service in the first phase and individual services in the second phase. We derive the probability generating function (PGF) of the system size and show that it is decomposed into two PGFs, one of which is the PGF of the system size in the standard discrete‐time Geo/G/1 queue without vacations. We also present the PGF of the sojourn time. Based on these PGFs, we present useful performance measures, such as the mean number of packets in the system and the mean sojourn time of a packet.     

Performance evaluation of polling systems for wireless localcommunication networks

This paper evaluates the performance of different polling systems used in wireless local networks where the transmission channel exhibits a nonstationary behavior. Many spatially dispersed data user terminals have been assumed to share a common short-range radio uplink channel to access a hub station. We have specifically considered cyclic polling systems with M queues (terminals), having the same general packet arrival process and general switchover period. The gated and exhaustive disciplines have been considered in ordering the transmission of the packets buffered at each terminal. By appropriately modeling the uplink channel, we propose analytical approaches to derive the average packet waiting time and the average cycle length for gated polling systems, combined with stop-and-wait (SW) and go-back-N (GBN) automatic repeat request (ARQ) techniques to control errors. A gated cyclic polling scheme combined with the selective-repeated (SR) stutter ARQ technique as well as an exhaustive cyclic polling scheme combined with SW, GBN, or SR stutter ARQ techniques, respectively, have also been considered In order to give an in-depth knowledge of the behavior of suitable polling alternatives for applications in wireless local communication networks     

Cyclic-service systems with probabilistically-limited service

An asymmetric cyclic-service system with a probabilistically limited (PL) service policy is analyzed. In such a service policy, the maximum number of customers served at a queue during a server visit is determined by a probability which is independent of system states. Exhaustive, limited-k, and Bernoulli services are special cases of the PL policy. Customer service times and changeover times have general distribution. A numerical technique based on discrete Fourier transforms is proposed to solve for the queue-length distributions. Thus, the waiting and response-time distribution are obtained. A set of numerical examples is presented to validate the approach     

Comments on `Exact results for nonsymmetric token ring systems'

The commenters identify and correct errors in some of the equations in the above-titled paper by Ferguson and Aminetzah (see ibid., vol.COM-33, p.223-31, Mar. 1985), particularly those related to gated service discipline. In addition, they compare equivalent gated and exhaustive systems (using the corrected equations) numerically in terms of the mean waiting time behaviors at the various nodes, and in terms of the overall mean and variance of the mean waiting times across the nodes     

Performance of Bluetooth Slave/Slave Bridge

The performance of a Bluetooth scatternet with a Slave/Slave bridge is analyzed using the tools of queueing theory. We analyze two possible scheduling policies: limited service and exhaustive service, and derive analytical results for the probability distribution of access delay (i.e., the time that a packet has to wait before being serviced) and end-to-end delay for both intra- and inter-piconet bursty traffic. The exhaustive service discipline was found to provide lower values for all delay variables, over a wide range of parameter values. All analytical results have been confirmed through simulations.     

An M/G/1 vacation model of an FDDI station

The author defines and analyzes an M/G/1 vacation model that can be used to describe a single station in the fiber distributed data interface (FDDI). The M/G/1 model uses a service discipline called the exhaustive limited with limit variation discipline. According to this discipline, the server provides service until either the system is emptied or a randomly chosen limit of l frames has been served. The server then goes on a vacation before returning to service the queue again. The model can be used to gain insight into how the varying (timer-controlled) limit on the number of frames that can be transmitted during token visit at a station affects the mean waiting time in the timed-token protocol of FDDI. The analytical results of the M/G/1 vacation model are applied to an FDDI simulation example     

Bridges of Bluetooth county: topologies, scheduling, and performance

The performance of two Bluetooth piconets linked through a shared device is analyzed using the tools of queueing theory. We analyze both possible topologies: the master/slave (MS) bridge, in which the shared device is the master in one of the piconets and a slave in the other, and the slave/slave (SS) bridge, where the shared device is the slave in both piconets. Two scheduling policies, limited service and exhaustive service, are considered. Analytical results are derived for the probability distribution of access delay (i.e., the time that a packet has to wait before being serviced) and end-to-end delay for both intrapiconet and interpiconet bursty traffic. The SS bridge has been found to offer lower access delays and local end-to-end delay than its MS counterpart, which provides lower end-to-end delay for nonlocal traffic due to the smaller number of hops (three, instead of four) for such traffic. In both topologies, exhaustive service scheduling was found to provide lower delays than the limited service one. All analytical results have been confirmed through simulations.     

A batchSPP/G/1 queue with multiple vacations and exhaustive service discipline

This paper considers a batch-arrival single-server queueing system with multiple vacations and exhaustive service discipline. Customers arrive to the system in accordance with a batch switched Poisson process (batchSPP). Using the supplementary variable technique, we analyze the stationary queue length distribution and derive various formulas for queue lengths and waiting times. In particular, we analytically show the decomposition property for the waiting time distributions. Therefore, the waiting time formulas developed in this paper can also be applied to a batchSPP/G/1 queue without vacations.     

Cost minimization in placing service chains for virtualized network functions

Network function virtualization (NFV) places network functions onto the virtual machines (VMs) of physical machines (PMs) located in data centers. In practice, a data flow may pass through multiple network functions, which collectively form a service chain across multiple VMs residing on the same or different PMs. Given a set of service chains, network operators have two options for placing them: (a) minimizing the number of VMs and PMs so as to reduce the server rental cost or (b) placing VMs running network functions belonging to the same service chain on the same or nearby PMs so as to reduce the network delay. In determining the optimal service chain placement, operators face the problem of minimizing the server cost while still satisfying the end‐to‐end delay constraint. The present study proposes an optimization model to solve this problem using a nonlinear programming (NLP) approach. The proposed model is used to explore various operational problems in the service chain placement field. The results suggest that the optimal cost ratio for PMs with high, hybrid, and low capacity, respectively, is equal to 4:2:1. Meanwhile, the maximum operating utilization rate should be limited to 55% in order to minimize the rental cost. Regarding quality of service (QoS) relaxation, the server cost reduces by 20%, 30%, and 32% as the end‐to‐end delay constraint is relaxed from 40 to 60, 80, and 100 ms, respectively. For the server location, the cost decreases by 25% when the high‐capacity PMs are decentralized rather than centralized. Finally, the cost reduces by 40% as the repetition rate in the service chain increases from 0 to 2. A heuristic algorithm, designated as common sub chain placement first (CPF), is proposed to solve the service chain placement problem for large‐scale problems (eg, 256 PMs). It is shown that the proposed algorithm reduces the solution time by up to 86% compared with the NLP optimization model, with an accuracy reduction of just 8%.     

Performance issues in public ABR service

The available bit rate (ABR) service attracted much attention during the negotiations leading to Traffic Management Specification Version 4.0, finalized by the ATM Forum. In thr ABR service, feedback flow control of the source rate is provided in response to the changing asynchronous transfer mode (ATM)-layer transfer characteristics. The reference behavior of the source end system, the destination end system, and the switch, as detailed in the specification, allows cooperative control among these systems. The performance of the public ABR service is discussed in connection with the evolution of ATM switches. Public networks with first-generation switches provide an ABR service with a limited peak cell rate (PCR), while those with second-generation switches can provide an ABR service with any PCR. In such networks, TCP-over-ABR works well. Point-to-multipoint ABR will be provided in advanced switches. A method is proposed for maintaining the throughput of point-to-multipoint ABR when the number of leaves is increased