Selecting the right monitoring level in Remote Patient Monitoring (RPM) systems for e-healthcare is crucial for balancing patient outcomes, various resources, and patient's quality of life. A prior work has used one-dimensional health representations, but patient health is inherently multidimensional and typically consists of many measurable physiological factors. In this paper, we introduce a multidimensional health state model within the RPM framework and use dynamic programming to study optimal monitoring strategies. Our analysis reveals that the optimal control is characterized by switching curves (for two-dimensional health states) or switching hyper-surfaces (in general): patients switch to intensive monitoring when health measurements cross a specific multidimensional surface. We further study how the optimal switching curve varies for different medical conditions and model parameters. This finding of the optimal control structure provides actionable insights for clinicians and aids in resource planning. The tunable modeling framework enhances the applicability and effectiveness of RPM services across various medical conditions.

In this paper, we examine the convergence landscape of multi-agent learning under uncertainty. Specifically, we analyze two stochastic models of regularized learning in continuous games—one in continuous and one in discrete time—with the aim of characterizing the long run behavior of the induced sequence of play. In stark contrast to deterministic, full-information models of learning (or models with a vanishing learning rate), we show that the resulting dynamics do not converge in general. In lieu of this, we ask instead which actions are played more often in the long run, and by how much. We show that, in strongly monotone games, the dynamics of regularized learning may wander away from equilibrium infinitely often, but they always return to its vicinity in finite time (which we estimate), and their long-run distribution is sharply concentrated around a neighborhood thereof. We quantify the degree of this concentration, and we show that these favorable properties may all break down if the underlying game is not strongly monotone—underscoring in this way the limits of regularized learning in the presence of persistent randomness and uncertainty

In this paper, we examine the robustness of Nash equilibria in continuous games, under both strategic and dynamic uncertainty. Starting with the former, we introduce the notion of a robust equilibrium as those equilibria that remain invariant to small—but otherwise arbitrary—perturbations to the game’s payoff structure, and we provide a crisp geometric characterization thereof. Subsequently, we turn to the question of dynamic robustness, and we examine which equilibria may arise as stable limit points of the dynamics of “follow the regularized leader” (FTRL) in the presence of randomness and uncertainty. Despite their very distinct origins, we establish a structural correspondence between these two notions of robustness: strategic robustness implies dynamic robustness, and, conversely, the requirement of strategic robustness cannot be relaxed if dynamic robustness is to be maintained. Finally, we examine the rate of convergence to robust equilibria as a function of the underlying regularizer, and we show that entropically regularized learning converges at a geometric rate in games with affinely constrained action spaces.

We develop a remote patient monitoring (RPM) service architecture, which has two tiers of monitoring: ordinary and intensive. The patient's health state improves or worsens in each time period according to certain probabilities, which depend on the monitoring tier. The patient incurs a "loss of quality of life" cost or an "invasiveness" cost, which is higher under intensive monitoring than under ordinary. On the other hand, their health improves faster under intensive monitoring than under ordinary. In each period, the service decides which monitoring tier to use, based on the health of the patient. We investigate the optimal policy for making that choice by formulating the problem using dynamic programming. We first provide analytic conditions for selecting ordinary vs intensive monitoring in the asymptotic regime where the number of health states is large. In the general case, we investigate the optimal policy numerically. We observe a threshold behavior, that is, when the patient's health drops below a certain threshold the service switches them to intensive monitoring, while ordinary monitoring is used during adequately good health states of the patient. The modeling and analysis provides a general framework for managing RPM services for various health conditions with medically/clinically defined system parameters.

Data centers increasingly consume large amounts of power. In this paper, we develop an efficient and scalable power management scheme, based on optimizing the tradeoff between a processor's speed and its response/delay time to process jobs. Processors/servers are lightly coordinated by a system manager that sets an internal power “price” signal to discourage excessive power usage. The stability of the power management scheme depends on the power pricing function, and a rule of thumb is given for pricing functions that guarantee stability. The analysis is consistent with simulations, which demonstrate the behavior of the scheme. It can be implemented in a decentralized manner across servers/processors, making it scalable to large data centers.

Motivated by the success of Nesterov's accelerated gradient algorithm for convex minimization problems, we examine whether it is possible to achieve similar performance gains in the context of online learning in games. To that end, we introduce a family of accelerated learning methods, which we call “follow the accelerated leader” (FTXL), and which incorporates the use of momentum within the general framework of regularized learning - and, in particular, the exponential / multiplicative weights algorithm and its variants. Drawing inspiration and techniques from the continuous-time analysis of Nesterov's algorithm, we show that FTXL converges locally to strict Nash equilibria at a superlinear rate, achieving in this way an exponential speed-up over vanilla regularized learning methods (which, by comparison, converge to strict equilibria at a geometric, linear rate). Importantly, the FTXL maintains its superlinear convergence rate in a broad range of feedback structures, from deterministic, full information models to stochastic, realization-based ones, and even bandit, payoff-based information, where players are only able to observe their individual realized payoffs.

Consider N devices that transmit packets for T time slots, where device n uses transmission power$P_{n}\left ({{t}}\right)$at time slot t. Independently at each time slot, a packet arrives at device n with probability$\lambda _{n}$. The probability of successfully transmitting a packet$\mu _{n}\left ({{\boldsymbol {P}}}\right)$is a function of the transmission powers of all devices$\boldsymbol {P}$and the channel gains$\left \{{{ g_{m,n}}}\right \} $between them. This function is unknown to the devices that only observe binary reward$r_{n}\left ({{\boldsymbol {P}}}\right)$of whether the transmission was successful (ACK/NACK). All packets of device n that were not successfully transmitted yet at time slot t wait in a queue$Q_{n}\left ({{t}}\right)$. The centralized max-weight scheduling (MWS) can stabilize the queues for any feasible$\boldsymbol {\lambda }$(i.e., throughput optimality). However, MWS for power control is intractable even as a centralized algorithm, let alone in a distributed network. We design a distributed yet asymptotically throughput optimal power control for the wireless interference channel, which has long been recognized as a major challenge. Our main observation is that the interference$I_{n}\left ({{t}}\right)=\sum g_{m,n}^{2}P_{m}\left ({{t}}\right)$can be leveraged to evaluate the weighted throughput if we add a short pilot signal with power$P_{m}\propto Q_{m}\left ({{t}}\right)r_{m}\left ({{\boldsymbol {P}}}\right)$after transmitting the data. Our algorithm requires no explicit communication between the devices and learns to approximate MWS, overcoming its intractable optimization and the unknown throughput functions. We prove that, for large T, our algorithm can achieve any feasible$\boldsymbol {\lambda }$. Numerical experiments show that our algorithm outperforms the state-of-the-art distributed power control, exhibiting better performance than our theoretical bounds.

We focus on robust estimation of the unobserved state of a discrete-time stochastic system with linear dynamics. A standard analysis of this estimation problem assumes a baseline innovation model; with Gaussian innovations we recover the Kalman filter. However, in many settings, there is insufficient or corrupted data to validate the baseline model. To cope with this problem, we minimize the worst-case mean-squared estimation error of adversarial models chosen within a Wasserstein neighborhood around the baseline. We also constrain the adversarial innovations to form a martingale difference sequence. The martingale constraint relaxes the i.i.d. assumptions which are often imposed on the baseline model. Moreover, we show that the martingale constraints guarantee that the adversarial dynamics remain adapted to the natural time-generated information. Therefore, adding the martingale constraint allows to improve upon over-conservative policies that also protect against unrealistic omniscient adversaries. We establish a strong duality result which we use to develop an efficient subgradient method to compute the distributionally robust estimation policy. If the baseline innovations are Gaussian, we show that the worst-case adversary remains Gaussian. Our numerical experiments indicate that the martingale constraint may also aid in adding a layer of robustness in the choice of the adversarial power.

In this paper, we study the problem of learning in quantum games - and other classes of semidefinite games - with scalar, payoff-based feedback. For concreteness, we focus on the widely used matrix multiplicative weights (MMW) algorithm and, instead of requiring players to have full knowledge of the game (and/or each other's chosen states), we introduce a suite of minimal-information matrix multiplicative weights (3MW) methods tailored to different information frameworks. The main difficulty to attaining convergence in this setting is that, in contrast to classical finite games, quantum games have an infinite continuum of pure states (the quantum equivalent of pure strategies), so standard importance-weighting techniques for estimating payoff vectors cannot be employed. Instead, we borrow ideas from bandit convex optimization and we design a zeroth-order gradient sampler adapted to the semidefinite geometry of the problem at hand. As a first result, we show that the 3MW method with deterministic payoff feedback retains the $\mathcal{O}(1/\sqrt{T})$ convergence rate of the vanilla, full information MMW algorithm in quantum min-max games, even though the players only observe a single scalar. Subsequently, we relax the algorithm's information requirements even further and we provide a 3MW method that only requires players to observe a random realization of their payoff observable, and converges to equilibrium at an $\mathcal{O}(T^{-1/4})$ rate. Finally, going beyond zero-sum games, we show that a regularized variant of the proposed 3MW method guarantees local convergence with high probability to all equilibria that satisfy a certain first-order stability condition.

Queue-processor service and communication switches are often reconfigured in data centers to dynamically reallocate resources based on demand and maximize utilization. However, reconfiguration introduces overhead that will reduce the usable processor bandwidth if done too frequently. We introduce a cost framework to determine how frequently such reconfigurations should occur in order to optimally trade off between the cost of the reconfiguration (or context switching) overhead and the latency cost due to the delayed reconfiguration. A general framing algorithm is introduced to optimize dynamic processor allocation that limits processors to only be reallocated at the beginning of a new frame, but allows a class of functions of the historical backlog to be employed when selecting the new allocation. We show that the system throughput is not affected by framing, however, the job latency increases with the frame's span. The cost model and framed allocation algorithm are investigated to determine how to balance a tolerable increase in job latency for significant reduction of system overhead due to processor reconfiguration.

Predicting whether a patient will have a prolonged length of stay (LoS) once admitted to a hospital can help ensure medical resources are allocated to where they are needed most. However, prior works on classifying prolonged-LoS patients define a prolonged-LoS as being greater than a single, flat number-of-days cutoff. Using a flat cutoff, means that the classification occurs without reference to a baseline LoS, fails to control for any covariates, and is generally only effective for a specific medical subgroup. Instead, in this work, we introduce an approach where the algorithm designer specifies a LoS percentile that should be used as the cutoff for prolonged-LoS. In a method known as weak-supervision, we use the LoS percentile cutoff to train a model to produce the actual labels for classification machine learning training. Contrary to a number-of-days cutoff, the LoS percentile cutoff coupled with weak-supervision, provides what we claim is a more principled and flexible approach to defining what constitutes a prolonged-LoS.Specifically, we train a quantile regression model to predict the designated LoS percentile value for each patient, which importantly allows us to control for covariates that access to medical care should be equalized across (such as primary medical condition, hospital facility, and admission time of day). The regression output is cast as a noisy binary label for prolonged-LoS, which is then used to train a machine learning model for prolonged-LoS classification. We empirically demonstrate that this weak-supervision based approach provides usable classification performance despite using noisy labels.

Identifying disease carriers is a key barrier to effectively control an epidemic outbreak, especially when many carriers are asymptomatic, have minor symptoms, or have a delayed symptom onset. Current isolation policies largely operate at the two ends of the spectrum: isolate almost everyone (lock-down) or isolate only those with severe symptoms. This leads to high misclassification costs. To address this issue, we develop an active learning approach. Active learning is useful when labeling is expensive and there is a limited budget; an active learning algorithm selects which data points to label in order to build the best training dataset for machine learning. We present the novel Active Testing protocol to combine 1) an online, disease-carrier classification model trained on symptom data paired with 2) an active learning based disease testing policy, that results in lower misclassification costs than either of the two extreme isolation policies. Coupling these two components enables our protocol to pick the best testing kit allocation policy to train the carrier classification model and minimize the total decision-theoretic, isolation misclassification cost. We accomplish this with a novel, cost-aware active learning algorithm, and demonstrate its effectiveness compared to existing algorithms in the class-imbalanced setting of disease-carrier classification.

As compute demands soar upwards, it is essential that systems not only scale throughput and latency, but also improve energy efficiency and alleviate power bottlenecks. A common quality of service metric for user-facing data center services is slowdown, the ratio of the actual response time of a computational job to the expected response time under no delay. In this work, we expand the definition of slowdown to the power-controlled, rate-optimizing setting. We take the initial steps to investigate and analyze the key tradeoffs between power and slowdown costs. Formulating the problem in a dynamic programming framework, we provide analytic solutions in the single class job setting, and formulate the multi-class job setting. Numerical solutions to the dynamic programming equation are also produced, and confirm the analytical results and parameter tradeoffs. In particular, we demonstrate both analytically and numerically that reasonable tradeoffs can be made between power and slowdown by optimizing the server processing rate. Optimizing for power consumption is increasingly important as data centers’ tackle the transition to renewable energy sources.

Abstract Consider $N$ cooperative agents such that for $T$ turns, each agent n takes an action $a_{n}$ and receives a stochastic reward $r_{n}\left(a_{1},\ldots,a_{N}\right)$. Agents cannot observe the actions of other agents and do not know even their own reward function. The agents can communicate with their neighbors on a connected graph $G$ with diameter $d\left(G\right)$. We want each agent $n$ to achieve an expected average reward of at least $\lambda_{n}$ over time, for a given quality of service (QoS) vector $\boldsymbol{\lambda}$. A QoS vector $\boldsymbol{\lambda}$ is not necessarily achievable. By giving up on immediate reward, knowing that the other agents will compensate later, agents can improve their achievable capacity region. Our main observation is that the gap between $\lambda_{n}t$ and the accumulated reward of agent $n$, which we call the QoS regret, behaves like a queue. Inspired by this observation, we propose a distributed algorithm that aims to learn a max-weight matching of agents to actions. In each epoch, the algorithm employs a consensus phase where the agents agree on a certain weighted sum of rewards by communicating only $O\left(d\left(G\right)\right)$ numbers every turn. Then, the algorithm uses distributed successive elimination on a random subset of action profiles to approximately maximize this weighted sum of rewards. We prove a bound on the accumulated sum of expected QoS regrets of all agents, that holds if $\boldsymbol{\lambda}$ is a safety margin $\varepsilon_{T}$ away from the boundary of the capacity region, where $\varepsilon_{T}\rightarrow0$ as $T\rightarrow\infty$. This bound implies that, for large $T$, our algorithm can achieve any $\boldsymbol{\lambda}$ in the interior of the dynamic capacity region, while all agents are guaranteed an empirical average expected QoS regret of $\tilde{O}\left(1\right)$ over $t=1,\ldots,T$ which never exceeds $\tilde{O}\left(\sqrt{t}\right)$ for any $t$. We then extend our result to time-varying i.i.d. communication graphs.

