We consider the problem of learning stable matchings with unknown preferences in a decentralized and uncoordinated manner, where ``decentralized" means that players make decisions individually without the influence of a central platform, and ``uncoordinated" means that players do not need to synchronize their decisions using pre-specified rules. First, we provide a game formulation for this problem with known preferences, where the set of pure Nash equilibria (NE) coincides with the set of stable matchings, and mixed NE can be rounded to a stable matching. Then, we show that for hierarchical markets, applying the exponential weight (EXP) learning algorithm to the stable matching game achieves logarithmic regret in a fully decentralized and uncoordinated fashion. Moreover, we show that EXP converges locally and exponentially fast to a stable matching in general matching markets. We complement our results by introducing another decentralized and uncoordinated learning algorithm that globally converges to a stable matching with arbitrarily high probability.

We present the first comprehensive finite-time global convergence analysis of policy gradient for infinite horizon average reward Markov decision processes (MDPs). Specifically, we focus on ergodic tabular MDPs with finite state and action spaces. Our analysis shows that the policy gradient iterates converge to the optimal policy at a sublinear rate of $O(\frac{1}{T})$, where $T$ represents the number of iterations. Performance bounds for discounted reward MDPs cannot be easily extended to average reward MDPs as the bounds grow proportional to the fifth power of the effective horizon. Recent work on such extensions makes a smoothness assumption that has not been verified. Thus, our primary contribution is in providing the first complete proof that the policy gradient algorithm converges globally for average-reward MDPs, without such an assumption. We also obtain the corresponding finite-time performance guarantees. In contrast to the existing discounted reward performance bounds, our performance bounds have an explicit dependence on constants that capture the complexity of the underlying MDP. Motivated by this observation, we reexamine and improve the existing performance bounds for discounted reward MDPs. We also present simulations that empirically validate the result.

Standard reinforcement learning (RL) assumes that an agent can observe a reward for each state-action pair. However, in practical applications, it is often difficult and costly to collect a reward for each state-action pair. While there have been several works considering RL with trajectory feedback, it is unclear if trajectory feedback is inefficient for learning when trajectories are long. In this work, we consider a model named RL with segment feedback, which offers a general paradigm filling the gap between per-state-action feedback and trajectory feedback. In this model, we consider an episodic Markov decision process (MDP), where each episode is divided into $m$ segments, and the agent observes reward feedback only at the end of each segment. Under this model, we study two popular feedback settings: binary feedback and sum feedback, where the agent observes a binary outcome and a reward sum according to the underlying reward function, respectively. To investigate the impact of the number of segments $m$ on learning performance, we design efficient algorithms and establish regret upper and lower bounds for both feedback settings. Our theoretical and experimental results show that: under binary feedback, increasing the number of segments $m$ decreases the regret at an exponential rate; in contrast, surprisingly, under sum feedback, increasing $m$ does not reduce the regret significantly.

Immersive technologies, such as virtual and augmented reality, demand high framerate, low latency, and precise synchronization between real and virtual environments. To meet these requirements, an edge server typically needs to perform high-quality rendering, and must predict user head motion and transmit a portion of the rendered panoramic scene that is large enough to cover the user's viewport, yet small enough to satisfy bandwidth constraints. Each portion yields two feedback signals: prediction feedback, indicating whether the selected portion covers the actual viewport, and transmission feedback, indicating whether all data packets are successfully delivered. While prior work models this setting as a multi-armed bandit with two-level bandit feedback, it overlooks that prediction feedback can be retrospectively computed for all possible portions, thus providing full-information feedback. In this work, we introduce a new two-level feedback model that combines full-information feedback with bandit feedback, and we formulate the portion selection problem as an online learning task under this hybrid setting. We derive an instance-dependent regret lower bound for this new hybrid feedback setting, and we propose AdaPort, a hybrid learning algorithm that leverages both the full-information feedback and bandit feedback to improve learning efficiency. We then show that the instance-dependent regret upper bound for AdaPort matches the lower bound asymptotically, proving its asymptotic optimality. Simulations using synthetic data and real-world traces demonstrate that AdaPort consistently outperforms state-of-the-art baselines, validating the benefits of exploiting the hybrid feedback structure.

The continuous nature of belief states in POMDPs presents significant computational challenges in learning the optimal policy. In this paper, we consider an approach that solves a Partially Observable Reinforcement Learning (PORL) problem by approximating the corresponding POMDP model into a finite-state Markov Decision Process (MDP) (called Superstate MDP). We first derive theoretical guarantees that improve upon prior work that relate the optimal value function of the transformed Superstate MDP to the optimal value function of the original POMDP. Next, we propose a policy-based learning approach with linear function approximation to learn the optimal policy for the Superstate MDP. Consequently, our approach shows that a POMDP can be approximately solved using TD-learning followed by Policy Optimization by treating it as an MDP, where the MDP state corresponds to a finite history. We show that the approximation error decreases exponentially with the length of this history. To the best of our knowledge, our finite-time bounds are the first to explicitly quantify the error introduced when applying standard TD learning to a setting where the true dynamics are not Markovian.

Network alignment, which aims to find node correspondence across different networks, is the cornerstone of various downstream multi-network and Web mining tasks. Most of the embedding-based methods indirectly model cross-network node relationships by contrasting positive and negative node pairs sampled from hand-crafted strategies, which are vulnerable to graph noises and lead to potential misalignment of nodes. Another line of work based on the optimal transport (OT) theory directly models cross-network node relationships and generates noise-reduced alignments. However, OT methods heavily rely on fixed, pre-defined cost functions that prohibit end-to-end training and are hard to generalize. In this paper, we aim to unify the embedding and OT-based methods in a mutually beneficial manner and propose a joint optimal transport and embedding framework for network alignment named JOENA. For one thing (OT for embedding), through a simple yet effective transformation, the noise-reduced OT mapping serves as an adaptive sampling strategy directly modeling all cross-network node pairs for robust embedding learning. For another (embedding for OT), on top of the learned embeddings, the OT cost can be gradually trained in an end-to-end fashion, which further enhances the alignment quality. With a unified objective, the mutual benefits of both methods can be achieved by an alternating optimization schema with guaranteed convergence. Extensive experiments on real-world networks validate the effectiveness and scalability of JOENA, achieving up to 16% improvement in MRR and 20 times speedup compared with the state-of-the-art alignment methods.

Cascading bandits have gained popularity in recent years due to their applicability to recommendation systems and online advertising. In the cascading bandit model, at each timestep, an agent recommends an ordered subset of items (called an item list) from a pool of items, each associated with an unknown attraction probability. Then, the user examines the list, and clicks the first attractive item (if any), and after that, the agent receives a reward. The goal of the agent is to maximize the expected cumulative reward. However, the prior literature on cascading bandits ignores the influences of user states (e.g., historical behaviors) on recommendations and the change of states as the session proceeds. Motivated by this fact, we propose a generalized cascading RL framework, which considers the impact of user states and state transition into decisions. In cascading RL, we need to select items not only with large attraction probabilities but also leading to good successor states. This imposes a huge computational challenge due to the combinatorial action space. To tackle this challenge, we delve into the properties of value functions, and design an oracle BestPerm to efficiently find the optimal item list. Equipped with BestPerm, we develop two algorithms CascadingVI and CascadingBPI, which are both computationally-efficient and sample-efficient, and provide near-optimal regret and sample complexity guarantees. Furthermore, we present experiments to show the improved computational and sample efficiencies of our algorithms compared to straightforward adaptations of existing RL algorithms in practice.

Reinforcement Learning from Human Feedback (RLHF) has achieved impressive empirical successes while relying on a small amount of human feedback. However, there is limited theoretical justification for this phenomenon. Additionally, most recent studies focus on value-based algorithms despite the recent empirical successes of policy-based algorithms. In this work, we consider an RLHF algorithm based on policy optimization (PO-RLHF). The algorithm is based on the popular Policy Cover-Policy Gradient (PC-PG) algorithm, which assumes knowledge of the reward function. In PO-RLHF, knowledge of the reward function is not assumed and the algorithm relies on trajectory-based comparison feedback to infer the reward function. We provide performance bounds for PO-RLHF with low query complexity, which provides insight into why a small amount of human feedback may be sufficient to get good performance with RLHF. A key novelty is our trajectory-level elliptical potential analysis technique used to infer reward function parameters when comparison queries rather than reward observations are used. We provide and analyze algorithms in two settings: linear and neural function approximation, PG-RLHF and NN-PG-RLHF, respectively.

A common technique in reinforcement learning is to evaluate the value function from Monte Carlo simulations of a given policy, and use the estimated value function to obtain a new policy which is greedy with respect to the estimated value function. A well-known longstanding open problem in this context is to prove the convergence of such a scheme when the value function of a policy is estimated from data collected from a single sample path obtained from implementing the policy (see page 99 of [Sutton and Barto, 2018], page 8 of [Tsitsiklis, 2002]). We present a solution to the open problem by showing that a first-visit version of such a policy iteration scheme indeed converges to the optimal policy provided that the policy improvement step uses lookahead [Silver et al., 2016, Mnih et al., 2016, Silver et al., 2017b] rather than a simple greedy policy improvement. We provide results both for the original open problem in the tabular setting and also present extensions to the function approximation setting, where we show that the policy resulting from the algorithm performs close to the optimal policy within a function approximation error.

Multi-server queueing systems are widely used models for job scheduling in machine learning, wireless networks, and crowdsourcing. This paper considers a multi-server system with multiple servers and multiple types of jobs, where different job types require different amounts of processing time at different servers. The goal is to schedule jobs on servers without knowing the statistics of the processing times. To fully utilize the processing power of the servers, it is known that one has to at least learn the service rates of different job types on different servers. Prior works on this topic decouple the learning and scheduling phases which leads to either excessive exploration or extremely large job delays. We propose a new algorithm, which combines the MaxWeight scheduling policy with discounted upper confidence bound (UCB), to simultaneously learn the statistics and schedule jobs to servers. We obtain performance bounds for our algorithm that hold for both stationary and nonstationary service rates. Simulations confirm that the delay performance of our algorithm is several orders of magnitude better than previously proposed algorithms. Our algorithm also has the added benefit that it can handle non-stationarity in the service processes.

The study of collaborative multi-agent bandits has attracted significant attention recently. In light of this, we initiate the study of a new collaborative setting, consisting of $N$ agents such that each agent is learning one of $M$ stochastic multi-armed bandits to minimize their group cumulative regret. We develop decentralized algorithms which facilitate collaboration between the agents under two scenarios. We characterize the performance of these algorithms by deriving the per agent cumulative regret and group regret upper bounds. We also prove lower bounds for the group regret in this setting, which demonstrates the near-optimal behavior of the proposed algorithms.

Many policy-based reinforcement learning (RL) algorithms can be viewed as instantiations of approximate policy iteration (PI), i.e., where policy improvement and policy evaluation are both performed approximately. In applications where the average reward objective is the meaningful performance metric, often discounted reward formulations are used with the discount factor being close to $1,$ which is equivalent to making the expected horizon very large. However, the corresponding theoretical bounds for error performance scale with the square of the horizon. Thus, even after dividing the total reward by the length of the horizon, the corresponding performance bounds for average reward problems go to infinity. Therefore, an open problem has been to obtain meaningful performance bounds for approximate PI and RL algorithms for the average-reward setting. In this paper, we solve this open problem by obtaining the first non-trivial finite time error bounds for average-reward MDPs which go to zero in the limit as policy evaluation and policy improvement errors go to zero.

For the misspecified linear Markov decision process (MLMDP) model of Jin et al. [2020], we propose an algorithm with three desirable properties. (P1) Its regret after K episodes scales as Kmax{\ensuremath{\varepsilon}mis,\ensuremath{\varepsilon}tol}, where \ensuremath{\varepsilon}mis is the degree of misspecification and \ensuremath{\varepsilon}tol is a user-specified error tolerance. (P2) Its space and per-episode time complexities remain bounded as $K\rightarrow\infty$. (P3) It does not require \ensuremath{\varepsilon}mis as input. To our knowledge, this is the first algorithm satisfying all three properties. For concrete choices of \ensuremath{\varepsilon}tol, we also improve existing regret bounds (up to log factors) while achieving either (P2) or (P3) (existing algorithms satisfy neither). At a high level, our algorithm generalizes (to MLMDPs) and refines the Sup-Lin-UCB algorithm, which Takemura et al. [2021] recently showed satisfies (P3) in the contextual bandit setting. We also provide an intuitive interpretation of their result, which informs the design of our algorithm.

We propose an algorithm that uses linear function approximation (LFA) for stochastic shortest path (SSP). Under minimal assumptions, it obtains sublinear regret, is computationally efficient, and uses stationary policies. To our knowledge, this is the first such algorithm in the LFA literature (for SSP or other formulations). Our algorithm is a special case of a more general one, which achieves regret square root in the number of episodes given access to a computation oracle.

Interactive panoramic scene delivery not only consumes 4∼6× more bandwidth than traditional video streaming of the same resolution but also requires timely displaying the delivered content to ensure smooth interaction. Since users can only see roughly 20% of the entire scene at a time (called the viewport), it is sufficient to deliver the relevant portion of the panoramic scene if we can accurately predict the user’s motion. It is customary to deliver a portion larger than the viewport to tolerate inaccurate predictions. Intuitively, the larger the delivered portion, the higher the prediction accuracy and lower the wireless transmission success probability. The goal is to select an appropriate delivery portion to maximize system throughput. We formulate this problem as a multi-armed bandit problem and use the classical Kullback-Leibler Upper Confidence Bound (KL-UCB) algorithm for the portion selection. We further develop a novel variant of the KL-UCB algorithm that effectively leverages two-level feedback (i.e., both prediction and transmission outcomes) after each decision on the selected portion and show its asymptotical optimality, which may be of independent interest by itself. We demonstrate the superior performance of our proposed algorithms over existing heuristic methods using both synthetic simulations and real experimental evaluations.

