Institute for Systems Research Technical Reports

Permanent URI for this collectionhttp://hdl.handle.net/1903/4376

This archive contains a collection of reports generated by the faculty and students of the Institute for Systems Research (ISR), a permanent, interdisciplinary research unit in the A. James Clark School of Engineering at the University of Maryland. ISR-based projects are conducted through partnerships with industry and government, bringing together faculty and students from multiple academic departments and colleges across the university.

Browse

Author: search.filters.author.Makowski, Armand M.Subject: search.filters.subject.queueing networks

Search Results

Now showing 1 - 10 of 14
  • Thumbnail Image
    Item
    Heavy Traffic Limits Associated with M|GI|Input Processes
    (1997) Tsoukatos, K.P.; Makowski, Armand M.; ISR; CSHCN
    We study the heavy traffic regime of a discrete-time queue driven by correlated inputs, namely the M|GI|input processes of Cox. We distinguish between M|GI|processes with short- and long- range dependence, identifying for each case the appropriate heavy traffic scaling that results in non-degenerate limits. As expected, the limits we obtain for short-range dependent input involve the standard Brownian motion. Of particular interest are the conclusions for the long-range dependent case: The normalized queue length can be expressed as a function not of a fractional Brownian motion, but of an a-stable, 1/a self-similar independent increments levy process. The resulting buffer asymptotics in heavy traffic display a hyperbolic decay, of power 1 - a. Thus M|GI|processes already demonstrate that, within long-range dependence, fractional Brownian motion does not necessarily assume the ubliquitous role that standard Brownian motion plays in the short-range dependence setup.
  • Thumbnail Image
    Item
    Stochastic Comparison Results for Non-Blocking Switches with Output Queueing
    (1996) Kim, Young B.; Makowski, Armand M.; ISR; CSHCN
    We propose a systematic approach to quantify the impact of nonuniform traffic on the performance of non-blocking switches with output queueing. We do so in the context of a simple queueing model where cells arrive to input ports according to independent Bernoulli processes, and are switched to an output port under a random routing mechanism. We give conditions on pairs of input rate vectors and switching matrices which ensure various stochastic comparisons for performance measures of interest. These conditions are formulated in terms of the majorization ordering while the comparison results are expressed in the strong and convex increasing orderings.
  • Thumbnail Image
    Item
    M|G|Input Processes: A versatile class of models for network traffic
    (1996) Parulekar, M.; Makowski, Armand M.; ISR
    We suggest the M|G|input process as a viable model for network traffic due to its versatility and tractability. To gauge its performance, we study the large buffer asymptotics of a multiplexer driven by an M|G|input process. We identify the process as short or long-range dependent by means of simple tests. The decay rate of the tail probabilities for the buffer content (in steady-state) at the multiplexer is investigated using large deviation techniques suggested by Duffield and O'Connell. The appropriate large deviations scaling is found to be related to the forward recurrence time for the service time distribution, and a closed-form expression is derived for the corresponding generalized limiting log-moment generating function associated with the input process. Two very different regimes are identified. We apply our results to cases where the service time distribution in the M|G|input model is (i) Rayleigh (ii) Gamma (iii) Geometric (iv) Weibull (v) Log-Normal and (vi) Pareto - cases (v) and (vi) have recently been found adequate for modeling packet traffic streams in certain networking applications. Finally, we comment on the insufficiency of the short or long- range dependence in the process in clearly describing buffer dynamics.
  • Thumbnail Image
    Item
    Tail Probabilities for M|G|input Processes (I): Preliminary Asymptotics
    (1996) Parulekar, M.; Makowski, Armand M.; ISR
    The infinite server model of Cox with arbitrary service time distribution appears to provide a very large class of traffic models - Pareto and log-normal distributions have already been reported in the literature for several applications. Here we begin the analysis of the large buffer asymptotics for a multiplexer driven by this class of inputs. Top do so we rely on recent results by Duffield and O'Connel on overflow probabilities for the general single server queue. In this paper we focus on the key step in this approach which is based on large deviations: The appropriate large deviations scaling is shown to be related to the forward recurrence time for the service time distribution, and a closed form expression is derived for the corresponding generalized limiting log-moment generating function associated with the input process. Tow very different regime are identified. In a companion paper we apply these results to obtain the large buffer asymptotics under a variety of service time distributions.
  • Thumbnail Image
    Item
    Simple Optimization Problems via Majorization Ordering
    (1996) Kim, Young B.; Makowski, Armand M.; ISR
    We introduce and explicitly solve a novel class of optimization problems which are motivated by load assignment issues in crossbar switches with output queueing. The optimization criterion is given in the majorization ordering sense. The solution to these problems indirectly provide solutions to a large class of convex optimization problems under a linear constraint.
  • Thumbnail Image
    Item
    Buffer Overflow Probabilities for a Multiplexer with Self- Similar Traffic
    (1995) Parulekar, M.; Makowski, Armand M.; ISR; CSHCN
    We study the large buffer asymptotics of a multiplexer under two different self-similar traffic inputs, namely the so-called M G  model of Cox and the fractional Gaussian noise input model. In the former case we show that the tail probabilities for the buffer content (in steady-state) decay at most hyperbolically. This is contrasted with the situation where the input traffic is fractional Gaussian noise, in which case the tail probabilities display a Weibullian character. Therefore, for a given input rate rin and Hurst parameter H, these dissimilar asymptotics would result in vastly differing buffer engineering practices, which points somewhat to the inadequacy of using H as the sole parameter to characterize long-range dependence.
  • Thumbnail Image
    Item
    Large Size Asymptotics for Crossbar Switches with Input Queueing
    (1995) Kim, Young B.; Makowski, Armand M.; ISR; CSHCN
    With the advent of high-speed networks, various switch architectures have been proposed to meet the increasingly stringent performance requirements being placed on the underlying switching systems. In general, the performance analysis of such a switch architecture is a difficult task mainly due to the fact that a switch consists of a large number of queues which interact with each other in a fairly complicated manner. In this paper, we analyze a crossbar switch with input queueing in terms of maximum throughput, and formalize the phenomenon that virtual queues formed by the head-of-line cells become decoupled as the switch size grows unboundedly large. We also establish various properties of the limiting queue size processes so obtained.
  • Thumbnail Image
    Item
    On the Effective Bandwidth of the Output Process of a Single Server Queue
    (1995) Banege, Lionel; Makowski, Armand M.; ISR; CSHCN
    We show that the initial condition of the buffer content in a G/G/1 queue satisfies a Sample Path Large Deviations Principle with convex good rate function, provided it has an exponential decay rate. This result is then used to derive conditions under which the transient and stationary output processes satisfy the same Large Deviations Principle. The relationship between the Large Deviations Principle and the effective bandwidth of a queue is discussed.
  • Thumbnail Image
    Item
    On Stochastic Approximations Driven by Sample Averages: Convergence Results via the ODE Method
    (1994) Bartusek, John D.; Makowski, Armand M.; ISR; CSHCN
    We consider a class of projected stochastic approximation algorithms drive by sample averages. These algorithms arise naturally in problems of on-line parametric optimization for discrete event dynamical systems., e.g., queueing systems and Petri net models. We develop a general framework for investigating the a.s. convergence of the iterate sequence, and show how such convergence results can be obtained by means of the ordinary differential equation (ODE) method under a condition of exponential convergence. We relate this condition of exponential convergence to certain Large Deviations upper bounds which are uniform in both the parameter q and the initial condition x. To demonstrate the applicability of the results, we specialize them to two specific classes of state processes, namely sequences of i.i.d. random variables and finite state time-homogeneous Markov chains. In both cases, we identify simple (and checkable) conditions that ensure the validity of a uniform Large Deviations upper bound.
  • Thumbnail Image
    Item
    Cell Loss Probabilities in Input Queueing Crossbar Switches Via Light Traffic
    (1994) Kim, Young B.; Makowski, Armand M.; ISR; CSHCN
    Under most system assumptions, closed form solutions of performance measures for input queueing crossbar switches are not available. In this paper, we present expressions and bounds for the derivatives of cell loss probabilities with respect to the arrival rate evaluated at a zero arrival rate. These bounds are used to give an approximation by Taylor expansion, thereby providing an economical way to estimate cell loss probabilities in light traffic.