Consider a scenario where a player chooses an action in each round $t$ out of $T$ rounds and observes the incurred cost after a delay of $d_{t}$ rounds. The cost functions and the delay sequence are chosen by an adversary. We show that in a non-cooperative game, the expected weighted ergodic distribution of play converges to the set of coarse correlated equilibria if players use algorithms that have “no weighted-regret” in the above scenario, even if they have linear regret due to too large delays. For a two-player zero-sum game, we show that no weighted-regret is sufficient for the weighted ergodic average of play to converge to the set of Nash equilibria. We prove that the FKM algorithm with $n$ dimensions achieves an expected regret of $O\left(nT^{\frac{3}{4}}+\sqrt{n}T^{\frac{1}{3}}D^{\frac{1}{3}}\right)$ and the EXP3 algorithm with $K$ arms achieves an expected regret of $O\left(\sqrt{\log K\left(KT+D\right)}\right)$ even when $D=\sum_{t=1}^{T}d_{t}$ and $T$ are unknown. These bounds use a novel doubling trick that, under mild assumptions, provably retains the regret bound for when $D$ and $T$ are known. Using these bounds, we show that FKM and EXP3 have no weighted-regret even for $d_{t}=O\left(t\log t\right)$. Therefore, algorithms with no weighted-regret can be used to approximate a CCE of a finite or convex unknown game that can only be simulated with bandit feedback, even if the simulation involves significant delays.

Consider N players that each uses a mixture of K resources. Each of the players’ reward functions includes a linear pricing term for each resource that is controlled by the game manager. We assume that the game is strongly monotone, so if each player runs gradient descent, the dynamics converge to a unique Nash equilibrium (NE). Unfortunately, this NE can be inefficient since the total load on a given resource can be very high. In principle, we can control the total loads by tuning the coefficients of the pricing terms. However, finding pricing coefficients that balance the loads requires knowing the players’ reward functions and their action sets. Obtaining this game structure information is infeasible in a large-scale network and violates the users’ privacy. To overcome this, we propose a simple algorithm that learns to shift the NE of the game to meet the total load constraints by adjusting the pricing coefficients in an online manner. Our algorithm only requires the total load per resource as feedback and does not need to know the reward functions or the action sets. We prove that our algorithm guarantees convergence in L2 to a NE that meets target total load constraints. Simulations show the effectiveness of our approach when applied to smart grid demand-side management or power control in wireless networks.

Accurate patient discharge time estimates are invaluable for hospital operations management. They are vital for efficient and effective scheduling of hospital resources including beds and staff. Unexpected discharges place strain on the patient families and care providers, in addition to causing hospital inefficiencies. Due to the increasing availability of electronic health record data, predictive models can be leveraged to not only offer clinical decision support, but also to optimize hospital operations. In this work, we incorporate clinical knowledge from operational leaders at Kaiser Perma-nente Northern California to design a predictive model for patient discharge using a novel dataset that contains hourly data from the electronic health records of 14 different Kaiser Permanente hospitals. We train and test several algorithms with varying complexity to predict patient-level discharges for the following day at operationally relevant times on the hospital-centric timescale. The highest AUC we achieve is 0.729 with a gradient boosted model, which significantly outperforms both the current estimates deployed in these 14 facilities and the baseline model without hourly data. A feature permutation importance assessment is performed and we conclude that the majority of the improvement is due to the inclusion of the detailed, hourly data.

Consider N cooperative but non-communicating players where each plays one out of M arms for T turns. Players have different utilities for each arm, representable as an NxM matrix. These utilities are unknown to the players. In each turn players receive noisy observations of their utility for their selected arm. However, if any other players selected the same arm that turn, they will all receive zero utility due to the conflict. No other communication or coordination between the players is possible. Our goal is to design a distributed algorithm that learns the matching between players and arms that achieves max-min fairness while minimizing the regret. We present an algorithm and prove that it is regret optimal up to a \log\log T factor. This is the first max-min fairness multi-player bandit algorithm with (near) order optimal regret.

Consider a team of cooperative players that take actions in a networked-environment. At each turn, each player chooses an action and receives a reward that is an unknown function of all the players' actions. The goal of the team of players is to learn to play together the action profile that maximizes the sum of their rewards. However, players cannot observe the actions or rewards of other players, and can only get this information by communicating with their neighbors. We design a distributed learning algorithm that overcomes the informational bias players have towards maximizing the rewards of nearby players they got more information about. We assume twice continuously differentiable reward functions and constrained convex and compact action sets. Our communication graph is a random time-varying graph that follows an ergodic Markov chain. We prove that even if at every turn players take actions based only on the small random subset of the players' rewards that they know, our algorithm converges with probability 1 to the set of stationary points of (projected) gradient ascent on the sum of rewards function. Hence, if the sum of rewards is concave, then the algorithm converges with probability 1 to the optimal action profile.

On-device learning promises collaborative training of machine learning models across edge devices without the sharing of user data. In state-of-the-art on-device learning algorithms, devices communicate their model weights over a decentralized communication network. Transmitting model weights requires huge communication overhead and means only devices with identical model architectures can be included. To overcome these limitations, we introduce a distributed distillation algorithm where devices communicate and learn from soft-decision (softmax) outputs, which are inherently architecture-agnostic and scale only with the number of classes. The communicated soft-decisions are each model's outputs on a public, unlabeled reference dataset, which serves as a common vocabulary between devices. We prove that our algorithm converges with probability 1 to a stationary point where all devices in the communication network distill the entire network's knowledge on the reference data, regardless of their local connections. Our analysis assumes smooth loss functions, which can be non-convex. Simulations support our theoretical findings and show that even a naive implementation of our algorithm significantly reduces the communication overhead while achieving an overall comparable performance to state-of-the-art, depending on the regime. By requiring little communication overhead and allowing for cross-architecture training, we remove two main obstacles to scaling on-device learning.

Consider an epidemic that propagates in a network of N individuals. The dynamics of the infection are governed by the N-intertwined SIR model, which is a non-linear model. Our goal is to prevent the epidemic by removing (vaccinating) nodes and removing (closing) links. Since vaccinating nodes and closing links are costly, we want to minimize this cost under the constraint of preventing the outbreak. We first show that preventing the outbreak can be guaranteed by ensuring that the maximal eigenvalue \lambda_{1} of a specific linear system is negative. This induces a well posed, but highly complex, combinatorial optimization problem. We propose a greedy algorithm that at each step picks the approximately best link to close or the best node to vaccinate, and proceeds to break the network until \lambda_{1}<; 0. We prove that running our algorithm on a coarser and smaller graph of regions, as opposed to individuals, still guarantees that the epidemic is prevented in the large network of size N. We tested our algorithm on an N-intertwined SIR model that was calibrated using real data that includes measles outbreaks and contact frequencies. The contact network was generated based on raw cellular localization data of 17 billion records from Radio Network Controllers that cover 1.8 million users over 2 months. Our encouraging results demonstrate that algorithms that consider the topology of the network can offer great value even in practical scenarios, where the decisions and computations can only be made on the regional level.

High-frequency identification of a patient's hypotensive state allows for early notification of adverse events and long-term trends. Risks of complications such as heart attack, acute kidney injury, and mortality increase with duration of hypotension during surgery, and a hypotensive state can affect the appropriate medication choices and dosages for congestive heart failure patients. Current methods for identifying hypotension are based on blood pressure cuff measurements, which are low-frequency and must be manually collected, or catheterized blood pressure sensors, which are invasive, painful, and not necessarily usable for the youngest and smallest neonatal patients. This paper explores the potential of replacing the high-frequency hypotensive state produced by the invasive arterial catheter with a high-frequency projection from a fusion of multiple noninvasive sensors. These noninvasive sensors are available for a large majority of hospital patients, and have a lower risk of adverse effects ranging from patient discomfort to site infection. In addition, using multiple sensor inputs and a robust model allows for higher-reliability identification than single-sensor architectures. Our results demonstrate that by using a single flexible convolutional-deconvolutional neural network architecture, a patient's hypotensive state may be reconstructed from any combination of the input sensor channels, with fidelity increasing in the number of available inputs.

Consider a distributed network with N devices and K channels. Each device chooses a single channel and controls its transmission power on that channel. Our goal is to minimize the total transmission power while maintaining reliable communication between devices. Minimizing the total power consumption involves both the combinatorial optimization aspect of assigning channels to devices and the continuous optimization aspect of finding the optimal transmission powers. We present a distributed algorithm that solves the multichannel power control problem, and prove that it converges to the optimal solution. The algorithm is based on exploring new channel allocations by trial and error and running the best-response power control algorithm on the explored channel allocation. Using a novel wireless consensus phase, where devices use their transmission power as a consensus variable, all devices learn if the explored allocation is better than the current one. If the new allocation is better, all devices start using this allocation until the next trial and error. Finally, we provide simulations that support our analytical findings.

We consider a microgrid that consists of N providers and B consumers. Each provider has a certain supply and each consumer has a certain demand. The efficiency of transmitting energy between providers and consumers is modeled using a bipartite graph G. Our goal is to maximize the amount of utilized energy using a distributed algorithm that each provider runs locally. We propose a non-cooperative energy allocation game, and adopt the best-response dynamics for this game as our distributed algorithm. We prove that the best-response dynamics converge in no more than N steps to one of at most N! pure Nash equilibria of our game. Despite the fact that some of these Nash equilibria are suboptimal, we are able to prove that our algorithm achieves near-optimal performance in “almost all” games. We do so by analyzing the best-response dynamics in a random game, where the network is generated using a random model for the graph G. We prove that the ratio between the utilized energy of our algorithm and that of the optimal solution converges to one in probability as B increases (and N is any function of B). Using numerical simulations, we demonstrate that our asymptotic analysis is valid even for B = 10 consumers.

We consider the use of a wireless body area network (WBAN) for remote health monitoring applications. A partially observable Markov decision process is used to describe the information flow and behavior of the WBAN. We then discuss a sensor activation policy, used for optimizing the tradeoff between power consumption and probability of patient health state misclassification. In order to determine the underlying health state transition probabilities, by which a patient's health state evolves, we develop a learning algorithm which uses the data collected from a group of patients, each being monitored by a WBAN. Finally, a numerical examination demonstrates the applicability of such a system, which applies the learning process and sensor activation policy simultaneously.

Anesthesiologists are currently assigned to surgeries based primarily on anesthesiologist availability and specialty, but optimizing anesthesia time is not generally considered. If certain anesthesiologists perform faster on different patient or surgical cohorts, then incorporating patient-specific and surgery-specific features in scheduling decisions could reduce anesthesia time, and therefore improve operating room efficiency. We formulate the problem of assigning anesthesiologists to surgeries as a policy learning problem. We use random forests and generalized random forests to derive counterfactual estimates, and find the optimal decision tree based on these estimates. We formulate and solve the optimal decision tree problem as a mixed-integer program, and evaluate our decision tree policies using doubly robust estimation techniques. We also demonstrate how our methods can be used to solve a budget-constrained assignment problem by assigning individual costs to each anesthesiologist. The derived policies offer performance improvements over historical scheduling, but are unable to offer larger anesthesia time reductions due to anesthesiologist performance being primarily correlated with prior performance.

Consider a player that in each of T rounds chooses one of K arms. An adversary chooses the cost of each arm in a bounded interval, and a sequence of feedback delays \left{ d_{t}\right} that are unknown to the player. After picking arm a_{t} at round t, the player receives the cost of playing this arm d_{t} rounds later. In cases where t+d_{t}>T, this feedback is simply missing. We prove that the EXP3 algorithm (that uses the delayed feedback upon its arrival) achieves a regret of O\left(\sqrt{\ln K\left(KT+\sum_{t=1}^{T}d_{t}\right)}\right). For the case where \sum_{t=1}^{T}d_{t} and T are unknown, we propose a novel doubling trick for online learning with delays and prove that this adaptive EXP3 achieves a regret of O\left(\sqrt{\ln K\left(K^{2}T+\sum_{t=1}^{T}d_{t}\right)}\right). We then consider a two player zero-sum game where players experience asynchronous delays. We show that even when the delays are large enough such that players no longer enjoy the “no-regret property”, (e.g., where d_{t}=O\left(t\log t\right)) the ergodic average of the strategy profile still converges to the set of Nash equilibria of the game. The result is made possible by choosing an adaptive step size \eta_{t} that is not summable but is square summable, and proving a “weighted regret bound” for this general case.

The immense stream of data from mobile devices during recent years enables one to learn more about human behavior and provide mobile phone users with personalized services. In this work, we identify clusters of users who share similar mobility behavioral patterns. We analyze trajectories of semantic locations to find users who have similar mobility “lifestyle,” even when they live in different areas. For this task, we propose a new grouping scheme that is called Lifestyle-Based Clustering (LBC). We represent the mobility movement of each user by a Markov model and calculate the Jensen–Shannon distances among pairs of users. The pairwise distances are represented by a similarity matrix, which is used for the clustering. To validate the unsupervised clustering task, we develop an entropy-based clustering measure, namely, an index that measures the homogeneity of mobility patterns within clusters of users. The analysis is validated on a real-world dataset that contains location-movements of 50,000 cellular phone users that were analyzed over a two-month period.

Machine Learning has great potential to improve automated real-time patient diagnostics. For the majority of machine learning algorithms, taking advantage of this potential requires a complete dataset with no missing data. In practice, missing values are estimated using a variety of imputation methods in the pre-processing stage. However, with time-series data, and physiological waveforms in particular, imputation can be difficult due to the unique patterns and shapes of each waveform, as well as how these patterns vary between patients, and even for a single patient over longer durations. We demonstrate that deep learning techniques can reconstruct missing data using patient-specific patterns present in the non-missing portions of the waveform. Using convolutional neural network (CNN) autoencoders trained on 288 15-minute samples from each of 138 pediatric patients, we develop a generalizable model to analyze and extract information from arbitrary physiological waveforms, and use this model to develop methods for mid-channel missing time-series imputation. We further show that the autoencoder can be used to compress the dense physiological waveforms to a low-dimensional representational space.

In this paper, we construct a framework for optimally sensing a patient's health state with a wireless body area network (WBAN). In such a resource-constrained paradigm, it is often necessary to use lower performance sensing modes, conditionally reducing system performance to increase efficiency and maximize system lifetime. The optimal control architecture trades between shallow and deep sensing modes according to the estimated patient health state, minimizing the expected costs over future states. We construct an implicit formulation for deriving the optimal sensing policy via dynamic programming, an easily implemented myopic sensing policy, and a useful performance bound for evaluating near-optimal approximate sensing policies. We further provide an Monte Carlo experimental evaluation of how such policies depend on key model parameters.

