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
Search Results
Item Heavy Traffic Limits Associated with M|GI|Input Processes(1997) Tsoukatos, K.P.; Makowski, Armand M.; ISR; CSHCNWe 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.Item Large Deviations for Partial Sum Processes Over Finite Intervals(1997) Banege, Lionel; Makowski, Armand M.; ISRWith any sequence {xn, n = ﯱ, ﯲ, ...} of IRp -valued random variables, we associate the partial sum processes {XTN(.)}$ which take value, in the space $(D[0,T]^p, au_0)$ of, right- continuous functions $[0,T] ightarrow R^p$ with left-hand, limits equipped with Skorohod's $J_1$ topology.Furthermore, in an attempt to capture the past of the sequence, we introduce the negative partial sum processes ${ X_n^{T,-}(cdot),; n=z }$ defined by [ X_n^{T,-}(t)(omega) ~ equiv ~ left{ a{ll} ds {1 over n} {sum_{i=1-ceiling{nt}}^{0} x_i(omega)} & mbox{if} quad ceiling{nt} geq 1 \ 0 & mbox{otherwise} ea ight., quad t in [0,T], quad omega in Omega .
] These processes take value in the space $(D_l[0,T]^p, au_0)$ of, left- continuous functions $[0,T] ightarrow R^p$ with right-hand, limits also equipped with the Skorohod's $J_1$ topology. This paper explores some of the issues associated with, transfering the LDP for the family ${X_n^1 (cdot),~n=z}$ in $(D[0,1]^p, au_0)$ to the families ${X_n^{T}(cdot), ; n=z}$ in $(D[0,T]^p, au_0)$, ${X_n^{T,-}(cdot), ; n=z}$ in $(D_l[0,T]^p, au_0)$ and ${(X_n^T(cdot), X_n^{T,-}(cdot)), ; n=z}$ in $(D[0,T]^p, au_0) x (D_l[0,T]^p, au_0)$ for arbitrary $T>0$; the last two types of transfers require, stationarity of the underlying sequence ${x_n, ; n=pmz}$. The motivation for this work can be found in the study of, large deviations properties for general single server queues, and more specifically, in the derivation of the effective bandwidth, of its output process, all discussed in a companion paper. In a significant departure from the situation under the uniform topology, such transfers are not automatic under the Skorohod topology, as additional continuity properties are required on the elements of, the effective domain of the rate function $I_X$ of the LDP, for ${X_n^1(cdot),~n=z}$ in $(D[0,1]^p, au_0)$.
However, when the rate function $I_X$ is of the usual integral form, the transfers are automatic, and the new rate functions assume, very simple forms suggesting that from the perspective, of large deviations, the past of the underlying stationary process, behaves {it as if} it were independent of its future.
======================================================= ===========
Item IEEE 1355-Based Architecture for an ATM Switch: A Case for Onboard Switching and Processing(1996) Kim, Jangkyung; Makowski, Armand M.; Narayan, Prakash; Lee, Jong-Hee; Chong, Il-Young; Charleston, Giles C.; Christofili, Thomas; Rao, Sandeep; Ryu, Man-Geun; ISR; CSHCNThe recent evolution of the communication scenario has profound implications for the role of communication satellites within the communication infrastructure. Indeed, it raises the possibility that the satellite be viewed not merely as a repeater but rather as a network node in its own right in a hopefully integrated space/terrestrial network. we draw attention to the new IEEE 1355 Standard for Heterogeneous InterConnect as a possible platform to support several onboard processing functions, including onboard communications and onboard ATM switching. The IEEE 1355 is a new serial bus standard which enables high- performance, scalable, modular, parallel systems to be constructed with low system integration cost. This IEEE 1355- based approach can satisfy many of the requirements of onboard communications and onboard ATM switching, e.g., size, flexibility, reliability, fault- tollerance, and high communication processing speeds. This made possible by using the highly integrated 1355 chipsets and performing protocol processing with multiple transputers in parallel. The IEEE 1355 approach also allows for easy expandability owing to its inherent design modularity.Item Stochastic Comparison Results for Non-Blocking Switches with Output Queueing(1996) Kim, Young B.; Makowski, Armand M.; ISR; CSHCNWe 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.Item ALAX- A P1355-Based Architecture for An ATM LAN Access Switch, with Application to ATM Onboard Switching(1996) Makowski, Armand M.; Narayan, Prakash; Kim, Jangkyung; Lee, Jong-Hee; Ryu, Man-Geun; Charleston, Giles C.; Christofili, Thomas; Rao, Sandeep; ISR; CSHCNWe draw attention to the new IEEE P1355 Standard for Heterogeneous InterConnect as a possible platform to support several onboard processing functions, including onboard communications and onboard ATM switching. The main features of IEEE P1355 are illustrated through a discussion of the basic principles and protocol architecture of ALAX, the ATM LAN Access Switch, currently under design in the Laboratory for Advanced Switching Technologies at the University of Maryland, College Park.Item Heavy Traffic Analysis for a Multiplexer Driven by M|GI|Input Processes(1996) Tsoukatos, K.P.; Makowski, Armand M.; ISRWe study the heavy traffic regime of a multiplexer driven by correlated inputs, namely the M|GI|input processes of Cox. We distinguish between M|GI|processes exhibiting short or 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 inputs involve the standard Brownian motion. Of particular interest though are our 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 some other stable non -- Gaussian self-similar process. Thus, the M|GI|processes serve as an example demonstrating that, within long-range dependence, fractional Brownian motion does not assume the ubiquitous role that its counterpart, standard Brownian motion, plays in the short-range dependence setup, and that modeling possibilities attracted to non -- Gaussian limits are not so hard to come by.Item M|G|Input Processes: A versatile class of models for network traffic(1996) Parulekar, M.; Makowski, Armand M.; ISRWe 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.Item Tail Probabilities for M|G|input Processes (I): Preliminary Asymptotics(1996) Parulekar, M.; Makowski, Armand M.; ISRThe 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.Item Simple Optimization Problems via Majorization Ordering(1996) Kim, Young B.; Makowski, Armand M.; ISRWe 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.Item Buffer Overflow Probabilities for a Multiplexer with Self- Similar Traffic(1995) Parulekar, M.; Makowski, Armand M.; ISR; CSHCNWe 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.
- «
- 1 (current)
- 2
- 3
- »