Cascading bandits is a natural and popular model that frames the task of learning to rank from Bernoulli click feedback in a bandit setting. For the case of unstructured rewards, we prove matching upper and lower bounds for the problem-independent (i.e., gap-free) regret, both of which strictly improve the best known. A key observation is that the hard instances of this problem are those with small mean rewards, i.e., the small click-through rates that are most relevant in practice. Based on this, and the fact that small mean implies small variance for Bernoullis, our key technical result shows that variance-aware confidence sets derived from the Bernstein and Chernoff bounds lead to optimal algorithms (up to log terms), whereas Hoeffding-based algorithms suffer order-wise suboptimal regret. This sharply contrasts with the standard (non-cascading) bandit setting, where the variance-aware algorithms only improve constants. In light of this and as an additional contribution, we propose a variance-aware algorithm for the structured case of linear rewards and show its regret strictly improves the state-of-the-art.

Collision-free path planning is a major challenge in managing unmanned aerial vehicles (UAVs) fleets, especially in uncertain environments. In this paper, we consider the design of UAV routing policies using multi-agent reinforcement learning, and propose a Multi-resolution, Multi-agent, Mean-field reinforcement learning algorithm, named3M-RL,for flight planning, where multiple vehicles need to avoid collisions with each other while moving towards their destinations. In the system we consider, each UAV makes decisions based on local observations, and does not communicate with other UAVs. The algorithm trains a routing policy using an Actor-Critic neural network with multi-resolution observations, including detailed local information and aggregated global information based on mean-field. The algorithm tackles the curse-of-dimensionality problem in multi-agent reinforcement learning and provides a scalable solution. We test our algorithm in different complex scenarios in both 2D and 3D space and our simulation results show that 3M-RL result in good routing policies.

Recent works have shown that agents facing independent instances of a stochastic K-armed bandit can collaborate to decrease regret. However, these works assume that each agent always recommends their individual best-arm estimates to other agents, which is unrealistic in envisioned applications (machine faults in distributed computing or spam in social recommendation systems). Hence, we generalize the setting to include n honest and m malicious agents who recommend best-arm estimates and arbitrary arms, respectively. We first show that even with a single malicious agent, existing collaboration-based algorithms fail to improve regret guarantees over a single-agent baseline. We propose a scheme where honest agents learn who is malicious and dynamically reduce communication with (i.e., "block") them. We show that collaboration indeed decreases regret for this algorithm, assuming m is small compared to K but without assumptions on malicious agents' behavior, thus ensuring that our algorithm is robust against any malicious recommendation strategy.

We consider a budget-constrained bandit problem where each arm pull incurs a random cost, and yields a random reward in return. The objective is to maximize the total expected reward under a budget constraint on the total cost. The model is general in the sense that it allows correlated and potentially heavy-tailed cost-reward pairs that can take on negative values as required by many applications. We show that if moments of order $(2+\gamma)$ for some $\gamma > 0$ exist for all cost-reward pairs, $O(\log B)$ regret is achievable for a budget $B>0$. In order to achieve tight regret bounds, we propose algorithms that exploit the correlation between the cost and reward of each arm by extracting the common information via linear minimum mean-square error estimation. We prove a regret lower bound for this problem, and show that the proposed algorithms achieve tight problem-dependent regret bounds, which are optimal up to a universal constant factor in the case of jointly Gaussian cost and reward pairs.

Motivated by the Internet of Things (IoT) and Cyber-Physical Systems (CPS), we consider dynamic wireless fading networks, where each incoming flow has a random service demand and leaves the system once its service request is completed. In such networks, one of the primary goals of network algorithm design is to achieve short-term fairness that characterizes how often each flow is served, in addition to the more traditional goals such as throughput-optimality and delay-insensitivity to the flow size distribution. In wireline networks, all of these desired properties can be achieved by the round-robin scheduling algorithm. In the context of wireless networks, a natural extension of round-robin scheduling has been developed in the last few years through the use of a counter called the Time-Since-Last-Service (TSLS) that keeps track of the time that passed since the last service time of each flow. However, the performance of this round-robin-like algorithm has been primarily studied in the context of persistent flows that continuously inject packets into the network and do not ever leave the network. The analysis of dynamic flow arrivals and departures is challenging since each individual flow experiences independent wireless fading and thus, flows cannot be served in a strict round-robin manner. In this paper, we overcome this difficulty by exploring the intricate dynamics of TSLS-based algorithm and show that flows are provided round-robin-like service with a very high probability. Consequently, we then show that our algorithm can achieve throughput-optimality. Moreover, through simulations, we demonstrate that the proposed TSLS-based algorithm also exhibits desired properties such as delay-insensitivity and excellent short-term fairness performance in the presence of dynamic flows over wireless fading channels.

In this paper, we establish a theoretical comparison between the asymptotic mean square errors of double Q-learning and Q-learning. Our result builds upon an analysis for linear stochastic approximation based on Lyapunov equations and applies to both tabular setting or with linear function approximation, provided that the optimal policy is unique and the algorithms converge. We show that the asymptotic mean-square error of Double Q-learning is exactly equal to that of Q-learning if Double Q-learning uses twice the learning rate of Q-learning and the output of Double Q-learning is the average of its two estimators. We also present some practical implications of this theoretical observation using simulations.

We consider the dynamics of a linear stochastic approximation algorithm driven by Markovian noise, and derive finite-time bounds on the moments of the error, i.e., deviation of the output of the algorithm from the equilibrium point of an associated ordinary differential equation (ODE). We obtain finite-time bounds on the mean-square error in the case of constant step-size algorithms by considering the drift of an appropriately chosen Lyapunov function. The Lyapunov function can be interpreted either in terms of Stein’s method to obtain bounds on steady-state performance or in terms of Lyapunov stability theory for linear ODEs. We also provide a comprehensive treatment of the moments of the square of the 2-norm of the approximation error. Our analysis yields the following results: (i) for a given step-size, we show that the lower-order moments can be made small as a function of the step-size and can be upper-bounded by the moments of a Gaussian random variable; (ii) we show that the higher-order moments beyond a threshold may be infinite in steady-state; and (iii) we characterize the number of samples needed for the finite-time bounds to be of the same order as the steady-state bounds. As a by-product of our analysis, we also solve the open problem of obtaining finite-time bounds for the performance of temporal difference learning algorithms with linear function approximation and a constant step-size, without requiring a projection step or an i.i.d. noise assumption.

We consider the optimal link rate selection problem in time-varying wireless channels with unknown channel statistics. The aim of optimal link rate selection is to transmit at the optimal rate at each time slot in order to maximize the expected throughput of the wireless channel/link or equivalently minimize the expected regret. Lack of information about channel state or channel statistics necessitates the use of online/sequential learning algorithms to determine the optimal rate. We present an algorithm called CoTS - Constrained Thompson sampling algorithm which improves upon the current state-of-the-art, is fast and is also general in the sense that it can handle several different constraints in the problem with the same algorithm. We also prove an asymptotic lower bound on the expected regret and a high probability large-horizon upper bound on the regret, which show that the regret grows logarithmically with time in an order sense. We also provide numerical results which establish that CoTS significantly outperforms the current state-of-the-art algorithms.

We study two time-scale linear stochastic approximation algorithms, which can be used to model well-known reinforcement learning algorithms such as GTD, GTD2, and TDC. We present finite-time performance bounds for the case where the learning rate is fixed. The key idea in obtaining these bounds is to use a Lyapunov function motivated by singular perturbation theory for linear differential equations. We use the bound to design an adaptive learning rate scheme which significantly improves the convergence rate over the known optimal polynomial decay rule in our experiments, and can be used to potentially improve the performance of any other schedule where the learning rate is changed at pre-determined time instants.

Power control in wireless networks is a well-studied problem. However, recently it has been demonstrated that significant throughput gains can be achieved using data-driven online learning algorithms, supported by a cloud computing infrastructure. In this paper, we provide theoretical guarantees for such algorithms. In particular, we consider two variants of the problem: one which emphasizes long-term throughput and the other which emphasizes robust short-term throughput. The first problem reduces to solving a convex optimization problem with noisy, stochastic measurements while the second one is an online optimization problem where an adversary chooses the reward functions. We provide stochastic and online gradient descent methods customized for the power control problem and establish their convergence analysis. We show that in both cases, the total regret over a time horizon T grows sublinearly at rate O(√T) for suitable choices of algorithms and algorithm parameters.

Modern cellular base stations can transmit over multiple frequencies, and further choose to transmit to different users over different frequencies. In much of the prior literature, it is assumed that the channel state of each user over each frequency is known. However, to get such channel state information for each user-channel pair requires a large overhead. Here, we consider the problem of computationally efficient and throughput-optimal scheduling in networks where the base station ensures a small probing overhead by limiting the number of allowed probe packets per time slot. We first argue that a naive optimization-based MaxWeight algorithm is combinatorially infeasible to implement, and then design a low-complexity algorithm that achieves the same throughput as the naive MaxWeight algorithm. Through simulations, we also investigate further improvements to achieve very small packet delays.

We consider the problem of separating error messages generated in large distributed data center networks into error events. In such networks, each error event leads to a stream of messages generated by hardware and software components affected by the event. These messages are stored in a giant message log. We consider the unsupervised learning problem of identifying the signatures of events that generated these messages; here, the signature of an error event refers to the mixture of messages generated by the event. One of the main contributions of the paper is a novel mapping of our problem which transforms it into a problem of topic discovery in documents. Events in our problem correspond to topics and messages in our problem correspond to words in the topic discovery problem. However, there is no direct analog of documents. Therefore, we use a non-parametric change-point detection algorithm, which has linear computational complexity in the number of messages, to divide the message log into smaller subsets called episodes, which serve as the equivalents of documents. After this mapping has been done, we use a well-known algorithm for topic discovery, called LDA, to solve our problem. We theoretically analyze the change-point detection algorithm, and show that it is consistent and has low sample complexity. We also demonstrate the scalability of our algorithm on a real data set consisting of 97 million messages collected over a period of 15 days, from a distributed data center network which supports the operations of a large wireless service provider.

It is widely conjectured that training algorithms for neural networks are successful because all local minima lead to similar performance; for example, see (LeCun et al., 2015; Choromanska et al., 2015; Dauphin et al., 2014). Performance is typically measured in terms of two metrics: training performance and generalization performance. Here we focus on the training performance of neural networks for binary classification, and provide conditions under which the training error is zero at all local minima of appropriately chosen surrogate loss functions. Our conditions are roughly in the following form: the neurons have to be increasing and strictly convex, the neural network should either be single-layered or is multi-layered with a shortcut-like connection, and the surrogate loss function should be a smooth version of hinge loss. We also provide counterexamples to show that, when these conditions are relaxed, the result may not hold.

We consider the problem of transmitting at the optimal rate over a rapidly-varying wireless channel with unknown statistics when the feedback about channel quality is very limited. One motivation for this problem is that, in emerging wireless networks, the use of mm Wave bands means that the channel quality can fluctuate rapidly and thus, one cannot rely on full channel-state feedback to make transmission rate decisions. Inspired by related problems in the context of multi-armed bandits, we consider a well-known algorithm called Thompson sampling to address this problem. However, unlike the traditional multi-armed bandit problem, a direct application of Thompson sampling results in a computational and storage complexity that grows exponentially with time. Therefore, we propose an algorithm called Modified Thompson sampling (MTS), whose computational and storage complexity is simply linear in the number of channel states and which achieves at most logarithmic regret as a function of time when compared to an optimal algorithm which knows the probability distribution of the channel states.

Approximate graph matching refers to the problem of finding the best correspondence between the node labels of two correlated graphs. The problem has been applied to a number of domains, including social network de-anonymization. Recently, a number of algorithms have been proposed for seeded graph matching, which uses a few seed matches between two graphs to determine the remaining correspondence. We adapt the ideas from seeded algorithms to develop a graph matching correction algorithm, which takes a partially correct correspondence as input and returns an improved correspondence. We show that this algorithm can correct all errors in graph matching for stochastic block model graphs with high probability. Finally, we apply our algorithm as a post-processing step for other approximate graph matching algorithms to significantly improve the performance of state-of-the-art algorithms for seedless graph matching.

As more applications and businesses move to the cloud, pricing for inter-datacenter links has become an important problem. In this paper, we study revenue maximizing pricing from the perspective of a network provider in inter-datacenter networks. Designing a practical bandwidth pricing scheme requires us to jointly consider the requirements of envy-freeness and arbitrage-freeness, where envy-freeness guarantees the fairness of resource allocation and arbitrage-freeness induces users to truthfully reveal their data transfer requests. Considering the non-convexity of the revenue maximization problem and the lack of information about the users' utilities, we propose a framework for computationally efficient pricing to approximately maximize revenue in a range of environments. We first study the case of a single link accessed by many users, and design a (1 + E)-approximation pricing scheme with polynomial time complexity and information complexity. Based on dynamic programming, we then extend the pricing scheme for the tollbooth network, preserving the (1 + E) approximation ratio and the computational complexity. For the general network setting, we analyze the revenue generated by uniform pricing, which determines a single per unit price for all potential users. We show that when users have similar utilities, uniform pricing can achieve a good approximation ratio, which is independent of network topology and data transfer requests. The pricing framework can be extended to multiple time slots, enabling time-dependent pricing.

One of the main difficulties in analyzing neural networks is the non-convexity of the loss function which may have many bad local minima. In this paper, we study the landscape of neural networks for binary classification tasks. Under mild assumptions, we prove that after adding one special neuron with a skip connection to the output, or one special neuron per layer, every local minimum is a global minimum.

Round robin and its variants are well known scheduling policies that are popular in wireline networks due to their throughput optimality, delay insensitivity to file size distributions and short-term fairness. The latter two properties are also extremely important for emerging wireless applications, such as Internet of Things and cyber-physical systems. However, there is no direct wireless analog of round robin with all the desirable properties in wireless networks, where wireless interference and channel fading are predominant. The main reason is due to the fact that it is very difficult to even define what round robin means in wireless networks. This motivates us to develop a round-robin-like algorithm in wireless networks that has nice properties as round robin in wireline networks. To that end, we utilize a counter called the Time-Since-Last-Service (TSLS) that keeps track of the time of each file since its last service, and observe that scheduling a file with maximum TSLS in a single server is equivalent to serving files in a round robin fashion. Based on this key observation, we develop a TSLS-based algorithm that balances the tradeoff between the TSLS value and the channel rate for each link and show that the proposed algorithm achieves maximum system throughput, which demands a nontraditional approach due to the abrupt dynamics of the TSLS metrics. Numerous simulations are provided to validate its desired properties such as delay insensitivity and excellent short-term fairness performance as in the case of round robin algorithms of wireline networks.