One of the most widely used optimization methods for large-scale machine learning problems is distributed asynchronous stochastic gradient descent (DASGD). However, a key issue that arises here is that of delayed gradients: when a “worker” node asynchronously contributes a gradient update to the “master”, the global model parameter may have changed, rendering this information stale. In massively parallel computing grids, these delays can quickly add up if the computational throughput of a node is saturated, so the convergence of DASGD is uncertain under these conditions. Nevertheless, by using a judiciously chosen quasilinear step-size sequence, we show that it is possible to amortize these delays and achieve global convergence with probability 1, even when the delays grow at a polynomial rate. In this way, our results help reaffirm the successful application of DASGD to large-scale optimization problems.

We consider a game-theoretical multi-agent learning problem where the feedback information can be lost during the learning process and rewards are given by a broad class of games known as variationally stable games. We propose a simple variant of the classical online gradient descent algorithm, called reweighted online gradient descent (ROGD) and show that in variationally stable games, if each agent adopts ROGD, then almost sure convergence to the set of Nash equilibria is guaranteed, even when the feedback loss is asynchronous and arbitrarily corrrelated among agents. We then extend the framework to deal with unknown feedback loss probabilities by using an estimator (constructed from past data) in its replacement. Finally, we further extend the framework to accomodate both asynchronous loss and stochastic rewards and establish that multi-agent ROGD learning still converges to the set of Nash equilibria in such settings. Together, these results contribute to the broad lanscape of multi-agent online learning by significantly relaxing the feedback information that is required to achieve desirable outcomes.

We propose a simple, novel and distributed power control algorithm, called dual averaging, that efficiently incorporates past information and regulates power to achieve better stability. The dual averaging power control algorithm converges to the optimal power vector in a feasible deterministic wireless network. More importantly, even if the network is stochastic and time- varying, as long as the channel is feasible on average, the proposed dual averaging power control algorithm converges almost surely to the deterministic optimal power vector, while existing power control algorithms (such as Foschini-Miljanic) may fail to converge (even to a distribution) altogether. We also provide an extensive set of simulations that demonstrate various interesting and desirable properties of the proposed algorithm.

Wireless video applications for Industrial Internet Of Things (IoT) are expanding into a multitude of new services. In the example of cloud processing for visual object detection, a camera is connected to the cloud via a local server and a data network, allowing the processing load to be handled in a distributed manner. This service model heavy taxes the data network with potentially unneeded traffic, thus degrading the overall quality of service for all users on the network. Edge computing techniques mitigate the degradation of service quality by partially processing the sensor data at the local server before the data is transmitted to the cloud. This is done according to the level of interest of the captured data which is categorized by machine learning algorithms. However, conventional edge computing is not optimally efficient as further recognition attributes of the captured object data are not considered. This paper presents a model that adds control of the camera video rate by considering the attributes of captured object. We then investigate cost trade-offs using dynamic programming, and evaluates the behavior of proposed method under wireless channel condition using NS-3 simulations. Our results show that by adding intelligent adaptive video rate control to the cloud processing of video data capture can reduce overall system power use while improving system efficiency and subsequently network throughput.

In this paper, we examine a class of non-convex stochastic optimization problems which we call variationally coherent, and which properly includes pseudo-/quasiconvex and star-convex optimization problems. To solve such problems, we focus on the widely used stochastic mirror descent (SMD) family of algorithms (which contains stochastic gradient descent as a special case), and we show that the last iterate of SMD converges to the problem’s solution set with probability 1. This result contributes to the landscape of non-convex stochastic optimization by clarifying that neither pseudo-/quasi-convexity nor star-convexity is essential for (almost sure) global convergence; rather, variational coherence, a much weaker requirement, suffices. Characterization of convergence rates for the subclass of strongly variationally coherent optimization problems as well as simulation results are also presented.

We consider a model of game-theoretic learning based on online mirror descent (OMD) with asynchronous and delayed feedback information. Instead of focusing on specific games, we consider a broad class of continuous games defined by the general equilibrium stability notion, which we call λ-variational stability. Our first contribution is that, in this class of games, the actual sequence of play induced by OMD-based learning converges to Nash equilibria provided that the feedback delays faced by the players are synchronous and bounded. Subsequently, to tackle fully decentralized, asynchronous environments with (possibly) unbounded delays between actions and feedback, we propose a variant of OMD which we call delayed mirror descent (DMD), and which relies on the repeated leveraging of past information. With this modification, the algorithm converges to Nash equilibria with no feedback synchronicity assumptions and even when the delays grow superlinearly relative to the horizon of play.

Consider a wireless networking architecture, where multiple infrastructure access points (AP) dynamically offer (bid) service deals (modes) to a mobile over time. Akin to a market offer, each service deal is comprised of service/quality attributes (e.g, AP, rate) for a price (cost). The mobile dynamically selects the desirable deal at each time, so as to efficiently trade long term latency/quality for cumulative price. Offered service modes depend on the randomly fluctuating congestion state of the AP infrastructure. Dynamically switching from one service mode/deal to another, the mobile encounters `friction' (e.g. bandwidth loss, disconnection risk) and, hence, has an incentive to stick with the current deal for as long as this is significantly competitive. A model of this architecture is first developed, which allows for the formulation and computation of the optimal control for the mobile to accept an offered deal amongst many and switch into the corresponding service mode. A suite of low-complexity heuristic controls for mode switching is also discussed. The performance of the optimal and heuristic controls is probed via simulation. Finally, the `switching curve' structure of the optimal control is demonstrated on a simple system where the curves can be plotted.

A prototypical scheduling problem in communication networks is that a server needs to select, from a set of parallel queues, a job for processing to achieve a pre-determined objective. Classical scheduling schemes that yield performance guarantees typically assume that the server has instant access to the realtime information of the entire system state. However, this is costly and hence rarely achievable in practice. A much more relaxed and realistic assumption is that the server only operates under intermittent sampling, where the server samples and thereby obtains the system information at random times. In this paper, we formalize this relaxed and more realistic model and using the well-known longest-queue-first policy as a particular scheduling scheme, study the resulting impacts on system stability and performance due to intermittent system updates. Through extensive simulations, we identify the key message that has practical value: Longest-queue-first scheduling scheme performs well under intermittent sampling.

Consider a dense wireless network of nodes, which can be used to transfer data between arbitrary sources and destinations. In this paper we develop a methodology based on variational calculus to optimize a number of path metrics, such as the success probability or the total power consumed by a packet delivery in the presence of external interference. We then extend the approach to the case of multiple origin-destination pairs, in which the relaying of each packet causes interference to the other. In both cases, we show that the optimal path may differ significantly from a straight line. We then discuss the consequences of these deviations in the context of network design.

Accurate predictions of surgical case lengths are useful for patient scheduling in hospitals. In pediatric hospitals, this prediction problem is particularly difficult. Predictions are typically provided by highly trained medical staff, but these predictions are not necessarily accurate. We present a novel decision support tool that detects when expert predictions are inaccurate so that these predictions can be re-evaluated. We explore several different algorithms. We provide methodological insights and suggest directions of future work.

Power control has been an important field in wireless communications with many applications. The well-known Foschini-Miljanic (FM) algorithm, which has greatly influenced the subsequent literature, is a simple and elegant distributed power control scheme that enjoys several desirable properties. However, the channel environment in the FM algorithm is assumed to be fixed and constant over time, an unrealistic assumption in most practical situations. In this paper, we lift this assumption and study the robustness of the FM algorithm by characterizing its stochastic stability in the presence of stochastic time- varying channel environments. We identify sufficient conditions that are both easily interpretable and efficiently verifiable, for ensuring such stochastic stability. We also present simulation examples to demonstrate the correctness and utility of our conditions.

Transmission Control Protocol (TCP) has long been used host-to-host over the internet in order to provide reliable and ordered exchange of data. A core component of the protocol is congestion control. Traditional forms of TCP congestion control such as New Reno have been shown to perform poorly over wireless links as a result of non-congestive losses induced by variations in the wireless channel. The fulfillment of the Internet of Things (IoT) will result in more wireless users disadvantaged by asymmetric links as well as power and processing constraints. We consider sender-side protocol adaptations, power control and channel aware congestion window evolution in order to mitigate performance shortfalls for such disadvantaged users. This paper presents a model of these congestion control adaptations, investigates cost tradeoffs, and considers protocol behavior under lossy channel conditions.

Processor hardware performance counters have recently improved in quality and features, while performance monitoring support in Linux has been significantly revamped with the development of the perf_events subsystem, which contributed in making performance analysis an increasingly common practice among developers. However, no performance analysis is possible without an efficient monitoring interface and reliable hardware counter data. In this paper, we first address a reliability issue in the Performance Monitoring Unit of recent Intel processors with Hyper-Threading enabled. A published erratum causes cross hyper-thread hardware counter corruption and may produce unreliable results. We propose a cache-coherence style protocol which we implement in the Linux kernel to address the issue by introducing cross hyper-thread dynamic event scheduling. Second, we improve event scheduling efficiency by introducing an algorithm which optimally schedules events onto hardware counters consistently. The proposed optimizations do not require any user level changes. They leverage the internal design of the perf_events subsystem and have broader applicability in processors. The improvements have been contributed to the upstream Linux kernel 4.1.

In this paper, we analyze the problem of power control in large, random wireless networks that are obtained by “erasing” a finite fraction of nodes from a regular d-dimensional lattice of N transmit-receive pairs. In this model, which has the important feature of a minimum distance between transmitter nodes, we find that when the network is infinite, power control is always feasible below a positive critical value of the users' signal-to-interference-plus-noise ratio (SINR) target. Drawing on tools and ideas from statistical physics, we show how this problem can be mapped to the Anderson impurity model for diffusion in random media. In this way, by employing the so-called coherent potential approximation method, we calculate the average power in the system (and its variance) for 1-D and 2-D networks. This approach is equivalent to traditional techniques from random matrix theory and is in excellent agreement with the numerical simulations; however, it fails to predict when power control becomes infeasible. In this regard, even though infinitely large systems are always unstable beyond a critical value of the users' SINR target, finite systems remain stable with high probability even beyond this critical SINR threshold. We calculate this probability by analyzing the density of low lying eigenvalues of an associated random Schrödinger operator, and we show that the network can exceed this critical SINR threshold by at least O((log N)-2/d) before undergoing a phase transition to the unstable regime. Finally, using the same techniques, we also calculate the tails of the distribution of transmit power in the system and the rate of convergence of the Foschini-Miljanic power control algorithm in the presence of random erasures.

In this paper, we consider a basic issue in wireless computing, where mobile devices (with relatively limited memory) fetch data (text, images, multimedia, etc.) from access points over wireless channels of fluctuating quality. When the channel quality is low, slow data downloads can contribute to application latency, and degradation of the user experience. To mitigate this issue, mobile devices can prefetch data during good quality channel periods preemptively, in anticipation of using them during low quality channel epochs. In other words, under favorable wireless channel conditions, the mobile terminal can prefetch data aggressively to reduce application latency when channel conditions have degraded. Considering channel fluctuations, memory constraints, and application latency, the issue at each point in time is whether to prefetch or not. A dynamic programming approach is taken here to determine the optimal prefetching policy. The latter is leveraged to develop a prefetching algorithm “Fetch-or-Not” (FON). We then design a randomized “Fetch-or-Not” (RFON) prefetching algorithm, which uses a randomized approximation of FON, thus lifting the need for online optimization and substantially reducing the computational complexity. Simulations are used to demonstrate that our low-complexity schemes perform well when compared to the optimal. In addition, our schemes outperform benchmark design techniques in realistic channel conditions.

In this paper, we develop a general-use autonomous control strategy for managing the trade-off between processing throughput and power consumption in data centers. This approach relies on the concept that the delay in completing computational tasks can be reduced at the cost of more power. The scheme's generality allows it to be applied at multiple hierarchical levels within a data center, or another system with similar architecture. In particular, we show that our scheme converges asynchronously to a unique solution. This property allows the control strategy to be implemented in a low-complexity, yet robust and scalable manner. These properties are particularly important when considering data center power control system architectures, which can involve a wide variety of distributed computing resources performing diverse tasks. The presented scheme is mostly decentralized, except for a single global power stress signal provided by a redundant central authority. Based on this power stress, computing resources independently and autonomously manage power consumption to optimally balance power versus delay.

We consider the problem of TCP congestion control over wireless links. Packet losses due to wireless channel variation needlessly throttle TCP's congestion window leading to sub-capacity throughput for a given link. We consider Received Signal Strength Indication (RSSI) as a marker of channel state and propose pausing packet transmission when the channel state is poor. Using this additional metric and control leads to a congestion control algorithm better tuned for the wireless environment. The resulting Channel Responsive TCP (CR-TCP) algorithm is simple to implement and interoperable with traditional variants. We develop an optimal control framework for interference dominated environments and demonstrate the CR-TCP algorithm over various wireless link conditions showing that it outperforms traditional TCP congestion control implementations.

We propose and evaluate a new distributed algorithm for transmit power control (TPC) in wireless networks. We cast the TPC problem as a dynamic program which captures a fundamental tradeoff between transmit power and delay, and we use its solution to inform our design. The resulting algorithm is reminiscent of existing TPC approaches which seek to have each link maintain a constant signal-to-interference-plus-noise ratio (SINR), but with a key difference: a queue-dependent backoff threshold which allows links to temporarily stop transmitting when the interference grows too large. In high interference scenarios, this difference allows our algorithm to automatically induce a network behavior similar to time-division multiple access (TDMA), without any explicit cross-link coordination. As a result of this behavior, we demonstrate that our algorithm can provide substantial throughput improvements over previous schemes.

Cloud infrastructures with virtualized CPU and memory resources have the potential for providing high quality of service at increased levels of energy efficiency. By dynamically tailoring the capacity of a virtual machine to workload demands, a cloud infrastructure can significantly reduce the number of physical resources it has online, saving on decreased power costs. These resource management techniques, however, have yet to gain widespread appeal among network engineers due to the significant delays and setup costs in activating or reconfiguring cloud resources. A further challenge is these "frictions" fluctuate through time, based on complex system-wide supply and demand "weather" patterns in the cloud as a whole. In this paper, we develop a loss queueing model for capacity provisioning for a virtual machine that draws its computation resources from the cloud under varying friction cost. We solve for the optimal control policy using dynamic programming and discuss its intuitive structural properties. Finally we run simulations to compare the performance of the optimal policy against two benchmarks and a heuristic policy.

In wireless media streaming from multiple access points, handoff control ensures optimal connectivity as the wireless environment fluctuates, while rebuffering control seeks to maximize user experience by avoiding playout jitters and prolonged freeze times. A joint policy aims to capture the interactions between these controls, but requires a fluctuating wireless environment to be estimated frequently, a process which can interrupt packet retrieval in many mobile applications. In this paper we develop a model for maximizing user QoE by optimally scanning wireless channels while making handoff and rebuffering decisions. We design a control scheme that utilizes partial knowledge of the wireless environment to decide when to explore alternative connections, when to handover to them, and when to exploit an access point while employing channel-aware rebuffering control. We develop a model for the general case of multiple access points, then computationally evaluate the system in specific relevant cases. We find that the resulting optimal control takes the form of threshold-based policies, and that it compares favorably to the omniscient policy with full knowledge of all channel states. We also find that the optimal decision regions can be greatly simplified with only a small decrease in optimality.

