A large proportion of jobs submitted to modern computing clusters and data centers are parallelizable and capable of running on a flexible number of computing cores or servers. Although allocating more servers to such a job results in a higher speed-up in the job’s execution, it reduces the number of servers available to other jobs, which in the worst case, can result in an incoming job not finding any available server to run immediately upon arrival. Hence, a key question to address is: how to optimally allocate servers to jobs such that (i) the average execution time across jobs is minimized and (ii) almost all jobs find at least one server immediately upon arrival. To address this question, we consider a system withnservers, where jobs are parallelizable up to$d^{(n)}$servers and the speed-up function of jobs is concave and increasing. Jobs not finding any available servers upon entry are blocked and lost. We propose a simple server allocation scheme that achieves the minimum average execution time of accepted jobs while ensuring that the blocking probability of jobs vanishes as the system becomes large ($n \to \infty $). This result is established for various traffic conditions as well as for heterogeneous workloads. To prove our result, we employ Stein’s method which also yields non-asymptotic bounds on the blocking probability and the mean execution time. Furthermore, our simulations show that the performance of the scheme is insensitive to the distribution of job execution times.

A large proportion of jobs submitted to modern computing clusters and data centers are parallelizable and capable of running on a flexible number of computing cores or servers. Although allocating more servers to such a job results in a higher speed-up in the job's execution, it reduces the number of servers available to other jobs, which in the worst case, can result in an incoming job not finding any available server to run immediately upon arrival. Hence, a key question to address is: how to optimally allocate servers to jobs such that (i) the average execution time across jobs is minimized and (ii) almost all jobs find at least one server immediately upon arrival. To address this question, we consider a system with n servers, where jobs are parallelizable up to d(n) servers and the speed-up function of jobs is concave and increasing. Jobs not finding any available servers upon entry are blocked and lost. We propose a simple server allocation scheme that achieves the minimum average execution time of accepted jobs while ensuring that the blocking probability of jobs vanishes as the system becomes large (n → ∞). This result is established for various traffic conditions as well as for heterogeneous workloads. To prove our result, we employ Stein's method which also yields non-asymptotic bounds on the blocking probability and the mean execution time. Furthermore, our simulations show that the performance of the scheme is insensitive to the distribution of job execution times.