The problem of least squares regression of a d-dimensional unknown parameter is considered. A stochastic gradient descent based algorithm with weighted iterate-averaging that uses a single pass over the data is studied and its convergence rate is analyzed. We first consider a bounded constraint set of the unknown parameter. Under some standard regularity assumptions, we provide an explicit O(1/k) upper bound on the convergence rate, depending on the variance (due to the additive noise in the measurements) and the size of the constraint set. We show that the variance term dominates the error and decreases with rate 1 /k, while the constraint set term decreases with rate log k/k2. We then compare the asymptotic ratio ρ between the convergence rate of the proposed scheme and the empirical risk minimizer (ERM) as the number of iterations approaches infinity. We show that ρ ≤ 4 under some mild conditions for all d ≥ 1. We further improve the upper bound by showing that ρ ≤ 4/3 for the case of d =1 and unbounded parameter set. Simulation results demonstrate strong performance of the algorithm as compared to existing methods, and coincide with ρ ≤ 4/3 even for large d in practice.

Here we examine the problem of rumor source identification in star networks. We assume the SI model for rumor propagation with exponential waiting times. We consider the case where a rumor originates from a single source, and find an explicit, non-iterative, maximum likelihood estimate for the source given the observed infection pattern. The theoretical derivation is supported by computational data. We contrast this estimator with the "rumor center" estimator of Shah and Zaman. Unlike rumor centrality, our ML estimator admits the possibility of more than two equiprobable maxima for a given infection pattern, and while a unique rumor center is always equivalent to the distance center, we show that this is not the case for our ML estimator.

We study cloud-storage systems with a very large number of files stored in a very large number of servers. In such systems, files are either replicated or coded to ensure reliability, i.e., file recovery from server failures. This redundancy in storage can further be exploited to improve system performance (mean file access delay) through appropriate load-balancing (routing) schemes. However, it is unclear whether coding or replication is better from a system performance perspective since the corresponding queueing analysis of such systems is, in general, quite difficult except for the trivial case when the system load asymptotically tends to zero. Here, we study the more difficult case where the system load is not asymptotically zero. Using the fact that the system size is large, we obtain a mean-field limit for the steady-state distribution of the number of file access requests waiting at each server. We then use the mean-field limit to show that, for a given storage capacity per file, coding strictly outperforms replication at all traffic loads while improving reliability. Further, the factor by which the performance improves in the heavy-traffic is at least as large as in the light-traffic case. Finally, we validate these results through extensive simulations.

We consider an input queued switch operating under the MaxWeight scheduling algorithm. This system is interesting to study because it is a model for Internet routers and data center networks. Recently, it was shown that the MaxWeight algorithm has optimal heavy-traffic queue length scaling when all ports are uniformly saturated. Here we consider the case where a fraction of the ports are saturated and others are not (which we call the incompletely saturated case), and also the case where the rates at which the ports are saturated can be different. We use a recently developed drift technique to show that the heavy-traffic queue length under the MaxWeight scheduling algorithm has optimal scaling with respect to the switch size even in these cases.

It is well-known that maximum weight scheduling, with link weights which are either functions of queue lengths or the ages of the Head-of-Line (HoL) packets in each queue, maximizes the throughput region of wireless networks with persistent flows. In particular, with only persistent flows, it does not matter for throughput optimality whether one uses queue lengths or HoL ages as weights. In this paper, we show the following interesting result: when some flows in the network are dynamic (i.e., they arrive and depart from the network and are not persistent), then HoL-age-based scheduling algorithms are throughput-optimal while it has previously been shown that queue-length-based algorithms are not. This reveals that, age-based algorithms are universal in the sense that their throughput optimality does not depend on whether the arriving traffic is persistent or not. We also present a distributed implementation of the proposed age-based algorithm using CSMA techniques, where each flow only knows its own age and carrier sensing information. Finally, we support our analytical results through simulations. The proof of throughput optimality may be interesting in its own right: it uses a novel Lyapunov function which is the sum of the ages of all the packets in the network.

In many computing and networking applications, arriving tasks have to be routed to one of many servers, with the goal of minimizing queueing delays. When the number of processors is very large, a popular routing algorithm works as follows: select two servers at random and route an arriving task to the least loaded of the two. It is well-known that this algorithm dramatically reduces queueing delays compared to an algorithm which routes to a single randomly selected server. In recent cloud computing applications, it has been observed that even sampling two queues per arriving task can be expensive and can even increase delays due to messaging overhead. So there is an interest in reducing the number of sampled queues per arriving task. In this paper, we show that the number of sampled queues can be dramatically reduced by using the fact that tasks arrive in batches (called jobs). In particular, we sample a subset of the queues such that the size of the subset is slightly larger than the batch size (thus, on average, we only sample slightly more than one queue per task). Once a random subset of the queues is sampled, we propose a new load balancing method called batch-filling to attempt to equalize the load among the sampled servers. We show that our algorithm dramatically reduces the sample complexity compared to previously proposed algorithms.

The number and size of data centers has seen a rapid growth in the last few years. It is no longer uncommon to see large data centers with thousands or even tens of thousands of machines. Hence, it is critical to develop scalable scheduling mechanisms for processing the enormous number of jobs handled by popular paradigms such as the MapReduce framework. This work explores the possibility of simplifying the scheduling procedure by exploiting the “largeness” of the data center system. Specifically, we consider the problem of minimizing the total flow time of a sequence of jobs under the MapReduce framework, where the jobs arrive over time and need to be processed through both Map and Reduce procedures before leaving the system. We show that any work-conserving scheduler is asymptotically optimal under a wide range of traffic loads, including the heavy traffic limit. Our results are shown for scenarios in which the tasks can be preempted and served in parallel over different machines, as well as scenarios when each task has to be served only on one machine and cannot be preempted. This result implies, somewhat surprisingly, that when we have a large number of machines, there is little to be gained by optimizing beyond ensuring that a scheduler should be work-conserving. For long running applications, we also study the relationship between the number of machines and total running time, and show sufficient conditions to guarantee the asymptotic optimality of work-conserving schedulers. Further, we run extensive simulations, that indeed verify that when the total number of machines is large, state-of-the-art work-conserving schedulers have similar and close-to-optimal delay performance.

We study contextual bandits with budget and time constraints under discrete contexts, referred to as constrained contextual bandits. The time and budget constraints significantly complicate the exploration and exploitation tradeoff because they introduce complex coupling among contexts over time. To gain insight, we first study unit-cost systems with known context distribution. When the expected rewards are known, we develop an approximation of the oracle, referred to Adaptive-Linear-Programming(ALP), which achieves near-optimality and only requires the ordering of expected rewards. With these highly desirable features, we then combine ALP with the upper-confidence-bound (UCB) method in the general case where the expected rewards are unknown a priori. We show that the proposed UCB-ALP algorithm achieves logarithmic regret except in certain boundary cases.Further, we design algorithms and obtain similar regret analysis results for more general systems with unknown context distribution or heterogeneous costs. To the best of our knowledge, this is the first work that shows how to achieve logarithmic regret in constrained contextual bandits. Moreover, this work also sheds light on the study of computationally efficient algorithms for general constrained contextual bandits.

We investigate multi-armed bandits with budgets, a natural model for ad-display optimization encountered in search engines. We provide asymptotic regret lower bounds satisfied by any algorithm, and propose algorithms which match those lower bounds. We consider different types of budgets: scenarios where the advertiser has a fixed budget over a time horizon, and scenarios where the amount of money that is available to spend is incremented in each time slot. Further, we consider two different pricing models, one in which an advertiser is charged for each time her ad is shown (i.e., for each impression) and one in which the advertiser is charged only if a user clicks on the ad. For all of these cases, we show that it is possible to achieve O(log(T)) regret. For both the cost-per-impression and cost-per-click models, with a fixed budget, we provide regret lower bounds that apply to any uniformly good algorithm. Further, we show that B-KL-UCB, a natural variant of KL-UCB, is asymptotically optimal for these cases. Numerical experiments (based on a real-world data set) further suggest that B-KL-UCB also has the same or better finite-time performance when compared to various previously proposed (UCB-like) algorithms, which is important when applying such algorithms to a real-world problem.

Motivated by emerging big streaming data processing paradigms (e.g., Twitter Storm, Streaming MapReduce), we investigate the problem of scheduling graphs over a large cluster of servers. Each graph is a job, where nodes represent compute tasks and edges indicate data-flows between these compute tasks. Jobs (graphs) arrive randomly over time, and upon completion, leave the system. When a job arrives, the scheduler needs to partition the graph and distribute it over the servers to satisfy load balancing and cost considerations. Specifically, neighboring compute tasks in the graph that are mapped to different servers incur load on the network; thus a mapping of the jobs among the servers incurs a cost that is proportional to the number of "broken edges''. We propose a low complexity randomized scheduling algorithm that, without service preemptions, stabilizes the system with graph arrivals/departures; more importantly, it allows a smooth trade-off between minimizing average partitioning cost and average queue lengths. Interestingly, to avoid service preemptions, our approach does not rely on a Gibbs sampler; instead, we show that the corresponding limiting invariant measure has an interpretation stemming from a loss system.

The backpressure scheduling algorithm for multihop wireless networks is known to be throughput optimal, but it requires each node to maintain per-destination queues. Recently, a clever generalization of processor sharing has been proposed which is also throughput optimal, but which only uses per-link queues. Here we propose another algorithm called Queue Proportional Rate Allocation (QPRA) which also only uses per-link queues, and allocates service rates to links in proportion to their queue-lengths and employs the Serve-In-Random-Order (SIRO) discipline within each link. Through fluid limit techniques and using a novel Lyapunov function, we show that the QPRA achieves the maximum throughput. We demonstrate an advantage of QPRA by showing that, for the so-called primary interference model, it is able to develop a low-complexity scheduling scheme which approximates QPRA and achieves a constant fraction of the maximum throughput region, independent of network size.

Given a set of pairwise comparisons, the classical ranking problem computes a single ranking that best represents the preferences of all users. In this paper, we study the problem of inferring individual preferences, arising in the context of making personalized recommendations. In particular, we assume users form clusters; users of the same cluster provide similar pairwise comparisons for the items according to the Bradley-Terry model. We propose an efficient algorithm to estimate the preference for each user: first, compute the net-win vector for each user using the comparisons; second, cluster the users based on the net-win vectors; third, estimate a single preference for each cluster separately. We show that the net-win vectors are much less noisy than the high dimensional vectors of pairwise comparisons, therefore our algorithm can cluster the users reliably. Moreover, we show that, when a cluster is only approximately correct, the maximum likelihood estimation for the Bradley-Terry model is still close to the true preference.

We consider a system of $N$ parallel servers, where each server consists of B units of a resource. Jobs arrive at this system according to a Poisson process, and each job stays in the system for an exponentially distributed amount of time. Each job may request different units of the resource from the system. The goal is to understand how to route arriving jobs to the servers to minimize the probability that an arriving job does not find the required amount of resource at the server, i.e., the goal is to minimize blocking probability. The motivation for this problem arises from the design of cloud computing systems in which the jobs are virtual machines (VMs) that request resources such as memory from a large pool of servers. In this paper, we consider power-of-d-choices routing, where a job is routed to the server with the largest amount of available resource among d ≥ 2 randomly chosen servers. We consider a fluid model that corresponds to the limit as N goes to infinity and provide an explicit upper bound for the equilibrium blocking probability. We show that the upper bound exhibits different behavior as B goes to infinity depending on the relationship between the total traffic intensity λ and B. In particular, if (B -- λ)/√λ → α, the upper bound is doubly exponential in √λ and if (B -- λ)/logd λ → β, β > 1, the upper bound is exponential in λ. Simulation results show that the blocking probability, even for small B, exhibits qualitatively different behavior in the two traffic regimes. This is in contrast with the result for random routing, where the blocking probability scales as O(1/√λ) even if (B -- λ)/√λ → α.

We consider distributed optimization over orthogonal collision channels in spatial multi-channel ALOHA networks. Users are spatially distributed and each user is in the interference range of a few other users. Each user is allowed to transmit over a subset of the shared channels with a certain attempt probability. We study both the non-cooperative and cooperative settings. In the former, the goal of each user is to maximize its own rate irrespective of the utilities of other users. In the latter, the goal is to achieve proportionally fair rates among users. We develop simple distributed learning algorithms to solve these problems. The efficiencies of the proposed algorithms are demonstrated via both theoretical analysis and simulation results.

Data offloading is an increasingly popular mechanism for meeting the rising demands of cellular users. In order to enable the small players, such as businesses and individual owners to make their services available to the bigger wireless service providers (WSPs) to help offload data, a simple, practical and easy-to-use payment machinery needs to be devised. Existing auction mechanisms usually assume that bidders can precisely estimate their true valuations, and they ignore the significant overhead to sellers incurred for obtaining a precise estimation. Such assumption is unrealistic in femtocell networks. To allow imprecise valuations, we introduce the novel concept of perceived valuation, which is a value that can be acquired by the seller at little or no cost. We further propose two novel metrics: partial truthfulness, and imprecision loss, to measure the quality of a truthful auction that accepts perceived valuations. Based on this, we propose EasyBid, a new auction model that provides guarantees for truthfulness even when considering a system with imprecise valuations. Finally, we design a dynamic programming based algorithm which aims to maximize the WSP's utility while satisfying any given constraints on partial truthfulness and imprecision loss. Through simulations, we show that the utility achieved by EasyBid with imprecise valuations can be close to the optimal solution that assumes precise valuations.

LP relaxations of Maximum Weighted Independent Set (MWIS) problems have been widely studied. A key motivation for this prior work comes from the central role that MWIS plays in designing throughput-optimal algorithms for wireless networks. However, to the best of our knowledge, the actual packet delay performance of these algorithms has not been studied in the context of wireless networks. In this paper, we first present an algorithm for solving the LP relaxation of MWIS which exhibits faster convergence to an optimal solution. Further, we show that one does not have to wait for infinite time for convergence to occur, but a simple rounding technique can be used to identify the ON/OFF states of the wireless links in finite time. As in prior work, such an approach only identifies the optimal MWIS states of some of the links in the network. Therefore, we present a scheme to combine this solution with Q-CSMA. Simulations indicate that the proposed scheme significantly improves the performance of Q-CSMA. Further, the proposed algorithm is shown to perform much better than previously suggested LP relaxation schemes due to its superior convergence properties.