We consider the problem of streaming media packets from a transmitter buffer to a receiver over a wireless channel, controlling the transmitter power. When each packet comes to the head-of-line (HOL) in the buffer, it is a given a deadline D, which is the maximum number of times it can attempt retransmission in order to get successfully transmitted to the receiver. If that fails to happen, the packet is dropped and the next in line packet becomes the HOL one. Cost is incurred in each time slot for keeping packets in the transmitter buffer, transmitting power, and dropping HOL packets exceeding their deadlines. We investigate how transmission power should be chosen efficiently given the remaining backlog and residual transmission attempts of the HOL packet, so as to minimize the overall cost to transmit the buffer content. We formulate the optimal power control problem and study properties of the optimal control, proving that it is monotone under certain conditions. We then develop an approximate power control, which increases logarithmically in the transmitter backlog, and is demonstrated to perform quite closely to the optimal one.

Inexpensive wireless communication and emerging energy storage technologies are creating a new future for the power grid. These tools are enabling a “smart grid” which can utilize novel control strategies, such as real-time pricing, to achieve efficiency, fairness, and stability. We propose a decentralized smart grid architecture which uses minimal communication to meet these objectives. Then, inspired by queueing models and distributed control in wireless networks, we develop an algorithm for allocating power which is sensitive to both delay as well as price. The delay sensitivity allows for load shifting while the price sensitivity is a natural consumer objective. We show that the algorithm quickly converges even when homes operate asynchronously which makes the architecture practical for implementation. In addition, we show convergence using techniques from lattice theory. Although similar ideas have been used in standard power control algorithms for wireless systems, we demonstrate that the underlying ideas are more general. This provides a theoretical contribution along with a practical contribution to smart grid power management systems.

Reducing energy consumption in data centers has been a persistent goal for the last decade. Advances in virtualization and dynamic power management have helped to curb excess utilization by sharing resources and running system components in lower energy states during periods of low traffic. However, switching components among virtual machines and energy states is subject to setup times and increased energy consumption to bring them online, and this combined with the innate burstiness of traffic in data centers are significant deterrents to the successful deployment of power management techniques. In this paper, we develop a queueing model with a controllable service rate that accounts for switching frictions within a setting that has a changing arrival rate. We solve for the optimal control policy using dynamic programming, and find it has intuitive structural properties. We compare its performance against benchmark heuristics, and the relative advantages among them in different scenarios are discussed.

We consider a problem faced by wireless base stations in which multiple requests to stream data must be accomodated while minimizing the amount of buffering time spent by clients. In our model, clients request content in discrete data chunks, but the base station is restricted in which clients can simultaneously be served data at certain rates. This limitation occurs frequently due to wireless connectivity and congestion issues in which some clients are difficult to reach from the base station, whereas others are more easily serviced. These constraints are represented by a set of admissible service rate vectors from which a scheduler at the base station must choose. We take a queuing theoretic approach to this decision problem and employ a stress alignment approach to ensure that maximal throughput from the data center to the clients is achieved. As a consequence, whenever it is possible to stabilize the backlog of requests from each client, we are able to do so. Numerical experiments show that among the variations of this scheduling algorithm, we can choose parameters to vary the priority levels of different clients and even induce dependencies between service rates of different clients.

Real-time internet traffic classification has potential applications in next-generation internet security and bandwidth management. Current machine learning-based algorithms for traffic classification, however, present scalability issues that would degrade system performance if executed to make control decisions on real-time streams. This tension gives rise to competing performance costs for traffic classification systems: higher throughput can be achieved at the expense of less stringent computation, and thus lower accuracy. In this paper, we develop a queueing model to explicitly weigh the tradeoff between accuracy and congestion costs in binary classification tasks of discretionary duration. We show the optimal control policy can be approximated well using standard dynamic programming techniques, and compare its performance against two benchmark policies. We also propose a simple heuristic based on constructing conic hulls, and show its performance is very close to optimal.

We introduce an algorithmic framework that uses nonparametric Bayesian models to process real-time physiological data in the context of developing and testing personalized wellness monitors and tailored intervention strategies. A wearable device aggregates signals from various sensors while periodically transmitting the collected data to a backend server. The server performs the computationally challenging model inference tasks offline and builds custom user profiles based on inferred hidden Markov states. We discuss how these user profiles can be used to detect possible physiological changes in a simple application based on a two-week study hosted at Jaslok Hospital, where relaxation therapy is given to eight healthy male subjects as intervention against stress from the workday. A heuristic is introduced to enable real-time state identification using the modest processing capabilities of the wearable device.

We examine the problem of tracking the states of a collection of systems over a finite horizon in a power limited scenario. Specifically, each system has a sensor which can track a property of interest and has a fixed budget with which to make measurements and communicate to a fusion center. The state at each system varies independently according to a Markov model and the transitions between different states occur according known transition matrices. Different systems can have vastly different state evolution statistics. At each time step, the fusion center can request an update from any number of the systems, subject to the constraint that the corresponding sensor has not exhausted its budget to do so. These measurement updates are expensive and hence resource limited. After the fusion center receives all updates, it must estimate the state at each system with minimum error. We give an optimal policy for the fusion center to request updates from each sensor and also provide an optimal policy for the fusion center to allocate the measurement budget to each sensor before deployment, given the transition matrices corresponding to each system.

We consider the problem of scheduling packets in an input queued switch with a focus on processing streamed multimedia data. In such applications, packets arrive with hard service deadlines; after the deadline for a packet has passed, it is no longer useful and does not get delivered - it is dropped. We seek policies to minimize the number of late packets, which are then dropped. The problem is formulated in a Dynamic Programming framework and shown to be intractable. The formulation is contrasted to the related crossbar switch scheduling problem, with an emphasis on the fact that we have a different objective function. A simplified probabilistic version of the streaming problem is used as motivation for a heuristic solution. Finally, we present results from a simulation in which a simple heuristic based on weighting queues according to the deadline of the leading packet consistently outperforms the well-known maximum weight matching (MWM) algorithm.

As smartphones, tablets, and other portable technologies become increasingly prevalent, scaling computational applications to run on these resource-constrained devices will continue to rise to the forefront of challenges in the wireless networking community. In particular, computing tasks which typically address a trade-off between robustness and efficiency, including emerging methods for intruder detection, cryptography, and context-aware applications, need to balance these two objectives against power to adequately transfer onto small systems with a limited power supply. In this paper, we present a queueing model that explicitly balances the competing objectives of minimizing latency, maximizing output quality, while regulating power consumption. We demonstrate the efficacy of this model against a sensible alternative heuristic, thus providing a general and integrated framework for evaluating the performance of quality-driven applications on resource-constrained devices.

Power management has become a critical issue for communication and computing infrastructures. In this paper, we develop systematic and heuristic algorithms for managing communication switches with multiple speed (throughput) modes. Switch speed is increased by activating additional network processor cores, voltage/frequency scaling of the electronics, etc. Higher speed modes burn more power. The developed power (speed) control algorithms are responsive to switch queue backlogs and aim to efficiently trade backlog vs. power costs, so as to minimize the long-run overall backlog and power cost. We first systematically model the system in a Dynamic Programming (DP) framework, where the optimal control can be computed in principle. Unfortunately, the complexity is so high that even for a 2 × 2 switch the computation time is practically infeasible. We therefore develop an Approximate Dynamic Programming (ADP) algorithm based on the Q-learning framework, which has good computation and performance properties. We also develop two low-complexity heuristic power controls, one based on a “myopic” view of the control problem, and the other on “congestion-awareness” of the standard maximum weight matching scheme. We study the performance of the Q-learning and heuristic controls against the optimal one (which we can practically compute only for the 2×2 switch case), and comment on their efficiency. We also extend the method and results to the general case of multiprocessor computing resources.

Consider a wireless network of transmitter-receiver pairs. The transmitters adjust their powers to maintain a particular SINR target at the corresponding receiver in the presence of interference from neighboring transmitters. In this paper we analyze the power vector that achieves this target (and hence is optimal) in the presence of randomness in the network. The randomness is realized by randomly turning off a fraction of transmitter-receiver pairs in a regular lattice. We show that the problem is identical to the so-called Anderson model, which describes the motion of electrons in a dirty metal. We show that traditional random matrix theory is only an approximation that, while accurate in some cases, fails to fully describe the system. We apply the coherent potential approximation (CPA), which is equivalent to random matrix theory, to evaluate the average power vector. We also find that although beyond a certain point the infinite system is infeasible with probability one, any arbitrarily large, but finite system has a typically small probability of becoming infeasible. The CPA framework allows us to calculate this outage probability with exponential accuracy by showing that it is proportional to the tails of the eigenvalue distribution of the system.

Many mobile applications retrieve content from remote servers via user generated queries. Processing these queries is often needed before the desired content can be identified. Processing the request on the mobile devices can quickly sap the limited battery resources. Conversely, processing user queries at remote servers can have slow response times due communication latency incurred during transmission of the potentially large query. We evaluate a network-assisted mobile computing scenario where mid-network nodes with “leasing” capabilities are deployed by a service provider. Leasing computation power can reduce battery usage on the mobile devices and improve response times. However, borrowing processing power from mid-network nodes comes at a leasing cost which must be accounted for when making the decision of where processing should occur. We study the tradeoff between battery usage, processing and transmission latency, and mid-network leasing. We use the dynamic programming framework to solve for the optimal processing policies that suggest the amount of processing to be done at each mid-network node in order to minimize the processing and communication latency and processing costs. Through numerical studies, we examine the properties of the optimal processing policy and the core tradeoffs in such systems.

We examine the problem of fault detection in networked computing systems and highlight the tradeoff between diagnosing/reacting to potentially harmful real-time events and minimizing the number of times the system is reset or scanned for malicious activity. The various health states of a system are modeled as states in a Markov chain, and we use a model fitting approach to estimate the transitions between these states. We proceed by considering a scenario in which a system is to be deployed over a fixed horizon but with a limit on the number of times that the health state can be scanned and the system can be reset. Each health state is assigned a cost according to the performance of the system while in that state. Dynamic Programming is then used to find an optimal admissible policy (one that obeys the usage limitation constraints) which achieves the lowest expected aggregate cost. Finally, we examine some properties of the solution.

Wireless hand-off control typically considers only connectivity strength from the mobile terminal to alternative access points. In wireless video streaming, however, where video freezing must be avoided at the mobile terminal, the playout buffer level should also be considered by hand-off control. In this paper, we first develop a model capturing hand-off dynamics under video streaming, and design a new playout buffer aware hand-off control. It aims to avert a video freeze for as long as possible, maximizing the expected time until freezing. We compute the optimal control in the general case of multiple access points and multiple connectivity strength states per channel. The optimal hand-off control is then computationally probed in specific relevant cases. It is demonstrated that there is a certain playout buffer threshold level - a buffer tipping point - above which a hand-off should be attempted. Of course, this tipping point depends on the access point to mobile channel statistics.

In this paper we profile a particular tradeoff between power budget and video quality that emerges in the transmission of multimedia packets over a wireless channel. These packets are due to arrive to a receiver at a particular time, so we consider a finite horizon problem over which multimedia data are transmitted. Due to the lossy nature of the wireless channel, however, not every packet can be successfully sent across the channel. Hence, each packet that is lost leads to distortion in the video that is experienced by the receiver. We suppose that there are M packets that must arrive at the receiver within N time steps, but that power limitations constrain the number of transmissions. At each time step, we may make a measurement of the wireless channel and decide whether or not to transmit a packet over the channel at that time. First we will suppose the times at which the channel state is sampled are spaced far enough apart so that the samples are i.i.d. Then we will continue by supposing that the channel state follows a Markov chain.

Power-controlled multiple access (PCMA) is a class of distributed algorithms for transmitter power control (TPC) in wireless networks. In this paper, we develop and evaluate a continuous analog (fluid model) of the discrete version of PCMA in order to clearly demonstrate PCMA's capability to, without centralized coordination, induce a network behavior akin to time-division multiple access (TDMA), which we call “induced” TDMA (iTDMA). This analysis allows us to provide new insights into the throughput improvements of PCMA over the classical and widely-used Foschini-Miljanic (FM) constant signal-to-interference algorithm for distributed TPC, particularly in high-interference channels. Furthermore, this fluid model shows that PCMA's iTDMA behavior is fundamentally tied to the functional form of the central PCMA equation, and that PCMA holds significant potential for various types of interference-limited wireless networks.

Consider a wireless network of transmitter-receiver pairs. The transmitters adjust their powers to maintain a particular SINR target at the corresponding receiver in the presence of interference from neighboring transmitters. In this paper we analyze the optimal power vector that achieves this target in the presence of randomness in the network. Specifically, starting from a regular lattice of transmitter-receiver pairs we randomly turn off a finite fraction of them. We apply random matrix theory to evaluate the asymptotic optimal power per link, as well as the variance of powers in the optimal power vector in the limit of a large number of links. Our analytical results show remarkable agreement with numerically generated networks, both in one- and two-dimensional network geometries. Interestingly, we observe that unlike regular lattices, the optimal power in random networks has a discontinuity at a finite value, while the variance of its powers diverges at that value. Beyond that critical point, no feasible power solution exists. We discuss the relevance of these results in realistic networks.

Due to increasing circuit densities and data throughput rates, power consumption has become a significant concern in the design and operation of high-performance packet switches. We extend the idea of Dynamic Power Management (DPM) to input queued switches, allowing operators to tradeoff power and delay in a useful way. We frame the problem as a dynamic program and solve a relaxation using techniques from Linear Quadratic Regulation (LQR). This optimal policy is combined with existing, nonpower-aware switch controls to generate two novel scheduling algorithms: 1) LQR Power Aware Maximum Weight Matching (LQR PA MWM) and 2) LQR Power Aware Projective Cone Scheduling (LQR PA PCS). Simulation results suggest that our algorithms result in significant power savings compared to MWM and previous power control schemes with little performance degradation.

This paper presents a game-theoretic and learning approach to security risk management based on a model that captures the diffusion of risk in an organization with multiple technical and business processes. Of particular interest is the way the interdependencies between processes affect the evolution of the organization's risk profile as time progresses, which is first developed as a probabilistic risk framework and then studied within a discrete Markov model. Using zero-sum dynamic Markov games, we analyze the interaction between a malicious adversary whose actions increases the risk level of the organization and a defender agent, e.g. security and risk management division of the organization, which aims to mitigate risks. We derive min-max (saddle point) solutions of this game to obtain the optimal risk management strategies for the organization to achieve a certain level of performance. This methodology also applies to worst-case scenario analysis where the adversary can be interpreted as a nature player in the game. In practice, the parameters of the Markov game may not be known due to the costly nature of collecting and processing information about the adversary as well an organization with many components itself. We apply ideas from Q-learning to analyze the behavior of the agents when little information is known about the environment in which the attacker and defender interact. The framework developed and results obtained are illustrated with a small example scenario and numerical analysis.