In this paper, we investigate the impact of majority-rule based random interactions among agents in a large social network on the diffusion of opinions in the network. Opinion of each agent is assumed to be a binary variable taking values in the set {0, 1}. Interactions among agents are modeled using the majority rule, where each agent updates its opinion at random instants by adopting the 'majority' opinion among a group of randomly sampled agents. We investigate two scenarios that respectively incorporate `bias' of the agents towards a specific opinion and stubbornness of some of the agents in the majority rule dynamics. For the first scenario, where all the agents are assumed to be 'biased' towards one of the opinions, it is shown that the agents reach a consensus on the preferred opinion (with high probability) only if the initial fraction of agents having the preferred opinion is above a certain threshold. Furthermore, the mean time taken to reach the consensus is shown to be logarithmic in the network size. In the second scenario, where the presence of 'stubborn' agents, who never update their opinions, is assumed, we characterize the equilibrium distribution of opinions of the non-stubborn agents using mean field techniques. The mean field limit is shown to have multiple stable equilibrium points which leads to a phenomenon known as metastability.

We consider randomized job routing techniques for a system consisting of a large number of parallel processor sharing servers with heterogeneous server speeds. In particular, a scheme, that routes an incoming job request to the server providing the highest instantaneous processing rate per job among two servers, chosen uniformly at random, is proposed. We show that, unlike the homogeneous case, in the heterogeneous case, such randomized dynamic schemes need not always perform better than the optimal static scheme (in which jobs are assigned to servers with fixed probabilities independent of server states) in terms of reducing the mean response time of jobs. Specifically, we show that the stability region under the proposed scheme is a subset of that under the optimal static routing scheme. We also obtain the stationary tail distribution of server occupancies for the proposed scheme in the limit as the system size grows to infinity. This distribution has been shown to be insensitive to job length distribution and decay super-exponentially.

We consider in-network computation of MAX and the approximate histogram in an n-node structure-free random multihop wireless network. The key assumption that we make is that the nodes do not know their relative or absolute locations and that they do not have an identity. For the Aloha MAC protocol, we first describe a protocol in which the MAX value becomes available at the origin in O(√{n/logn}) slots (bit-periods) with high probability. This is within a constant factor of that required by the best coordinated protocol. A minimal structure (knowledge of hop-distance from the sink) is imposed on the network and with this structure, we describe a protocol for pipelined computation of MAX that achieves a rate of Ω(1/(logn)2). Finally, we show how the protocol for computation of MAX can be modified to achieve approximate computation of the histogram. The approximate histogram can be computed in O(n7/2(logn)1/2) bit-periods with high probability.

We revisit the stability analysis of the well-known slotted Aloha protocol with a finite number of queues. Under standard modeling assumptions, we derive a sufficient condition for the stability by applying a positive recurrence criterion due to Rosberg (JAP, vol. 17, no. 3, 1980). Our sufficiency condition for stability is linear in arrival rates and does not require knowledge of the stationary joint statistics of queue lengths as has been the case in previous results. We also derive some sufficient conditions for instability of the protocol. We believe that the technique reported here could be useful in analyzing other stability problems in countable space Markovian settings.

Classical Gaussian white noise in communications and signal processing is viewed as the limit of zero-mean second-order Gaussian processes with a compactly supported flat spectral density as the support goes to infinity. The difficulty of developing a theory to deal with nonlinear transformations of white noise has been to interpret the corresponding limits. In this paper, we show that a renormalization and centering of powers of band-limited Gaussian processes is Gaussian white noise, and, as a consequence, homogeneous polynomials under suitable renormalization remain white noises.

We consider the problem of determining asymptotic bounds on the capacity of a randomadhocnetwork. Previous approaches assumed a link layer model in which if a transmitter-receiver pair can communicate with each other, i.e., the signal to interference and noise ratio (SINR) is above a certain threshold, then the transmitted packet is received error-free by the receiver thereby. Using this model, the per node capacity of the network was shown to be Theta(radic(nlogn)/1). In reality, for any finite link SINR, there is a nonzero probability of erroneous reception of the packet. We show that in a large network, as the packet travels an asymptotically large number of hops from source to destination, the cumulative impact of packet losses over intermediate links results in a per-node throughput of onlyO(radic(n)/1) under the previously proposed routing and scheduling strategy. We then propose a new scheduling scheme to counter this effect. The proposed scheme provides tight guarantees on end-to-end packet loss probability, and improves the per-node throughput to Omega(radic(n)(logn)/12(alpha-2)/alpha+2) wherealpha>2is the path loss exponent.

We study the problem of optimal reduced-dimension linear transform coding and reconstruction of a signal based on distributed correlated observations of the signal. In the mean square estimation context this involves finding the optimal signal representation based on multiple incomplete or only partial observations that are correlated. In particular, this leads to the study of finding the optimal Karhunen-Loeve basis based on the censored observations. The problem has been considered previously by Gastpar, Dragotti, and Vetterli in the context of jointly Gaussian random variables based on using conditional covariances. In this paper, we derive the estimation results in the more general setting of second-order random variables with arbitrary distributions, using entirely different techniques based on the idea of innovations. We explicitly solve the single transform coder case, give a characterization of optimality in the multiple distributed transform coders scenario and provide additional insights into the structure of the problem.

In this paper, the maximum number of simultaneous active transmitters (i.e. user capacity) is obtained in the many user case for fading multiple-access channels in which a minimum rate must be maintained for all active users. The results are presented in the form of scaling laws as the number of transmitters increases and three commonly used fading models, namely, Rayleigh, Rician and Nakagami are considered. It is shown that in all three cases, the user capacity scales double logarithmically with the number of users and differs only by constants depending on the distributions. We also show that the scheduling policy maximizing the number of simultaneous active transmitters can be implemented in a distributed fashion.

In this paper, we extend the results on the maximum number of active users maintaining minimum rate Rmin> 0 in broadcast channels, known for Rayleigh fading to the cases of Rician and Nakagami fading models. Under the assumption of independent Rician fading channels for different receivers, as the total number of receivers n goes to infinity, the maximum number of active receivers is shown to be equal to ln(2P In n)/Rminwith probability approaching one, where P is total transmit power. For broadcast channels with Nakagami fading, the maximum number of active receivers is shown to be equal to ln(omega/mu P In n)/Rminwith probability approaching one, where omega and mu are the Nakagami distribution parameters. A by-product of the results is to also provide a power allocation strategy that maximizes the total throughput subject to the rate constraints.

In this paper, a power allocation scheme is proposed to maximize the number of active terminals in fading multi-user channels in which a minimum rate must be maintained for all active users. It is assumed that receivers and transmitters have perfect channel state information. Both uplink and downlink scenarios are considered and under the assumption of independent Rayleigh fading channels for different terminals, the optimal number of active terminals is asymptotically obtained as the total number of users, n, is large enough. For broadcast channels with successive interference cancellation at receivers and multiple- access channels with joint decoding at the receiver, the maximum number of active terminals is shown to be arbitrarily close to In ( Ptotal/sigma2\ In n) /Rminwith probability approaching one, where Ptotaland Rmindenote total transmit power and the minimum rate respectively, and sigma2represents the noise variance.

Stability and fairness are two design objectives of congestion control mechanisms; they have traditionally been analyzed for long-lived flows (or elephants). It is only recently that short-lived flows (or mice) have received attention. Whereas stability has been established for the existing primal-dual based control mechanisms, the performance issue has been largely overlooked. In this paper, we study utility maximization problems for networks with dynamic flows. In particular, we consider the case where sessions of each class results in flows that arrive according to a Poisson process and have a length given by a general distribution. The goal is to maximize the long-term expected system utility that is a function of the number of flows and the rate (identical within a given class) allocated to each flow. Our results show that, as long as the average amount of work brought by the flows is strictly within the network stability region, the rate allocation and stability issues are decoupled. While stability can be guaranteed by, for example, a FIFO policy, utility maximization becomes an unconstrained optimization that results in a static rate allocation for flows. We also provide a queueing interpretation of this seemingly surprising result and show that not all utility functions make sense for dynamic flows. Finally, we use simulation results to show that indeed the open-loop algorithm maximizes the expected system utility.

For broadcast channels, a power allocation scheme is proposed to maximize the number of active receivers, for each of which, a minimum rate Rmin> 0 can be achieved. Under the assumption of independent Rayleigh-fading channels for different receivers, as the total number of receivers n goes to infinity, the maximum number of active receivers is shown to be arbitrarily close to ln(Pln n)/Rminwith probability approaching 1, where P is the total transmit power.

We consider the problem of throughput-optimal cross-layer design of wireless networks. We propose a joint congestion control and scheduling algorithm that achieves a fraction 1/dI(G) of the capacity region, where dI(G) depends on certain structural properties of the underlying connectivity graph G of the wireless network and also on the type of interference constraints. For a wide range of wireless networks, dI(G) can be upper bounded by a constant, independent of the number of nodes in the network. The scheduling element of our algorithm is the maximal scheduling policy. Although maximal scheduling policy has been considered in many of the previous works, the difficulties that arise in implementing it in a distributed fashion in the presence of interference have not been dealt with previously. In this paper, we propose two novel randomized distributed algorithms for implementing the maximal scheduling policy under the 1-hop and 2-hop interference models.

We consider the problem of throughput-optimal scheduling in wireless networks subject to interference constraints. We model the interference using a family of K -hop interference models. We define a K-hop interference model as one for which no two links within K hops can successfully transmit at the same time (Note that IEEE 802.11 DCF corresponds to a 2-hop interference model.) .For a given K, a throughput-optimal scheduler needs to solve a maximum weighted matching problem subject to the K-hop interference constraints. For K=1, the resulting problem is the classical Maximum Weighted Matching problem, that can be solved in polynomial time. However, we show that for K>1,the resulting problems are NP-Hard and cannot be approximated within a factor that grows polynomially with the number of nodes. Interestingly, we show that for specific kinds of graphs, that can be used to model the underlying connectivity graph of a wide range of wireless networks, the resulting problems admit polynomial time approximation schemes. We also show that a simple greedy matching algorithm provides a constant factor approximation to the scheduling problem for all K in this case. We then show that under a setting with single-hop traffic and no rate control, the maximal scheduling policy considered in recent related works can achieve a constant fraction of the capacity region for networks whose connectivity graph can be represented using one of the above classes of graphs. These results are encouraging as they suggest that one can develop distributed algorithms to achieve near optimal throughput in case of a wide range of wireless networks.

There has been significant recent interest within the networking research community to characterize the impact of mobility on the capacity and delay in mobile ad hoc networks. In this correspondence, the fundamental tradeoff between the capacity and delay for a mobile ad hoc network under the Brownian motion model is studied. It is shown that the two-hop relaying scheme proposed by Grossglauser and Tse (2001), while capable of achieving a per-node throughput of /spl Theta/(1), incurs an expected packet delay of /spl Omega/(logn//spl sigma//sub n//sup 2/), where /spl sigma//sub n//sup 2/ is the variance parameter of the Brownian motion model. It is then shown that an attempt to reduce the delay beyond this value results in the throughput dropping to its value under static settings. In particular, it is shown that under a large class of scheduling and relaying schemes, if the mean packet delay is O(n/sup /spl alpha////spl sigma//sub n//sup 2/), for any /spl alpha/<0, then the per-node throughput must be O(1//spl radic/n). This result is in sharp contrast to other results that have recently been reported in the literature.

In this paper, we present an opportunistic power scheduling scheme, i.e., a joint time-slot and power allocation scheme for downlink communication in wireless systems. Unlike past works, we allow multiple transmissions in a time-slot that could potentially interfere with each other. These multiple transmissions are allowed to achieve high system efficiency. Hence, it is important to not only select the mobiles to be scheduled in a time-slot, but also to allocate an appropriate transmission power level to these scheduled mobiles. We model the time-varying wireless channel as a stochastic process and formulate a stochastic optimization problem that attempts to maximize the expected total system utility with general constraints on performance or fairness. The power scheduling algorithm is obtained by using stochastic duality and implemented via stochastic subgradient techniques

In this paper, we investigate the use of limited infrastructure, in the form of wires, for improving the energy efficiency of a wireless sensor network. We call such a sensor network - a wireless sensor network with a limited infrastructural support - a hybrid sensor network. The wires act as short cuts to bring down the average hop count of the network, resulting in a reduced energy dissipation per node. Our results indicate that adding a few wires to a wireless sensor network can not only reduce the average energy expenditure per sensor node, but also the non-uniformity in the energy expenditure across the sensor nodes.

We consider a heterogeneous sensor network in which nodes are to be deployed over a unit area for the purpose of surveillance. An aircraft visits the area periodically and gathers data about the activity in the area from the sensor nodes. There are two types of nodes that are distributed over the area using two-dimensional homogeneous Poisson point processes; type 0 nodes with intensity (average number per unit area) /spl lambda//sub 0/ and battery energy E/sub 0/; and type 1 nodes with intensity /spl lambda//sub 1/ and battery energy E/sub 1/. Type 0 nodes do the sensing while type 1 nodes act as the cluster heads besides doing the sensing. Nodes use multihopping to communicate with their closest cluster heads. We determine them optimum node intensities (/spl lambda//sub 0/, /spl lambda//sub 1/) and node energies (E/sub 0/, E/sub 1/) that guarantee a lifetime of at least T units, while ensuring connectivity and coverage of the surveillance area with a high probability. We minimize the overall cost of the network under these constraints. Lifetime is defined as the number of successful data gathering trips (or cycles) that are possible until connectivity and/or coverage are lost. Conditions for a sharp cutoff are also taken into account, i.e., we ensure that almost all the nodes run out of energy at about the same time so that there is very little energy waste due to residual energy. We compare the results for random deployment with those of a grid deployment in which nodes are placed deterministically along grid points. We observe that in both cases /spl lambda//sub 1/ scales approximately as /spl radic/(/spl lambda//sub 0/). Our results can be directly extended to take into account unreliable nodes.

In this paper, we investigate the problem of distributively allocating transmission data rates to users in the Internet. We allow users to have concave as well as sigmoidal utility functions as appropriate for different applications. In the literature, for simplicity, most works have dealt only with the concave utility function. However, we show that applying rate control algorithms developed for concave utility functions in a more realistic setting (with both concave and sigmoidal types of utility functions) could lead to instability and high network congestion. We show that a pricing-based mechanism that solves the dual formulation can be developed based on the theory of subdifferentials with the property that the prices "self-regulate" the users to access the resources based on the net utility. We discuss convergence issues and show that an algorithm can be developed that is efficient in the sense of achieving the global optimum when there are many users.

In this paper we consider a power allocation problem in multi-class wireless systems. We focus on the downlink of the system. Each mobile has a utility function that characterizes its degree of satisfaction for the received service. The objective is to obtain a power allocation that maximizes the total system utility. Typically, natural utility functions for each mobile are nonconcave. Hence, we cannot use existing convex optimization techniques to derive a global optimal solution. We develop a simple (distributed) algorithm to obtain a power allocation that is asymptotically optimal in the number of mobiles. The algorithm is based on dynamic pricing and consists of two stages. At the mobile selection stage, the base station selects mobiles to which power is allocated. At the power allocation stage, the base station allocates power to the selected mobiles. We provide numerical results that illustrate the performance of our scheme. In particular, we show that our algorithm results in system performance that is close to the performance of a global optimal solution in most cases.

We study the asymptotic throughput capacity and delay in mobile ad hoc networks following the 2-hop relaying algorithm proposed by Grossglauser and Tse (2001). We assume the nodes to be uniformly distributed on a sphere, and consider two canonical mobility models: the Brownian mobility model (BMM), and the random way-point mobility model (RWMM). We show that for an ad hoc network formed by n mobile nodes the delay scales as O (log/sup 2/n//spl sigma//sup 2/(n)) under the BMM, and, /spl Theta/ (1/r(n)v(n)) under the RWMM, where /spl sigma//sup 2/(n) is the variance parameter of the BMM, v(n) is the average speed of nodes under the RWMM, and r(n) is the communication radius of the nodes.

In this paper, we investigate the problem of distributively allocating transmission rates to users on the Internet. We allow users to have concave as well as sigmoidal utility functions that are natural in the context of various applications. In the literature, for simplicity, most works have dealt only with the concave case. However, we show that when applying rate control algorithms developed for concave utility functions in a more realistic setting (with both concave and sigmoidal types of utility functions), they could lead to instability and high network congestion. We show that a pricing based mechanism that solves the dual formulation can be developed based on the theory of subdifferentials with the property that the prices "self-regulate" the users to access the resource based on the net utility. We discuss convergence issues and show that an algorithm can be developed that is efficient in the sense of achieving the global optimum when there are many users.

We present and power scheduling scheme, i.e., a joint time-slot and power allocation method for wireless cellular systems. We allow multiple transmissions in a time-slot that can interfere with each other. Hence, it is important to not only select the mobiles to he scheduled in a time-slot, hut also important to allocate an appropriate power level for transmission to these scheduled mobiles in order to achieve high system performance and quality of service. We model the time-varying wireless channel as a stochastic process and formulate a stochastic programming problem that attempts to maximize the expected total system utility, with constraints on the minimum expected utility for each mobile. The power scheduling algorithm is obtained by using stochastic duality and implemented via stochastic subgradient techniques.

In this paper, we present simple performance bounds for multiplexed regulated traffic streams, which are leaky-bucket regulated with peak, mean rate and burst size constraints. We consider independent, heterogeneous streams, which are multiplexed in a common buffer. We derive bounds on the mean delay in the deterministic context and we then obtain a simple stochastic bound, which is exact when the number of sources increases. A byproduct is a characterization of the worst case sources for mean delay, when they are leaky bucket regulated.

We use a utility based power allocation framework in the downlink to treat multi-class CDMA wireless services in a unified way. Our goal is to obtain a power allocation which maximizes the total system utility. Natural utility functions for each mobile are non-concave. Hence we cannot use existing techniques on convex optimization problems to derive a social optimal solution. We propose a simple distributed algorithm to obtain an approximation to the social optimal power allocation. The algorithm is based on dynamic pricing and allows partial cooperation between mobiles and the base station. The algorithm consists of two stages. At the first stage, the base station selects mobiles to which power is allocated, considering their partial-cooperative nature. This is called partial-cooperative optimal selection, since in a partial-cooperative setting and pricing scheme, this selection is optimal and satisfies system feasibility. At the next stage, the base station allocates power to the selected mobiles. This power allocation is a social optimal power allocation among mobiles in the partial-cooperative optimal selection, thus, we call it a partial-cooperative optimal power allocation. We compare the partial-cooperative optimal power allocation with the social optimal power allocation for the single class case. From these results, we infer that the system utility obtained by partial-cooperative optimal power allocation is quite close to the system utility obtained by social optimal allocation.

In this paper we consider a multi-buffered system consisting of N buffers accessed by heterogeneous long-tailed sessions and served according to the generalized processor sharing (GPS) discipline with weights {/spl phi//sub i/}. We assume that sessions arrive according to a Poisson process. A session of type i transmits at rate r/sub i/ and has a duration whose distribution is longtailed of the form P(/spl tau//sub i/>t)/spl sim//spl alpha//sub i/t/sup -(1+/spl beta/i)/ where /spl alpha//sub i/, /spl beta//sub i/>0. We obtain the large buffer asymptotics under very general stability hypotheses. In particular we show that recent results on the GPS asymptotics obtained by Borst, Boxma and Jelenkovic (see IEEE INFOCOM, vol.2, p.912-21, 2000) can be recovered and there are important cases for which we obtain exact asymptotes for which the previous results do not apply. The methodology exploits the sample-path description of the workload evolution under GPS as well as the marked Poisson structure of the inputs.

In this paper we consider a generalization of the so-called M/G//spl infin/ model where M types of long-tailed sessions enter a buffer. The instantaneous rates of the sessions are functions of the occupancy of an M/G//spl infin/ system with long-tailed G distributions. In particular we assume that a session of type i transmits r/sub i/ cells per unit time and lasts for a random time r with long-tailed distribution given by P(/spl tau/>x)/spl sim//spl alpha//sub i/x(-(1+/spl beta//sub i/)) where /spl beta//sub i/>0. We derive the mean cell loss asymptotics for large buffer size as well as the complementary distribution of the buffer occupancy exceeding a high level. When specialized to the homogeneous case we show that recent results on large buffer asymptotics, which have been shown under more restrictive assumptions, hold more generally. In the heterogeneous case, we show that the asymptotics are not necessarily governed by the sources with the smallest /spl beta//sub i/ but also depend on the rates r/sub i/ and it is the ratio of /spl beta//sub i/ to r/sub i/ which is important. Finally it is a simple observation that light-tailed (exponential tails for example) sources have no influence on the asymptotics except that they contribute to reducing the capacity available to heavy-tailed sources by their mean load.

The Nash arbitration scheme from cooperative game theory provides a natural framework to address the allocation of available bandwidth in network links which is network (Pareto) optimal and satisfies precise notions of fairness. In this paper we propose two distributed bandwidth allocation schemes that allocate available bandwidths to elastic sources according to the Nash arbitration scheme. We prove convergence to the desired allocations for both algorithms. Finally we show how such a scheme can be implemented in a real network.

In this paper, we present a game theoretic framework for bandwidth allocation for elastic services in high-speed networks. The framework is based on the idea of the Nash bargaining solution from cooperative game theory, which not only provides the rate settings of users that are Pareto optimal from the point of view of the whole system, but are also consistent with the fairness axioms of game theory. We first consider the centralized problem and then show that this procedure can be decentralized so that greedy optimization by users yields the system optimal bandwidth allocations. We propose a distributed algorithm for implementing the optimal and fair bandwidth allocation and provide conditions for its convergence. The paper concludes with the pricing of elastic connections based on users' bandwidth requirements and users' budget. We show that the above bargaining framework can be used to characterize a rate allocation and a pricing policy which takes into account users' budget in a fair way and such that the total network revenue is maximized.

In this paper we study the cell loss asymptotics for finite buffers accessed by a large number of stationary independent sources and which are served according to a strict HOL priority rule. We first consider the case of two buffers with one of them having strict priority over the other and we obtain asymptotically exact expressions for the cell loss probability for the queues. The asymptotics are studied in terms of a scaling parameter which reflects the server speed, buffer size and the number of sources in such a way that the ratios remain constant. Moreover, as in the single queue case the results are valid for long-range dependent sources with bounded instantaneous rates. The results are then generalised to the case of M buffers where it is shown that resource pooling takes place by which all higher order priority queues can be lumped together when calculating the asymptotics of the lowest priority queue. We conclude with some numerical validation of our formulae against simulations which confirm the theory.

We derive asymptotically exact expressions for buffer overflow probabilities and cell loss probabilities for a finite buffer which is fed by a large number of independent and stationary sources. The technique is based on scaling, measure change and local limit theorems and extends the results of Courcoubetis and Weber (see J. Appl. Prob., vol.33, no.3, p.886-903, 1996) on buffer overflow asymptotics. We discuss the cases when the buffers are of the same order as the transmission bandwidth as well as the case of bufferless multiplexers. Moreover we show that the results hold for a wide variety of traffic sources including on/off sources with heavy-tailed distributed on periods which are typical candidates for so-called "self-similar" inputs showing that the asymptotic cell loss probability behaves in much the same manner for such sources as for Markovian type of sources which has important implications for statistical multiplexing. The paper concludes with comparison of the theoretical results with simulations.

In this paper we consider the problem of calculation of cell loss probabilities when M classes of stationary ON-OFF sources access a given multiplexer of large capacity. We show that when the number of sources of each type is large and scaled according to the capacity we can obtain an explicit analytic formula (O(1) in complexity) in terms of the parameters of the sources. This is based on a measure change technique combined with the use of uniform local limit theorems which gives estimates with a precise notion of the order of errors. We compare our results with standard Gaussian approximations which have been reported showing the improvement in the ATM context where cell loss probabilities are typically of the order 10/sup -9/.

We consider a new policing device suitable for ATM applications. The device operates on an arbitrary source which is fed to a single server queue with a deterministic server. The policing function is implemented at the cell level by assuming the source traffic passes through an infinite server queue whose performance allows a tight control of the policed parameters. An interesting element is that this policing function is not only capable of simultaneously enforcing source parameters like mean rate and burst length, but it also serves to control some desired performance of the single server queue like maximum and mean occupancies.

The robust form of the likelihood ratio for a signal in the presence of white noise has an additional term in the exponent called the correction factor which corresponds to the trace of the conditional covariance of the signal given the observations. The authors show that this correction term is nothing but the trace of the symmetrized Frechet derivative of the nonlinear filter map and hence the likelihood ratio can be completely represented in terms of the observations and the filter map.>

A new approach to congestion management is explored. A traffic process is supposed to be passing through an infinite server queue. The resulting queueing process happens to follow or to track the periods of time during which the "congestion" is being built into the system, giving as a result a real time picture of the congestion introduced by this particular traffic process. This picture, called the congestion process, can be used to throttle the amount of "congestion" introduced to the ATM network, as well as to seize the on-line network resources necessary to guarantee a particular quality of service. Special emphasis is given to applications in ATM B-ISDN with deterministic service queues. Using the congestion process concept, a policing application is discussed as well as some ideas regarding the ATM bandwidth management problem.>

Shows that the interdependence of the discrete wavelet coefficients of fractional Brownian motion, defined by normalized correlation, decays exponentially fast across scales and hyperbolically fast along time.>

Consideration is given to the problem of optimal flow control in a multiclass telecommunications environment where each user (or class) desires to optimize its performance while being fair to the other users (classes). The Nash (1950) arbitration scheme from game theory is shown to be a suitable candidate for a fair, optimal operation point in the sense that it satisfies certain axioms of fairness and is pareto optimal. This strategy can be realized by defining the product of individuals user performance objectives as the network optimization criterion. This provides the rationale for considering the product of user powers, as has been suggested in the literature. For delay constrained traffic, the constrained optimization problem of maximizing the product of user throughputs subject to the constraints leads to a Nash arbitration point. It is shown that these points are unique in throughput space, and the authors also obtain some convexity properties for power and delays with respect to throughputs in a Jackson network.>