In standard clustering problems, data points are represented by vectors, and by stacking them together, one forms a data matrix with row or column cluster structure. In this paper, we consider a class of binary matrices, arising in many applications, which exhibit both row and column cluster structure, and our goal is to exactly recover the underlying row and column clusters by observing only a small fraction of noisy entries. We first derive a lower bound on the minimum number of observations needed for exact cluster recovery. Then, we study three algorithms with different running time and compare the number of observations needed by them for successful cluster recovery. Our analytical results show smooth time-data trade offs: one can gradually reduce the computational complexity when increasingly more observations are available.

The problem of designing scheduling algorithms for a multichannel (e.g., orthogonal frequency division multiplexing-based) wireless downlink network is considered. The classic MaxWeight algorithm, although throughput-optimal, results in a very poor per-user delay performance in such systems. Hence, an alternate class of algorithms called iterated longest queues first (iLQF) is proposed for overcoming this issue. The iLQF-class algorithms are analyzed in a number of different system configurations. A particular algorithm in this class, called iLQF with pullup, is shown to be rate function optimal for the problem in an appropriate large deviations setting, and is shown to result in a strictly positive value of the rate function for a number of modifications to the basic system model. Thus, the proposed algorithm yields provable performance guarantees. The analytic results are confirmed through simulations.

We consider a stochastic model of jobs arriving at a cloud data center. Each job requests a certain amount of CPU, memory, disk space, etc. Job sizes (durations) are also modeled as random variables, with possibly unbounded support. These jobs need to be scheduled nonpreemptively on servers. The jobs are first routed to one of the servers when they arrive and are queued at the servers. Each server then chooses a set of jobs from its queues so that it has enough resources to serve all of them simultaneously. This problem has been studied previously under the assumption that job sizes are known and upper-bounded, and an algorithm was proposed that stabilizes traffic load in a diminished capacity region. Here, we present a load balancing and scheduling algorithm that is throughput-optimal, without assuming that job sizes are known or are upper-bounded.

We consider a stochastic model of jobs arriving at a cloud data center. Each job requests a certain amount of CPU, memory, disk space, etc. Job sizes (durations) are also modeled as random variables, with possibly unbounded support. These jobs need to be scheduled non preemptively on servers. The jobs are first routed to one of the servers when they arrive and are queued at the servers. Each server then chooses a set of jobs from its queues so that it has enough resources to serve all of them simultaneously. This problem has been studied previously under the assumption that job sizes are known and upper bounded, and an algorithm was proposed which stabilizes traffic load in a diminished capacity region. Here, we present a load balancing and scheduling algorithm that is throughput optimal, without assuming that job sizes are known or are upper bounded.

We are motivated by the problem of designing a simple distributed algorithm for peer-to-peer streaming applications that can achieve high throughput and low delay, while allowing the neighbor set maintained by each peer to be small. While previous works have mostly used tree structures, our algorithm constructs multiple random directed Hamiltonian cycles and disseminates content over the superposed graph of the cycles. We show that it is possible to achieve the maximum streaming capacity even when each peer only transmits to and receives from Θ(1) neighbors. Further, we show that the proposed algorithm achieves the streaming delay of Θ(log N) when the streaming rate is less than (1 - 1/K) of the maximum capacity for any fixed constant K ≥ 2, where N denotes the number of peers in the network. The key theoretical contribution is to characterize the distance between peers in a graph formed by the superposition of directed random Hamiltonian cycles, in which edges from one of the cycles may be dropped at random. We use Doob martingales and graph expansion ideas to characterize this distance as a function of N, with high probability.

Recently, it has been shown that a simple, distributed backlog-based carrier-sense multiple access (CSMA) algorithm is throughput-optimal. However, throughput optimality is established under the perfect or ideal carrier-sensing assumption, i.e., each link can precisely sense the presence of other active links in its neighborhood. In this paper, we investigate the achievable throughput of the CSMA algorithm under imperfect carrier sensing. Through the analysis on both false positive and negative carrier sensing failures, we show that CSMA can achieve an arbitrary fraction of the capacity region if certain access probabilities are set appropriately. To establish this result, we use the perturbation theory of Markov chains.

Back-pressure-based adaptive routing algorithms where each packet is routed along a possibly different path have been extensively studied in the literature. However, such algorithms typically result in poor delay performance and involve high implementation complexity. In this paper, we develop a new adaptive routing algorithm built upon the widely studied back-pressure algorithm. We decouple the routing and scheduling components of the algorithm by designing a probabilistic routing table that is used to route packets to per-destination queues. The scheduling decisions in the case of wireless networks are made using counters called shadow queues. The results are also extended to the case of networks that employ simple forms of network coding. In that case, our algorithm provides a low-complexity solution to optimally exploit the routing–coding tradeoff.

It has been recently shown that queue-based carrier sense multiple access (CSMA) algorithms are throughput-optimal. In these algorithms, each link of the wireless network has two parameters: a transmission probability and an access probability. The transmission probability of each link is chosen as an appropriate function of its queue length, however the access probabilities are simply regarded as some random numbers since they do not play any role in establishing the network stability. In this paper, we show that the access probabilities control the mixing time of the CSMA Markov chain and, as a result, affect the delay performance of the CSMA. In particular, we derive formulas that relate the mixing time to access probabilities and use these to develop the following guideline for choosing access probabilities: Each link i should choose its access probability equal to 1/(di+1), where diis the number of links that interfere with link i. Simulation results show that this choice of access probabilities results in good delay performance.

In this paper, we consider a wireless network where interference is treated as noise, and we study the nonconvex problem of sum rate maximization by power control. We focus on finding approximately optimal solutions that can be efficiently computed to this NP-hard problem by studying the solutions to two related problems, the sum rate maximization using a signal-to-interference-plus-noise ratio (SINR) approximation and the max-min weightedSINRoptimization. We show that these two problems are intimately connected, can be solved efficiently by algorithms with fast convergence and minimal parameter configuration, and can yield high-quality approximately optimal solutions to sum rate maximization in the low interference regime. As an application of these results, we analyze the connection-level stability of cross-layer utility maximization in the wireless network, where users arrive and depart randomly and are subject to congestion control, and the queue service rates at all the links are determined by the sum rate maximization problem. In particular, we determine the stability region when all the links solve the max-min weightedSINRproblem, using instantaneous queue sizes as weights.

The paper studies throughput-optimal scheduling in wireless networks when there are file arrivals and departures. In the case of single-hop traffic, the well-studied Max Weight algorithm provides soft priorities to links with larger queue lengths. If packets arrive in bursts during file arrival instants, then large variances in file sizes would imply that some links will have very large queue lengths while others will have small queue lengths. Thus, links with small queue lengths may be starved for long periods of time. An alternative is to use only MAC-layer queue lengths in making scheduling decisions; in fact, typically only this information is available since scheduling is performed at the MAC layer. Therefore the questions we ask in this paper are the following: (i) is scheduling using only MAC-layer queue length information throughput-optimal? and (ii) does it improve delay performance compared to the case where scheduling is performed using the total number of packets waiting at a link? We affirmatively answer both questions in the paper (the first theoretically and the second using simulations), making minimal assumptions on the transport-layer window control mechanism.

It has been recently shown that queue-based CSMA algorithms can be throughput optimal. In these algorithms, each link of the wireless network has two parameters: a transmission probability and an access probability. The transmission probability of each link is chosen as an appropriate function of its queue-length, however, the access probabilities are simply regarded as some random numbers since they do not play any role in establishing the network stability. In this paper, we show that the access probabilities control the mixing time of the CSMA Markov chain and, as a result, affect the delay performance of the CSMA. In particular, we derive formulas that relate the mixing time to access probabilities and use these to develop the following guideline for choosing access probabilities: each link i should choose its access probability equal to 1/(di+ 1), where diis the number of links which interfere with link i. Simulation results show that this choice of access probabilities results in good delay performance.

Cloud computing services are becoming ubiquitous, and are starting to serve as the primary source of computing power for both enterprises and personal computing applications. We consider a stochastic model of a cloud computing cluster, where jobs arrive according to a stochastic process and request virtual machines (VMs), which are specified in terms of resources such as CPU, memory and storage space. While there are many design issues associated with such systems, here we focus only on resource allocation problems, such as the design of algorithms for load balancing among servers, and algorithms for scheduling VM configurations. Given our model of a cloud, we first define its capacity, i.e., the maximum rates at which jobs can be processed in such a system. Then, we show that the widely-used Best-Fit scheduling algorithm is not throughput-optimal, and present alternatives which achieve any arbitrary fraction of the capacity region of the cloud. We then study the delay performance of these alternative algorithms through simulations.

Glauber dynamics is a powerful tool to generate randomized, approximate solutions to combinatorially difficult problems. It has been recently used to design distributed carrier-sense multiple-access (CSMA) scheduling algorithms for multihop wireless networks. In this paper, we derive bounds on the mixing time of a generalization of Glauber dynamics where multiple links update their states in parallel and the fugacity of each link can be different. The results are used to prove that the average queue length (and hence, the delay) under the parallel-Glauber-dynamics-based CSMA grows polynomially in the number of links for wireless networks with bounded-degree interference graphs when the arrival rate lies in a fraction of the capacity region. Other versions of adaptive CSMA can be analyzed similarly. We also show that in specific network topologies, the low-delay capacity region can be further improved.

This paper considers the problem of designing scheduling algorithms for multichannel (e.g., OFDM-based) wireless downlink networks, with a large number of users and proportionally large bandwidth. For this system, while the classical MaxWeight algorithm is known to be throughput-optimal, its buffer-overflow performance is very poor (formally, it is shown that it has zero rate function in our setting). To address this, a class of algorithms called iterated Heaviest matching with Longest Queues First (iHLQF) is proposed. The algorithms in this class are shown to be throughput-optimal for a general class of arrival/channel processes, and also rate-function-optimal (i.e., exponentially small buffer overflow probability) for certain arrival/channel processes. iHLQF, however, has higher complexity than MaxWeight (n4versusn2, respectively). To overcome this issue, a new algorithm called Server-Side Greedy (SSG) is proposed. It is shown that SSG is throughput-optimal, results in a much better per-user buffer overflow performance than the MaxWeight algorithm (positive rate function for certain arrival/channel processes), and has a computational complexity (n2) that is comparable to the MaxWeight algorithm. Thus, it provides a nice tradeoff between buffer-overflow performance and computational complexity. These results are validated by both analysis and simulations.

Recently, it has been shown that carrier-sense multiple access (CSMA)-type random access algorithms can achieve the maximum possible throughput in ad hoc wireless networks. However, these algorithms assume an idealized continuous-time CSMA protocol where collisions can never occur. In addition, simulation results indicate that the delay performance of these algorithms can be quite bad. On the other hand, although some simple heuristics (such as greedy maximal scheduling) can yield much better delay performance for a large set of arrival rates, in general they may only achieve a fraction of the capacity region. In this paper, we propose a discrete-time version of the CSMA algorithm. Central to our results is a discrete-time distributed randomized algorithm that is based on a generalization of the so-called Glauber dynamics from statistical physics, where multiple links are allowed to update their states in a single timeslot. The algorithm generates collision-free transmission schedules while explicitly taking collisions into account during the control phase of the protocol, thus relaxing the perfect CSMA assumption. More importantly, the algorithm allows us to incorporate heuristics that lead to very good delay performance while retaining the throughput-optimality property.

We consider structured peer-to-peer (P2P) networks for distributing streaming data such as real-time video. In such P2P networks, each chunk of data is transferred from the server to all the peers using a data distribution tree. The number of trees and the number of children in each tree contribute to the overhead in the data distribution process. In this paper, we show that the maximum streaming rate can be achieved using O(logN) trees in a network of N peers with homogeneous upload capacities, where each peer has O(1) children in each tree. It is further shown that O(1) trees suffice to achieve a near- maximum streaming rate with heterogeneous upload capacities. The solution involves mapping the tree construction problem to a novel Block Packing problem where two-dimensional blocks are packed into a two-dimensional bin subject to some packing constraints. The block packing problem allows us to visualize network bandwidth usage, thus facilitating a particular way to construct trees which establish the above bounds.

This paper considers the problem of designing scheduling algorithms for multi-channel (e.g., OFDM-based) wireless downlink systems. We show that the Server-Side Greedy (SSG) rule introduced in earlier papers for ON-OFF channels performs well even for more general channel models. The key contribution in this paper is the development of new mathematical techniques for analyzing Markov chains that arise when studying general channel models. These techniques include a way of calculating the distribution of the maximum of a multi-dimensional Markov chain (note that the maximum does not have the Markov property on its own), and also a Markov chain stochastic dominance result using coupling arguments.

Glauber dynamics is a powerful tool to generate randomized, approximate solutions to combinatorially difficult problems. It has been recently used to design distributed CSMA scheduling algorithms for multi-hop wireless networks. In this paper, we derive bounds on the mixing time of a generalization of Glauber dynamics where multiple links update their states in parallel and the fugacity of each link can be different. The results are used to prove that the average queue length (and hence, the delay) under the parallel-Glauber-dynamics-based CSMA grows polynomially in the number of links for wireless networks with bounded-degree interference graphs when the arrival rate lies in a fraction of the capacity region. Other versions of adaptive CSMA can be analyzed similarly.

Recently, it has been shown that a simple, distributed CSMA algorithm can achieve throughput-optimality. However, the optimality is established under the ideal carrier sensing assumption, i.e., each link can precisely sense the presence of other active links in its neighborhood. This paper, in contrast, investigates the achievable throughput of the CSMA algorithm under imperfect carrier sensing. The main result is that CSMA can achieve an arbitrary fraction of the capacity region if certain access probabilities are set appropriately. To establish this result, we use the perturbation theory of Markov chains.

This paper studies the problem of scheduling in single-hop wireless networks with real-time traffic, where every packet arrival has an associated deadline and a minimum fraction of packets must be transmitted before the end of the deadline. Using optimization and stochastic network theory we study the problem of scheduling to meet quality of service (QoS) requirements under heterogeneous delay constraints and time-varying channel conditions. Our analysis results in an optimal scheduling algorithm which fairly allocates data rates to all flows while meeting long-term delay demands. We also prove that under a simplified scenario our solution translates into a greedy strategy that makes optimal decisions with low complexity.