We present a model for keeping track of vulnerabilities in a networked computing system and study the tradeoff between risk mitigation and keeping disruption at an acceptable level. The tradeoff is such that one can either choose to perform maintenance of the computing system very frequently and experience low risk, or disrupt the system with less frequency, but bear more risk. Formally, we suppose there are n types of vulnerabilities, where each type is jointly characterized by (i) maliciousness, as measured by risk per time slot due to its presence and (ii) probability of occurrence. At each time step, at most one new vulnerability appears in the system, a property that follows if we take the discretized time step size to be small compared to the rate of arrivals for vulnerabilities. We consider a finite-horizon framework of duration N in which the number of times the network may be patched is M <; N. This limitation captures the fact that in many engineering systems we would like to limit the number of times processes are interrupted for maintenance. Indeed, service providers may wish to promise clients that service will be disrupted no more than M times so that a certain level of operational continuity can be guaranteed. We develop an optimal policy for mitigating the risk due to exposure from vulnerabilities while obeying the patching constraint.

In this paper, we formulate a delay-power control (DPC) scheme for wireless networking, which efficiently balances delay against transmitter power on each wireless link. The DPC scheme is scalable, as each link autonomously updates its power based on the interference observed at its receiver; no cross-link communication is required. It is shown that DPC converges to a unique equilibrium power and several key properties are established, concerning the nature of channel bandwidth sharing achieved by the links. The DPC scheme is contrasted to the well-known Foschini-Miljanic (FM) formulation for transmitter power control in wireless networks, and some key advantages are established. Based on the DPC and FM schemes, two protocols are developed, which leverage adaptive tuning of DPC parameters. One of them is inspired by TCP and exhibits analogous behavior. This paper primarily focuses on the theoretical underpinnings of DPC and their practical implications for efficient protocol design. The DPC dynamics are also investigated numerically.

Security risk management is becoming increasingly important in a variety of areas related to information technology (IT), such as telecommunications, cloud computing, banking information systems, etc. In this paper, we develop a systematic quantitative framework for security risk management in IT-intensive organizations. This framework provides a unified viewpoint for considering a wide array of security risk factors which can disrupt business continuity. Our approach integrates the three phases of security risk management, namely risk modeling, assessment, and control/mitigation, through a formulation based on directed graphs, cascades of failures, and mathematical optimization. We consider how security events can propagate through an organization and how resource allocation decisions can be made in order to mitigate the amount of damage they cause. The applicability and effectiveness of our framework is demonstrated through a numerical study which shows significant cost reductions when compared to heuristic methods.

Power-controlled multiple access (PCMA) is a distributed algorithm for transmitter power control of autonomous communication links in wireless networks. By allowing links to trade off transmission power for packet delay, PCMA has been demonstrated to outperform standard approaches (e.g., the Foschini-Miljanic constant signal-to-interference ratio algorithm) in terms of maximum throughput, especially in cases of high interference. However, recent experiments have revealed that as interference grows higher, links using PCMA may "lock" into inefficient power evolution patterns which compromise network performance. In this paper, we explore this locking dynamic, which is caused by the highly non-linear nature of PCMA. We then propose simple randomization-based mitigation mechanisms to alleviate locking behavior, and we demonstrate that these mechanisms can substantially improve PCMA efficiency.

An admission control algorithm for power-controlled wireless networks, proposed previously for the case of linear interference functions, is considered in this paper. We analyze the properties of the algorithm using the framework of standard interference functions, which makes it applicable to many system designs. Furthermore, we introduce individual power constraints into the system. The key property of the algorithm is the protection of active users, which guarantees that as new users attempt to join the network, the quality of the established links is sustained. We present conditions under which this key property is preserved under power constraints and analyze the convergence properties of the scheme.

Security risk management for information technology-based organizations has become increasingly important in recent years. However, the risk assessment and mitigation strategies that these organizations employ have remained relatively ad hoc and qualitative. In this paper, we extend a quantitative framework for risk assessment called Risk-Rank to include risk mitigation through Markov Decision Processes. By doing so, we provide an analysis-to-action quantitative approach to security risk management, enabling IT managers to perform more comprehensive evaluations of their risk exposures. We demonstrate the effectiveness of this approach through an example related to the patching of computers in a corporate network.

In this paper, we present a new hybrid class of transmitter power control algorithms which couples two separate previous schemes, specifically: (1) the Foschini-Miljanic algorithm for delay-sensitive streaming traffic, and (2) the power controlled multiple access (PCMA) approach for delay-tolerant data traffic. We develop a unified dynamic programming framework to reveal the underlying connection between these two seemingly disparate approaches. We then leverage this framework to design hybrid algorithms exhibiting key performance benefits. Finally, we demonstrate through simulations substantial performance gains over the traditional approaches, that is, lower power consumption and higher throughput.

We study scheduling of multimedia traffic on the downlink of a wireless communication system. We examine a scenario where multimedia packets are associated with strict deadlines and are equivalent to lost packets if they arrive after their associated deadlines. Lost packets result in degradation of playout quality at the receiver, which is quantified in terms of the "distortion cost" associated with each packet. Our goal is to design a scheduler which minimizes the aggregate distortion cost over all receivers. We study the scheduling problem in a dynamic programming (DP) framework. Under well justified modeling reductions, we extensively characterize structural properties of the optimal control associated with the DP problem. We leverage these properties to design a low-complexity Channel, Deadline, and Distortion (CD2) aware heuristic scheduling policy amenable to implementation in real wireless systems. We evaluate the performance of CD2via trace-driven simulations using H.264/MPEG-4 AVC coded video. Our experimental results show that CD2comfortably outperforms benchmark schedulers like earliest deadline first (EDF) and best channel first (BCF). CD2achieves these performance gains by using the knowledge of packet deadlines, wireless channel conditions, and application specific information (per-packet distortion costs) in a systematic and unified way for multimedia scheduling.

