Search

Motivated by emerging Internet-of-Things (IoT) applications and smart building environments, we analyze the performance of large-scale symmetric polling systems where the number of queues grows large. We consider a scenario in which the total arrival rate is kept fixed and the individual switch-over time and service time distributions remain the same. This asymptotic regime leads to cycles of infinite length and queue lengths with non-trivial distributions. We show that for most traditional service policies the scaled cycle times converge to a deterministic value in the limit, which in turn implies that the queue lengths at the various nodes become asymptotically independent. Using these insights, we find that the behavior of individual queues simplifies to that of a discrete-time bulk service queue in the limit, so that the marginal queue length and waiting-time distributions become considerably easier to analyze. Additionally, we propose a new flexible k -limited service discipline aimed at striking a good balance between short mean queue lengths and predictable cycle times for deadline-critical applications.

We investigate the stability condition for redundancy- d systems where each of the servers follows a processor-sharing (PS) discipline. We allow for generally distributed job sizes, with possible dependence among the d replica sizes being governed by an arbitrary joint distribution. We establish that for homogeneous servers the stability condition for the associated fluid-limit model is characterized by the expectation of the minimum of d replica sizes being less than the mean interarrival time per server. In the special case of identical replicas, the stability condition is insensitive to the job size distribution given its mean, and the stability threshold is inversely proportional to the number of replicas. In the special case of i.i.d. replicas, the stability threshold decreases (increases) in the number of replicas for job size distributions that are NBU (NWU). We also discuss the extension to heterogeneous servers. For heavy-tailed job sizes we characterize the tail behavior of the response time distribution. In particular, for regularly varying job sizes with tail index − ν it is shown that the tail index of the response time equals − ν and − d ν for identical and i.i.d. replicas, respectively.

We consider job dispatching in systems with N parallel servers. In redundancy- d policies, replicas of an arriving job are assigned to d ≤ N servers selected uniformly at random (without replacement) with the objective to reduce the delay. We introduce a quite general workload model, in which job sizes have some probability distribution while the speeds (slowdown factors) of the various servers for a given job are allowed to be inter-dependent and non-identically distributed. This allows not only for inherent speed differences among different servers, but also for affinity relations. We further propose two novel redundancy policies, so-called delta-probe- d policies, where d probes of a fixed, small, size Δ are created for each incoming job, and assigned to d servers selected uniformly at random. As soon as the first of these d probe tasks finishes, the actual job is assigned for execution – with the same speed – to the corresponding server and the other probe tasks are abandoned. We also consider a delta-probe- d policy in which the probes receive preemptive-resume priority over regular jobs. The aim of these policies is to retain the benefits of redundancy- d policies while accounting for systematic speed differences and mitigating the risks of running replicas of the full job simultaneously for long periods of time. Analytical and numerical results are presented to evaluate the effect of both probing policies on the job latency, and to illustrate the potential performance improvements.

We study a polling model in which we want to achieve a balance between the fairness of the waiting times and the efficiency of the system. For this purpose, we introduce a novel service discipline: the @k-gated service discipline. It is a hybrid of the classical gated and exhausted disciplines, and consists of using @k"i consecutive gated service phases at queue i before the server switches to the next queue. The advantage of this discipline is that the parameters @k"i can be used to balance fairness and efficiency. We derive the distributions and means of the waiting times, a pseudo conservation law for the weighted sum of the mean waiting times, and the fluid limits of the waiting times. Our goal is to optimize the @k"i so as to minimize the differences in the mean waiting times, i.e. to achieve maximal fairness, without giving up too much on the efficiency of the system. From the fluid limits we derive a heuristic rule for setting the @k"i. In a numerical study, the heuristic is shown to perform well in most cases.

In this paper we consider a single-server cyclic polling system. Between visits to successive queues, the server is delayed by a random switch-over time. The order in which customers are served in each queue is determined by a priority level that is assigned to each customer at his arrival. For this situation the following service disciplines are considered: gated, exhaustive, and globally gated. We study the cycle time distribution, the waiting times for each customer type, the joint queue length distribution of all priority classes at all queues at polling epochs, and the steady-state marginal queue length distributions for each customer type., Comment: arXiv admin note: substantial text overlap with arXiv:1408.0110

We consider a polling system of N queues Q"1,...,Q"N, cyclically visited by a single server. Customers arrive at these queues according to independent Poisson processes, requiring generally distributed service times. When the server visits Q"i, i=1,...,N, it serves a number of customers according to a certain polling discipline. This discipline is assumed to belong to the class of branching-type disciplines, which includes the gated and exhaustive disciplines. The special feature of our study is that, within each queue, we do not restrict ourselves to service in order of arrival (FCFS); we are interested in the effect of different service disciplines, like Last-Come-First-Served, Processor Sharing, Random Order of Service, and Shortest Job First, on the sojourn time distribution of a typical customer that arrives to the system during steady-state. After a discussion of the joint distribution of the numbers of customers at each queue at visit epochs of the server to a particular queue, we determine the Laplace-Stieltjes transform of the cycle-time distribution, viz., the time between two successive visits of the server to, say, Q"1. This yields the transform of the joint distribution of past and residual cycle time, w.r.t. the arrival of a tagged customer at Q"1. Subsequently concentrating on the case of gated service at Q"1, we use that cycle-time result to determine the (Laplace-Stieltjes transform of the) sojourn-time distribution at Q"1, for each of the scheduling disciplines mentioned above. Next to locally gated polling disciplines, we also consider the globally gated discipline. Again, we consider various non-FCFS service disciplines at the queues, and we determine the (Laplace-Stieltjes transform of the) sojourn-time distribution at an arbitrary queue.

We present a simple mean value analysis (MVA) framework for analyzing the effect of scheduling within queues in classical asymmetric polling systems with gated or exhaustive service. Scheduling in polling systems finds many applications in computer and communication systems. Our framework leads not only to unification but also to extension of the literature studying scheduling in polling systems. It illustrates that a large class of scheduling policies behaves similarly in the exhaustive polling model and the standard M/GI/1 model, whereas scheduling policies in the gated polling model behave very differently than in an M/GI/1.

This paper surveys the M/G/1 queue with regularly varying service requirement distribution. It studies the effect of the service discipline on the tail behavior of the waiting-time and/or sojourn-time distribution, demonstrating that different disciplines lead to quite different tail behavior. The orientation of the paper is methodological: We outline four different methods for determining tail behavior, illustrating them for service disciplines like FCFS, Processor Sharing and LCFS.

In this paper we consider some models for contention resolution in cable networks, in case the contention pertains to requests from a finite population of stations and is carried out by means of contention trees. More specifically, we study a number of variants of the standard machine repair model, that differ in the service order at the repair facility. Considered service orders are first come first served, random order of service, and gated random order of service. For these variants, we study the sojourn time at the repair facility. In the case of the free access protocol for contention trees, the first two moments of the access delay in contention are accurately represented by those of the sojourn time at the repair facility under random order of service. In the case of the blocked access protocol, gated random order of service is shown to be more appropriate.

We consider a two-stage closed cyclic queueing model. For the case of an exponential server at each queue we derive the joint distribution of the successive response times of a custumer at both queues, using a reversibility argument. This joint distribution turns out to have a product form. The correlation coefficient is calculated and shown to be non-positive. For the case of one general server and one exponential server we derive two approximations for the joint distribution of the response times. The numerical results based on these approximations are compared with simulation results. The first approximation which heavily relies on results for the M/G/1 queue with finite capacity, is somewhat complicated, but it yields exact marginal distributions and appears to be very accurate. The second one is less accurate, but very easily ???.