The growth of real-time content streaming over the Internet has resulted in the use of peer-to-peer (P2P) approaches for scalable content delivery. In such P2P streaming systems, each peer maintains a playout buffer of content chunks which it attempts to fill by contacting other peers in the network. The objective is to ensure that the chunk to be played out is available with high probability while keeping the buffer size small. A small playout buffer means that the playout delay is small. Thus, the objective is to study the tradeoff between two measures of QoS, chunk playout rate and delay. A policy is a rule that suggests which chunks should be requested by the peer from other peers. We consider consider a number of recently suggested policies consistent with buffer minimization for a given target of skip-free playout. We first study a rarest-first policy that attempts to obtain chunks farthest from playout, and a greedy policy that attempts to obtain chunks nearest to playout. We show that they both have similar buffer scalings (as a function of the number of peers of target probability of skip-free probability). We then study a hybrid policy which achieves order sense improvements over both policies and can achieve order optimal performance. We validate our results using simulations.

The back-pressure algorithm is a well-known throughput-optimal algorithm. However, its implementation requires that each node has to maintain a separate queue for each commodity in the network, and only one queue is served at a time. This fact may lead to a poor delay performance even when the traffic load is not close to network capacity. Also, since the number of commodities in the network is usually very large, the queueing data structure that has to be maintained at each node is respectively complex. In this paper, we present a solution to address both of these issues in the case of a fixed-routing network scenario where the route of each flow is chosen upon arrival. Our proposed architecture allows each node to maintain only per-neighbor queues and, moreover, improves the delay performance of the back-pressure algorithm.

This paper studies the problem of congestion control and scheduling in ad hoc wireless networks that have to support a mixture of best-effort and real-time traffic. Optimization and stochastic network theory have been successful in designing architectures for fair resource allocation to meet long-term throughput demands. However, to the best of our knowledge, strict packet delay deadlines were not considered in this framework previously. In this paper, we propose a model for incorporating the quality-of-service (QoS) requirements of packets with deadlines in the optimization framework. The solution to the problem results in a joint congestion control and scheduling algorithm that fairly allocates resources to meet the fairness objectives of both elastic and inelastic flows and per-packet delay requirements of inelastic flows.

Traditionally, it had been assumed that the efficiency requirements of TCP dictate that the buffer size at the router must be of the order of the bandwidth-delay (C× RTT) product. Recently, this assumption was questioned in a number of papers, and the rule was shown to be conservative for certain traffic models. In particular, by appealing to statistical multiplexing, it was shown that on a router withNlong-lived connections, buffers of sizeO([(C× RTT)/(√N)]) or evenO(1) are sufficient. In this paper, we reexamine the buffer-size requirements of core routers when flows arrive and depart. Our conclusion is as follows: If the core-to-access-speed ratio is large, thenO(1) buffers are sufficient at the core routers; otherwise, larger buffer sizes do improve the flow-level performance of the users. From a modeling point of view, our analysis offers two new insights. First, it may not be appropriate to derive buffer-sizing rules by studying a network with a fixed number of users. In fact, depending upon the core-to-access-speed ratio, the buffer size itself may affect the number of flows in the system, so these two parameters (buffer size and number of flows in the system) should not be treated as independent quantities. Second, in the regime where the core-to-access-speed ratio is large, we note that theO(1) buffer sizes are sufficient for good performance and that no loss of utilization results, as previously believed.

In this paper, we derive new bounds on the throughput efficiency of Greedy Maximal Scheduling (GMS) for wireless networks of arbitrary topology under the generalk-hop interference model. These results improve the known bounds for networks with up to 26 nodes under the 2-hop interference model. We also prove that GMS is throughput-optimal in small networks. In particular, we show that GMS achieves 100% throughput in networks with up to eight nodes under the 2-hop interference model. Furthermore, we provide a simple proof to show that GMS can be implemented using only local neighborhood information in networks of any size.

We consider multiuser scheduling in wireless networks with channel variations and flow-level dynamics. Recently, it has been shown that the MaxWeight algorithm, which is throughput-optimal in networks with a fixed number of users, fails to achieve the maximum throughput in the presence of flow-level dynamics. In this paper, we propose a new algorithm, called Workload-based Scheduling with Learning, which is provably throughput-optimal, requires no prior knowledge of channels and user demands, and performs significantly better than previously suggested algorithms.

In this paper, we study distributed channel assignment in wireless networks with applications to peer discovery in ad hoc wireless networks. We model channel assignment as a coloring problem for spatial point processes in whichnnodes are located in a unit cube uniformly at random and each node is assigned one ofKcolors, where each color represents a channel. The objective is to maximize the spatial separation between nodes of the same color. In general, it is hard to derive the optimal coloring algorithm, and we therefore consider a natural online greedy coloring algorithm first proposed by Ko and Rubenstein in 2005. We prove two key results: 1) with just logn/log logncolors, the distance separation achieved by the greedy coloring algorithm asymptotically matches the optimal distance separation that can be achieved by an algorithm which is allowed to optimally place the nodes but is allowed to use only one color; and 2) when K=Ω(log n), the greedy coloring algorithm asymptotically achieves the best distance separation that can be achieved by an algorithm which is allowed to both optimally color and place nodes. The greedy coloring algorithm is also shown to dramatically outperform a simple random coloring algorithm. Moreover, the results continue to hold under node mobility.

The back-pressure algorithm introduced in 1992 by Tassiulas and Ephremides is a well-known distributed and adaptive routing/scheduling algorithm where nodes only need the queue-length information of neighboring nodes to make routing decisions. Packets are adaptively routed in the network according to congestion information, which makes the algorithm resilient to traffic and topology changes. However, the back-pressure algorithm requires routers to maintain a separate queue for each destination, which precludes its implementation in large-scale networks. In this paper, we propose a distributed cluster-based back-pressure routing algorithm that retains the adaptability of back-pressure routing while significantly reducing the number of queues that have to be maintained at each node.

This paper considers the problem of designing scheduling algorithms for multi-channel (e.g., OFDM) wireless downlink networks with n users/OFDM sub-channels. For this system, while the classical MaxWeight algorithm is known to be throughput-optimal, its buffer-overflow performance is very poor (formally, we show it has zero rate function in our setting). To address this, we propose a class of algorithms called iHLQF (iterated Heaviest matching with Longest Queues First) that is shown to be throughput optimal for a general class of arrival/channel processes, and also rate-function optimal (i.e., exponentially small buffer overflow probability) for certain arrival/channel processes. iHLQF however has higher complexity than MaxWeight (n4vs. n2respectively). To overcome this issue, we propose a new algorithm called SSG (Server-Side Greedy). We show that SSG is throughput optimal, results in a much better per-user buffer overflow performance than the MaxWeight algorithm (positive rate function for certain arrival/channel processes), and has a computational complexity (n2) that is comparable to the MaxWeight algorithm. Thus, it provides a nice trade-off between buffer-overflow performance and computational complexity. These results are validated by both analysis and simulations.

The problem of anonymous networking when an eavesdropper observes packet timings in a communication network is considered. The goal is to hide the identities of source-destination nodes, and paths of information flow in the network. One way to achieve such an anonymity is to use mixers. Mixers are nodes that receive packets from multiple sources and change the timing of packets, by mixing packets at the output links, to prevent the eavesdropper from finding sources of outgoing packets. In this paper, we consider two simple but fundamental scenarios: double input-single output mixer and double input-double output mixer. For the first case, we use the information-theoretic definition of the anonymity, based on average entropy per packet, and find an optimal mixing strategy under a strict latency constraint. For the second case, perfect anonymity is considered, and a maximal throughput strategy with perfect anonymity is found that minimizes the average delay.

This paper studies the problem of congestion control and scheduling in ad hoc wireless networks that have to support a mixture of best-effort and real-time traffic. Optimization and stochastic network theory have been successful in designing architectures for fair resource allocation to meet long-term throughput demands. However, to the best of our knowledge, strict packet delay deadlines were not considered in this framework previously. In this paper, we propose a model for incorporating the quality of service (QoS) requirements of packets with deadlines in the optimization framework. The solution to the problem results in a joint congestion control and scheduling algorithm which fairly allocates resources to meet the fairness objectives of both elastic and inelastic flows, and per-packet delay requirements of inelastic flows.

We consider multiuser scheduling in wireless networks with channel variations and flow-level dynamics. Recently, it has been shown that the MaxWeight algorithm, which is throughput-optimal in networks with a fixed number users, fails to achieve the maximum throughput in the presence of flow-level dynamics. In this paper, we propose a new algorithm, calledworkload-based scheduling with learning, which is provably throughput-optimal, requires no prior knowledge of channels and user demands, and performs significantly better than previously suggested algorithms.

Recently, it has been shown that CSMA-type random access algorithms can achieve the maximum possible throughput in ad hoc wireless networks. However, these algorithms assume an idealized continuous-time CSMA protocol where collisions can never occur. In addition, simulation results indicate that the delay performance of these algorithms can be quite bad. On the other hand, although some simple heuristics (such as distributed approximations of greedy maximal scheduling) can yield much better delay performance for a large set of arrival rates, they may only achieve a fraction of the capacity region in general. In this paper, we propose a discrete-time version of the CSMA algorithm. Central to our results is a discrete-time distributed randomized algorithm which is based on a generalization of the so-called Glauber dynamics from statistical physics, where multiple links are allowed to update their states in a single time slot. The algorithm generates collision-free transmission schedules while explicitly taking collisions into account during the control phase of the protocol, thus relaxing the perfect CSMA assumption. More importantly, the algorithm allows us to incorporate delay-reduction mechanisms which lead to very good delay performance while retaining the throughput-optimality property.

This paper studies scheduling in multichannel wireless networks with flow-level dynamics. We consider a downlink network with a single base station, M channels (frequency bands), and multiple mobile users (flows). We also assume mobiles dynamically join the network to receive finite-size files and leave after downloading the complete files. A recent study [16] has shown that the MaxWeight algorithm fails to be throughput-optimal under this flow-level dynamics. The main contribution of this paper is the development of joint channel-assignment and workload-based scheduling algorithms for multichannel downlink networks with dynamic flow arrivals/departures. We prove that these algorithms are throughput-optimal. Our simulations further demonstrate that a hybrid channel-assignment and workload-based scheduling algorithm significantly improves the network performance (in terms of both file-transfer delay and blocking probability) compared to the existing algorithms.

In this paper, we study distributed channel assignment in wireless networks with applications to peer discovery in ad hoc wireless networks. We model channel assignment as a coloring problem for spatial point processes in which n nodes are located in a unit cube uniformly at random and each node is assigned one of K colors, where each color represents a channel. The objective is to maximize the spatial separation between nodes of the same color. In general, it is hard to derive the optimal coloring algorithm and therefore, we consider a natural greedy coloring algorithm, first proposed in [5]. We prove two key results: (i) with just a small number of colors when K is roughly of the order of log(n) loglog(n), the distance separation achieved by the greedy coloring algorithm asymptotically matches the optimal distance separation that can be achieved by an algorithm which is allowed to select the locations of the nodes but is allowed to use only one color, and (ii) when K = Omega(log(n)), the greedy coloring algorithm asymptotically achieves the best distance separation that can be achieved by an algorithm which is allowed to both optimally color and place nodes. The greedy coloring algorithm is also shown to dramatically outperform a simple random coloring algorithm. Moreover, the results continue to hold under node mobilities.

It has been conjectured that MWS-α scheduling policies with α going to zero are heavy-traffic optimal for scheduling in a generalized switch when the objective is to minimize the number of backlogged packets in the system. We examine this conjecture by first deriving optimal or heavy-traffic optimal policies for small switches and then comparing them to MWS- α policies by simulation. Our conclusion is that the conjecture is not true in general, i.e., there are simple topologies for which there exist policies that outperform MWS-α in heavy traffic.

We consider wireless ad hoc networks with a large number of users. Subsets of users might be interested in identical information, and so we have a regime in which several multicast sessions may coexist. We first calculate an upper bound on the achievable transmission rate per multicast flow as a function of the number of multicast sources in such a network. We then propose a simple comb-based architecture for multicast routing, which achieves the upper bound in an order sense under certain constraints. Compared to the approach of constructing a Steiner tree to decide multicast paths, our construction achieves the same order-optimal results while requiring little location information and no computational overhead.

The back-pressure algorithm is a well-known throughput-optimal algorithm. However, its delay performance may be quite poor even when the traffic load is not close to network capacity due to the following two reasons. First, each node has to maintain a separate queue for each commodity in the network, and only one queue is served at a time. Second, the backpressure routing algorithm may route some packets along very long routes. In this paper, we present solutions to address both of the above issues, and hence, improve the delay performance of the back-pressure algorithm. One of the suggested solutions also decreases the complexity of the queueing data structures to be maintained at each node.

We consider small generalized switches with less than or equal to four links, and study scheduling policies designed to minimize the total number of packets in the system. By focusing on very small switches, we are able to derive optimal or heavy-traffic optimal policies whose performance can then be compared to previously conjectured optimal policies. In particular, it has been conjectured that the max-weight policy with weight qalphais optimal in heavy-traffic when alpha rarr 0. Our results show that this conjecture is not true.

Sum rate maximization by power control is an important, challenging, and extensively studied problem in wireless networks. It is a nonconvex optimization problem and achieves a rate region that is in general nonconvex. We derive approximation ratios to the sum rate objective by studying the solutions to two related problems, sum rate maximization using an SIR approximation and max-min weighted SIR optimization. We also show that these two problems can be solved very efficiently, using much faster algorithms than the existing ones in the literature. Furthermore, using a new parameterization of the sum rate maximization problem, we obtain a characterization of the power controlled rate region and its convexity property in various asymptotic regimes. Engineering implications are discussed for IEEE 802.11 networks.

Maximizing the minimum weighted SIR, minimizing the weighted sum MSE and maximizing the weighted sum rate in a multiuser downlink system are three important performance objectives in joint transceiver and power optimization, where all the users have a total power constraint. We show that, through connections with the nonlinear Perron-Frobenius theory, jointly optimizing power and beamformers in the max-min weighted SIR problem can be solved optimally in a distributed fashion. Then, connecting these three performance objectives through the arithmetic-geometric mean inequality and nonnegative matrix theory, we solve the weighted sum MSE minimization and weighted sum rate maximization in the low to moderate interference regimes using fast algorithms.