This paper develops a framework for analyzing security risk dependencies in organizations and ranking the risks. The framework captures how risk `diffuses' via complex interactions and reaches an equilibrium by introducing a risk-rank algorithm. A conceptual structure of an organization-comprised of business units, security threats/vulnerabilities, and people-is leveraged for modeling risk dependencies and cascades. The risk-rank algorithm captures risk diffusion over time and ranks various risks based on a balancing of the immediate risk versus the future one emerging via cascading across system dependencies. Thus, the presented framework facilitates a systematic prioritization of risks in organizations.

Previous work has proposed the Dynamic Switch Buffer Management (DSBM) scheme, a promising approach for improving the scalability of switch ingress memories. In this paper, we extend these results by adding increased backlog awareness into the latter. In particular, we propose using a novel combination of two backlog-aware algorithms: BA-DSBM to map incoming packets to the switch's ingress buffers and the Backlog-Aware Wrapped Wavefront Arbiter (BA-WWFA) to set the configuration of the switch fabric. We then simulate these algorithms under a variety of load intensities and types. These simulations suggest that adding backlog-awareness into the DSBM scheme leads to significant performance enhancements, particularly as the switch is "stressed" by asymmetric or heavy loading. Our algorithms, therefore, mitigate some of the design tradeoffs made in this novel, highly-scalable switch design.

High variability of access resources in heterogeneous wireless networks and limited computing power and battery life of mobile computing devices such as smartphones call for novel approaches to satisfy the quality-of-service requirements of emerging wireless services and applications. Towards this end, we first investigate a Markov-based stochastic scheme for modeling and estimation of bandwidth and delay on heterogeneous wireless networks. Borrowing clustering techniques from machine learning literature for intelligent state quantization, we demonstrate that the performance of the Markov model is enhanced significantly. We implement a measurement tool Zeus on smartphones and collect real-world data on 802.11g, 2.5G, and 3G wireless networks. The accuracy of the developed model is evaluated through simulation studies based on the collected data. Furthermore, a distributed rate-control scheme leveraging the predictions of our model is developed and observed to be much more efficient than a baseline additive-increase multiplicative- decrease scheme.

In this paper we propose two advanced algorithms which allow for both differentiated quality-of-service (QOS) and power conservation in input-queued packet switches. These algorithms are based on two core ideas: first, we assume that the switch can operate in a number of operational speed modes; a higher speed mode serves more packets per time slot at the cost of higher power consumption. Second, each virtual output queue may tolerate a certain low backlog which is called a target in this setting. Thus, one can control power by adjusting the speed mode and QOS by setting the targets appropriately. We first survey previous work to provide the necessary background behind our approach. We then describe our algorithms and evaluate their performance experimentally through simulation. Our preliminary results show that these new procedures offer significant performance gains compared to existing approaches.

We consider a power-controlled wireless network with an established network topology in which the communication links (transmitter-receiver pairs) are subject to some constraints on transmit powers and corrupted by the cochannel interference and background noise. The interference is completely determined by a so-called gain matrix. Assuming irreducibility of the gain matrix, we provide an elegant characterization of the max-min SIR-balanced power allocation under general power constraints. This characterization gives rise to two types of algorithms for computing the max-min SIR-balanced power allocation. It also allows for an interesting saddle point characterization of the Perron root of extended gain matrices.

We investigate a wireless computing architecture, where mobile terminals can execute their computation tasks either 1) locally, at the terminal's processor, or 2) remotely, assisted by the network infrastructure, or even 3) combining the former two options. Remote execution involves: 1) sending the task to a computation server via the wireless network, 2) executing the task at the server, and 3) downloading the results of the computation back to the terminal. Hence, it results to energy savings at the terminal (sparing its processor from computations) and execution speed gains due to (typically) faster server processor(s), as well as overheads due to the terminal server wireless communication. The net gains (or losses) are contingent on network connectivity and server load. These may vary in time, depending on user mobility, network, and server congestion (due to the concurrent sessions/connections from other terminals). In local execution, the wireless terminal faces the dilemma of power managing the processor, trading-off fast execution versus low energy consumption. We model the system within a Markovian dynamic control framework, allowing the computation of optimal execution policies. We study the associated energy versus delay trade-off and assess the performance gains attained in various test cases in comparison to conventional benchmark policies.

The growing popularity of multimedia streaming applications brings a growth in diversity of media clients (laptops, PDAs, cellphones). Effectively serving this heterogeneous group of users is highly desirable. Scalable media codecs such as H.264/MPEG-4 SVC help make this adaptation possible. To account for the various capabilities and requests of each user, such as varying spatial or temporal resolutions, multiple distortion measures (MDM) are considered. Rather than consider a homogeneity in users, the MDM framework considers multiple different distortion values for each media packet for each user type. We consider the scenario of simultaneously broadcasting a video stream to multiple users over wireless links. The objective is to design a scheduling algorithm which achieves the highest aggregate quality-of-service, measured by distortion and delay, over all different user types. We cast the problem as a stochastic shortest path problem and use dynamic programming to find the optimal policy. For statistically static channels, the optimal policy is shown to be of threshold type. For time-varying channels, a quasi-static policy is introduced. Experimental results show that our policy reduces distortion by up to a factor of 2 over conventional approaches which do not consider MDM.

In various settings, such as when customers use the same passwords at several independent web sites, security decisions by one organization may have a significant impact on the security of another. We develop a model for security decision-making in such settings, using a variation of linear influence networks. The linear influence model uses a matrix to represent linear dependence between security investment at one organization and resulting security at another, and utility functions to measure the overall benefit to each organization. A simple matrix condition implies the existence and uniqueness of Nash equilibria, which can be reached by a natural iterative algorithm. A free-riding index, expressible using quantities computed in this model, measures the degree to which one organization can potentially reduce its security investment and benefit from investments of others. We apply this framework to investigate three examples: web site security with shared passwords, customer education against phishing and identity theft, and anti-spam email filters. While we do not have sufficient quantitative data to draw quantitative conclusions about any of these situations, the model provides qualitative information about each example.

Many data center devices, for instance packet switches, can be modeled within the context of resource constrained queueing systems. In this paper, we define a novel algorithm class which simultaneously addresses three significant concerns in the operation of such systems: stability, differentiated QOS, and power control. This class, which we refer to as target/power projective cone scheduling (TP-PCS), encapsulates many previously studied algorithms as special cases. At the same time, however, it is broad enough to include a rich set of other, potentially superior control procedures. In the first part of our paper, we explain our model as well as some previously studied approaches to scheduling in these systems. We then define TP-PCS, show how it relates to the former algorithms, and discuss how members of this class can be tailored to control for both power and QOS. Finally, we test some instances of TP-PCS on a simulated, input-queued switch. These show that a wide variety of operating modes are possible by adjusting various scheduling parameters. Hence, TP-PCS opens up for exploration a large set of new controls for packet switches and other systems operating in the queueing space.

The growing diversity in media clients calls for content providers to adapt media content to adhere to their various needs. It is desirable to serve these heterogeneous users in a fast and efficient manner. Scalable media, such as H.264/MPEG- 4 SVC, helps make this possible. To account for various viewing capabilities of each user, such as different spatial or temporal resolutions, the Multiple Distortion Measures framework is used [1], [2]. MDM associates multiple distortion values with each packet depending on the user types (low/high resolution viewers, low/high frame rate viewers, etc.) who will consume the media packets. In this paper, we examine how to broadcast media packets with multiple distortion measures to multiple users. The tradeoff between media distortion and delay (in the form of retransmissions) plays an integral role in the scheduling decision. We cast the problem as a stochastic shortest path problem and use Dynamic Programming to find the optimal policy. In the case of statistically static channels, the optimal policy is shown to be a threshold policy where the number of allowable retransmissions is dictated by the importance, in terms of incurred distortion, of each packet. Through experimental results, we show that our policy, which considers multiple distortion measures, achieves up to 8 dB gains over conventional approaches. Finally, a policy based on the theoretical results of statistically static channels is empirically shown to have high performance for time-varying channels modeled by a two-state Markov Chain.

A novel architecture was proposed in [1] to address scalability issues in large, high speed packet switches. The architecture proposed in [1], namely OBIG (output buffers with input groups), distributes the switch fabric across multiple chips, which communicate via high speed interconnects enabled by proximity communication (PC), a recently developed circuit technology [2]. An OBIG switch aggregates multiple input flows inside the switch fabric, thereby significantly reducing the amount of memory required for internal buffers, vis-a-vis a conventional buffered crossbar, which has buffers at every crosspoint. Thus, the OBIG architecture is promising for realizing terabit switches with hundreds of ports. This paper studies packet scheduling algorithms which help realize the potential of OBIG-like switch architectures. The emphasis here is on designing backlog aware scheduling algorithms, while ensuring desirable traits such as low computational complexity and scalability. The efficacy of the proposed scheduling algorithms with respect to performance metrics such as average delay and fairness is demonstrated via simulations under a variety of scenarios.

In this paper, we explore two novel scheduling algorithms which allow for both differentiated quality-of-service (QOS) and power conservation in input-queued packet switches. At their core is the idea of a backlog target which represents the delay sensitivity of each input/output port combination. The first algorithm, target-based projective cone scheduling (T- PCS), incorporates these targets into the well-studied projective cone scheduling algorithm, a generalized form of maximum weight matching (MWM). The second algorithm, average backlog scheduling(ABS), uses a 'memory window' to push average backlogs towards their targets. We explain the intuition behind each of these and then show, through simulation, that both exhibit high performance in terms of managing power and QOS, while simultaneously addressing these two key concerns in switches.

Multimedia applications for mobile devices are increasing and growing more sophisticated. Many of these applications require computationally intensive processing, such as image processing, source coding, feature extraction and feature matching. If all of this processing were performed on the mobile device, its limited battery supply would quickly deplete. However, if the request must be transmitted through a network and processed at a remote application server large delays may be incurred due to communication latency-especially if the original size of the request message is very large. In this paper, we propose the use of mid-network processing on intermediary nodes in a multistage tandem network. We refer to this as ldquowireless network-Assisted computingrdquo. Allowing for mid-network processing can alleviate some of the processing burden on the mobile device, thereby extending its lifetime. It can also reduce communication latency by reducing the amount of information transmitted along each link. Certainly ldquoleasingrdquo processing power from these nodes comes at a price-in some cases it is beneficial to lease, in others it is not. We examine the core tradeoff between battery usage, latency, and usage of processing power at mid-network nodes. We identify some interesting properties of the optimal processing schedule. Through numerical analysis we study these properties and tradeoffs.

We investigate efficient schemes for data communication from a server (base station and access point) to a mobile terminal over a wireless channel of randomly fluctuating quality. The terminal user generates requests for data items. If the buffer (cache) of the terminal contains the requested data, no access delay/latency is incurred. If not, the data is downloaded from the server, and until becoming available locally at the terminal, the user incurs a delay cost. Moreover, a transmission/power cost is incurred to transmit the data over the wireless link at a dynamically selected power level. To lower both the access delay and transmission costs, the system may prefetch data predictively and cache them on the terminal (especially during high-link-quality periods), anticipating future user requests. The goal is to jointly minimize the overall latency and power costs by dynamically choosing what data to (pre)fetch, what power level to use, and when to use it. We develop a modeling framework (based on dynamic programming and controlled Markov chains) that captures essential performance trade-offs. It allows for the computation of optimal decisions regarding what data to (pre)fetch and what power levels to use. To cope with emerging complexities, we then design efficient online heuristics whose simulation analysis demonstrates substantial performance gains over standard approaches.

Media streaming over wireless links is a challenging problem due to both the unreliable, time-varying nature of the wireless channel and the stringent delivery requirements of media traffic. In this paper, we use joint control of packet scheduling at the transmitter and content-aware playout at the receiver, so as to maximize the quality of media streaming over a wireless link. Our contributions are twofold. First, we formulate and study the problem of joint scheduling and playout control in the framework of Markov decision processes. Second, we propose a novel content-aware adaptive playout control, that takes into account the content of a video sequence, and in particular the motion characteristics of different scenes. We find that the joint scheduling and playout control can significantly improve the quality of the received video, at the expense of only a small amount of playout slowdown. Furthermore, the content-aware adaptive playout places the slowdown preferentially in the low-motion scenes, where its perceived effect is lower.

Abstract We investigate joint transmission power control and playout buffer control for packetized media streaming over wireless links. We propose a novel model formulation that tracks the play/freeze duration and play/freeze switch jitter to control the transmission power and playout rate (1 or 0, i.e., play or rebuffer). The model is especially appropriate for audio/music streaming. The optimal joint control is obtained using a Dynamic Programming approach to balance the average power used against achieved quality of service (QoS), reflecting play/freeze duration and jitter frequency. We also investigate two key special cases, where either only power control or rebuffer control is exercised; we obtain certain useful provable structural properties of these individual side controls. Based on those, we also design a low‐complexity heuristic control that ‘mimics’ the obtained structural properties of the optimal ones. Through simulation we see that the developed controls can achieve substantially higher performance over standard benchmark schemes. Copyright © 2008 John Wiley & Sons, Ltd.

In this brief paper, we formulate a novel analytical framework for modeling and mitigation of dynamically changing security risk profiles in information systems and networks. Risk accumulates at components/nodes (hosts, servers, databases, etc.) due to risk shocks hitting them (virus, worm attacks, etc.) and is monitored by risk indicators. The risk manager dynamically chooses defenses by reconfiguring and allocating available protection resources to various infrastructure components/nodes. The issue is to dynamically control risk by (re)deploying defenses on the spot in response to changing risk indicators. The framework is designed to parallel queuing modeling ones, mapping backlog/congestion to risk level/stress. This exposes interesting connections between dynamic risk management and queueing systems. It also allows for leveraging some results of congestion management for risk mitigation, as well as developing new ones to capture risk management performance tradeoffs.

We study playout buffer management at the receiver for supporting multimedia streaming services over unreliable wireless links. On one hand, memory is a precious resource on portable wireless devices and must be used judiciously. On the other hand, allocating a big playout buffer to a media streaming application reduces the probability of a playout interruption/freeze due to buffer underflow, thus improving the user's perceived experience. Thus, inherent in the wireless media streaming scenario is a tradeoff between memory utilization and quality-of-service (QoS) delivered to the application layer. We study this buffer vs. QoS tradeoff in a dynamic programming (DP) framework. Within the same setting, we also address the issue of determining the optimal rebuffering level when the buffer underflows. Leveraging closed form solutions obtained for a special case of our formulation, we propose BuM, a very low complexity heuristic dynamic buffer management algorithm. The near optimality of BuM, as demonstrated by experimental results, in conjunction with its ease of implementation, makes it an attractive option from a practical perspective.

In this paper, we examine the wireless network power control problem. We first consider two approaches that have evolved in parallel, catering to distinct concerns: (a) a distributed approach with convergence to 'hard' SIR targets, introduced by Foschini and Miljanic [1] and (b) an incentive- based, game theoretic approach, investigated by Saraydar, Man- dayam, and Goodman [2] among others. We then seek to reconcile these two approaches and explore the rich space in between by formulating a utility-based model in which users have 'soft' SIR targets. We prove that, under certain cost conditions, a Nash Equilibrium of the resulting game is identical to the convergence point of the Foschini-Miljanic (FM) algorithm. Thus, one can use the latter in an incentive-compatible way. If these conditions are not met, however, then the system necessarily will operate at a non-FM point, i.e. one in which some SIR targets are not attained. We propose an algorithm for this case and show by simulation that the resulting Nash points may have desirable power efficiency properties. Thus, under our model, the network can be either aligned or not aligned with the FM scheme, each of which potentially has its advantages.

We address the problem of scheduling multiple traffic streams associated with target profiles on a shared wireless link, arising in real-time applications with soft/flexible deadline constraints (e.g. multimedia streaming). A target profile specifies the inter-packet deadline constraints for a user's traffic stream, or equivalently, the time instants at which the user should ideally receive packets to ensure uninterrupted multimedia playout. Contention for the shared link and fluctuations in wireless channel quality prevent users from being served in accordance with their desired target profiles. The goal of the scheduler is to dynamically schedule users to ensure that their target profiles are adhered to as closely as possible. We formulate the scheduling problem in a dynamic programming (DP) framework. Leveraging key structural properties of the optimal control to the DP, we propose our heuristic MinProj scheduling policy. We experimentally demonstrate the efficacy of MinProj over benchmark schedulers. The computational complexity of MinProj grows only linearly with the number of users in the system. Further, MinProj is agnostic to statistical assumptions on input traffic or channel behavior. These features make MinProj an attractive policy to implement in real wireless systems.

High power dissipation in packet switches and routers is fast turning into a key problem, owing to increasing line speeds and decreasing chip sizes. To address this issue, we introduce and develop the notion of a power-managed input-queued (PMIQ) switch in this paper. A PMIQ switch is an input-queued switch with an additional hierarchy of control to regulate the power dissipated by the switch. We formulate the joint scheduling and power management problem for a PMIQ switch as a dynamic program (DP). Leveraging intuition gained from provable structural properties of the optimal solution to the DP, we propose the power-aware switch scheduling (PASS) switch management policy. PASS dynamically selects the rate/speed at which the switch operates, in conjunction with the switch configuration, as a function of the backlogs of the input buffers. PASS can easily be tuned to tradeoff high power consumption for larger queuing delays. Experimental results show that PASS yields an attractive power-delay tradeoff relative to the benchmark maximum weight matching (MWM) scheduler. The low computational complexity of PASS makes it amenable to implementation in large, high-speed switches.

In this paper, we introduce a new scheme called SecureRank for prioritizing vulnerabilities to patch in computing systems/networks. This has become a key issue for IT infrastructures, as large numbers of vulnerabilities are continuously announced and IT administrators devote increasingly more resources to managing them. SecureRank prioritizes vulnerabilities and network nodes to patch based on the percentage of time a random attacker would spend trying to exploit them. Going beyond state-of-the-art approaches, SecureRank takes into account the network topology and potential node interactions in calculating their relative risk and priority. We define two metrics for the security of a network and use them to show how SecureRank outperforms key industry benchmarks in certain natural operational settings. We believe that these findings can be used as a starting point in exploring what defense strategies make sense given topology and attack strategy.

Due to the increase in diversity of wireless devices, streaming media systems must be capable of serving multiple types of users. Scalable coding allows for adaptations without re-encoding. To account for various viewing capabilities of each user, such as different spatial resolutions, multiple distortion measures are used. In this paper, we examine the question of how to broadcast media packets with multiple distortion measures to multiple users. We cast the problem as a stochastic shortest path problem and use Dynamic Programming to find the optimal policy. We generate an offline algorithm to generate the optimal transmission policy for the general case. We then show the optimal policy can be done online via a simple threshold policy for the case of independent Bernoulli packet losses. Through experimental results, we show that our policy, which considers multiple distortion measures, achieves up to 2dB gains over conventional approaches.

We address the problem of distributed power control for supporting packetized traffic in wireless ad hoc networks (e.g. 802.11 based wireless LANs). The interference experienced by a link coexisting with other links in a shared wireless medium is responsive to the actions of the transmitter on the link. Consequently, the evolution of seemingly independent queues at autonomously acting transmitters is tightly entangled through the shared wireless channel. Thus, an exact analysis of the distributed power control problem which also incorporates queuing dynamics is intractable. To establish a performance benchmark, we first design the optimal centralized backlog aware power control algorithm (Oracle) in a dynamic programming (DP) framework. We then propose a heuristic backlog aware distributed power control algorithm (BDD). The implementation of BDD is based on randomized selection from lookup tables which are computed offline at each transmitter. The computational complexity and memory requirements for BDD are independent of the network size and topology, making it attractive from a practical perspective. Experimental results demonstrate that BDD closely matches Oracle in performance and enhances system throughput by 20-30% compared to benchmark backlog insensitive power control algorithms (e.g. Foschini-Miljanic).

Next-generation cellular wireless communication networks aim to provide a variety of quality-of-service (QoS)-sensitive packet-based services to downlink users. Included among these are real-time multimedia services, which have stringent delay requirements. Downlink packet scheduling at the base station plays a key role in efficiently allocating system resources to meet the desired level of QoS for various users. In this paper, we employ dynamic programming (DP) to study the design of a downlink packet scheduler capable of supporting real-time multimedia applications. Under well-justified modeling reductions, we extensively characterize structural properties of the optimal control associated with the DP problem. We leverage intuition gained from these properties to propose a heuristic scheduling policy, namely, Channel-Aware Earliest Due Date (CA-EDD), which is based on a "quasi- static" approach to scheduling. The per-time-slot implementation complexity of CA-EDD is only O(K) for a system with K downlink users. Experimental results show that CA-EDD delivers up to 50 percent of performance gains over benchmark schedulers. CA-EDD achieves these performance gains by using channel and deadline information in conjunction with application layer information (relative importance of packets) in a systematic and unified way for scheduling.

Almost a decade long research on the performance of TCP in wireless networks has resulted in many proposals and solutions to the problem of TCP throughput degradation. Several of these measures, however, have their share of drawbacks. With the continuing emergence of wireless technologies ever since the work on TCP performance over wireless began, smart link-layer mechanisms like adaptive modulation and coding, power control, and incremental redundancy have been designed and deployed. In this work, we outline a cross-layer optimization framework based on the congestion control dynamics of a bulk-transfer TCP flow and demonstrate its application to networks which offer link-layer adaptive measures. We begin by observing that the TCP's congestion window dynamics are comprised of certain recurring patterns which we term as cycles. We then overlay a TCP throughput optimization methodology that selects link-layer transmission modes (e.g. modulation scheme, coding rate, transmission power, or a combination thereof) in accordance with TCP dynamics and wireless channel conditions. We provide insights into the working of the optimization procedure which protects TCP segments against losses on the wireless channel when the TCP congestion window size (in bytes) is below the bandwidth-delay product of the network. The protection against wireless channel losses is rendered by the link-layer by employing robust modulation and coding schemes, high transmission power, etc. We show that TCP dynamics aware link adaptation measures lead to substantial enhancement of TCP throughput in EGPRS and IEEE 802.11a networks

We study low jitter-scheduler design for deadline-aware input-queued (IQ) packet switches. We consider scheduling of traffic streams associated with service profiles, which reflect the inter-packet deadlines between packets constituting the stream. To make the NP-hard problem of scheduling with strict deadlines tractable, we use soft deadlines as a modeling tool, and study the scheduling problem with soft deadlines in a dynamic programming (DP) framework. We establish the optimality of a myopic scheduling policy for the canonical 2times2 crossbar switch. For bigger switches, we develop low-complexity approximations to the myopic policy (which is near-optimal), one based on the notion of neighborhood search, and two others based on convex relaxations of an integer programming problem. We demonstrate the efficacy of the proposed policies via simulations, employing good put as a performance metric. A key feature of the proposed policies is that they do not require knowledge of traffic statistics (rate, periodicity etc.), rendering them robust and amenable to implementation.

We study the problem of joint power allocation and scheduling for deadline constrained traffic on the downlink of a cellular wireless communication system, where multiple users can be scheduled simultaneously on orthogonal spreading codes (HSDPA), or sub-carriers (OFDMA), subject to a sum power constraint. We formulate the problem for a canonical two-user model within a dynamic programming (DP) framework. We present key structural properties of the optimal solution to the DP, and leverage the intuition thus gained into the fundamental power allocation and scheduling trade-offs to propose the Channel-Aware Power Allocation and Scheduling (CAPAS) policy. We demonstrate the efficacy of CAPAS relative to benchmark schedulers via simulations. The key conclusion from our work is that scheduling one user at a time is sub- optimal for deadline constrained wireless traffic, both in terms of number of missed packet deadlines, and average transmit power consumption at the base-station.

We investigate the important problem of patching vulnerabilities in highly utilized data centers with heterogeneous groups of servers. In particular, our goal is to select the patching rate so as to efficiently (if not optimally), balance the trade-off between service disruption and risk exposure due to potential exploitation of vulnerabilities. We formulate the problem using a dynamic programming approach, that captures the aforementioned tradeoff, and study the structural properties of the optimal solution. Furthermore, we focus on insightful special cases and develop low-complexity justified heuristics, which achieve significant performance gains over standard benchmarks. We also demonstrate that the heuristics are very efficient, in the sense that they perform very close to the optimal solution obtained via dynamic programming.

In this paper, we analyze the throughput of interconnection networks, viewed as multi-stage queueing networks with infinite input queues, but finite internal cross-stage ones. We find that for very general arrival processes and arbitrarily fixed network topology, the stability region with finite internal buffers is identical to that for the corresponding network with infinite internal buffers, and is achievable via special scheduling policies. In particular, we define and study a class of throughput maximizing policies, known as projective cone scheduling (PCS) algorithms, which activate a set of concurrent service rates to all queues in the network based on observed backlog levels.

Next generation wireless cellular networks will support a variety of quality-of-service (QoS) sensitive applications like streaming multimedia and high-speed data for downlink users. Channel and QoS aware downlink packet scheduling policies are going to play a key role in efficiently utilizing system resources and enhancing QoS experienced by end users. Schedulers specifically designed to support non-real-time delay tolerant services perform poorly for real-time delay sensitive services, and vice-versa. Scheduler design for supporting a heterogeneous mixture of real-time and non-real-time traffic is a relatively less studied problem. We propose a "quasi-stationary" approach to scheduling of hetergeneous traffic, which involves solving a stationary infinite horizon stochastic shortest-path problem at each scheduling instant. We thoroughly characterize the structural properties of the optimal control associated with the stationary problem, and leverage the intuition thus gained to construct a low-complexity heuristic scheduling policy. We demonstrate the efficacy of the proposed scheduler over benchmark schedulers like the exponential rule via link-level simulations.

We consider transfer of video frames over a time-varying wireless channel. When the channel is good, the transmitter can send frames at a higher rate than the receiver can consume them via playout. In that case, we introduce the idea of admitting new frames even when the receiver buffer is full, by selectively evicting frames already in the buffer; we can also control the playout rate, so as to optimize the tradeoff between video distortion and the time to freeze when the channel turns bad and frames arrive at a lower rate than should be played out. The decision/control problem of whether to admit a new frame, which already stored one to evict to accommodate the new one, and at what rate to play out frames is formulated within a dynamic programming framework, and an interesting connection to the Knapsack problem is made. Application of the idea in a relevant simple system shows significant performance gains, indicating that it is a promising approach for improving video delivery performance over challenging wireless channels

We study distributed power control for supporting real-time multimedia traffic over multiple access wireless links. The responsive nature of interference observed on wireless links coupled with the absence of a central co-ordinating entity makes distributed design a challenging problem. A trade-off between transmit power control and quality-of-service (QoS) arises naturally in such a setting. While transmitting at low power is socially beneficial in terms of reducing interference experienced by other links, it degrades the QoS experienced by the receiver. We capture this trade-off within a dynamic programming (DP) framework. We study the structural properties of the optimal power control policy under the assumption of unresponsive interference, and leverage the intuition thus gained to design power control policies for a responsive interference environment. We argue that the optimal policy has key fundamental differences compared to the classical Foschini-Miljanic type distributed power control. We demonstrate the efficacy of the proposed policies via simulation. We invoke the idea of inter-packet deadlines (IPD) to characterize real-time traffic, which leads to a tremendous reduction in the complexity of the state-space of the DP

Migrating (uploading) encrypted file blocks from mobile wireless devices to network servers for decryption provides substantial performance gains, including (i) reduced battery drain at the device, and (ii) fast execution at server’s powerful processors. This, however, introduces the risk of communicating through an unreliable wireless channel of varying (soft) connectivity, which can induce substantial performance degradation. To address the dilemma of decrypting blocks locally at the device, or remotely at the network server, we develop a parsimonious stochastic model that leverages the Dynamic Programming methodology and captures the dominant performance trade-offs. Based on this model, we obtain efficient algorithms for making upload decisions, as well as power management at the wireless device. Of particular interest is the case of RSA decoding at wireless sensors where the developed algorithms are demonstrated to achieve substantial performance gains over conventional approaches.

Media streaming applications over wireless links face various challenges, due to both the nature of the wireless channel and the stringent delivery requirements of media traffic. In this paper, we seek to improve the performance of media streaming over an interference-limited wireless link, by using appropriate transmission and playout control. In particular, we choose both the power at the transmitter and the playout scheduling at the receiver, so as to minimize the power consumption and maximize the media playout quality. We formulate the problem using a dynamic programming approach, and study the structural properties of the optimal solution. We further develop a justified, low-complexity heuristic that achieves significant performance gain over benchmark systems. In particular, our joint power-playout heuristic outperforms: 1) the optimal power control policy in the regime where power is most important and 2) the optimal playout control policy in the regime where media (playout) quality is most important; furthermore, this heuristic has only a slight performance loss as compared to the optimal joint power-playout control policy over the entire range of the investigation

Portable devices (such as personal digital assistants and laptops with wireless connectivity) are becoming ubiquitous. As their functionality and capabilities increase, their energy consumption requirements also increase. Yet, these devices have to operate on limited batteries. In order to maximize the battery lifetime, it is necessary to optimize the use of energy at various components of such a device. In this paper, we consider a single portable device operating on a limited battery that transmits information over an interference-limited wireless channel. We seek to optimize the power consumption on the communication radio in this device, by controlling both the operation mode and the transmission power. We model the general problem using dynamic programming, obtain the optimal solutions for insightful special cases and explore various design tradeoffs. Our work provides an analytical framework for stochastic modeling and optimization of energy spent for communications in battery-operated portable devices.

We consider the problem of downlink packet scheduling in a time-slotted wireless communication system when a hybrid automatic repeat request (H-ARQ) re-transmission strategy is adopted. User level fairness and average delay per packet are two important metrics used for evaluating the performance of a scheduling policy. However, these are two competing objectives. A good scheduling policy must be flexible enough so that it can be tuned to trade-off one objective for another. We propose one such scheduling policy characterized by a single parameter that can be varied to capture points on the trade-off curve. Our approach is to study two reduced versions of the original problem and construct delay and fairness optimal scheduling policies based on the optimal solutions to these reduced problems. We then leverage intuition from these optimal policies to design a heuristic scheduler that captures the fairness v/s delay trade-off. We demonstrate the efficacy of the proposed scheduler over benchmark schedulers like round-robin (RR), maximum SNR or C/I and proportional fair (PF) via link level simulations. The proposed policy offers a superior fairness and delay performance and is also low complexity from an implementation perspective

We investigate autonomic power control policies for Internet servers and data centers. In particular, by monitoring the system load and thermal status, we decide how to vary the utilized processing resources to achieve acceptable delay and power performance. We formulate the problem using a dynamic programming approach that captures the power-performance tradeoff. We study the structural properties of the optimal solution and develop low-complexity justified heuristics, which achieve significant performance gains over standard benchmarks. The performance gains are higher when the load exhibits stronger temporal variations. We also demonstrate that the heuristics are very efficient, in the sense that they perform very close to the optimal solution obtained via dynamic programming.

Recent research in packet switch scheduling algorithms has moved beyond throughput maximization to quality of service (QoS) control. Several classes of algorithms have been shown to achieve maximal throughput under certain system conditions. Between classes and within each class, QoS performance varies based on arrival traffic and properties of the scheduling algorithm being utilized. Here we compare two classes of throughput-maximizing algorithms and their performance with respect to buffer sizes. These classes are randomized algorithms, which can be characterized as offline algorithms, and projective cone scheduling algorithms, which are online since they respond to the current workload in the system. In each class, parameters can be fine-tuned to reflect the priorities of individual switch ports. We show how the online algorithms lead to significantly better quality of service performance.

Although the problem of mal-performance of TCP in the wireless scenario has been extensively addressed, an integrated solution has remained undeciphered. Conventionally, measures have been suggested to either adapt or shield TCP from non-congestion losses over the wireless channel. On the other hand, the issues of wireless channel compensation and error control for achieving a better quality channel, have been extensively studied too. Recent efforts to investigate joint approaches do not model TCP dynamics over wireless channel, but study the impact of power control and link layer error correction mechanisms in relation to standard TCP throughput models. In this work, we propose and evaluate transmission power adaptation as an integrated solution to mal-performance of TCP in wireless networks. The congestion control dynamics of bulk-transfer TCP flow are modeled for the wireless channel, and an optimization framework is delineated. Based on dynamic programming solutions and low-complexity heuristics, adaptive power control measures are suggested and analyzed for their merit. Via simulations, we demonstrate that suitable power adaptation can lead to a considerable improvement in TCP throughput for slow and fast fading channels.

Media streaming over wireless links is a challenging problem due to both the unreliable, time-varying nature of the wireless channel and the stringent delivery requirements of media traffic. In this paper, we use joint control of packet scheduling at the transmitter and content-aware playout at the receiver, so as to maximize the quality of media streaming over a wireless link. Our contributions are twofold. First, we formulate and study the problem of joint scheduling and playout control within a dynamic programming framework. Second, we propose a novel content-aware playout control, that takes into account the content of a video sequence, and in particular the motion characteristics of different scenes. We find that the joint scheduling and playout control can significantly improve the quality of the received video, at the expense of only a small amount of playout slowdown. Furthermore, thanks to the content-aware playout, the slowdown takes place mainly in the low-motion scenes, where its perceived effect is limited

We introduce1 a novel probabilistic modeling2 framework, which captures key performance tradeoffs arising in information network security. Given a set of resources available to protect and defend a network, how should those be dynamically configured to maximize the protection level? Different resource configurations enable various network defense modes. Besides the capital and operational costs of the resources, there are also ‘invasiveness’ costs associated with stresses that network users experience due to protection measures. How should these costs be balanced and how should the network dynamically configure its protection resources to efficiently defend itself? Taking a risk management point of view, we develop a parsimonious flexible model, capturing the above issues in a unified manner. The model enables the formulation of key optimization schemes for dynamically controlling the network defense modes via on-line algorithms. It provides a systematic design framework for ‘self-defending’ networks that can autonomously maintain their integrity in the presence of changing adverse conditions.

In this work we assess the performance of a WLAN in different vehicular traffic and mobility scenarios. Furthermore, we investigate ad-hoc routing for a vehicular network. We deploy a topology consisting of vehicles bearing laptop computers equipped with IEEE 802.11b compliant equipment. Test scenarios for WLAN assessment are varied by conducting experiments under different vehicular mobility, peer-distance and driving environment conditions. The network throughput and the quality of the channel are observed to degrade with increasingly stressful communication scenarios. Based on empirical observations, we present results that can facilitate the development of efficient applications for inter-vehicular communication. To address multihop routing, we investigate and demonstrate the application of link connectivity assessment to efficient ad-hoc routing. A framework for enhancements is delineated and incorporated in the implementation of the optimized link state routing (OLSR) protocol. We demonstrate that the link quality assessment based enhancements improve the performance of OLSR.

We address the issue of power-controlled shared channel access in wireless networks supporting packetized data traffic. We formulate this problem using the dynamic programming framework and present a new distributed fuzzy reinforcement learning algorithm (ACFRL-2) capable of adequately solving a class of problems to which the power control problem belongs. Our experimental results show that the algorithm converges almost deterministically to a neighborhood of optimal parameter values, as opposed to a very noisy stochastic convergence of earlier algorithms. The main tradeoff facing a transmitter is to balance its current power level with future backlog in the presence of stochastically changing interference. Simulation experiments demonstrate that the ACFRL-2 algorithm achieves significant performance gains over the standard power control approach used in CDMA2000. Such a large improvement is explained by the fact that ACFRL-2 allows transmitters to learn implicit coordination policies, which back off under stressful channel conditions as opposed to engaging in escalating "power wars."

We investigate a power-controlled transmission scheme for streaming media traffic in an interference-limited wireless environment, where many data-packet links (transmissions) coexist with the streamed media link. The transmissions from individual links in the system interfere with each other. The media server (source) transmits encoded media packets to the client (user) over the media link. The client stores the received packets into a fixed-size buffer and plays them out at a constant rate. Due to random and response-induced interference, the source needs to adapt its transmission power and rate to guarantee a certain level of received media quality (QoS) and to minimize the average power (energy consumption), thus to reduce the interference perceived by other links in the system. The QoS is primarily measured by the distortion due to packets missing their playtime deadlines at the receiver. We develop a modelling framework to identify the characteristics of the optimal power/rate control policy. Based on these characteristics, we propose two practical heuristic algorithms designed to operate in realistic interference-limited environments. Through simulation, the proposed algorithms show significant performance improvements when compared to standard benchmarks.

This paper presents new distributed power and admission control algorithms for ad-hoc wireless networks in random channel environments. Previous work in this area has focused on distributed control for ad-hoc networks with fixed channels. We show that the algorithms resulting from such formulations do not accurately capture the dynamics of a time-varying channel. The performance of the network in terms of power consumption and generated interference can be severely degraded when power and admission control algorithms that are designed for deterministic channels are applied to random channels. In particular, some well-known optimality results for deterministic channels no longer hold. In order to address these problems we propose a new criterion for power optimality in ad-hoc wireless networks. We then show that the optimal power allocation for this new criterion can be found through an appropriate stochastic approximation algorithm. We also present a modified version of this algorithm for tracking nonstationary equilibria, which allows us to perform admission control. Ultimately, the iterations of the stochastic approximation algorithms can be decoupled to form fully distributed on-line power and admission control algorithms for ad-hoc wireless networks with time-varying channels.

Recently, extensive analytic research into packet scheduling in crossbar switches has yielded interesting throughput maximizing algorithms. Surprisingly, however, quality of service (QoS) performance associated with these algorithms has only been approximated through simulation. We present here certain randomized algorithms with analytic QoS. These are simple to implement and possess closed form expressions for various performance measures. By fine tuning particular parameters of these algorithms, one can vary the QoS associated with the individual ports as desired. This allows cost and utility optimization, a feature which was not feasible under previously studied packet scheduling algorithms.

We consider the (generalized) packet switch scheduling problem, where the switch service configuration has to be dynamically chosen based on observed queue backlogs, so as to maximize the throughput. A class of recently developed 'projective' scheduling algorithms, which substantially generalize the well-known maximum weight matching (MWM) algorithms for crossbar switches, are explored from the perspective of complexity. The typically huge number of possible switch configurations that the scheduler has to consider in each timeslot has been previously observed to lead to an impractical computational requirement. We introduce a new class of projective schedules based on 'local search' concepts. In particular, rather than searching the entire (typically huge) set of available service configurations to find the best one, the new scalable scheduling algorithms search 'locally' over a small neighborhood of service configurations to find a 'better' one in each time slot. We show that local projective scheduling algorithms can provide dramatic reduction in complexity without causing any loss of throughput (although they may observe higher delay). We explore the nature and structure of such schedules, which show a much higher promise for practical implementation than their global versions.

This paper presents new distributed power and admission control algorithms for ad-hoc wireless networks in random channel environments. Previous work in this area has focused on distributed control for ad-hoc networks with fixed channels. We show that the algorithms resulting from such formulations do not accurately capture the dynamics of a time-varying channel. Hence, algorithms designed for fixed channels may perform quite poorly in random channels. In order to address these issues, this work proposes new algorithms, based on stochastic approximation, for optimal distributed power and admission control in random channels

We introduce a probabilistic framework, based on service risk mitigation and disruption management, for the problem of capacity protection in optical networks. This contrasts the established deterministic approach of designing the protection network to guarantee no service disruption for up to M failures. We present the novel problem formulation and establish a framework for optimal network design in this extended abstract, while leaving the detailed optimization results and algorithms for the full paper (N. Bambos et al., 2003).

Prefetching is a technique for lowering the access delay by making data available in anticipation of future requests. Correspondingly, power control has been proposed in wireless networks for the efficient use of the wireless resources and low energy consumption at the transmitters. This work investigates the two techniques jointly (1) for communications over a fluctuating wireless channel whose dynamics and statistics is unknown, and (2) explore approximating schemes for exercising deep prefetching. In short, a user uses a wireless terminal to access various data items residing at a server over a wireless network. Every requested item not found in the cache of the terminal incurs to the system (1) an access delay cost, and (2) an energy/network cost to download it over the wireless link. To minimize the total cost, the system may either (i) postpone the transmissions when the link quality is sensed to be low, or reversely, (ii) proactively prefetch data items during link quality 'highs', in anticipation to future user requests. The decision therefore involves choosing when and what to (pre)fetch, and at what power level. To quantify on the above, we formulate the problem in the context of controlled Markov chains using the technique of dynamic programming. After analyzing the structure of the problem, we construct a set of policies based on justified heuristics for taking near-to-optimal decisions. Simulation is then used to quantify on the performance gains over standard schemes.

We investigate the technique of the task migration from mobile terminals to computation servers over the wireless network. In the perceived architecture, the mobile terminals are assisted by the network infrastructure in the execution of their computational tasks. Thus, the terminal has two basic options (and combinations of them): A) local execution, that is execute the tasks locally, or B) remote execution, which involves (1) sending the tasks to a computation server over the wireless network, (2) executing the tasks at the server, and (3) downloading the computation results back to the terminal. The latter provides energy savings for the terminal (sparing its local processor) and execution speed gains (the server is usually much faster than the terminal), but incurs some overhead as well, resulting from the terminal /spl harr/ server wireless communication. The net gains, if any, are dependent on (i) the degree of the connectivity between the terminal and the network server, and (ii) the server load. Both these two parameters fluctuate with time; the former due to the varying network load and the volatile wireless channel, and the latter due to the sharing with other clients at the server. To decide optimally on the execution policy, we introduce a Markovian framework. We then study the associated energy vs. delay trade-offs, and assess the performance gains attained in various test cases compared to the conventional paradigms of the exclusively local/remote execution.

We investigate the problem of packet relaying in power-controlled wireless data networks. For reasons of limited range or energy efficiency, packets are not transmitted from the source to the destination nodes directly, but in two hops via an intermediary relay node. The nodes are equipped with buffers to store the incoming packets while they take turns to transmit. The communication takes place over wireless links whose quality fluctuates due to fading and interference from other users. At each point in time, the system has to decide (i) which transmitter takes possession of the channel, and (ii) the power level at the transmitter. On adverse channel conditions, the system can even decide to refrain from all transmissions (back-off), waiting for the links to improve before resuming transmissions. Clearly, this dilemma induces the fundamental trade-off between packet delay and transmission power. In a delay-sensitive configuration, the transmitters prefer to remain always active so as to keep the packet backlogs at the queues low. On the contrary, a power-sensitive configuration favors the use of back-off, resulting in low transmission power levels at the cost of increased packet delay and high packet backlogs. Overall, the decision is taken based on (i) the state of the wireless links, and (ii) the backlog size of the queues. Toward designing efficient transmission schemes, we model the system as a controlled Markov chain and formulate the optimization problem in the context of dynamic programming. We construct a set of transmission schemes by analyzing the system dynamics, which are evaluated over standard approaches and shown to achieve significant performance gains.

A time-domain wavelength interleaved network (TWIN) (Widjaja, I. et al., IEEE Commun. Mag., vol.41, 2003) is an optical network with an ultrafast tunable laser and a fixed receiver at each node. We consider the problem of scheduling bursts of data in a TWIN. Due to the high data rates employed on the optical links, the burst transmissions typically last for very short times compared with the round trip propagation times between source-destination pairs. A good schedule should ensure that: 1) there are no transmit/receive conflicts; 2) propagation delays are observed; 3) throughput is maximized (schedule length is minimized). We formulate the scheduling problem with periodic demand as a generalization of the well-known crossbar switch scheduling. We prove that even in the presence of propagation delays, there exist a class of computationally viable scheduling algorithms which asymptotically achieve the maximum throughput obtainable without propagation delays. We also show that any schedule can be rearranged to achieve a factor-two approximation of the maximum throughput even without asymptotic limits. However, the delay/throughput performance of these schedules is limited in practice. We consequently propose a scheduling algorithm that exhibits near optimal (on average within ∼7% of optimum) delay/throughput performance in realistic network examples.

We investigate efficient schemes for data communication from a server to a mobile terminal over a wireless channel of fluctuating quality. A user requests to access various data items on the terminal. If a requested item is found in the local terminal buffer or cache, no access delay is incurred. If not, it is downloaded from the server and the user incurs a delay cost until it becomes locally available. Moreover, a power cost is incurred to transmit the data item at a selected power level over the wireless link. To lower both the average delay and power costs, the system may prefetch data items and predictively cache them on the terminal - especially during link quality 'highs' - in anticipation of future user requests. The goal is to minimize the overall delay and power cost, by judiciously choosing which data item to fetch and what power level to use, given the current user, buffer, and channel states. We develop a modeling framework - based on controlled Markov chains and dynamic programming - capturing the essential performance tradeoffs in the system and allowing computation of optimal decisions on items to (pre)fetch and power levels to use. To cope with emerging complexities, we then design efficient heuristics, whose simulation analysis demonstrates substantial performance gains over standard approaches.

In this paper, we investigate power control algorithms for wireless networks utilizing groupwise serial multiuser detection (GSMD), which has recently emerged as an important technology for supporting multirate services over wireless channels. Under GSMD, users are clustered according to their transmission rate/power. Higher rate/power users are detected first, and their signals arc cancelled out before detection of lower rate/power ones, in a sequential manner. We investigate power control algorithms with active link protection for GSMD technologies, which can obtain significant performance gains by utilizing multiuser detection.

We investigate novel channel access schemes for packetized wireless networks, which can dynamically switch between distinct transmission modes in order to better match the channel state and deliver packets to the receiver with higher success probability (rate). We call them multimodal dynamic multiple access-MDMA schemes. Based on the observed channel impairment state (typically a combination of interference, fading, multipath, etc.) and the transmitter queue packet backlog at any time instant (slot), each user autonomously selects the best transmission mode to activate and power level to transmit at. First, a general formulation of the MDMA problem is introduced in several methodological steps of progressive complexity. It is based on dynamic programming and captures the basic tradeoffs. Analytical issues are not pursued in detail here, but instead several ubiquitous structural properties of MDMA schemes are identified and explored. Based on those, a novel suite of MDMA algorithms is designed and evaluated. On a simulated baseline scenario, MDMA is shown to achieve over 30% higher throughput than previously studied raw PCMA schemes and even higher performance gains over other standard benchmark ones. This indicates that MDMA schemes can release 'latent' network capacity which is suppressed by others, and should be further explored. This study is a first step towards designing full MDMA protocols for high-performance wireless packet networks.

We address the issue of power-controlled shared channel access in future wireless networks supporting packetized data traffic, beyond the voice-oriented continuous traffic primarily supported by current-generation networks. First, some novel formulations of the power control problem are introduced, which become progressively more general by incorporating various relevant costs. The analysis of the models under simple, yet natural, assumptions yields certain ubiquitous structural properties of 'optimal' power control algorithms. Based on such structural properties, we design a new family of distributed and asynchronous PCMA algorithms and evaluate them experimentally by simulation. They are found to perform substantially better than a standard benchmark algorithm for power control. This is a first step towards the design of full PCMA protocols for autonomous channel access in high-performance wireless networks.

A distributed power-control algorithm with active link protection (DPC/ALP) is studied in this paper. It maintains the quality of service of operational (active) links above given thresholds at all times (link quality protection). As network congestion builds up, established links sustain their quality, while incoming ones may be blocked and rejected. A suite of admission control algorithms, based on the DPC/ALP one, is also studied. They are distributed/autonomous and operate using local interference measurements. A primarily networking approach to power control is taken here, based on the concept of active link protection, which naturally supports the implementation of admission control. Extensive simulation experiments are used to explore the network dynamics and investigate basic operational effects/tradeoffs related to system performance.

We examine the problems of routing and server assignment in networks with random connectivities. In such a network the basic topology is fixed, but during each time slot and for each of its input queues, each server (node) is either connected to or disconnected from each of its input queues with some probability. During each time slot a server must decide which of its connected input queues to serve and into which of its output queues the completed job should be placed. For single-input single-output acyclic queueing networks with random connectivities, we show that the joint routing/service policy that routes customers along the least populated path to the destination and serves any non-empty queue maximizes throughput. We briefly discuss some implementation aspects of the proposed policy, including its robustness in stabilizing the system with respect to delayed state information.

For wireless networks, time division multiple access (TDMA) offers certain well-known advantages over methods such as spread spectrum code division (CDMA). Foremost among them is the guarantee that other users will not interfere during a node's dedicated time slots. For this desirable isolation, the cost is synchronization. Viewing arbitrary time intervals as potential TDMA time slots, we ask whether it is possible to obtain some of the benefit of time division without incurring the synchronization cost. In particular, we address the question of whether a TDMA-like state can be induced on asynchronous channels in such a way as to reduce interference and energy consumption. Through analysis and simulation we find conditions under which it is desirable to use time division. We then show how autonomous power management may be used as a mechanism to induce a form of time division. In this context a backlog-sensitive power management system is presented.

We consider the message routing/broadcasting problem in an optically interconnected massively parallel processing system, where each node in the system sends/broadcasts randomly generated packets to others. The network model considered is the reconfigurable optical interconnect (ROI). It is based on the new device capabilities enabled by recent advances in optical technology. A ROI node can use light beams to transmit messages to any other nodes in the network, provided that no others transmit to the same destination concurrently. We present communication schemes that can achieve near optimal throughput with significantly lower delay. The difference in performance for routing is on the order of /spl Omega/(n/sup 2/3/ log log n/log n) when the number of nodes n in the network is large.

We address the problem of how a mobile node in a wireless network should vary its transmitter power so that energy consumption is minimized, subject to fixed quality-of-service constraints. Optimal solutions are obtained for channels with stationary, extraneous interference. A simple dynamic power management algorithm based on these solutions is developed. The algorithm is tested by a series of simulations, including the extraneous-interference case and the more general case where multiple, mutually interfering transmitters operate in a therefore highly responsive interference environment. Results show improved network capacity and stability in addition to substantially improved battery life at the mobile terminals.

Presents a distributed power control scheme, which maintains the signal/interference ratios (SIRs) of operational (active) links above their required thresholds at all times (link quality protection), while new users are being admitted; furthermore, when new users cannot be successfully admitted, existing ones do not suffer fluctuations of their SIRs below their required thresholds values. The authors also present two admission/rejection control algorithms, which exercise voluntary drop-out of links inadmissible to the network so as to reduce interference and possibly facilitate the admission of other links.

Integrated multiplexing schemes are needed to optimize the use of transmission bandwidth in integrated networks. In this paper, we introduce the idea of a dynamically controlled (T/sub 1/, T/sub 2/) multiplexing scheme. The advantages of this transmission policy is that it allocates the transmission capacity of the channel to two traffic types according to the instantaneous needs. We consider only two types of traffic, voice band traffic and digital data. The channel access times for voice and data are T/sub 1/ and T/sub 2/, respectively. In this paper, we present some preliminary results of our proposed scheme. In our simulations, we observe that a reduction in blocking probability of 15% or more is possible.

When new mobiles are admitted in some channel of a wireless communication network traditional power control algorithms cannot foresee the effect that new admissions have on the signal-to-interference ratios (SIR) of active mobiles already using the channel, and may cause fluctuations of their SIR below acceptable levels during the process. The authors present two algorithms that manage transmission power and channel admissions jointly to maintain the SIR of all links above some quality factor /spl gamma/ at all times. This joint control of power and channels results in high channel reuse.>

The general problem of parallel (concurrent) processing is investigated from a queuing theoretic point of view. As a basic simple model, consider infinitely many processors that can work simultaneously, and a stream of arriving jobs, each carrying a processing time requirement. Upon arrival, a job is allocated to a processor and starts being executed, unless it is blocked by another one already in the system. Indeed, any job can be randomly blocked by any preceding one, in the sense that it cannot start being processed before the one that blocks it leaves. After execution, the job leaves the system. The arrival times, the processing times and the blocking structures of the jobs form a stationary and ergodic sequence. The random precedence constraints capture the essential operational characteristic of parallel processing and allow a unified treatment of concurrent processing systems from such diverse areas as parallel computation, database concurrency control, queuing networks, flexible manufacturing systems. The above basic model includes the G/G/1 and G/G/∞ queuing systems as special extreme cases. Although there is an infinite number of processors, the precedence constraints induce a queuing phenomenon, which, depending on the loading conditions, can lead to stability or instability of the system. In this paper, the condition for stability of the system is first precisely specified. The asymptotic behavior, at large times, of the quantities associated with the performance of the system is then studied, and the degree of parallelism, expressed as the asymptotic average number of processors that work concurrently, is computed. Finally, various design and simulation aspects concerning parallel processing systems are considered, and the case of finite number of processors is discussed. The results proved for the basic model are then extended to cover more complex and realistic parallel processing systems, where each job has a random internal structure of subtasks to be executed according to some internal precedence constriants.