We consider a switched (queuing) network in which there are constraints on which queues may be served simultaneously; such networks have been used to effectively model input-queued switches and wireless networks. The scheduling policy for such a network specifies which queues to serve at any point in time, based on the current state or past history of the system. In the main result of this paper, we provide a new class of online scheduling policies that achieve optimal queue-size scaling for a class of switched networks including input-queued switches. In particular, it establishes the validity of a conjecture (documented in Shah, Tsitsiklis and Zhong [Queueing Syst. 68 (2011) 375-384]) about optimal queue-size scaling for input-queued switches.
Another line of works -- so-called large-deviations analysis -- concerns exponentially decaying bounds on the tail probability of the steady-state distributions of queue sizes. established that the maximum weight policy with weight parameter @math , MW- @math , optimizes the tail exponent of the @math norm of the queue-size vector. showed that a so-called exponential rule'' optimizes the tail exponent of the max norm of the queue-size vector. However, these works do not characterize the tail exponent explicitly. See @cite_24 which has the best known explicit bounds on the tail exponent.
@cite_24
1978225669 2592044494 1984181498 2083715455
We provide bounds for the expectations of the stationary delay and the sum of the stationary queue sizes under the approximate maximum weight scheduling (MWS) policy and under the longest-queue-first (LQF) policy in one-hop wireless networks. For MWS, our results improves the previously provided bounds; for LQF, the results are new. In the derivation of the new bounds, a connection with certain graph theory quantities has been established. We also derive bounds for the sum of the second moments of the stationary queue sizes, which are also bounds for the sum of the queue-size variances. The method is general and it can be used to derive bounds for the sum of even higher moments of the stationary queue sizes. However, for the approximate MWS policy, the bounds for the second or higher moments are only valid when the average arrival rate vector is confined to a subset of the capacity region that depends on the order of the moment. We study the tail behavior for the maximum of discrete Gaussian free field on a 2D box with Dirichlet boundary condition after centering by its expectation. We show that it exhibits an exponential decay for the right tail and a double exponential decay for the left tail. In particular, our result implies that the variance of the maximum is of order 1, improving an (o( n) ) bound by Chatterjee (Chaos, concentration, and multiple valleys, 2008) and confirming a folklore conjecture. An important ingredient for our proof is a result of Bramson and Zeitouni (Commun. Pure Appl. Math, 2010), who proved the tightness of the centered maximum together with an evaluation of the expectation up to an additive constant. It is well known that max-weight policies based on a queue backlog index can be used to stabilize stochastic networks, and that similar stability results hold if a delay index is used. Using Lyapunov optimization, we extend this analysis to design a utility maximizing algorithm that uses explicit delay information from the head-of-line packet at each user. The resulting policy is shown to ensure deterministic worst-case delay guarantees and to yield a throughput utility that differs from the optimally fair value by an amount that is inversely proportional to the delay guarantee. Our results hold for a general class of 1-hop networks, including packet switches and multiuser wireless systems with time-varying reliability . It is well known that max-weight policies based on a queue backlog index can be used to stabilize stochastic networks, and that similar stability results hold if a delay index is used. Using Lyapunov Optimization, we extend this analysis to design a utility maximizing algorithm that uses explicit delay information from the head-of-line packet at each user. The resulting policy is shown to ensure deterministic worst-case delay guarantees, and to yield a throughput-utility that differs from the optimally fair value by an amount that is inversely proportional to the delay guarantee. Our results hold for a general class of 1-hop networks, including packet switches and multi-user wireless systems with time varying reliability.