Due to its low complexity, Greedy Maximal Scheduling (GMS), also known as Longest Queue First (LQF), has been studied extensively for wireless networks. However, GMS can result in degraded throughput performance in general wireless networks. In this paper, we prove that GMS achieves 100% throughput in all networks with eight nodes or less, under the two-hop interference model. Further, we obtain performance bounds that improve upon previous results for larger networks up to a certain size. We also provide a simple proof to show that GMS can be implemented using only local neighborhood information in networks of any size.

Traditionally, it had been assumed that the efficiency requirements of TCP dictate that the buffer size at the router must be of the order of the bandwidth (C)-delay (RTT) product. Recently this assumption was questioned in a number of papers and the rule was shown to be conservative for certain traffic models. In particular, by appealing to statistical multiplexing it was shown that on a router with N long-lived connections, buffers of size O(CxRTT)/radic(N) or even O(1) are sufficient. In this paper, we reexamine the buffer size requirements of core routers when flows arrive and depart. Our conclusion is as follows: if the core to access speed ratio is large, then O(1) buffers are sufficient at the core routers; otherwise, larger buffer sizes do improve the flow-level performance of the users. From a modeling point of view, our analysis offers two new insights. First, it may not be appropriate to derive buffer-sizing rules by studying a network with a fixed number of users. In fact, depending upon the core-to-access speed ratio, the buffer size itself may affect the number of flows in the system, so these two parameters (buffer size and number of flows in the system) should not be treated as independent quantities. Second, in the regime where the core-to- access speed ratio is large, we note that the O(1) buffer sizes are sufficient for good performance and that no loss of utilization results, as previously believed.

We study scalable, distributed, and adaptive routing algorithms for communication networks. The back-pressure algorithm introduced in [21] is a well-known distributed and adaptive routing/scheduling algorithm where nodes only need the queue length information of neighboring nodes to make routing decisions, and packets are adaptively routed in the network according to congestion information, which makes the algorithm resilient to traffic and topology changes. However, the back-pressure algorithm requires routers to maintain a separate queue for each destination, which prevents its implementation in large-scale networks like the Internet. In this paper, we propose a cluster-based back-pressure routing algorithm, which retains the distributability and adaptability of back-pressure routing, while significantly reducing the number of queues that have to be maintained at each node. Since the cluster-based algorithm performs adaptive load-balancing in the network, it has the potential to eliminate the need for off-line traffic engineering in the Internet.

We study revenue-maximizing pricing by a service provider in a communication network and compare revenues from simple pricing rules to the maximum revenues that are feasible. In particular, we focus on flat entry fees as the simplest pricing rule. We provide a lower bound for the ratio between the revenue from this pricing rule and maximum revenue, which we refer to as the Price of Simplicity. We characterize what types of environments lead to a low Price of Simplicity and show that in a range of environments, the loss of revenue from using simple entry fees is small. We then study the Price of Simplicity for a simple non-linear pricing (price discrimination) scheme based on the Paris Metro Pricing. The service provider creates different service classes and charges differential entry fees for these classes. We show that the gain from this type of price discrimination is small, particularly in environments in which the simple entry fee pricing leads to a low Price of Simplicity.

In this paper, we are interested in the connection-level stability of a network employing congestion control. In particular, we study how the stability region of the network (i.e., the set of offered loads for which the number of active users in the network remains finite) is affected by congestion control. Previous works in the literature typically adopt a time-scale separation assumption, which assumes that, whenever the number of users in the system changes, the data rates of the users are adjusted instantaneously to the optimal and fair rate allocation. Under this assumption, it has been shown that such rate assignment policies can achieve the largest possible stability region. In this paper, this time-scale separation assumption is removed and it is shown that the largest possible stability region can still be achieved by a large class of control algorithms. A second assumption often made in prior work is that the packets of a source (or user) are offered to each link along its path instantaneously, rather than passing through one queue at a time. We show that connection-level stability is again maintained when this assumption is removed, provided that a back-pressure scheduling algorithm is used jointly with the appropriate congestion controller.

In this paper, we investigate the delay–throughput tradeoffs in mobilead-hocnetworks. We consider four node mobility models: 1) two-dimensional independent and identically distributed (i.i.d.) mobility, 2) two-dimensional hybrid random walk, 3) one-dimensional i.i.d. mobility, and 4) one-dimensional hybrid random walk. Two mobility time scales are included in this paper. i) Fast mobility, where node mobility is at the same time scale as data transmissions. ii) Slow mobility, where node mobility is assumed to occur at a much slower time scale than data transmissions. Given a delay constraint$D$, we first characterize the maximum throughput per source–destination (S-D) pair for each of the four mobility models with fast or slow mobiles. We then develop joint coding–scheduling algorithms to achieve the optimal delay–throughput tradeoffs.

We consider the problem of distributed scheduling in wireless networks. We present two different algorithms whose performance is arbitrarily close to that of maximal schedules, but which require low complexity due to the fact that they do not necessarily attempt to find maximal schedules. The first algorithm requires each link to collect local queue-length information in its neighborhood, and its complexity is independent of the size and topology of the network. The second algorithm is presented for the node-exclusive interference model, does not require nodes to collect queue-length information even in their local neighborhoods, and its complexity depends only on the maximum node degree in the network.

Mobile ad-hoc networks are deployed under the assumption that participating nodes are willing to forward other nodes' packets. In reputation-based mechanisms cooperation is induced by means of a threat of partial or total disconnection from the network if a node is non-cooperative; however packet collisions and interference may make cooperative nodes appear selfish sometimes. In this paper we use a simple network model to first study the performance of some proposed reputation strategies and then present a new mechanism that we call DARWIN (Distributed and Adaptive Reputation mechanism for WIreless ad-hoc Networks). The idea is to avoid a retaliation situation after a node has been falsely perceived as selfish so cooperation can be restored quickly. We prove that our strategy is robust to imperfect measurements, is collusion-resistant and can achieve full cooperation among nodes.

We consider wireless ad hoc networks with a large number of users. Subsets of users might be interested in identical information, and so we have a regime in which several multicast sessions may coexist. We first calculate an upper-bound on the achievable transmission rate per multicast flow as a function of the number of multicast sources in such a network. We then propose a simple comb-based architecture for multicast routing which achieves the upper bound in an order sense under certain constraints. Compared to the approach of constructing a Steiner tree to decide multicast paths, our construction achieves the same order-optimal results while requiring little location information and no computational overhead.

This paper proposes a new class of simple, distributed algorithms for scheduling in wireless networks. The algorithms generate new schedules in a distributed manner via simple local changes to existing schedules. The class is parameterized by integers k\geq 1. We show that algorithm k of our class achieves k/(k+2) of the capacity region, for every k\geq 1. .

Internet worms, which spread in computer networks without human mediation, pose a severe threat to computer systems today. The rate of propagation of worms has been measured to be extremely high and they can infect a large fraction of their potential hosts in a short time. We study two different methods of patch dissemination to combat the spread of worms. We first show that using a fixed number of patch servers performs inadequately against Internet worms. We then show that by exploiting the exponential data dissemination capability of P2P systems, the spread of worms can be halted effectively. We compare the two methods by using fluid models to compute two quantities of interest: the time taken to effectively combat the progress of the worm, and the maximum number of infected hosts. We validate our models using simulations.

We consider multiple-input multiple-output (MIMO) fading channels and characterize the reliability function in the low signal-to-noise (SNR) regime as a function of the number of transmit and receive antennas. For the case when the fading matrix H has independent entries, we show that the number of transmit antennas plays a key role in reducing the peakiness in the input signal required to achieve the optimal error exponent for a given communication rate. Further, by considering a correlated channel model, we show that the maximum performance gain (in terms of the error exponent and communication rate) is achieved when the entries of the channel fading matrix are fully correlated. The results we presented in this work in the low-SNR regime can also be applied to the infinite bandwidth regime

In this paper, we investigate the fundamental tradeoff between rate and bandwidth when a constraint is imposed on the error exponent. Specifically, we consider both additive white Gaussian noise (AWGN) and Rayleigh-fading channels where the input symbols are assumed to have a peak constraint. For the AWGN channel model, the optimal values of Rz(0) and Rz(0) are calculated, where Rz(1/B) is the maximum rate at which information can be transmitted over a channel with bandwidth B when the error-exponent is constrained to be greater than or equal to z. The computation of Rz(0) follows Gallager's infinite-bandwidth reliability function computation, while the computation of Rz(0) is new and parallels Verdu's second-order calculation for channel capacity. Based on these calculations, we say that a sequence of input distributions is near optimal if both Rz(0) and Rz(0) are achieved. We show that quaternary phase-shift keying (QPSK), a widely used signaling scheme, is near optimal within a large class of input distributions for the AWGN channel. Similar results are also established for a fading channel where full channel side information (CSI) is available at the receiver

In this correspondence, we consider a wireless sensor network consisting of n sensors, and each sensor has a measurement, which is an integer value belonging to the set {().....m-1}, so that it can be represented by [log2m] bits. The network has a special node called the fusion center whose goal is to compute a symmetric function of these measurements. The problem studied is to minimize the total transmission energy used by the network when computing this function, subject to the constraint that this computation be correct with high probability. We assume the wireless channels are binary symmetric channels with a probability of error p, and that each sensor uses ralphaunits of energy to transmit each bit, where r is the transmission range of the sensor.

We consider the problem of distributed scheduling in wireless networks subject to simple collision constraints. We define the efficiency of a distributed scheduling algorithm to be the largest number (fraction) such that the throughput under the distributed scheduling policy is at least equal to the efficiency multiplied by the maximum throughput achievable under a centralized policy. For a general interference model, we prove a lower bound on the efficiency of a distributed scheduling algorithm by first assuming that all of the traffic only uses one hop of the network. We also prove that the lower bound is tight in the sense that, for any fraction larger than the lower bound, we can find a topology and an arrival rate vector within the fraction of the capacity region such that the network is unstable under a greedy scheduling policy. We then extend our results to a more general multihop traffic scenario and show that similar scheduling efficiency results can be established by introducing prioritization or regulators to the basic greedy scheduling algorithm

Abstract — We consider a multi-hop wireless network shared by many users. For an interference model that only constrains a node to either transmit or receive at a time, but not both, we propose an architecture for fair resource allocation that consists of a distributed scheduling algorithm operating in conjunction with an asynchronous congestion control algorithm. We show that the proposed joint congestion control and scheduling algorithm supports at least one-third of the throughput supportable by any other algorithm, including centralized algorithms. I.

We consider the problem of distributed scheduling in wireless networks subject to simple collision constraints. We define the efficiency of a distributed scheduling algorithm to be the largest number (fraction) such that the throughput under the distributed scheduling policy is at least equal to the efficiency multiplied by the maximum throughput achievable under a centralized policy. For a general interference model, we prove a lower bound on the efficiency of a distributed scheduling algorithm by first assuming that all of the traffic only uses one hop of the network. We also prove that the lower bound is tight in the sense that, for any fraction larger than the lower bound, we can find a topology and an arrival rate vector within the fraction of the capacity region such that the network is unstable under a greedy scheduling policy. We then extend our results to a more general multihop traffic scenario and show that similar scheduling efficiency results can be established by introducing prioritization or regulators to the basic greedy scheduling algorithm.

We study the distributed averaging problem on arbitrary connected graphs, with the additional constraint that the value at each node is an integer. This discretized distributed averaging problem models averaging in a network with finite capacity channels (and in this form has applications to distributed detection in sensor networks) and load balancing in a processor network. We describe simple randomized distributed algorithms which achieve consensus to the extent that the discrete nature of the problem permits.

We consider a cellular network consisting of a base station and N receivers. The channel states of the receivers are assumed to be identical and independent of each other. The goal is to compare the throughput of two different scheduling policies ( a queue-length-based policy and a greedy scheduling policy) given an upper bound on the queue overflow probability. We consider a multi-state channel model, where each channel is assumed to be in one of L states. Given an upper bound on the queue overflow probability, we obtain a lower bound on the throughput of the queue-length-based policy. For sufficiently large N, the lower bound is shown to be tight, strictly increasing with N, and strictly larger than the throughput of the greedy policy

We consider a wireless sensor network consisting of n sensors, each having a recorded bit, the sensor’s measurement, which has been set to either “0” or “1”. The network has a special node called the fusion center whose goal is to compute a symmetric function of these bits; i.e., a function that depends only on the number of sensors that have a “1.” The sensors convey information to the fusion center in a multi-hop fashion to enable the function computation. The problem studied is to minimize the total transmission energy used by the network when computing this function, subject to the constraint that this computation is correct with high probability. We assume the wireless channels are binary symmetric channels with a probability of error p, and that each sensor uses rαunits of energy to transmit each bit, where r is the transmission range of the sensor. The main result in this paper is an algorithm whose energy usage is Θ (n(loglogn)(√logn/n)α), and we also show that any algorithm satisfying the performance constraints must necessarily have energy usage Ω (n(√logn/n)α). Then, we consider the case where the sensor network observes N events, and each node records one bit per event, thus having N bits to convey. The fusion center now wants to compute N symmetric functions, one for each of the events.

In this paper, we describe and analyze a joint scheduling, routing and congestion control mechanism for wireless networks, that asymptotically guarantees stability of the buffers and fair allocation of the network resources. The queue-lengths serve as common information to different layers of the network protocol stack. Our main contribution is to prove the asymptotic optimality of a primal-dual congestion controller, which is known to model different versions of transmission control protocol well

This tutorial paper overviews recent developments in optimization-based approaches for resource allocation problems in wireless systems. We begin by overviewing important results in the area of opportunistic (channel-aware) scheduling for cellular (single-hop) networks, where easily implementable myopic policies are shown to optimize system performance. We then describe key lessons learned and the main obstacles in extending the work to general resource allocation problems for multihop wireless networks. Towards this end, we show that a clean-slate optimization-based approach to the multihop resource allocation problem naturally results in a "loosely coupled" cross-layer solution. That is, the algorithms obtained map to different layers [transport, network, and medium access control/physical (MAC/PHY)] of the protocol stack, and are coupled through a limited amount of information being passed back and forth. It turns out that the optimal scheduling component at the MAC layer is very complex, and thus needs simpler (potentially imperfect) distributed solutions. We demonstrate how to use imperfect scheduling in the cross-layer framework and describe recently developed distributed algorithms along these lines. We conclude by describing a set of open research problems.

We investigate the following issue: if fast fades are Markovian and known at the receiver, while the transmitter has only a coarse quantization of the fading process, what capacity penalty comes from having the transmitter act on the current coarse quantization alone? For time-varying channels which experience rapid time variations, sender and receiver typically have asymmetric channel side information. To avoid the expense of providing, through feedback, detailed channel side information to the sender, the receiver offers the sender only a coarse, generally time-averaged, representation of the state of the channel, which we term slow variations. Thus, the receiver tracks the fast variations of the channel (and the slow ones perforce) while the sender receives feedback only about the slow variations. While the fast variations (micro-states) remain Markovian, the slow variations (macro-states) are not. We compute an approximate channel capacity in the following sense: each rate smaller than the "approximate" capacity, computed using results by Caire and Shamai, can be achieved for sufficiently large separation between the time scales for the slow and fast fades. The difference between the true capacity and the approximate capacity is O(/spl epsi/log/sup 2/(/spl epsi/)log(-log(/spl epsi/))), where /spl epsi/ is the ratio between the speed of variation of the channel in the macro- and micro-states. The approximate capacity is computed by power allocation between the slowly varying states using appropriate water filling.

In this correspondence, we consider a cellular network consisting of a base station and N receivers. The channel states of the receivers are assumed to be identical and independent of each other. The goal is to compare the throughput of two different scheduling policies (a queue-length-based (QLB) policy and a greedy policy) given an upper bound on the queue overflow probability or the delay violation probability. We consider a multistate channel model, where each channel is assumed to be in one of L states. Given an upper bound on the queue overflow probability or an upper bound on the delay violation probability, we show that the total network throughput of the (QLB) policy is no less than the throughput of the greedy policy for all N. We also obtain a lower bound on the throughput of the (QLB) policy. For sufficiently large N, the lower bound is shown to be tight, strictly increasing with N, and strictly larger than the throughput of the greedy policy. Further, for a simple multistate channel model-ON-OFF channel, we prove that the lower bound is tight for all N

We consider the problem of allocating resources (time slots, frequency, power, etc.) at a base station to many competing flows, where each flow is intended for a different receiver. The channel conditions may be time-varying and different for different receivers. It is well-known that appropriately chosen queue-length based policies are throughput-optimal while other policies based on the estimation of channel statistics can be used to allocate resources fairly (such as proportional fairness) among competing users. In this paper, we show that a combination of queue-length-based scheduling at the base station and congestion control implemented either at the base station or at the end users can lead to fair resource allocation and queue-length stability.

In this paper, we model and characterize the performance of multihop radio networks in the presence of energy constraints and design routing algorithms to optimally utilize the available energy. The energy model allows vastly different energy sources in heterogeneous environments. The proposed algorithm is shown to achieve a competitive ratio (i.e., the ratio of the performance of any off-line algorithm that has knowledge of all past and future packet arrivals to the performance of our online algorithm) that is asymptotically optimal with respect to the number of nodes in the network. The algorithm assumes no statistical information on packet arrivals and can easily be incorporated into existing routing frameworks (e.g., proactive or on-demand methodologies) in a distributed fashion. Simulation results confirm that the algorithm performs very well in terms of maximizing the throughput of an energy-constrained network. Further, a new threshold-based scheme is proposed to reduce the routing overhead while incurring only minimum performance degradation.

Deterministic delay differential equation models, where the packet traffic is modeled as a fluid, are widely used to study congestion control algorithms in the Internet. In this paper, we point out some pitfalls in such fluid modeling of window flow control algorithms. Specifically, we argue that the modeling assumptions used to capture the variability in the RTT (due to queue length fluctuations) may play a critical role in our ability to design stable algorithms. We study two scenarios to illustrate the dramatic impact of RTT modeling. We first consider TCP-Reno with RED, and show that assuming that the RTT is a constant (when it is actually time-varying) leads to conservative parameter choices, i.e., the system continues to be stable even with variable RTT. On the other hand, for the recently proposed stabilized Vegas, we show the following result: while the network can be stabilized under the constant RTT assumption, there is no choice of parameters that would stabilize the system when the RTT variations are taken into account. Interestingly, such problems do not arise if the congestion-control mechanisms at the end-users are rate-based.

In this paper we examine how transit and customer prices are set in a network consisting of multiple ISPs. Some ISPs may be geographically co-located so that they compete for the same set of end users. We examine the existence of equilibrium price strategies in this situation and show how positive profit can be achieved using threat strategies. It is shown that if the number of ISPs competing for the same customers is large then it can lead to price wars. ISPs that are not geographically co-located may not directly compete for users, but are nevertheless involved in a non-cooperative game of setting access and transit prices for each other. We study how such ISPs are linked economically through transit ISPs by considering a multi-stage game. We also consider the economics of private exchange points and show that they could become far more wide spread then they currently are.

We consider the problem of allocating resources at a base station to many competing flows, when each flow is intended for a different receiver. The channel conditions may be time-varying and different for different receivers. It has been shown in A. Eryilmaz and R. Srikant (2005) that in a delay-free network, a combination of queue-length-based scheduling at the base station and congestion control at the end users can guarantee queue-length stability and fair resource allocation. In this paper, we extend this result to wireless networks where the congestion information from the base station is received with a feedback delay at the transmitters. The delays can be heterogeneous (i.e., different users may have different round-trip delays) and time-varying, but are assumed to be upper-bounded, with possibly very large upper bounds. We show that the joint congestion control-scheduling algorithm continues to be stable and continues to provide a fair allocation of the network resources.

We study the problem of stable scheduling for a class of wireless networks. The goal is to stabilize the queues holding information to be transmitted over a fading channel. Few assumptions are made on the arrival process statistics other than the assumption that their mean values lie within the capacity region and that they satisfy a version of the law of large numbers. We prove that, for any mean arrival rate that lies in the capacity region, the queues will be stable under our policy. Moreover, we show that it is easy to incorporate imperfect queue length information and other approximations that can simplify the implementation of our policy.

In this paper, we evaluate the performance of both real and virtual queue-based marking schemes designed for use at routers in the Internet. Using fluid flow models, we show via analysis and simulations that Virtual Queue (VQ)-based marking schemes outperform Real Queue (RQ)-based marking schemes in terms of robustness to disturbances and the ability to maintain low queueing delays. In fact, we prove that a linearized model of RQ-based marking schemes exhibit a lack of robustness to constant but otherwise unknown levels of disturbances. The analytical results we present are applicable to combinations of proportionally fair and TCP-type congestion controllers at the source, and Random Exponential Marking (REM) and Proportional Control (PC) schemes at the router. The behavior of Random Early Discard (RED) and Proportional-Integral (PI) control schemes at the router are also studied via simulations.

This paper introduces and analyzes a decentralized network congestion control algorithm which has dynamic adaptations at both user ends and link ends, a so-called general primal-dual algorithm. We obtain sufficient conditions for local stability of this algorithm in a general topology network with heterogeneous round-trip delays. Then, as an implementation of this algorithm in the Internet, we introduce an AQM (Active Queue Management) scheme called Exponential-RED (E-RED), which outperforms RED and is inherently stable when combined with TCP-Reno or its variants for high-speed networks.

A zero-sum mutual information game on MIMO Gaussian Rayleigh fading channels is considered in this paper. The players are an encoder-decoder pair as the maximizer, and a jammer as the minimizer, of the mutual information between the input and the output of the channel. There are total power constraints on both the jammer and the encoder. Also, the jammer has access to the encoder output. We find the unique saddle point of this game, and prove the somewhat surprising result that the knowledge of the channel input is useless to the jammer.

The fundamental tradeoff between bandwidth and rate for wideband additive Gaussian channels, when there is a constraint in the error exponent is investigated in the previous paper. This paper extends these results to fading channels. Specifically, we consider fading channels with large coherent dimension D. which is the defined to be the product of coherent time and coherent bandwidth. The behavior of R/sub z/(1/D) which is the maximum rate at which one can communicate when the coherent dimension is D and the error exponent is constrained to be at least equal to z is considered and calculates two quantities: R/sub z/(0) and R/spl dot//sub z/(0), which together partially characterize the behavior of R/sub z/(1/D) when D is large. We show that QPSK is near-optimal for fading channels with large coherent dimension, in the sense that both R/sub z/(0) and R/spl dot//sub z/(0) can be achieved.

In this paper, a channel which is subject to multipath fading, by considering a doubly block fading model is presented. The performance of the channels with large coherence dimension and the receiver with the full knowledge of channel state information, which leads to a coherent fading model is studied. The calculations of the optimal values and the proof that QPSK is near optimal with the independent of the error-exponent constraint are proved.

We consider noncoherent MIMO fading channels and characterize the reliability function in the low-SNR regime as a function of the number of transmit and receive antennas. We assume no CSI is available at the transmitter or the receiver. For the case when the fading matrix H has independent entries, we show that the number of transmit antennas plays a key role in reducing the peakiness in the input signal required to achieve the optimal error exponent for a given communication rate. Further, by considering a correlated channel model, we show that the maximum performance gain (in terms of the error exponent and communication rate) is achieved when the entries of the channel fading matrix are fully correlated.

In this paper, we study the connectivity properties of a wireless sensor network from an information-theoretic viewpoint. We consider both regular linear (one-dimensional) and planar (two-dimensional) networks with unreliable sensor nodes, i.e., each node is inactive/dead with a certain probability. We study the following problems: 1) what is the fundamental limit on the data rate that such a network can support for a single sensor node to the destination under transmission power and network-topology constraints? 2) What are the constraints on the network topology such that any (single) sensor can communicate with the destination at a desired rate? For problem 1), we provide upper and lower bounds on the achievable data rate, and for problem 2), we provide upper and lower bounds on the distance between the nodes required for communication at the desired rate.

In this paper, we develop simple models to study the performance of BitTorrent, a second generation peer-to-peer (P2P) application. We first present a simple fluid model and study the scalability, performance and efficiency of such a file-sharing mechanism. We then consider the built-in incentive mechanism of BitTorrent and study its effect on network performance. We also provide numerical results based on both simulations and real traces obtained from the Internet.

Mathematical models of congestion control capture the congestion indication mechanism at the router in two different ways: rate-based models, where the queue-length at the router does not explicitly appear in the model, and queue-based models, where the queue length at the router is explicitly a part of the model. Even though most congestion indication mechanisms use the queue length to compute the packet marking or dropping probability to indicate congestion, we argue that, depending upon the choice of the parameters of the AQM scheme, one would obtain a rate-based model or a rate-and-queue-based model as the deterministic limit of a stochastic system with a large number of users. We also consider the impact of implementing AQM schemes in the real queue or a virtual queue. If an AQM scheme is implemented in a real queue, we show that, to ensure that the queuing delays are negligible compared to RTTs, one is forced to choose the parameters of a AQM scheme in a manner which yields a rate-based deterministic model. On the other hand, if the AQM scheme is implemented in a virtual queue, small-queue operation is achieved independent of the choice of the parameters, thus showing a robustness property of virtual queue-based schemes.

We consider a zero-sum mutual information game on multiple-input multiple-output (MIMO) Gaussian Rayleigh-fading channels. The players are an encoder-decoder pair as the maximizer, and a jammer as the minimizer, of the mutual information between the input and the output of the channel. There are total power constraints on both the jammer and the encoder. Also, the jammer has access to the encoder output. We find the unique saddle point of this game, and prove the somewhat surprising result that the knowledge of the channel input is useless to the jammer.

Congestion control algorithms used in the Internet are difficult to analyze or simulate on a large scale, i.e., when there are large numbers of nodes, links, and sources in a network. The reasons for this include the complexity of the actual implementation of the algorithm and the randomness introduced in the packet arrival and service processes due to many factors such as arrivals and departures of sources and uncontrollable short flows in the network. To make the analysis or simulation tractable, often deterministic fluid approximations of these algorithms are used. These approximations are in the form of either deterministic delay differential equations, or more generally, deterministic functional-differential equations (FDEs). In this paper, we ignore the complexity introduced by the window-based implementation of such algorithms and focus on the randomness in the network. We justify the use of deterministic models for proportionally-fair congestion controllers under a limiting regime where the number of flows in a network is large.

We consider the problem of congestion control in networks which support both multirate multicast sessions and unicast sessions. We present a decentralized algorithm which enables the different rate-adaptive receivers in different multicast sessions to adjust their rates to satisfy some fairness criterion. A one-bit ECN marking strategy to be used at the nodes is also proposed. The congestion-control mechanism does not require any per-flow state information for unicast flows at the nodes. At junctions nodes of each multicast tree, some state information about the rates along the branches at the node may be required. The congestion-control mechanism takes into account the diverse user requirements when different receivers within a multicast session have different utility functions, but does not require the network to have any knowledge about the receiver utility functions.

Virtual queue-based marking schemes have been recently proposed for Active Queue Management (AQM) in Internet routers. We consider a particular scheme, which we call the Adaptive Virtual Queue (AVQ), and study its following properties: its stability in the presence of feedback delays, its ability to maintain small queue lengths, and its robustness in the presence of extremely short flows (the so-called web mice). Using a linearized model of the system dynamics, we present a simple rule to design the parameters of the AVQ algorithm. We then compare its performance through simulation with several well-known AQM schemes such as RED, REM, Proportional Integral (PI) controller, and a nonadaptive virtual queue algorithm. With a view toward implementation, we show that AVQ can be implemented as a simple token bucket using only a few lines of code.

In this paper, we will investigate the fundamental tradeoff between bandwidth and rate for a coherent fading channel in the wideband regime, when a constraint on the error exponent is imposed. In an earlier paper (X. Wu, et al., (2003)), we computed optimal values of R(0) and R/spl dot/(0) for a nonfading channel, where R(/spl middot/) is the maximum rate at which information can be transmitted as a function of the inverse of bandwidth B, given a lower bound on the error exponent. Based on this calculation, we defined an input distribution to be near-optimal or second-order optimal if both optimal values for R(0) and R/spl dot/(0) can be achieved. In this paper, we extend this result to coherent fading channels. We show that, although both BPSK and QPSK are first-order optimal, only QPSK is second-order optimal.

With the rapid growth of Internet, parameter design and analysis for large-scale networks has become a topic of active interest. Since simulation of such large scale systems is not easy, deterministic fluid models have been widely used for both qualitative understanding of the behavior, as well as parameter design for such networks. In this paper, we first study a deterministic fluid model for Internet congestion control when there are multiple TCP-like flows present. We provide conditions under which such a system is globally asymptotically stable in the presence of feedback delay. We then study the corresponding system with the addition of web mice and other nonresponsive flows modeled as stochastic disturbances. We show that, when there are a large number of flows, choosing parameters based on the global stability criterion for the deterministic system (with the noise replaced by its mean value) ensures global stability for the stochastic system as well. Numerical examples and simulation results with some popular active queue management mechanisms validate the parameter choices from analysis. The results indicate that a system with multiple TCP-like flows is globally stable as long as the bandwidth-delay product per flow is not very small.

We consider an unreliable wireless sensor grid-network with n nodes placed in a square of unit area. We are interested in the coverage of the region and the connectivity of the network. We first show that the necessary and sufficient conditions for the random grid network to cover the unit square region as well as ensure that the active nodes are connected are of the form p(n)r2(n) ~ log(n)/n, where r(n) is the transmission radius of each node and p(n) is the probability that a node is "active" (not failed). This result indicates that, when n is large, even if each node is highly unreliable and the transmission power is small, we can still maintain connectivity with coverage. We also show that the diameter of the random grid (i.e., the maximum number of hops required to travel from any active node to another) is of the order √{n/log(n)}. Finally, we derive a sufficient condition for connectivity of the active nodes (without necessarily having coverage). If the node success probability p(n) is small enough, we show that connectivity does not imply coverage.

We present a framework for designing end-to-end congestion control schemes in a network where each user may have a different utility function and may experience noncongestion-related losses. We first show that there exists an additive-increase-multiplicative-decrease scheme using only end-to-end measurable losses such that a socially optimal solution can be reached. We incorporate round-trip delay in this model, and show that one can generalize observations regarding TCP-type congestion avoidance to more general window flow control schemes. We then consider explicit congestion notification (ECN) as an alternate mechanism (instead of losses) for signaling congestion and show that ECN marking levels can be designed to nearly eliminate losses in the network by choosing the marking level independently for each node in the network. While the ECN marking level at each node may depend on the number of flows through the node, the appropriate marking level can be estimated using only aggregate flow measurements, i.e., per-flow measurements are not required.

We consider decentralized congestion control algorithms for low-loss operation of the Internet using the ECN bit. There has been much analysis of such algorithms, but with a few exceptions, these typically ignore the effect of feedback delays in the network on stability. We study a single node with many flows passing through it, with each flow (possibly) having a different round-trip delay. Using a fluid model for the flows, we show that even with delays, the total data rate at the router is bounded; and this bound shows that the (peak) total rate grows linearly with increase in system size, i.e., the fraction of overprovisioning required is constant with respect to N, the number of flows in the system. Further, for typical user data rates and delays seen in the Internet today, the bound is very close to the data rate at the router without delays. Earlier results by Johari and Tan have given conditions for a linearized model of the network to be (locally) stable. We show that even when the linearized model is not stable, the nonlinear model is upper bounded, i.e., the total rate at the bottleneck link is upper bounded, and the upper bound is close to the equilibrium rate for TCP.

We consider a network where each user is charged a fixed price per unit of bandwidth used, but where there is no congestion-dependent pricing. However, the transmission rate of each user is assumed to be a function of network congestion (like TCP), and the price per unit bandwidth. We are interested in answering the following question: how should the network choose the price to maximize its overall revenue? To obtain a tractable solution, we consider a single link accessed by many users where the capacity is increased in proportion to the number of users. We show the following result: as the number of users increases, the optimal price per unit bandwidth charged by the service provider may increase or decrease depending upon the bandwidth of the link. However, for all values of the link capacity, the service provider's revenue per unit bandwidth increases and the overall performance of each user (measured in terms of a function of its throughput, the network congestion and the cost incurred by the user for bandwidth usage) improves. Since the revenue per unit bandwidth increases, it provides an incentive for the service provider to increase the available bandwidth in proportion to the number of users.

Congestion control algorithms used in the Internet are difficult to analyze or simulate on a large scale, i.e., when there are large numbers of nodes, links and sources in a network. The reasons for this include the complexity of the actual implementation of the algorithm and the randomness introduced in the packet arrival and service processes due to many factors such as arrivals and departures of sources and uncontrollable short flows in the network. To make the simulation tractable, often deterministic fluid model approximations of these algorithms are used. These approximations are in the form of either deterministic delay differential equations, or more generally, deterministic functional differential equations. We justify the use of deterministic models for proportionally fair congestion controllers under a limiting regime where the number of sources in a network is large. We verify our results through simulations of window-based implementations of proportionally fair controllers and TCP.

Fair resource allocation in high-speed networks such as the Internet can be viewed as a constrained optimization program. Kelly and his co-workers have shown that an unconstrained penalty function formulation of this problem can be used to design congestion controllers that are stable. In this paper, we examine the question of providing feedback from the network such that the congestion controllers derived from the penalty function formulation lead to the solution of the original unconstrained problem. This can be viewed as the decentralized design of early congestion notification (ECN) marking rates at each node in the Internet to ensure global loss-free operation of a fluid model of the network. We then look at the stability of such a scheme using a time-scale decomposition of the system. This results in two separate systems which are stable individually and we show that under certain assumptions the entire system is semi-globally stable and converges to the equilibrium point exponentially fast.

Virtual Queue-based marking schemes have been recently proposed for AQM (Active Queue Management) in Internet routers. We consider a particular scheme, which we call the Adaptive Virtual Queue (AVQ), and study its following properties: stability in the presence of feedback delays, its ability to maintain small queue lengths and its robustness in the presence of extremely short flows (the so-called web mice). Using a mathematical tool motivated by the earlier work of Hollot et al, we present a simple rule to design the parameters of the AVQ algorithm. We then compare its performance through simulation with several well-known AQM schemes such as RED, REM, PI controller and a non-adaptive virtual queue algorithm. With a view towards implementation, we show that AVQ can be implemented as a simple token bucket using only a few lines of code.

Fair resource allocation in high-speed networks such as the Internet can be viewed as a constrained convex program. Kelly, Maulloo and Tan (see Journal of the Operational Research Society, vol.49, p.237-52, 1998) have shown that an unconstrained penalty function formulation of this problem can be used to design congestion controllers that are stable. We examine the question of providing feedback from the network such that the congestion controllers derived from the penalty function formulation lead to the solution of the original unconstrained problem. This can be viewed as the decentralized design of early congestion notification (ECN) marking rates at each node in the Internet to ensure global loss-free, socially-optimal operation of a fluid model of the network.

We present a novel ABR congestion control algorithm which is adaptive to changing network conditions and robust to network delays. The algorithm is easy to implement, as it only requires a single design parameter, and no centralized knowledge about the status of the network. Further, max-min fairness and queue length stability under minimum cell rate (MCR) and peak cell rate (PCR) constraints are automatically achieved.

We present a framework for designing end-to-end congestion control schemes in a network where each user may have a different utility function. We first show that there exists an additive increase-multiplicative decrease scheme using only end-to-end measurable losses such that a socially-optimal solution can be reached. We incorporate non-congestion-related random losses and round-trip delay in this model, and show that one can generalize observations regarding TCP-type congestion avoidance to more general window flow control schemes. We then consider explicit congestion notification (ECN) as an alternate mechanism (instead of losses) for signaling congestion and show that ECN marking levels can be designed to nearly eliminate losses in the network by choosing the marking level independently for each node in the network. While the ECN marking level at each node may depend on the number of flows through the node, the appropriate marking level can be estimated using only aggregate flow measurements, i.e., per-flow measurements are not required.

In this paper, we study discrete-time priority queueing systems fed by a large number of arrival streams. We first provide bounds on the actual delay asymptote in terms of the virtual delay asymptote. Then, under suitable assumptions on the arrival process to the queue, we show that these asymptotes are the same. We then consider a priority queueing system with two queues. Using the earlier result, we derive an upper bound on the tail probability of the delay. Under certain assumptions on the rate function of the arrival process, we show that the upper bound is tight. We then consider a system with Markovian arrivals and numerically evaluate the delay tail probability and validate these results with simulations.

We propose competitive policies for admission control and routing in general topology networks, with bandwidth and buffer resources. The goal of these solutions is to maximize the network revenue, when the traffic demand is not known ahead of time, and over-allocation of network resources is allowed with some probability. On top of appropriate resource reservation setup protocols, these solutions provide statistical service while optimizing the profit of the network operator.

We consider the problem of obtaining non-trivial lower bounds on the the lost revenue under any routing and admission control scheme in a multi-class loss network. First, we use the following simple idea to bound the performance of any coordinate-convex admission policy on a single link: the blocking probability of any call class is lower bounded by considering just this class in isolation and replacing the available bandwidth (a random quantity) by its mean. Then, following the methods of Kelly (1994) and Gibbens and Kelly (see IEEE Journal on Selected Areas in Communications, p.100-10, 1995), we use this single link bound to obtain linear programs which give bounds in the case of sparsely-connected networks with multiple bandwidth classes and alternate routing.

We consider single-hop wavelength-division multiplexed networks in which the transmitters take a nonzero amount of time, called tuning latency, to tune from one wavelength to another. For such networks, we show that, under certain conditions on the traffic matrix, there exist polynomial-time algorithms that produce the optimal schedule. Further, the tuning latency is masked in the length of the optimal schedule. Using Chernoff-Hoeffding bounds, we show that the condition on the traffic matrix is satisfied with high probability when the wavelength reuse factor is large, i.e., the number of nodes is large compared to the number of wavelengths. Simulation results show the dramatic improvement in the performance of the network using our algorithm as compared with other heuristics.

In order to provide an adequate quality of service to large-bandwidth calls, such as video conference calls, service providers of integrated services networks may want to allow some customers to book their calls ahead, i.e., make advance reservations. We propose a scheme for sharing resources among book-ahead (BA) calls (that announce their call holding times as well as their call initiation times upon arrival) and non-BA calls (that do not announce their holding times). It is possible to share resources without allowing any calls in progress to be interrupted, but in order to achieve a more efficient use of resources, we think that it may be desirable to occasionally allow a call in progress to be interrupted. (In practice, it may be possible to substitute service degradation, such as bit dropping or coarser encoding of video, for interruption.) Thus, we propose an admission control algorithm in which a call is admitted if an approximate interrupt probability (computed in real time) is below a threshold. Simulation experiments show that the proposed admission control algorithm can be better (i.e., yield higher total utilization or higher revenue) than alternative schemes that do not allow interruption, such as a strict partitioning of resources.

Fair scheduling of delay and rate-sensitive packet flows over a wireless channel is not addressed effectively by most contemporary wireline fair-scheduling algorithms because of two unique characteristics of wireless media: (1) bursty channel errors and (2) location-dependent channel capacity and errors. Besides, in packet cellular networks, the base station typically performs the task of packet scheduling for both downlink and uplink flows in a cell; however, a base station has only a limited knowledge of the arrival processes of uplink flows. We propose a new model for wireless fair-scheduling based on an adaptation of fluid fair queueing (FFQ) to handle location-dependent error bursts. We describe an ideal wireless fair-scheduling algorithm which provides a packetized implementation of the fluid mode, while assuming full knowledge of the current channel conditions. For this algorithm, we derive the worst-case throughput and delay bounds. Finally, we describe a practical wireless scheduling algorithm which approximates the ideal algorithm. Through simulations, we show that the algorithm achieves the desirable properties identified in the wireless FFQ model.

The paper considers the design of explicit rate-based flow control for available bit rate (ABR) sources in an ATM network. The goal is to share the available capacity "fairly" among many sources while maintaining queue length at a bottleneck node at a desired level. This problem is formulated as a stochastic control problem, and in this framework rate-control mechanisms are developed, which stabilize the queue length even though different sources may have different round-trip delays to the bottleneck node. Various robustness properties of the solution are illustrated through simulation experiments.

Fair scheduling of delay and rate-sensitive packet flows over a wireless channel is not addressed effectively by most contemporary wireline fair scheduling algorithms because of two unique characteristics of wireless media: (a) bursty channel errors, and (b) location-dependent channel capacity and errors. Besides, in packet cellular networks, the base station typically performs the task of packet scheduling for both downlink and uplink flows in a cell; however a base station has only a limited knowledge of the arrival processes of uplink flows.In this paper, we propose a new model for wireless fair scheduling based on an adaptation of fluid fair queueing to handle location-dependent error bursts. We describe an ideal wireless fair scheduling algorithm which provides a packetized implementation of the fluid model while assuming full knowledge of the current channel conditions. For this algorithm, we derive the worst-case throughput and delay bounds. Finally, we describe a practical wireless scheduling algorithm which approximates the ideal algorithm. Through simulations, we show that the algorithm achieves the desirable properties identified in the wireless fluid fair queueing model.

Computational techniques are presented for the connection-level performance evaluation of communication networks, with stochastic multirate traffic, state-dependent admission control, alternate routing, and general topology-all characteristics of emerging integrated service networks. The techniques involve solutions of systems of fixed-point equations, which estimate equilibrium network behaviour. Although similar techniques have been applied with success to single-rate fully connected networks, the curse of dimensionality arises when the techniques are extended to multirate, multihop networks, and the cost of solving the fixed point equations exactly is exponential. This exponential barrier is skirted by exploiting, in particular, a close relationship with the network reliability problem, and by borrowing effective heuristics from the reliability domain. A series of experiments are reported on, comparing the estimates from the new techniques to the results of discrete-event simulations.

Computational techniques are presented for connection-level performance evaluation of communication networks, with stochastic multirate traffic, state dependent admission control, alternate routing, and general topology --- all characteristics of emerging integrated service networks. The techniques involve solutions of systems of fixed point equations, which estimate equilibrium network behavior. Though similar techniques have been applied with success to single-rate fully connected networks, the curse of dimensionality arises when the techniques are extended to multirate, multihop networks, and the cost of solving the fixed point equations exactly is exponential. This exponential barrier is skirted by exploiting, in particular, a close relationship with the network reliability problem, and by borrowing effective heuristics from the reliability domain. A series of experiments are reported on, comparing the estimates from the new techniques to the results of discrete event simulations.