In classification tasks, it is critical to accurately distinguish between specific classes, as misclassifications can undermine system reliability and user trust. In this paper, we study how client selection in both centralized and federated learning environments affects the performance of classification models trained on heterogeneous data. When training datasets across clients are statistically diverse, careful client selection becomes crucial to improve the ability of the model to discriminate between classes, while preserving privacy. In particular, we introduce a novel metric based on conformal prediction outcomes – the conformal correlation matrix – which captures the likelihood of class pairs co-occurring within conformal prediction sets. Unlike the traditional confusion matrix, which quantifies actual misclassifications, our metric characterizes potential ambiguities between classes, thus offering a complementary perspective on model performance and uncertainty. Through a series of examples, we demonstrate how our proposed metric can guide informed client selection and enhance model performance in both centralized and federated training settings. Our results highlight the potential of conformal-based metrics to improve classification reliability while safeguarding sensitive information about individual client data.

While neural lossy compression techniques have markedly advanced the efficiency of Channel State Information (CSI) compression and reconstruction for feedback in MIMO communications, efficient algorithms for more challenging and practical tasks—such as CSI compression for future channel prediction and reconstruction with relevant side information—remain underexplored, often resulting in suboptimal performance when existing methods are extended to these scenarios. To that end, we propose a novel framework for compression with side information, featuring an encoding process with fixed-rate compression using a trainable codebook for codeword quantization, and a decoding procedure modeled as a backward diffusion process conditioned on both the codeword and the side information. Experimental results show that our method significantly outperforms existing CSI compression algorithms, often yielding over twofold performance improvement by achieving comparable distortion at less than half the data rate of competing methods in certain scenarios. These findings underscore the potential of diffusion-based compression for practical deployment in communication systems.

Risk-averse modeling is critical in safety-sensitive and high-stakes applications. Conditional Value-at-Risk (CVaR) quantifies such risk by measuring the expected loss in the tail of the loss distribution, and minimizing it provides a principled framework for training robust models. However, direct CVaR minimization remains challenging due to the difficulty of accurately estimating rare, high-loss events—particularly at extreme quantiles. In this work, we propose a novel training framework that synthesizes informative samples for CVaR optimization using score-based generative models. Specifically, we guide a diffusion-based generative model to sample from a reweighted distribution that emphasizes inputs likely to incur high loss under a pretrained reference model. These samples are then incorporated via a loss-weighted importance sampling scheme to reduce noise in stochastic optimization. We establish convergence guarantees and show that the synthesized, high-loss-emphasized dataset substantially contributes to the noise reduction. Empirically, we validate the effectiveness of our approach across multiple settings, including a real-world wireless channel compression task, where our method achieves significant improvements over standard risk minimization strategies.

In modern wireless systems, the feedback of DownLink (DL) Channel State Information (CSI) from User Equipment (UE) to Base Stations (BS) may require substantial computational and feedback bandwidth overheads. A promising approach to improve feedback efficiency is to leverage side information which is correlated to DL CSI. Despite potential of doing so, critical aspects remain underexplored in current research, particularly the quantification of the benefits and the inherent limitations of utilizing side information. This paper addresses these gaps by introducing a novel algorithm to compute the rate-distortion function for general compression scenarios incorporating side information. We apply this algorithm to the DL CSI feedback problem having UL CSI as the side information and generate rate-distortion functions. Using the estimated rate-distortion functions, we measure the gain of side information over diverse feedback rates and UE mobility profiles. The results reveal that the benefits of leveraging side information are particularly significant for UEs characterized by high mobility and constrained to operate at low feedback overheads.

We introduce two classes of measurement-based wireless schedulers. The Opportunistic Guaranteed Rate Scheduler (OGRS) meets a user’s delay constraints by opportunistically allocating the user the equivalent of a fixed service rate, which for a leaky-bucket constrained traffic ensures the delay requirements are met. By contrast, the Opportunistic Guaranteed Delay Schedulers (OGDS) schedules data transmissions when the current channel is better than what is expected in the time window before packet deadlines expire. Meeting such delay requirements requires a complementary admission control policy. We exhibit a simple measurement based policy, that indirectly accounts for heterogeneity in traffic, channel, and delay constraints by monitoring the statistics of user’s aggregate resource usage. We show that the spectral efficiency of our proposed approach is stochastically better than a wireless guaranteed rate scheduler. We bound spectral efficiency by considering an optimal offline policy with access to future channel rates and show via extensive simulations that OGRS can be within 10%-40% of the bound whereas OGDS is within 10% of the bound for a range of delay constraints. Additionally, we demonstrate that OGDS can exhibit better spectral efficiency at higher delay deadlines than schedulers leveraging neural network based predictions for future channel rates.

Future wireless applications, such as online gaming, live video streaming, augmented/virtual reality need high fidelity data transfer with reliable control information exchange to provide an immersive user experience. Developing wireless scheduling algorithms that can guarantee a minimum data rate for users over a few hundred milliseconds with possibly heterogeneous requirements and/or channel quality is crucial. We propose a class of measurement based wireless schedulers that are able to trade off between opportunistically scheduling users with good channels and prioritizing users with service deficits. The proposed algorithms continuously track the QoS provided to each user and switch between conservative or greedy resource allocation depending on user channel strength, QoS deadline, and past channel realizations. We also formulate an oracle-aided linear optimization of the minimum rate QoS constrained scheduling problem to derive a spectral efficiency bound. Through extensive simulations, we show that our proposed algorithms provide a much higher user rate than popular scheduling algorithms such as QoS-PF, EXP-QoS, and weighted MaxQuantile with better reliability when the network is critically loaded. We observe at least a two-fold increase in the mean rate for each user in the network when compared to the EXP-QoS algorithm.

Clustered Federated Learning (CFL) is a promising distributed learning framework that addresses data heterogeneity issues across multiple clients by grouping clients and providing a shared generalized model for each group. However, under privacy-preserving federated learning protocols where there is no direct sharing of clients' local datasets, existing approaches often fail to find optimal client groupings resulting in sub-optimal performance. In this paper, we propose a novel CFL algorithm that achieves robust clustering and learning performance. Conceptually, our algorithm groups clients that exhibit similarity in their model updates by periodically accumulating and clustering the gradients that clients compute for various models. The proposed algorithm is shown to achieve a near-optimal error rate for stochastic convergence to optimal models under mild conditions. We present a detailed analysis of the algorithm along with an evaluation on several CFL benchmarks demonstrating that it outperforms existing approaches in terms of convergence speed, clustering accuracy, and task performance.

We consider a hierarchical inference system with multiple clients connected to a server via a shared communication resource. When necessary, clients with low-accuracy machine learning models can offload classification tasks to a server for processing on a high-accuracy model. We propose a distributed online offloading algorithm which maximizes the accuracy subject to a shared resource utilization constraint thus indirectly realizing accuracy-delay tradeoffs possible given an underlying network scheduler. The proposed algorithm, named Lyapunov-EXP4, introduces a loss structure based on Lyapunov-drift minimization techniques to the bandits with expert advice framework. We prove that the algorithm converges to a near-optimal threshold policy on the confidence of the clients’ local inference without prior knowledge of the system’s statistics and efficiently solves a constrained bandit problem with sublinear regret. We further consider settings where clients may employ multiple thresholds, allowing more aggressive optimization of overall accuracy at a possible loss in fairness. Extensive simulation results on real and synthetic data demonstrate convergence of Lyapunov-EXP4, and show the accuracy-delay-fairness tradeoffs achievable in such systems.

There has been growing interest in computing rate-distortion functions for real-world data, as they can provide a theoretical benchmark for compression problems. However, a generalized form of rate-distortion that includes side information and coding for computing has been underexplored, despite its relevance in modern compression problems. To address this gap, we propose a new method for estimating the rate-distortion function for computing with side information, using a Lagrangian framework with neural network-parametrized encoding and decoding strategies. This approach enables targeting specific points on the rate-distortion curve through gradient-based optimization. Our methodology is validated in synthetic environments where rate-distortion functions are known, ensuring accuracy in estimation. Additionally, we extend its application to practical, high-dimensional channel state information compression scenarios. We provide rate-distortion estimation results on these scenarios, which in turn enables us to quantify the usefulness of side information in the practical scenarios.11The code is available at https://github.com/Heasung-Kimlrate-distortion-side-information.

The increasing demands of computationally intensive device applications are driving advancements in edge technologies and the need for improved computation offloading policies. This paper focuses on “adaptive” offloading and computation, i.e., adapting the amount of offload data and, consequently, the associated compute adaptive job's quality to the wireless channel quality, network congestion, and the compute adaptive job's computational options. For example, when the channel quality is poor and a job has a tight deadline, the amount of offloaded data can be reduced in exchange for a loss in the associated compute adaptive job's quality. In this paper, we show the substantial advantages of adapting the amount of offloaded data to channel quality and network congestion. We begin by defining a reward model for compute adaptive jobs based on the amount of offloaded data and resulting computation quality. We then develop an upper bound on the achievable revenue rate and propose/compare various offloading policies: Greedy, Predictive Abandonment (PA), Probabilistic Admission Control and Layer Assignment (PACLA), and combinations thereof. We evaluate our policies via simulation and observe that the combination of PACLA + PA provides the best offloading performance for homogeneous or heterogeneous compute adaptive jobs for devices with varied channel qualities.

In order to achieve the dual goals of privacy and learning across distributed data, Federated Learning (FL) systems rely on frequent exchanges of large files (model updates) between a set of clients and the server. As such FL systems are exposed to, or indeed the cause of, congestion across a wide set of network resources. Lossy compression can be used to reduce the size of exchanged files and associated delays, at the cost of adding noise to model updates. By judiciously adapting clients’ compression to varying network congestion, an FL application can reduce wall clock training time. To that end, we propose a Network Adaptive Compression (NAC-FL) policy, which dynamically varies the client’s lossy compression choices to network congestion variations. We prove, under appropriate assumptions, that NAC-FL is asymptotically optimal in terms of directly minimizing the expected wall clock training time. Further, we show via simulation that NAC-FL achieves robust performance improvements with higher gains in settings with positively correlated delays across time.

As the automotive industry shifts towards enabling self-driving vehicles, real-time situational awareness is becoming a crucial requirement. This paper introduces a novel information-sharing mechanism to opportunistically improve the vehicles’ local environment estimates via infrastructure-assisted collaborative sensing, while still allowing them to operate autonomously when no assistance is available. As vehicles might have different sensing capabilities, combining and sharing information from a judiciously selected subset is often sufficient to considerably improve all the vehicles’ estimation errors. We develop an opportunistic framework for vehicular collaborative sensing determining (1) which nodes require assistance, (2) which ones are best suited to provide it, and (3) the corresponding information-sharing rates, so as to minimize the communication overheads while meeting the vehicles’ target estimation error. We leverage the supermodularity of the problem to devise an efficient vehicle information sharing algorithm with suboptimality guarantees to solve this problem and make it suitable to deploy in dynamic environments where network conditions might fluctuate rapidly. We support our analysis with simulations showing evidence that vehicles can considerably benefit from the proposed opportunistic collaborative sensing framework compared to operating autonomously. Finally, we explore the value of information-sharing in vehicular collaborative sensing networks by evaluating the associated safe driving velocity gains.

Increasing demand for computationally intensive jobs on mobile devices is driving interest in computation offloading to the edge/cloud servers. This paper presents a comprehensive framework for managing offloading of stochastic and heterogeneous user(s)-generated jobs while considering job deadlines and congestion on wireless channels and edge/cloud servers. The goal of offloading is to maximize either the net computational work offloaded or power savings. We propose a class of policies called Predictive Abandonment (PA), where users opportunistically cut and offload jobs but abandon offloading if they predict that communication and computation delays will preclude on-time completion. Although these user-driven policies are desirable from an implementation perspective and achieve relatively good performance, they cannot coordinate tradeoffs amongst users with heterogeneous job types. To address this, we propose a complementary approach to coordinate offloading based on Probabilistic Admission Control and Cut Assignment (PACCA). When combined with PA, it delivers significant offloading benefits. We also develop an upper bound on the benefits of offloading, which can serve as a baseline for evaluating the additional gains of more complex offloading policies. We evaluate these policies via simulation for a range of loads and job profiles, demonstrating robust gains over a naive greedy offloading policy and near-optimal performance in some settings. Furthermore, we assess the robustness of PACCA + PA to imperfect knowledge of offered job rates.

We consider a setting where requests for updates regarding time-varying processes are required prior to making a sequence of decisions. Each request has a finite length time window during which the update should be received. The end of the window reflects the time at which a decision is to be made, while the start of the window models the earliest possible time at which a useful update could be sent. An update scheduled as near to the end of the window as possible is deemed the best, i.e., reflects the most timely information about the process' state. This is modelled by a reward depending on the time difference between the decision point and the last scheduled update. Requests arrive arbitrarily and share a limited communication resource, e.g., a single request can be scheduled per time slot, hence not all decisions can be based on the latest possible update. We consider update scheduling policies which maximize the overall reward rate. In particular we consider an adversarial request model and evaluate proposed algorithms via their Competitive Ratio (CR). Specifically, we first derive a lower bound on the CR of any causal policy. We then propose two scheduling policies, denoted adversarial and greedy, and provide further analysis and insights on regimes where one might be superior to the other. We validate these observations via simulation for a setting with stochastic arrivals.

Next generation wireless schedulers will support increasingly heterogeneous devices/applications in terms of their traffic characteristics and service requirements. Particularly challenging is the need to deliver traffic subject to delay and reliability constraints in a spectrally efficient manner. We propose a new measurement-based Opportunistic Guaranteed Deadline Scheduler (OGDS) that meets strict delay deadlines on users’ packets. This is achieved by scheduling packet transmissions when the current channel rate is better than that expected in the time window before packet deadlines expire. In order to meet such requirements one must have a complementary admission control policy. We exhibit a simple, once again measurement based policy, that indirectly accounts for heterogeneity in traffic, channel and delay constraints by monitoring statistics of OGDS’s resource usage. We show via extensive synthetic and trace driven simulations that OGDS requires at most 10−25% more resources compared to an optimal offline scheduling policy with complete knowledge of future channel rates, and performs much better than standard baselines including the state-of-the-art MLWDF scheduler. Finally, we propose a modification to OGDS that enables one to control the jitter at a possible loss in spectral efficiency.

We address the problem of distributed resource allocation in wireless systems in the presence of dynamic user traffic and coupling resulting from interference. We propose a Reinforcement Learning (RL) framework based on a separation of concerns between frequency reuse for interference mitigation and opportunistic user scheduling. In particular we explore a setting where a stochastic game is set up among base stations to learn frequency reuse patterns and solved using multi-agent RL given an underlying choice for user scheduling. We establish the existence and convergence to a Nash equilibrium of the proposed setting. The performance of our framework and theoretical findings are evaluated through simulation and compared to more aggressive oracle-aided centralized baselines. The resulting frequency reuse policy is shown to achieve 5–25% improvements in capacity and associated delay performance over a centralized interference aware max weight scheduling policy across BSs. Furthermore, a reduced physical resource utilization on the order of 9–34% leads to a higher energy efficiency as compared to the centralized benchmark.

Next generation wireless schedulers will support increasingly heterogeneous users/devices in terms of their traffic characteristics and service requirements. Particularly challenging is the need to deliver low latency traffic with strict deadlines in a spectrally efficient manner. We introduce a class of wireless schedulers, Opportunistic Guaranteed Rate (OGRS) that exploits the temporal variability in users' channel capacity with a view on maintaining delay guarantees. OGRS meets the user's delay constraints by opportunistically allocating the user the equivalent of a fixed service rate, which given a dual leaky bucket constraint on its traffic will ensure the delay requirements are met. We consider offline policies with access to future channel rates, which establishes a bound to the wireless spectral efficiency. We show via extensive simulations that OGRS can be within 10%-40 % of this bound for a range of delays that were considered. These gains translate to more than a two fold enhancement in eMBB users' throughput, when URLLC and eMBB traffic share resources. Finally, we propose a measurement based admission control strategy for latency constrained URLLC users, so that the network can guarantee QoS to all its users - existing as well as newly admitted ones.

Network slicing is a key capability for next generation mobile networks. It enables infrastructure providers to cost effectively customize logical networks over a shared infrastructure. A critical component of network slicing is resource allocation, which needs to ensure that slices receive the resources needed to support their services while optimizing network efficiency. In this paper, we propose a novel approach to slice-based resource allocation named Guaranteed seRvice Efficient nETwork slicing (GREET). The underlying concept is to set up a constrained resource allocation game, where ($i$) slices unilaterally optimize their allocations to best meet their (dynamic) customer loads, while ($ii$) constraints are imposed to guarantee that, if they wish so, slices receive a pre-agreed share of the network resources. The resulting game is a variation of the well-known Fisher market, where slices are provided a budget to contend for network resources (as in a traditional Fisher market), but (unlike a Fisher market) prices are constrained for some resources to ensure that the pre-agreed guarantees are met for each slice. In this way, GREET combines the advantages of a share-based approach (high efficiency by flexible sharing) and reservation-based ones (which provide guarantees by assigning a fixed amount of resources). We characterize the Nash equilibrium, best response dynamics, and propose a practical slice strategy with provable convergence properties. Extensive simulations exhibit substantial improvements over network slicing state-of-the-art benchmarks.

We observe that current Deep Learning (DL)-based Channel State Information (CSI) encoder and decoder architectures achieve a distortion which is highly channel-dependent. To exploit this, we propose a novel learning-based variable-rate coding scheme to reduce overheads associated with CSI feedback. To that end, we propose an architecture which combines (a) training an efficient predictor for the distortion rate tradeoffs achievable for a given channel, and (b) optimization of a decision logic which allocates rates based on the predicted distortion. We evaluate our approach on various wireless channel datasets including the 3GPP 3D channel model and COST2100 with Massive MIMO channel model, and show significant potential reductions of up to 20% in the CSI feedback overhead.

Underlying blockchain's scalability and performance is a Peer-to-Peer (P2P) overlay network and protocols for relaying blocks and transactions among participating nodes. In this work, we model and perform a systematic analysis of blockchain communication protocols. We begin by introducing the performance metric of interest for blockchains, the sequence of ordered-completion-times, which captures the progress distributed nodes are making in jointly constructing a consistent blockchain. We then study the characteristics of block relaying protocols. In particular, we show that when nodes cannot perform cut-through relaying, there is no optimal causal block relaying protocol if block relaying times are deterministic. We propose a simple age-based block relaying protocol that is provably near-optimal in terms of minimizing ordered-completion-times when the P2P overlay network is a tree. This analysis is relevant to blockchain relay networks such as Bitcoin-Fibre, Bloxroute etc., where the core part of the overlay is a tree. Finally, using the insights derived for tree overlays, we explore the interplay between transaction and block relaying and prioritization (age, size, FCFS based) on both tree and fully connected overlays via simulation. We observe that policies that relay blocks and incorporate transactions into blocks based on 'age' outperform other natural policies. We also explore a fundamental tradeoff between mining and computational efficiencies and performance (in terms of ordered completion times).

We propose and evaluate a learning-based framework to address multi-agent resource allocation in coupled wireless systems. In particular we consider, multiple agents (e.g., base stations, access points, etc.) that choose amongst a set of resource allocation options towards achieving their own performance objective /requirements, and where the performance observed at each agent is further coupled with the actions chosen by the other agents, e.g., through interference, channel leakage, etc. The challenge is to find the best collective action. To that end we propose a Multi-Armed Bandit (MAB) framework wherein the best actions (aka arms) are adaptively learned through online reward feedback. Our focus is on systems which are "weakly-coupled" wherein the best arm of each agent is invariant to others' arm selection the majority of the time - this majority structure enables one to develop light weight efficient algorithms. This structure is commonly found in many wireless settings such as channel selection and power control. We develop a bandit algorithm based on the Track-and-Stop strategy, which shows a logarithmic regret with respect to a genie. Finally through simulation, we exhibit the potential use of our model and algorithm in several wireless application scenarios.

This paper presents a theoretical analysis for a self-driving vehicle’s velocity as it navigates through a random environment. We study a stylized environment and vehicle mobility model capturing the essential features of a self-driving vehicle’s behavior, and leverage results from stochastic geometry to characterize the distribution of a typical vehicle’s safe driving velocity, as a function of key network parameters such as the density of objects in the environment and sensing accuracy. We then consider a setting wherein the sensing accuracy is subject to a sensing/communication rate constraint. We propose a procedure that focuses the vehicle’s sensing/communication resources and estimation efforts on the objects that affect its velocity and safety the most so as to optimize its ability to drive faster in uncertain environments. Simulation results show that the proposed methodology achieves considerable gains in the vehicle’s safe driving velocity as compared to uniform rate allocation policies.

Current wireless networks employ sophisticated multi-user transmission techniques to fully utilize the physical layer resources for data transmission. At the MAC layer, these techniques rely on a semi-static map that translates the channel quality of users to the potential transmission rate (more precisely, a map from the Channel Quality Index to the Modulation and Coding Scheme) for user selection and scheduling decisions. However, such a static map does not adapt to the actual deployment scenario and can lead to large performance losses. Furthermore, adaptively learning this map can be inefficient, particularly when there are a large number of users. In this work, we make this learning efficient by clustering users. Specifically, we develop an online learning approach that jointly clusters users and channel-states, and learns the associated rate regions of each cluster. This approach generates a scenario-specific map that replaces the static map that is currently used in practice. Furthermore, we show that our learning algorithm achieves sub-linear regret when compared to an omniscient genie. Next, we develop a user selection algorithm for multi-user scheduling using the learned user-clusters and associated rate regions. Our algorithms are validated on the WiNGS simulator from AT&T Labs, that implements the PHY/MAC stack and simulates the channel. We show that our algorithm can efficiently learn user clusters and the rate regions associated with the user sets for any observed channel state. Moreover, our simulations show that a deployment-scenario-specific map significantly outperforms the current static map approach for resource allocation at the MAC layer.

In this paper, we study learning-assisted multi-user scheduling for the wireless downlink. There have been many scheduling algorithms developed that optimize for a plethora of performance metrics; however a systematic approach across diverse performance metrics and deployment scenarios is still lacking. We address this by developing a meta-scheduler – given a diverse collection of schedulers, we develop a learning-based overlay algorithm (meta-scheduler) that selects that “best” scheduler from amongst these for each deployment scenario. More formally, we develop a multi-armed bandit (MAB) framework for meta-scheduling that assigns and adapts a score for each scheduler to maximize reward (e.g., mean delay, timely throughput etc.). The meta-scheduler is based on a variant of the Upper Confidence Bound algorithm (UCB), but adapted to interrupt the queuing dynamics at the base-station so as to filter out schedulers that might render the system unstable. We show that the algorithm has a poly-logarithmic regret in the expected reward with respect to a genie that chooses the optimal scheduler for each scenario. Finally through simulation, we show that the meta-scheduler learns the choice of the scheduler to best adapt to the deployment scenario (e.g. load conditions, performance metrics).

Weak submodular optimization underpins many problems in signal processing and machine learning. For such problems, under a cardinality constraint, a simple greedy algorithm is guaranteed to find a solution with a value no worse than 1 − e−γof the optimal. Given the high cost of queries to large-scale signal processing models, the complexity of GREEDY becomes prohibitive in modern applications. In this work, we study the tradeoff between performance and complexity when one resorts to random sampling strategies to reduce the query complexity of GREEDY. Specifically, we quantify the effect of uniform sampling strategies on the performance through two criteria: (i) the probability of identifying an optimal subset, and (ii) the suboptimality of the solution’s value with respect to the optimal. Building upon this insight, we propose a simple progressive stochastic greedy algorithm, study its approximation guarantees, and consider its applications to dimensionality reduction and feature selection tasks.

In this paper, we analyze the performance of Multiplayer Cloud Gaming (MCG) systems. To that end, we introduce a model and new MCG-Quality of Service (QoS) metric that captures the freshness of the players' updates and fairness in their gaming experience. We introduce an efficient measurement-based Joint Multiplayer Rate Adaptation (JMRA) algorithm that optimizes the MCG-QoS by overcoming large (possibly varying) network transport delays by increasing the associated players' update rates. The resulting MCG-QoS is shown to be Schur-concave in the network delays, leading to natural characterizations and performance comparisons associated with the players' spatial geometry and network congestion. In particular, joint rate adaptation enables service providers to combat variability in network delays and players' geographic spread to achieve high service coverage. This, in turn, allows us to explore the spatial density and capacity of compute resources that need to be provisioned. Finally, we leverage tools from majorization theory, to show how service placement decisions can be made to improve the robustness of the MCG-QoS to stochastic network delays.

We consider the joint scheduling of uplink URLLC and eMBB user traffic in a cellular system. The central challenge is coordinating URLLC uplink user transmissions for traffic requiring extremely low latency, high reliability, and in the absence of knowledge of instantaneous URLLC channel qualities, albeit with knowledge of channel distributions. To avoid collisions and meet latency and reliability constraints, we propose to pre optimize layouts of non-overlapping transmission opportunities for URLLC users’, which may, or may not, be used depending on their traffic. To increase overall throughput we propose to leverage Non-Orthogonal Multiple Access (NOMA) based opportunistic scheduling of overlapping eMBB user traffic and propose power control policies, i.e. eMBB transmit power backoff, to protect possible URLLC transmissions from overlapping eMBB traffic. We derive the sum-rate optimal power control for eMBB traffic, and propose a linear approximation that simplifies the later scheduling task. Utilizing an outage capacity model for the unknown URLLC channel qualities, we assign the URLLC allocations as a greedy first fit decreasing packing problem. We then apply an opportunistic overlapping scheduler that, subject to meeting URLLC users' latency constraints, optimizes eMBB users’ sum utility. Substantial discrete event simulations were conducted to explore the performance impact of system parameters associated with URLLC traffic requirements, eMBB power control, etc. Depending on the traffic scenarios, we show gains reaching 75% in the sum eMBB throughput and/or 5th percentile throughput relative to an orthogonal multiple access baseline.

Motivated by the potentially high downlink traffic demands of commuters in future autonomous vehicles, we study a network architecture where vehicles use Vehicle-to-Vehicle (V2V) links to form relay network clusters, which in turn use Vehicle-to-Infrastructure (V2I) links to connect to one or more Road Side Units (RSUs). Such cluster-based multihoming offers improved performance, e.g., in coverage and per user shared rate, but depends on the penetration of V2V+V2I capable vehicles and possible blockage, by legacy vehicles, of line of sight based V2V links, such as those based on millimeter-wave and visible light technologies. This paper provides a performance analysis of a typical vehicle's connectivity and throughput on a highway in the free-flow regime, exploring its dependence on vehicle density, sensitivity to blockages, number of lanes and heterogeneity across lanes. The results, backed up by simulations of realistic vehicular traffic, show that even with moderate vehicle densities and penetration of V2V+V2I capable vehicles, such architectures can achieve substantial improvements in connectivity and reduction in per-user rate variability as compared to V2I based networks. The typical vehicle's performance is also shown to improve considerably in the multilane highway setting as compared to a single lane road. This paper also sheds light on how the network performance is affected when vehicles can control their relative positions, by characterizing the connectivity-throughput tradeoff faced by the clusters of vehicles.

We propose an online algorithm for clustering channel-states and learning the associated achievable multiuser rates. Our motivation stems from the complexity of multiuser scheduling. For instance, MU-MIMO scheduling involves the selection of a user subset and associated rate selection each time-slot for varying channel states (the vector of quantized channels matrices for each of the users) — a complex integer optimization problem that is different for each channel state. Instead, our algorithm clusters the collection of channel states to a much lower dimension, and for each cluster provides achievable multiuser capacity trade-offs, which can be used for user and rate selection. Our algorithm uses a bandit approach, where it learns both the unknown partitions of the channel-state space (channel-state clustering) as well as the rate region for each cluster along a pre-specified set of directions, by observing the success/failure of the scheduling decisions (e.g. through packet loss). We propose an epoch-greedy learning algorithm that achieves a sub-linear regret, given access to a class of classifying functions over the channel-state space. We empirically validate our approach on a high-fidelity 5G New Radio (NR) wireless simulator developed within AT&T Labs. We show that our epoch-greedy bandit algorithm learns the channel-state clusters and the associated rate regions. Further, adaptive scheduling using this learned rate-region model (map from channel-state to the set of feasible rates) outperforms the corresponding hand-tuned static maps in multiple settings. Thus, we believe that auto-tuning cellular systems through learning-assisted scheduling algorithms can significantly improve performance in real deployments.

This paper explores an emerging wireless Internet-of-things (IoT) architecture based on unmanned aerial vehicles (UAVs). We consider a network where a fleet of UAVs at a fixed altitude flies on planned trajectories and IoT devices on the ground are scheduled to transmit their data to the UAVs when the latter are nearby. In such a system, the UAVs' motion triggers the uplink transmissions of the IoT devices. As a result, network performance is determined by the geometric and dynamic characteristics of the system. We propose a joint stationary model for UAVs and IoT devices and then evaluate the interference, the coverage probability, and the data rate of the typical UAV. To assess the harvesting capability of the proposed architecture, we derive a formula for the amount of data uploaded from each IoT device to a UAV. We also establish a linear relationship between the UAV coverage and the harvesting capability of the network, which provides insights into the design of the proposed harvesting scheme. In addition, we use our analytical results to numerically show that there exists a trade-off between the uploaded data and the size of the IoT scheduling window. Specifically, for a given UAV and IoT geometry, there exists an optimal scheduling window that maximizes the harvesting capability of the proposed network.

The automotive industry is undergoing disruptive changes, e.g., ride sharing and self-driving cars which, in addition to leveraging wireless connectivity, may lead to dramatic changes in the volume of infotainment and work related data consumption of vehicle bound passengers. This paper studies the potential gains of leveraging clusters of V2V interconnected vehicles to enable: (1) improved opportunistic access to the cellular infrastructure; and (2), balancing traffic loads across cells through cluster multihoming. A stochastic geometric model and associated analysis are used to obtain a preliminary understanding of possible gains of cluster-based opportunistic relaying and its sensitivity to the system parameters, e.g., base station density, vehicular cluster size and density etc. An optimal network utility maximization formulation is then developed to serve as a baseline to evaluate a simple distributed cluster management algorithm which for the scenarios considered proves to be near-optimal. Overall the results suggest that 3-10x throughput gains are possible along with significant improvements in user rate fairness depending on the system parameters.

In this paper we propose an online algorithm for clustering channel-states and learning the associated achievable multiuser rates. Our motivation stems from the complexity of multiuser scheduling. For instance, MU-MIMO scheduling involves the selection of a user subset and associated rate selection each time-slot for varying channel states (the vector of quantized channels matrices for each of the users) - a complex integer optimization problem that is different for each channel state. Instead, our algorithm clusters the collection of channel states to a much lower dimension, and for each cluster provides achievable multiuser capacity trade-offs, which can be used for user and rate selection. Our algorithm uses a bandit approach, where it learns both the unknown partitions of the channel-state space (channel-state clustering) as well as the capacity region for each cluster along a pre-specified set of directions, by observing the success/failure of the scheduling decisions (e.g. through packet loss). We propose an epoch-greedy learning algorithm that achieves a sub-linear regret, given access to a class of classifying functions over the channel-state space. Finally, we empirically validate the performance of our algorithm through simulations.

This paper explores an emerging wireless architecture based on unmanned aerial vehicles (UAVs), i.e., drones. We consider a network where UAVs at fixed altitude harvest data from Internet-of-Things (IoT) devices on the ground. Each UAV serves IoT devices within its coverage area. In such a system, the UAVs' motion activates IoT uplink transmissions and so the motion triggers the interference field and determines the network performance. To analyze the performance, we propose a stochastic geometry model. The coverage area of each UAV, referred to as the activation window, is modeled for simplicity as a rectangle where at most one IoT device is scheduled to transmit at any given time. In this setting, we analyze the signal-to-interference and data rate from two typical perspectives, namely from a typical UAV's and from a typical IoT device's points of view.

This paper focuses on optimizing resource allocation amongst a set of tenants, network slices, supporting dynamic customer loads over a set of distributed resources, e.g., base stations. The aim is to reap the benefits of statistical multiplexing resulting from flexible sharing of `pooled' resources, while enabling tenants to differentiate and protect their performance from one another's load fluctuations. To that end we consider a setting where resources are grouped into Virtual Resource Pools (VRPs) wherein resource allocation is jointly and dynamically managed. Specifically for each VRP we adopt a Share-Constrained Proportionally Fair (SCPF) allocation scheme where each tenant is allocated a fixed share (budget). This budget is to be distributed equally amongst its active customers which in turn are granted fractions of their associated VRP resources in proportion to customer shares. For a VRP with a single resource, this translates to the well known Generalized Processor Sharing (GPS) policy. For VRPs with multiple resources SCPF provides a flexible means to achieve load elastic allocations across tenants sharing the pool. Given tenants' per resource shares and expected loads, this paper formulates the problem of determining optimal VRP partitions which maximize the overall expected shared weighted utility while ensuring protection guarantees. For a high load/capacity setting we exhibit this network utility function explicitly, quantifying the benefits and penalties of any VRP partition, in terms of network slices' ability to achieve performance differentiation, load balancing, and statistical multiplexing. Although the problem is shown to be NP-Hard, a simple greedy heuristic is shown to be effective. Analysis and simulations confirm that the selection of optimal VRP partitions provide a practical avenue towards improving network utility in network slicing scenarios with dynamic loads.

This paper proposes a framework to explore the optimization of applications where a distributed set of nodes/sensors, e.g., automated vehicles, collaboratively exchange information over a network to achieve real-time situational-awareness. To that end we propose a reasonable proxy for the usefulness of possibly delayed sensor updates and their sensitivity to the network resources devoted to such exchanges. This enables us to study the joint optimization of (1) the application-level update rates, i.e., how often and when sensors update other nodes, and (2), the transmission resources allocated to, and resulting delays associated with, exchanging updates. We first consider a network scenario where nodes share a single resource, e.g., an ad hoc wireless setting where a cluster of nodes, e.g., platoon of vehicles, share information by broadcasting on a single collision domain. In this setting we provide an explicit solution characterizing the interplay between network congestion and situational awareness amongst heterogeneous nodes. We then extend this to a setting where such clusters can also exchange information via a base station. In this setting we characterize the optimal solution and develop a natural distributed algorithm based on exchanging congestion prices associated with sensor nodes' update rates and associated network transmission rates. Preliminary numerical evaluation provides initial insights on the trade-offs associated with optimizing situational awareness and the proposed algorithm's convergence.

In order to meet the performance/privacy requirements of future data-intensive mobile applications, e.g., self-driving cars, mobile data analytics, and AR/VR, service providers are expected to draw on shared storage/computation/connectivity resources at the network “edge”. To be cost-effective, a key functional requirement for such infrastructure is enabling the sharing of heterogeneous resources amongst tenants/service providers supporting spatially varying and dynamic user demands. This paper proposes a resource allocation criterion, namely, Share Constrained Slicing (SCS), for slices allocated predefined shares of the network's resources, which extends traditional α-fairness criterion, by striking a balance among inter- and intra-slice fairness vs. overall efficiency. We show that SCS has several desirable properties including slice-level protection, envy-freeness, and load-driven elasticity. In practice, mobile users' dynamics could make the cost of implementing SCS high, so we discuss the feasibility of using a simpler (dynamically) weighted max-min as a surrogate resource allocation scheme. For a setting with stochastic loads and elastic user requirements, we establish a sufficient condition for the stability of the associated coupled network system. Finally, and perhaps surprisingly, we show via extensive simulations that while SCS (and/or the surrogate weighted max-min allocation) provides inter-slice protection, they can achieve improved job delay and/or perceived throughput, as compared to other weighted max-min based allocation schemes whose intra-slice weight allocation is not share-constrained, e.g., traditional max-min or discriminatory processor sharing.

This paper considers the design of cross-layer opportunistic transport protocols for stored video over wireless networks with a slow varying (average) capacity. We focus on two key principles: 1) scheduling data transmissions when capacity is high; and 2) exploiting knowledge of future capacity variations. The latter is possible when users' mobility is known or predictable, for example, users riding on public transportation or using navigation systems. We consider the design of cross-layer transmission schedules, which minimize system utilization (and, thus, possibly transmit/receive energy) while avoiding, if at all possible, rebuffering/delays in several scenarios. For the single-user anticipative case where all future capacity variations are known beforehand, we establish the optimal transmission schedule in a generalized piecewise constant thresholding (GPCT) scheme. For the single-user partially anticipative case where only a finite window of future capacity variations is known, we propose an online greedy fixed horizon control (GFHC). An upper bound on the competitive ratio of GFHC and GPCT is established showing how performance loss depends on the window size, receiver playback buffer, and capacity variability. We also consider the multiuser case where one can exploit both future temporal and multiuser diversity. Finally, we investigate the impact of uncertainty in knowledge of future capacity variations, and propose an offline approach as well as an online algorithm to deal with such uncertainty. Our simulations and evaluation based on a measured wireless capacity trace exhibit robust potential gains for our proposed transmission schemes.

Network slicing to enable resource sharing among multiple tenants-network operators and/or services-is considered as a key functionality for next generation mobile networks. This paper provides an analysis of a well-known model for resource sharing, the share-constrained proportional allocation mechanism, to realize network slicing. This mechanism enables tenants to reap the performance benefits of sharing, while retaining the ability to customize their own users' allocation. This results in a network slicing game in which each tenant reacts to the user allocations of the other tenants so as to maximize its own utility. We show that, for elastic traffic, the game associated with such strategic behavior converges to a Nash equilibrium. At the Nash equilibrium, a tenant always achieves the same or better performance than that of a static partitioning of resources, thus providing the same level of protection as static partitioning. We further analyze the efficiency and fairness of the resulting allocations, providing tight bounds for the price of anarchy and envy-freeness. Our analysis and extensive simulation results confirm that the mechanism provides a comprehensive practical solution to realize network slicing. Our theoretical results also fills a gap in the analysis of this resource allocation model under strategic players.

In a large-scale computing cluster, the job completions can be substantially delayed due to two sources of variability, namely, variability in the job size and that in the machine service capacity. To tackle this issue, existing works have proposed various scheduling algorithms which exploit redundancy wherein a job runs on multiple servers until the first completes. In this paper, we explore the impact of variability in the machine service capacity and adopt a rigorous analytical approach to design scheduling algorithms using redundancy and checkpointing. We design several online algorithms which can dynamically vary the number of redundant copies for jobs. We also provide new theoretical performance bounds for these algorithms in terms of the overall job flowtime by introducing the notion of a speedup function, based on which a novel potential function can be defined to enable the corresponding competitive ratio analysis. In particular, by adopting the online primal-dual fitting approach, we prove that our SRPT+R Algorithm in a non-multitasking cluster is$(1+\epsilon)$-speed,$\ O(\frac{1}{\epsilon })$-competitive. We also show that our proposed Fair+R and LAPS+R($\beta$) Algorithms for a multitasking cluster are$(4+\epsilon)$-speed,$\ O(\frac{1}{\epsilon })$-competitive and ($2 + 2\beta + 2\epsilon)$-speed$O(\frac{1}{\beta \epsilon })$-competitive respectively. We demonstrate via extensive simulations that our proposed algorithms can significantly reduce job flowtime under both the non-multitasking and multitasking modes.

Network densification, i.e., increasing the density of fixed infrastructure nodes, is the key approach underlying gains in infrastructure-based network capacity and coverage. These gains are a natural result of reducing the distance (and thus improving wireless channels) between end devices and infrastructure and possibly reducing the number of devices per infrastructure node. Unfortunately, wireless traffic demands exhibit high spatio-temporal variability, whence densification may result in deployment of poorly utilized infrastructure resources. One alternative is to leverage the availability of wireless resources whose presence aligns with the mobile traffic demand variations, e.g., high density of vehicles where there is high demand. The promise of such dynamic densification is to both decrease infrastructure costs and deliver improved capacity. This paper proposes a stochastic geometry-based modelling framework to evaluate how the network performance (per user rate superquantiles) depends on the alignment of resources and traffic demands for dynamic network densification.

Emerging 5G systems will need to efficiently support both broadband traffic (eMBB) and ultra-low-latency (URLLC) traffic. In these systems, time is divided into slots which are further sub-divided into minislots. From a scheduling perspective, eMBB resource allocations occur at slot boundaries, whereas to reduce latency URLLC traffic is pre-emptively overlapped at the minislot timescale, resulting in selective superposition/puncturing of eMBB allocations. This approach enables minimal URLLC latency at a potential rate loss to eMBB traffic. We study joint eMBB and URLLC schedulers for such systems, with the dual objectives of maximizing utility for eMBB traffic while satisfying instantaneous URLLC demands. For a linear rate loss model (loss to eMBB is linear in the amount of superposition/puncturing), we derive an optimal joint scheduler. Somewhat counter-intuitively, our results show that our dual objectives can be met by an iterative gradient scheduler for eMBB traffic that anticipates the expected loss from URLLC traffic, along with an URLLC demand scheduler that is oblivious to eMBB channel states, utility functions and allocations decisions of the eMBB scheduler. Next we consider a more general class of (convex) loss models and study optimal online joint eMBB/URLLC schedulers within the broad class of channel state dependent but time-homogeneous policies. We validate the characteristics and benefits of our schedulers via simulation.

Ultra densification along with the use of wider bands at higher frequencies are likely to be key elements towards meeting the throughput/coverage objectives of 5G wireless networks. In addition to increased parallelism, densification leads to improved, but eventually bounded, benefits from proximity of users to base stations, while resulting in increased aggregate interference. Such networks are expected to be interference limited, and in higher frequency regimes, the interference is expected to become spatially variable due to the increased sensitivity of propagation to obstructions and the proximity of active interferers. This paper studies the characteristics of the spatial random fields associated with interference and Shannon capacity in ultra-dense limiting regimes. They rely on the theory of Gaussian random fields which arise as natural limits under densification. Our models show how densification and operation at higher frequencies, could lead to increasingly rough temporal variations in the interference process. This is characterized by the Holder exponent of the interference field. We show that these fluctuations make it more difficult for mobile users to adapt modulation and coding. We further study how the spatial correlations in users' rates impact backhaul dimensioning. Therefore, this paper identifies and quantifies challenges associated with densification in terms of the resulting unpredictability and the correlation of interference on the achievable rates.

Disruptive changes are underway in the automotive industry as large-scale platforms based on vehicular fleets are deployed to deliver ride sharing and delivery services. Such platforms can also be leveraged to deliver wireless connectivity services, e.g., large-scale connectivity for the Internet of Things (IoT). This paper examines a network architecture based on a mesh of IoT devices, roadside repositories and vehicular mobile gateways -- referred to as mesh+vehicular. We propose a system-level model to study its relative merits versus conventional infrastructure-based IoT architectures-- referred to as mesh+cellular. The model reflects the salient properties of the architectures including the key interplay among the variability in the network geometries, routing trees, wireless capacity and eventually IoT queue stability.

To enable situational awareness for automated driving in intelligent transportation systems (ITS), it is envisioned that vehicles will be equipped with sensors, and possibly perform collaborative sensing amongst themselves. Unfortunately such sensing is subject to obstructions, e.g., other vehicles, and the performance can be poor when the penetration of collaborating vehicles is low. A possible solution is to deploy sensing and communication capable infrastructure, e.g., road side units (RSUs) and base stations (BSs), to assist collaborative sensing. This paper explores the performance of infrastructure assisted sensing of roads under various deployment schemes. Our analytical results show that deploying RSUs at intersections and at even spacings is most efficient in covering the roads while cellular based sensors may subject to building obstructions and should be located along roads working as RSUs. RSUs located above the vehicles can have 100% coverage of vehicles once the communication range is large enough to reach relevant sensors. Infrastructure provides a second advantage in providing a dynamic view of the road and thus better coverage over time. Such benefit from sensing temporal diversity is shared by vehicles moving in the opposite direction, yet collaborating with such vehicles involves more challenging V2V communication given the high relative speed and obstruction unless leveraging V2I relays.

5G wireless networks are expected to support ultra-reliable low latency communications (URLLC) traffic which requires very low packet delays (<; 1 ms) and extremely high reliability (~99.999%). In this paper, we focus on the design of a wireless system supporting downlink URLLC traffic. Using a queuing network-based model for the wireless system, we characterize the effect of various design choices on the maximum URLLC load it can support, including: 1) system parameters such as the bandwidth, link SINR, and QoS requirements; 2) resource allocation schemes in orthogonal frequency-division multiple access (OFDMA)-based systems; and 3) hybrid automatic repeat request schemes. Key contributions of this paper which are of practical interest are: 1) study of how the minimum required system bandwidth to support a given URLLC load scales with associated QoS constraints; 2) characterization of optimal OFDMA resource allocation schemes which maximize the admissible URLLC load; and 3) optimization of a repetition code-based packet re-transmission scheme.

This paper focuses on the modeling and analysis of the temporal performance variation experienced by a mobile user in a wireless network and its impact on system-level design. We consider a simple stochastic geometry model: the infrastructure nodes are Poisson distributed while the user’s motion is the simplest possible, i.e., constant velocity on a straight line. We first characterize variations in the signal-to-noise ratio (SNR) process and associated downlink Shannon rate, resulting from variations in the infrastructure geometry seen by the mobile. Specifically, by making a connection between stochastic geometry and queuing theory, the level crossings of the SNR process are shown to form an alternating renewal process whose distribution is completely characterized. For large/small SNR levels, and associated rare events, we further derive simple distributional (exponential) models. We then characterize the second major contributor to such variations, namely, changes in the number of other users sharing the infrastructure. Combining these two phenomena, we study what are the dominant factors (infrastructure geometry or sharing number) when a mobile experiences a very high/low shared rate. These results are then used to evaluate and optimize the system-level quality of experience of the mobile users sharing such a wireless infrastructure, including mobile devices streaming video which proactively buffer content to prevent rebuffering and mobiles which are downloading large files. Finally, we use simulation to assess the fidelity of this model and its robustness to factors which are presently not taken into account.

Next-generation wireless architectures are expected to enable slices of shared wireless infrastructure, which are customized to specific mobile operators/services. Given infrastructure costs and the stochastic nature of mobile services' spatial loads, it is highly desirable to achieve efficient statistical multiplexing among such slices. We study a simple dynamic resource sharing policy, which allocates a “share” of a pool of (distributed) resources to each slice-share constrained proportionally fair (SCPF). We give a characterization of SCPF's performance gains over static slicing and general processor sharing. We show that higher gains are obtained when a slice's spatial load is more “imbalanced” than, and/or “orthogonal” to, the aggregate network load, and that the overall gain across slices is positive. We then address the associated dimensioning problem. Under SCPF, traditional network dimensioning translates to a coupled share dimensioning problem, which characterizes the existence of a feasible share allocation, given slices' expected loads and performance requirements. We provide a solution to robust share dimensioning for SCPF-based network slicing. Slices may wish to unilaterally manage their users' performance via admission control, which maximizes their carried loads subject to performance requirements. We show that this can be modeled as a “traffic shaping” game with an achievable Nash equilibrium. Under high loads, the equilibrium is explicitly characterized, as are the gains in the carried load under SCPF versus static slicing. Detailed simulations of a wireless infrastructure supporting multiple slices with heterogeneous mobile loads show the fidelity of our models and the range of validity of our high-load equilibrium analysis.

Technologies that enable network slicing are expected to be a key component of next generation mobile networks. Their promise lies in enabling tenants (such as mobile operators and/or services) to reap the cost and performance benefits of sharing resources while retaining the ability to customize their own allocations. When employing dynamic sharing mechanisms, tenants may exhibit strategic behavior, optimizing their choices in response to those of other tenants. This paper analyzes dynamic sharing in network slicing when tenants support inelastic users with minimum rate requirements. We propose a NEtwork Slicing (NES) framework combining: 1) admission control; 2) resource allocation; and 3) user dropping. We model the network slicing system with admitted users as a NES game; this is a new class of game where the inelastic nature of the traffic may lead to dropping users whose requirements cannot be met. We show that, as long as admission control guarantees that slices can satisfy the rate requirements of all their users, this game possesses a Nash equilibrium. Admission control policies (a conservative and an aggressive one) are considered, along with a resource allocation scheme and a user dropping algorithm, geared at maintaining the system in Nash equilibria. We analyze our NES framework's performance in equilibrium, showing that it achieves the same or better utility than static resource partitioning, and bound the difference between NES and the socially optimal performance. Simulation results confirm the effectiveness of the proposed approach.

Traditional wireless schedulers have been driven by rate-based criteria, e.g., utility maximizing/proportionally fair, and/or queue-based packet schedulers which do not directly reflect the Quality of Experience (QoE) associated with flow-based transactions and services. This paper proposes, a Measurement-Based Delay Optimal (MBDO) scheduler, which optimizes a cost function of the mean flow delays in a multi-class system, e.g,. web interactive, file downloads, etc. In this context the cost function expresses desired trade-offs amongst traffic classes reflecting heterogeneous QoE sensitivities which are nonlinear in the flow delays and/or system loads. To achieve optimality, MBDO scheduling uses measured system variables and knowledge (or measurement) of class flow-size distributions to adapt a weighted Gittins index scheduler. We show that under mild assumptions, and in a stationary regime, that MBDO scheduling is indeed asymptotically optimal. Perhaps more importantly, MBDO schedulers can self-optimize by adapting to slowly varying traffic loads, mixes and flow size distributions. Our extensive simulations confirm the effectiveness at realizing trade-offs and performance of the proposed approach.

Network slicing to enable resource sharing among multiple tenants-network operators and/or services-is considered a key functionality for next generation mobile networks. This paper provides an analysis of a well-known model for resource sharing, the `share-constrained proportional allocation' mechanism, to realize network slicing. This mechanism enables tenants to reap the performance benefits of sharing, while retaining the ability to customize their own users' allocation. This results in a network slicing game in which each tenant reacts to the user allocations of the other tenants so as to maximize its own utility. We show that, under appropriate conditions, the game associated with such strategic behavior converges to a Nash equilibrium. At the Nash equilibrium, a tenant always achieves the same, or better, performance than under a static partitioning of resources, hence providing the same level of protection as such static partitioning. We further analyze the efficiency and fairness of the resulting allocations, providing tight bounds for the price of anarchy and envy-freeness. Our analysis and extensive simulation results confirm that the mechanism provides a comprehensive practical solution to realize network slicing. Our theoretical results also fill a gap in the literature regarding the analysis of this resource allocation model under strategic players.

The completion times of jobs in a computing cluster may be influenced by a variety of factors including job size and machine processing variability. In this paper, we explore online resource allocation policies which combine size-dependent scheduling with redundant execution and opportunistic checkpointing to minimize the overall job flowtime. We introduce a simplified model for the job service capacity of a computing cluster while leveraging redundant execution/checkpointing. In this setting, we propose two resource allocation algorithms, SRPT+R and LAPS+R(β) subject to checkpointing overhead not exceeding the number of jobs which are processed. We provide new theoretical performance bounds for these algorithms: SRPT+R is shown to be O(1/∊) competitive under (1 + ∊)-speed resource augmentation, while LAPS+R(β) is shown to be O(1/β∊) competitive under (2+ 2β + 2∊)-speed resource augmentation.

Wireless channels in millimeter wave based wearable networks are particularly susceptible to environmental blockages and dynamics when there are humans/objects in motion. Such dynamics imply, not only physical layer overheads to discover and track viable transmission paths, but also MAC overheads to keep track of neighboring interferers, perform clustering and enable proper scheduling of transmissions. We shall focus on overheads at timescale associated with the latter. This paper introduces a stochastic geometric model to study the impact of mobility on overheads in such networks. We provide a complete characterization of the temporal dynamics of strong interference channels resulting from blocking in networks comprising both fixed and mobile nodes. We show the state of a channel, Line-of-Sight(LOS)/Non-LOS(NLOS), follows an on/off renewal process and derive the associated distributions. Our model further enables us to evaluate how the overall rate of change for the set of strong LOS interferers seen by a fixed user scales with user density and proportion of mobile users. The overhead to track the interference environment may in fact be limited with user density but increases with proportion of mobile users. In a highly mobile environment, the changes in channels are frequent and the overheads for coordination become high, with distant and/or mobile users requiring more overheads. Based on our results, we suggest fixed users may coordinate with close by neighbors while mobile users are better off resorting to simpler ad hoc MACs.

Next generation wireless architectures are expected to enable slices of shared wireless infrastructure which are customized to specific mobile operators/services. Given infrastructure costs and the stochastic nature of mobile services' spatial loads, it is highly desirable to achieve efficient statistical multiplexing amongst network slices. We study a simple dynamic resource sharing policy which allocates a `share' of a pool of (distributed) resources to each slice-Share Constrained Proportionally Fair (SCPF). We give a characterization of the achievable performance gains over static slicing, showing higher gains when a slice's spatial load is more `imbalanced' than, and/or `orthogonal' to, the aggregate network load. Under SCPF, traditional network dimensioning translates to a coupled share dimensioning problem, addressing the existence of a feasible share allocation given slices' expected loads and performance requirements. We provide a solution to robust share dimensioning for SCPF-based network slicing. Slices may wish to unilaterally manage their users' performance via admission control which maximizes their carried loads subject to performance requirements. We show this can be modeled as a "traffic shaping" game with an achievable Nash equilibrium. Under high loads the equilibrium is explicitly characterized, as are the gains in the carried load under SCPF vs. static slicing. Detailed simulations of a wireless infrastructure supporting multiple slices with heterogeneous mobile loads show the fidelity of our models and range of validity of our high load equilibrium analysis.

This paper addresses the slicing of radio access network resources by multiple tenants, e.g., virtual wireless operators and service providers. We consider a criterion for dynamic resource allocation amongst tenants, based on a weighted proportionally fair objective, which achieves desirable fairness/protection across the network slices of the different tenants and their associated users. Several key properties are established, including: the Pareto-optimality of user association to base stations, the fair allocation of base stations' resources, and the gains resulting from dynamic resource sharing across slices, both in terms of utility gains and capacity savings. We then address algorithmic and practical challenges in realizing the proposed criterion. We show that the objective is NP-hard, making an exact solution impractical, and design a distributed semi-online algorithm, which meets performance guarantees in equilibrium and can be shown to quickly converge to a region around the equilibrium point. Building on this algorithm, we devise a practical approach with limited computational information and handoff overheads. We use detailed simulations to show that our approach is indeed near-optimal and provides substantial gains both to tenants (in terms of capacity savings) and end users (in terms of improved performance).

Measurement traces from real-world production environment show that the execution time of tasks within a MapReduce job varies widely due to the variability in machine service capacity. This variability issue makes efficient job scheduling over large-scale MapReduce clusters extremely challenging. To tackle this problem, we adopt the task cloning approach to mitigate the effect of machine variability and design corresponding scheduling algorithms so as to minimize the overall job flowtime in different scenarios. For offline scheduling where all jobs arrive at the same time, we design an$O(1)$-competitive algorithm, which gives priorities to jobs with small effective workload. We then extend this offline algorithm to yield the so-called Smallest Remaining Effective Workload based$\beta$-fraction Sharing plus Cloning algorithm (SREW+C($\beta$)) for the online case. We also show that SREW+C($\beta$) is$(1+ 2\beta + \epsilon)$-speed$O(\frac{1}{\beta \epsilon })$-competitive with respect to the sum of job flowtime within a cluster. We demonstrate via trace-driven simulations that SREW+C($\beta$) can significantly reduce the overall job flowtime by cutting down the elapsed time of small jobs substantially. In particular, SREW+C($\beta$) reduces the total job flowtime by 14, 10 and 11 percent respectively when comparing to Mantri, Dolly and Grass.

Cloud-based computing infrastructure provides an efficient means to support real-time processing workloads, e.g., virtualized base station processing, and collaborative video conferencing. This paper addresses resource allocation for a computing system with multiple resources supporting heterogeneous soft real-time applications subject to Quality of Service (QoS) constraints on failures to meet processing deadlines. We develop a general outer bound on the feasible QoS region for non-clairvoyant resource allocation policies, and an inner bound for a natural class of policies based on dynamically prioritizing applications' tasks by favoring those with the largest (QoS) deficits. This provides an avenue to study the efficiency of two natural resource allocation policies: (1) priority-based greedy task scheduling for applications with variable workloads, and (2) priority-based task selection and optimal scheduling for applications with deterministic workloads. The near-optimality of these simple policies emerges when task processing deadlines are relatively large and/or when the number of compute resources is large. Analysis and simulations show substantial resource savings for such policies over reservation-based designs.

An increasing number of real-time applications with compute and/or communication deadlines are being supported on shared infrastructure. Such applications can often tolerate occasional deadline violations without substantially impacting their Quality of Service (QoS). A fundamental problem in such systems is deciding how to allocate shared resources so as to meet applications' QoS requirements. A simple framework to address this problem is to, (1) dynamically prioritize users as a possibly complex function of their deficits (difference of achieved vs required QoS), and (2) allocate resources so to expedite users with higher priority. This paper focuses on a general class of systems using such priority-based resource allocation. We first characterize the set of feasible QoS requirements and show the optimality of max weight-like prioritization. We then consider simple weighted Largest Deficit First (w-LDF) prioritization policies, where users with higher weighted QoS deficits are given higher priority. The paper gives an inner bound for the feasible set under w-LDF policies, and, under an additional monotonicity assumption, characterizes its geometry leading to a sufficient condition for optimality. Additional insights on the efficiency ratio of w-LDF policies, the optimality of hierarchical-LDF and characterization of clustering of failures are also discussed.

Modern broadband wireless networks support application mixes, with different, possibly complex, application/user Quality of Service/Experience (QoS/QoE) metrics. The central problem underlying resource allocation for such systems is realizing QoS/QoE trade-offs given the dynamic loads and capacity variability they would typically see. The paper explores a framework for context-aware scheduling based on: (1) context-aware flow classification and management, and (2), complementary base station scheduler. Motivated by typical flow-size distributions for current traffic and characteristics of the associated delay optimal (Gittins index-based) schedulers we propose a novel flow and channel-aware scheduler which meets our design objectives. Using a combination of analysis and simulation we explore the achieved QoS/QoE trade-offs across a dynamic mix of traffic, in particular: 1) mobile web browsing and small file delays; 2) stored streaming video quality vs re-buffering; 3) throughput of larger file downloads. They suggest improved QoS/QoE tradeoffs vs traditional proportionally fair schedulers and are robust to the network load.

This paper proposes a stochastic geometry framework to study the temporal performance variations experienced by a mobile user in a cellular network. The focus is on the variations of the Signal to Noise Ratio (SNR) and the downlink Shannon rate experienced when the user moves across Poisson cellular network of the Euclidean plane. The motion is the simplest possible i.e., a user moving at a constant velocity on a straight line. The level crossings of the associated SNR process are shown to form an alternating-renewal process. The two distributions characterizing this process are derived in closed form. The theory of rare events provides simplified expressions for the law of this process for extremes (very large and very small) SNR thresholds. The framework is then leveraged to predict the quality of service experienced by mobile users in two concrete scenarios: that of streaming a video on the downlink and partially buffered on the hand-set to prevent video freezing; and that of downloading a large file, where the main question is the download delay. Finally, discrete event simulation is used to assess practical use of this model on its robustness to perturbations that cannot presently be taken into account in the analysis.

MmWave based wearable networks will need to function in various environments including possibly high density settings, e.g., train cars. At such densities one might expect challenges in interference management and/or excessive overheads tracking and jointly scheduling interferers. In this paper we use simple stochastic geometric models to examine the characteristics (number and sensitivity to motion) of "strong interferers" and show that due to blocking they are not monotonic in user density. Indeed, perhaps surprisingly, the most challenging setting appears to arise at "intermediate" user densities. We then propose a simple model to evaluate the performance of current MAC designs based on clustering and hierarchical scheduling. The results exhibit a performance trade-off leading to an optimal cluster size which depends on the directionality of transmissions. More importantly, we show that at high densities the per user throughput is roughly constant, suggesting wearable networks will scale well in dense scenarios.

State-of-the-art D2D schedulers' performance can be evaluated from at least two different perspectives: the sum throughput and the fraction of satisfied users/applications. In this paper we revisit the performance of such schedulers, e.g., FlashLinQ/ITLinQ, showing they strike particular trade-offs between these two metrics. Our analysis and simulations show that the sum-rate benefits of such schedulers come at the expense of fairness, which under high densities can lead to a substantial fraction of unsatisfied users. This motivates a proposed opportunistic scheduler design, Binary Quantile (BQ) scheduling, which further exploits temporal channel variations via a low overhead distributed mechanisms and realizes substantial improvements in user/application performance. We further show that an adapting version of BQ scheduling where link quantile thresholds are adjusted based on achieved throughput can further achieve substantial improvement in user/application level satisfaction which is robust to heterogeneity in the network topology.

In this paper, we present an approach for joint rate allocation and quality selection for a novel video streaming scheme called streamloading. Streamloading is a recently developed method for delivering high-quality video without violating copyright enforced restrictions on content access for video streaming. In regular streaming services, content providers restrict the amount of viewable video that users can download prior to playback. This approach can cause inferior user experience due to bandwidth variations, especially in mobile networks with varying capacity. In streamloading, the video is encoded using scalable video coding, and users are allowed to pre-fetch enhancement layers and store them on the device, while base layers are streamed in a near real-time fashion ensuring that buffering constraints on viewable content are met. We begin by formulating the offline problem of jointly optimizing rate allocation and quality selection for streamloading in a wireless network. This motivates our proposed online algorithms for joint scheduling at the base station and segment quality selection at receivers. The results indicate that streamloading outperforms the state-of-the-art streaming schemes in terms of the number of additional streams we can admit for a given video quality. Furthermore, the quality adaptation mechanism of our proposed algorithm achieves a higher performance than baseline algorithms with no (or limited) video-centric optimization of the base station's allocation of resources, e.g., proportional fairness.

With ever increasing network traffic rates, multicore architectures for network processors have successfully provided performance improvements through high parallelism. However, naively allocating the network traffic to multiple cores without considering diversified applications and flow locality results in issues such as packet reordering, load imbalance and inefficient cache usage. Consequently, these issues degrade the performance of latency sensitive network processors by dropping packets or delivering packets out of order. In this paper, we propose a packet scheduling scheme that considers the multiple dimensions of locality to improve the throughput of a network processor while minimizing out of order packets. Our scheduling policy tries to maintain packet order my maintaining the flow locality, minimizes the migration of flows from one core to another by identifying the aggressive flows, and partitions the cores among multiple services to gain instruction cache locality. Our light weight hardware implementation shows improvement of 60 percent in the number of packets dropped and 80 percent in the number of out-of-order packet deliveries over previously proposed techniques.

We consider the multicast scheduling problem for the block transmission of packets in a heterogeneous network using a half-duplex relay station (RS). The RS uses random linear coding to efficiently transmit packets over time-varying multicast channels. Our goal is to minimize the average decoding delay. Because of the half-duplex operation, at each time slot, the RS must decide to either: (1) fetch a new packet for encoding from the base station or (2) multicast a coded packet to wireless users. Thus, optimal scheduling hinges on exploiting multicast opportunities while persistently supplying the encoder (at the RS) with new packets. We formulate an associated fluid control problem and show that the optimal policy incorporates opportunism across multicast channels, i.e., the RS performs a multicast transmission only if the collection of channel conditions is favorable; otherwise, it performs a fetch. Based on the fluid policy, we propose an online algorithm. We prove that our algorithm asymptotically incurs no more than 4/3 and 2 times the optimal delay, for two-user and arbitrary number of user system, respectively. Simulation results show that, in fact, our algorithm's performance is very close to theoretical bounds.

Finding a document or resource in an unstructured peer-to-peer network can be an exceedingly difficult problem. In this paper we propose a query routing approach that accounts for arbitrary overlay topologies, nodes with heterogeneous processing capacity, e.g., reflecting their degree of altruism, and heterogenous class-based likelihoods of query resolution at nodes which may reflect query loads and the manner in which files/resources are distributed across the network. The approach is shown to be stabilize the query load subject to a grade of service constraint, i.e., a guarantee that queries' routes meet pre-specified class-based bounds on their associated a priori probability of query resolution. An explicit characterization of the capacity region for such systems is given and numerically compared to that associated with random walk based searches. Simulation results further show the performance benefits, in terms of mean delay, of the proposed approach. Additional aspects associated with reducing complexity, estimating parameters, and adaptation to class-based query resolution probabilities and traffic loads are studied.

We consider multi-class queueing systems where the per class service rates depend on the network state, fairness criterion, and is constrained to be in a symmetric polymatroid capacity region. We develop new comparison results leading to explicit bounds on the mean service time under various fairness criteria and possibly heterogeneous loads. We then study large-scale systems with growing numbers of service classes n (e.g., files), heterogenous servers m and polymatroid capacity resulting from a random bipartite graph modeling service availability (e.g., placement of files across servers). This models, for example, a large scale content delivery network (CDN) supporting parallel servicing of a download request. For an appropriate asymptotic regime, we show that the system's capacity region is uniformly close to a symmetric polymatroid -- i.e., heterogeneity in servers' capacity and file placement disappears.

We consider a centralized content delivery infrastructure where a large number of storage-intensive files are replicated across several collocated servers. To achieve scalable mean delays in file downloads under stochastic loads, we allow multiple servers to work together as a pooled resource to meet individual download requests. In such systems, basic questions include: How and where to replicate files? What is the impact of dynamic service allocation across request types, and whether such allocations can provide substantial gains over simpler load balancing policies? What are tradeoffs among performance, reliability and recovery costs, and energy? This paper provides a simple performance model for large systems towards addressing these basic questions.

We conducted a subjective study wherein we found that viewers' Quality of Experience (QoE) was strongly correlated with the empirical cumulative distribution function (eCDF) of the predicted video quality. Based on this observation, we propose a rate-adaptation algorithm that can incorporate QoE constraints on the empirical cumulative quality distribution per user. Simulation results show that the proposed technique can reduce network resource consumption by 29% over conventional average-quality maximized rate-adaptation algorithms.

Cellular systems using Coordinated Multi-Point (CoMP) transmissions leveraging clusters of spatially distributed radio antennas as Virtual Base Stations (VBSs) have the potential to realize overall throughput gains and, perhaps more importantly, can deliver substantial enhancement to poor performing “edge” users. In this paper we propose a novel framework aimed at fully exploiting the potential of such systems through dynamic radio resource clustering and user scheduling which maximize system utility. The dynamic clustering problem is modeled as a maximum weight clustering problem which is NP-hard, however, we show that by structuring the set of possible VBSs to be “2-decomposable” it can be efficiently computed. We also propose to optimize over a class of power allocation policies to radio resources, and thus VBSs, which allow dynamic user scheduling and flexible power allocations depending on instantaneous channel realizations. We use simulation to compare our approach with a state-of-the-art baseline which exploits dynamic frequency reuse and opportunistic user scheduling, but no clustering, and show edge users' throughput gains are as high as 80% without degrading the performance of others.

We consider the problem of optimizing video delivery for a network supporting video clients streaming stored video. Specifically, we consider the joint optimization of network resource allocation and video quality adaptation. Our objective is to fairly maximize video clients' Quality of Experience (QoE) realizing tradeoffs among the mean quality, temporal variability in quality, and fairness, incorporating user preferences on rebuffering and cost of video delivery. We present a simple asymptotically optimal online algorithm, NOVA, to solve the problem. NOVA is asynchronous, and using minimal communication, distributes the tasks of resource allocation to network controller, and quality adaptation to respective video clients. Video quality adaptation in NOVA is also optimal for standalone video clients, and is well suited for use in the DASH framework. Further, NOVA can be extended for use with more general QoE models, networks shared with other traffic loads and networks using fixed/legacy resource allocation.

Large scale Content Delivery Networks (CDNs) are one of the key components of today's information infrastructure. This paper proposes and analyzes a simple stochastic model for a file-server system wherein servers can work together, as a pooled resource, to meet individual user requests. In such systems basic questions include: How and where to replicate files? What is the impact of dynamic service allocation across request types, and whether it can provide substantial gains over simpler load balancing policies? What are tradeoffs amongst performance, reliability and recovery costs, and energy? The paper provides both explicit and asymptotic approximations for large systems towards addressing these basic questions.

Newly developed hypertext transfer protocol (HTTP)-based video streaming technologies enable flexible rate-adaptation under varying channel conditions. Accurately predicting the users' quality of experience (QoE) for rate-adaptive HTTP video streams is thus critical to achieve efficiency. An important aspect of understanding and modeling QoE is predicting the up-to-the-moment subjective quality of a video as it is played, which is difficult due to hysteresis effects and nonlinearities in human behavioral responses. This paper presents a Hammerstein-Wiener model for predicting the time-varying subjective quality (TVSQ) of rate-adaptive videos. To collect data for model parameterization and validation, a database of longer duration videos with time-varying distortions was built and the TVSQs of the videos were measured in a large-scale subjective study. The proposed method is able to reliably predict the TVSQ of rate adaptive videos. Since the Hammerstein-Wiener model has a very simple structure, the proposed method is suitable for online TVSQ prediction in HTTP-based streaming.

We investigate the benefits of channel-aware (opportunistic) scheduling of transmissions in ad hoc networks. The key challenge in optimizing the performance of such systems is finding a good compromise among three interdependent quantities: 1) the density of scheduled transmitters; 2) the quality of transmissions; and 3) the long term fairness among nodes. We propose two new channel-aware slotted CSMA protocols opportunistic CSMA and quantile-based CSMA (QT-CSMA) and develop new stochastic geometric models to quantify their performance in terms of spatial reuse and spatial fairness. When properly optimized, these protocols offer substantial improvements in performance relative to CSMA—particularly, when the density of nodes is moderate to high. In addition, we show that a simple version of QT-CSMA can achieve robust performance gains without requiring careful parameter optimization. The quantitative results in this paper suggest that channel-aware scheduling in ad hoc networks can provide substantial benefits which might far outweigh the associated implementation overheads.

Although electric vehicles are attracting increasing interest from consumers and automakers, the disadvantages associated with limited range and the current scarcity of public recharge stations have played a key role in limiting their large scale adoption. In this paper, we explore how information technologies might be used to mitigate ‘range anxiety’ and further strengthen the potential of electric vehicle integration with the renewable energy generation and storage. We motivate several mobile applications/services which would improve the ownership experience of electric vehicles and flexibility for energy providers. Our work leverages a previously proposed sensor platform for collecting travel-time and energy-usage data for a road network by a community of electric car drivers. Travel-time and energy-usage on a given road segment may exhibit substantial variability due to environmental and temporal factors, e.g., congestion, road's grade, AC on/off, etc. Such variability in turn, makes it difficult to accurately predict travel-times as well as the feasible range of a car given its current energy reserves. However, by collecting statistical data using cars/mobiles as probes one can quantify such uncertainty and develop complementary algorithms to counter the anxiety and time waste associated with such uncertainty. This paper develops the necessary (routing) algorithms to support these new classes of applications/services for electric vehicles.

Newly developed HTTP-based video streaming technology enables flexible rate-adaptation in varying channel conditions. The users' Quality of Experience (QoE) of rate-adaptive HTTP video streams, however, is not well understood. Therefore, designing QoE-optimized rate-adaptive video streaming algorithms remains a challenging task. An important aspect of understanding and modeling QoE is to be able to predict the up-to-the-moment subjective quality of video as it is played. We propose a dynamic system model to predict the time-varying subjective quality (TVSQ) of rate-adaptive videos that is transported over HTTP. For this purpose, we built a video database and measured TVSQ via a subjective study. A dynamic system model is developed using the database and the measured human data. We show that the proposed model can effectively predict the TVSQ of rate-adaptive videos in an online manner, which is necessary to be able to conduct QoE-optimized online rate-adaptation for HTTP-based video streaming.

This paper considers the design of cross-layer opportunistic transport for stored video over wireless networks with a slow varying (average) capacity. We focus on two key ideas: (1) scheduling data transmissions when capacity is high; and (2), exploiting knowledge of future capacity variations. The latter is possible when users' mobility is known or predictable, e.g., users riding on public transportation or using navigation systems. We consider the design of cross-layer transmission schedules which minimize system utilization (and thus possibly transmit/receive energy) while avoiding, if at all possible, rebuffering/delays, in several scenarios. For the single-user anticipative case where all future capacity variations are known beforehand; we establish the optimal transmission schedule is a Generalized Piecewise Constant Thresholding (GPCT) scheme. For the single-user partially anticipative case where only a finite window of future capacity variations is known, we propose an online Greedy Fixed Horizon Control (GFHC). An upper bound on the competitive ratio of GFHC and GPCT is established showing how performance loss depends on the window size, receiver playback buffer, and capacity variability. Finally we consider the multiuser case where we can exploit both future temporal and multiuser diversity. Our simulations and evaluation based on a measured wireless capacity trace exhibit robust potential gains for our proposed transmission schemes.

We propose two scheduling algorithms that seek to optimize the quality of scalably coded videos that have been stored at a video server before transmission. The first scheduling algorithm is derived from a Markov decision process (MDP) formulation developed here. We model the dynamics of the channel as a Markov chain and reduce the problem of dynamic video scheduling to a tractable Markov decision problem over a finite-state space. Based on the MDP formulation, a near-optimal scheduling policy is computed that minimizes the mean square error. Using insights taken from the development of the optimal MDP-based scheduling policy, the second proposed scheduling algorithm is an online scheduling method that only requires easily measurable knowledge of the channel dynamics, and is thus viable in practice. Simulation results show that the performance of both scheduling algorithms is close to a performance upper bound also derived in this paper.

This article presents a novel framework for data-centric storage (DCS) in a wireless sensor and actor network (WSAN) that employs a randomly selected set of data replication nodes, which also change over time. This enables reductions in the average network traffic and energy consumption by adapting the number of replicas to applications' traffic, while balancing energy burdens by varying their locations. To that end, we propose and validate a simple model to determine the optimal number of replicas, in terms of minimizing average traffic/energy consumption, based on measurements of applications' production and consumption traffic. Simple mechanisms are proposed to decide when the current set of replication nodes should be changed, to enable new applications and nodes to efficiently bootstrap into a working WSAN, to recover from failing nodes, and to adapt to changing conditions. Extensive simulations demonstrate that our approach can extend a WSAN's lifetime by at least 60%, and up to a factor of 10× depending on the lifetime criterion being considered. The feasibility of the proposed framework has been validated in a prototype with 20 resource-constrained motes, and the results obtained via simulation for large WSANs have been also corroborated in that prototype.

User perceived video quality depends on a variety of only partially understood factors, e.g., the application domain, content, compression, transport mechanism, and most importantly psycho-visual systems determining the ultimate Quality of Experience (QoE) of users. This paper centers on two key observations in addressing the problem of joint rate adaptation for video streams sharing a congested resource. First, we note that a user viewing a given video will experience temporal variations in the dependence of perceived video quality to the compression rate. Intuitively this is due to the possibly changing nature of the content, e.g., from an action to a slower scene. Thus, in allocating rates to users sharing a congested resource, in particular a wireless system where additional temporal variability in users' capacity may be high, content dependent tradeoffs can be realized to deliver a better overall average perceived video quality. Second, we note that such adaptation of users' rates, may result in temporal variations in video quality which combined with perceptual hysteresis effects will degrade users' QoE. We develop an asymptotically optimal online algorithm, requiring minimal statistical information, for optimizing users' QoE by realizing tradeoffs across mean, variance and fairness. Simulations show that our approach achieves significant gains in viewers' QoE. The novelty of this work lies not only in tackling the fundamental problem of achieving fair allocations of perceived video quality across a user population with time varying sensitivities and capacity, but, in addition, in integrating the deleterious impact that variations in perceived quality has on their QoE.

Finding a document or resource in an unstructured peer-to-peer network can be an exceedingly difficult problem. In this paper we propose a dynamic query routing approach that accounts for arbitrary overlay topologies, nodes with heterogeneous processing capacity and heterogenous class-based likelihoods of query resolution at nodes, reflecting the query loads and manner in which files/resources are distributed across the network. Finite processing capacity at nodes, e.g., reflecting their degree of altruism, can indeed limit the stabilizable load into the system. Our approach is shown to be throughput optimal subject to a grade of service constraint, i.e., it stabilizes the query load subject to a guarantee that queries' routes meet pre-specified class-based bounds on their associated a priori probability of query resolution. Numerical and simulation results show significant improvement in capacity region and performance benefits, in terms of mean delay, over random walk based searches. Additional aspects associated with reducing complexity, learning, and adaptation to class-based query resolution probabilities and traffic loads are studied.

We propose mechanisms to combat the congestion caused by non-homogeneities in the distribution of information, the peers' locations, and the demand for information in a peer-to-peer system for exchanging context. We propose two novel mechanisms for adapting the topology formed by the peers to the underlying traffic: our first mechanism employs virtual locations for the peers while the second modifies the edges connecting them. The positive effect of our mechanisms is evaluated experimentally. Our key metric is the average query delay, a critical performance indicator in a prototypical system we have already presented, expected to be used by mobile users for exchanging contextual information.

The unpredictability of the wireless medium poses a major challenge to delivering a high quality of experience (QoE) for real-time video services. Bursty co-channel interference is a prominent cause of wireless throughput variability, which leads to video QoE degradation, even for a fixed average channel quality. In this paper, we propose and analyze a network-level resource management algorithm termed interference shaping to smooth out the throughput variations (and hence improve the QoE) of video users by decreasing the peak rate of co-channel best effort users. Wireless link capacity variations are mapped to the real-time video packet loss rate, and the interference shaping QoE gain for video users is quantified by benchmarking against a modified multi-scale structural similarity (H-MS-SSIM) index. H-MS-SSIM is an accurate perceptual video quality metric that incorporates the important hysteresis effect whereby the current QoE (which is subjective) may strongly depend on the recent past. The proposed technique increases mean QoE and reduces the QoE variability over time, with a net perceptual increase of about 2-3x in illustrative settings while incurring insignificant decrease in the QoE for co-channel best effort users. Interference shaping can be implemented in both unicast and multicast real-time video streaming with much higher potential gains for multicast.

In this paper, we develop a framework for user association in infrastructure-based wireless networks, specifically focused on flow-level cell load balancing under spatially inhomogeneous traffic distributions. Our work encompasses several different user association policies: rate-optimal, throughput-optimal, delay-optimal, and load-equalizing, which we collectively denote α-optimal user association. We prove that the optimal load vector ρ*that minimizes a generalized system performance function is the fixed point of a certain mapping. Based on this mapping, we propose and analyze an iterative distributed user association policy that adapts to spatial traffic loads and converges to a globally optimal allocation. We then address admission control policies for the case where the system is overloaded. For an appropriate system-level cost function, the optimal admission control policy blocks all flows at cells edges. However, providing a minimum level of connectivity to all spatial locations might be desirable. To this end, a location-dependent random blocking and user association policy are proposed.

We study the problem of adaptive video data scheduling over wireless channels. We prove that, under certain assumptions, adaptive video scheduling can be reduced to a Markov decision process over a finite state space. Therefore, the scheduling policy can be optimized via standard stochastic control techniques using a Markov decision formulation. Simulation results show that significant performance improvement can be achieved over heuristic transmission schemes.

Multipath flow control has been proposed as a key way to improve the Internet's performance, reliability, and flexibility in supporting changing loads. Yet, at this point, there are very few tools to quantify the performance benefits; particularly in the context of a stochastic network supporting best effort flows, e.g., file transfers and web browsing sessions, where the metric of interest is transfer delay. This paper's focus is on developing analysis tools to evaluate flow-level performance and to support network design when multipath bandwidth allocation is based on proportional fairness. To overcome the analytical intractability of such systems we study closely related multipath approximations based on insensitive allocations such as balanced fairness. We obtain flow-level performance bounds on the mean per bit delay, exhibiting the role of resource pooling in the network, and use these to explore scenarios where increased path diversity need not result in high gains. While insightful these results are difficult to use to drive network design and capacity allocation. To that end, we study the large deviations for congestion events, i.e., accumulation of flows, in networks supporting multipath flow control. We show that such asymptotics are determined by certain critical resource pools, and study the sensitivity of congestion asymptotics to the pool's capacity and traffic loads. This suggests a disciplined approach to a capacity allocation problem in multipath networks based on a linear optimization problem.

We investigate the benefits of channel-aware (opportunistic) scheduling of transmissions in ad-hoc networks. The key challenge in optimizing the performance of such systems is finding a good compromise among three interdependent quantities, the density and channel quality of the scheduled transmitters, and the resulting interference at receivers. We propose two new channel-aware slotted CSMA protocols: opportunistic CSMA (O-CSMA) and quantile-based CSMA (QT-CSMA) and develop stochastic geometric models allowing us to quantify their performance in terms of spatial reuse and spatial fairness. When properly optimized these protocols offer substantial improvements in terms of both of these metrics relative to CSMA — particularly when the density of nodes is moderate to high. Moreover, we show that a simple version of QT-CSMA can achieve robust performance gains without requiring careful parameter optimization. The paper supports the case that the benefits associated with channel-aware scheduling in ad hoc networks, as in centralized base station scenarios, might far outweigh the associated overhead, and this can be done robustly using a QT-CSMA like protocol.

In this paper, we characterize the joint network capacity region (JNCR) for a licensed broadcast (primary) and ad hoc cognitive (secondary) network in a heterogeneous environment, including indoor and outdoor transmissions, under various spectrum (white space) detection techniques. Each technique delivers a different degree of RF-environment awareness - the more a device knows about its environment the larger the network capacity region. To quantify the gains, we develop a simple stochastic model capturing the interdependency amongst primary and secondary nodes and compare their joint capacity. Cognitive devices using the classical signal energy detection method are shown to perform poorly due to limitations on detecting primary transmitters in environments with indoor shadowing. This can be circumvented through direct use (e.g., database access) of location information on primary transmitters, or better yet, on that of primary receivers. The specific capacity trade-off between primary and secondary networks depends on white space detection techniques, resulting in JNCRs which range from complement convex to linear to (almost) convex. Our results show that, for example, the gain of positioning-assisted method over signal energy detection is 76% and the gain of receiver location-aware approach is 177% when the density of primary transmitters is 2 x 10^{-10}m^{-2}, the indoor shadowing level is -10dB, and the fraction of indoor nodes is 0.5. Furthermore we show that if cognitive devices have positioning information then the secondary network's capacity increases monotonically with increased indoor shadowing in the environment. These are the first analytical results quantifying, albeit for simple heterogeneous environmental model, the capacity gains one can expect when cognitive devices leverage additional information.

This paper presents a system-level approach to interference management in an infrastructure-based wireless network with full frequency reuse. The key idea is to use loose base-station coordination that is tailored to the spatial load distribution and the propagation environment to exploit the diversity in a user population's sensitivity to interference. System architecture and abstractions to enable such coordination are developed for both the downlink and the uplink cases, which present differing interference characteristics. The basis for the approach is clustering and aggregation of traffic loads into classes of users with similar interference sensitivities that enable coarse-grained information exchange among base stations with greatly reduced communication overheads. This paper explores ways to model and optimize the system under dynamic traffic loads where users come and go, resulting in interference-induced performance coupling across base stations. Based on extensive system-level simulations, we demonstrate load-dependent reductions in file transfer delay ranging from 20%-80% as compared to a simple baseline not unlike systems used in the field today while simultaneously providing more uniform coverage. Average savings in user power consumption of up to 75% is achieved. Performance results under heterogeneous spatial loads illustrate the importance of being traffic- and environment-aware.

We study the impact of user association policies on flow-level performance in interference-limited wireless networks. Most research in this area has used static interference models (neighboring base stations are always active) and resorted to intuitive objectives such as load balancing. In this paper, we show that this can be counterproductive in the presence of dynamic interference that couples the transmission rates to users at various base stations. We propose a methodology to optimize the performance of a class of coupled systems and apply it to study the user association problem. We show that by properly inducing load asymmetries, substantial performance gains can be achieved relative to a load-balancing policy (e.g., 15 times reduction in mean delay). We present a practical, measurement based, interference-aware association policy that infers the degree of interference-induced coupling and adapts to it. Systematic simulations establish that both our optimized static and adaptive association policies substantially outperform various dynamic policies that can, in extreme cases, even be susceptible to Braess's paradox-like phenomena, i.e., an increase in the number of base stations can lead to worse performance under greedy association policies. Furthermore, these results are robust to changes in file-size distributions, large-scale propagation parameters, and spatial load distributions.

This paper considers the design of multiuser opportunistic packet schedulers for users sharing a time-varying wireless channel from performance and robustness points of view. For a simplified model falling in the classical Markov decision process framework, we numerically compute and characterize mean-delay-optimal scheduling policies. The computed policies exhibit radial sum-rate monotonicity: As users' queues grow linearly, the scheduler allocates service in a manner that deemphasizes the balancing of unequal queues in favor of maximizing current system throughput (being opportunistic). This is in sharp contrast to previously proposed throughput-optimal policies, e.g., Exp rule and MaxWeight (with any positive exponent of queue length). In order to meet performance and robustness objectives, we propose a new class of policies, called the Log rule, that are radial sum-rate monotone (RSM) and provably throughput-optimal. In fact, it can also be shown that an RSM policy minimizes the asymptotic probability of sum-queue overflow. We use extensive simulations to explore various possible design objectives for opportunistic schedulers. When users see heterogenous channels, we find that emphasizing queue balancing, e.g., Exp rule and MaxWeight, may excessively compromise the overall delay. Finally, we discuss approaches to implement the proposed policies for scheduling and resource allocation in OFDMA-based multichannel systems.

In this paper we develop a framework for user association in infrastructure-based wireless networks, specifically focused on flow-level cell load balancing under spatially inhomogeneous traffic distributions. Our work encompasses several different user association policies: rate-optimal, throughput- optimal, delay-optimal, and load-equalizing, which we collectively denote α-optimal user association. We prove that the optimal load vector ρ∗ that minimizes a generalized system performance function is the fixed point of a certain mapping. Based on this mapping we propose and analyze an iterative distributed user association policy that adapts to spatial traffic loads and converges to a globally optimal allocation.

This paper presents a novel framework for Data Centric Storage in a wireless sensor and actor network that enables the use of a randomly-selected set of data replication nodes which also change over the time. This allows reducing the average network traffic and energy consumption by adapting the number of replicas to applications' traffic, while balancing energy burdens by varying their location. To that end we propose and validate a simple model to determine the optimal number of replicas, in terms of minimizing average traffic/energy consumption, from the measured applications' production/consumption traffic. Simple protocols/mechanisms are proposed to decide when the current set of replication nodes should be changed, to enable new applications and sensor nodes to efficiently bootstrap into a working sensor network, to recover from failing nodes, and to adapt to changing conditions. Extensive simulations demonstrate that our approach can extend a sensor network's lifetime by at least a 60%, and up to a factor of 10x depending on the lifetime criterion being considered.

A centralized wireless system is considered that is serving a fixed set of users with time varying channel capacities. An opportunistic scheduling rule in this context selects a user (or users) to serve based on the current channel state and user queues. Unless the user traffic is symmetric and/or the underlying capacity region a polymatroid, little is known concerning how performance optimal schedulers should tradeoffmaximizing current service rate(being opportunistic) versusbalancing unequal queues(enhancing user-diversity to enable future high service rate opportunities). By contrast, with currently proposed opportunistic schedulers, e.g., MaxWeight and Exp Rule, a radial sum-rate monotonic (RSM) scheduler de-emphasizes queue-balancing in favor of greedily maximizing the system service rate as the queue-lengths are scaled up linearly. In this paper, it is shown that an RSM opportunistic scheduler, p-Log Rule, is not only throughput-optimal, but also maximizes the asymptotic exponential decay rate of the sum-queue distribution for a two-queue system. The result complements existing optimality results for opportunistic scheduling and point to RSM schedulers as a good design choice given the need for robustness in wireless systems with both heterogeneity and high degree of uncertainty.

In this paper, we study several ways in which mobile terminals can backoff on their uplink transmit power in order to extend battery lifetimes. This is particularly effective when a wireless system is underloaded as the degradation in user's perceived quality of service can be negligible. The challenge, however, is developing a mechanism that achieves a good tradeoff among transmit power, idling/circuit power, and the performance customers will see. We consider systems with flow-level dynamics supporting either real-time or best effort (e.g., file transfers) sessions. The energy-optimal transmission strategy for real-time sessions is determined by solving a convex optimization. An iterative approach exhibiting superlinear convergence achieves substantial amount energy savings, e.g., more than 50% when the session blocking probability is 0.1% or less. The case of file transfers is more subtle because power backoff changes the system dynamics. We study energy-efficient transmission strategies that realize energy-delay tradeoff. The proposed mechanism achieves a 35%-75% in energy savings depending on the load and file transfer target throughput. A key insight, relative to previous work focusing onstaticscenarios, is that idling power has a significant impact on energy-efficiency, while circuit power has limited impact as the load increases.

Aggregate traffic loads and topology in multihop wireless networks may vary slowly, permitting MAC protocols to “learn” how to spatially coordinate and adapt contention patterns. Such an approach could reduce contention, leading to better throughput. To that end, we propose a family of MAC scheduling algorithms and demonstrate general conditions, which, if satisfied, ensure lattice rate optimality (i.e., achieving any rate-point on a uniform discrete lattice within the throughput region). This general framework enables the design of MAC protocols that meet various objectives and conditions. In this paper, as instances of such a lattice-rate-optimal family, we propose distributed, synchronous contention-based scheduling algorithms that: 1) are lattice-rate-optimal under both the signal-to-interference-plus-noise ratio (SINR)-based and graph-based interference models; 2) do not require node location information; and 3) only require three-stage RTS/CTS message exchanges for contention signaling. Thus, the protocols are amenable to simple implementation and may be robust to network dynamics such as topology and load changes. Finally, we propose a heuristic, which also belongs to the proposed lattice-rate-optimal family of protocols and achieves faster convergence, leading to a better transient throughput.

This paper considers the design of opportunistic packet schedulers for users sharing a time-varying wireless channel from the performance and the robustness points of view. Firstly, for a simplified model falling in the classical Markov decision process framework where arrival and channel statistics are known, we numerically compute and evaluate the characteristics of mean-delay-optimal scheduling policies. The computed policies exhibit radial sum-rate monotonicity (RSM), i.e., when users' queues grow linearly (i.e. scaled up by a constant), the scheduler allocates service in a manner that de-emphasizes the balancing of unequal queues in favor of maximizing current system throughput (being opportunistic). This is in sharp contrast to previously proposed policies, e.g., MaxWeight and Exp rule. The latter, however, are throughput-optimal, in that without knowledge of arrival/channel statistics they achieve stability if at all feasible. To meet performance and robustness objectives, secondly, we propose a new class of policies, called the Log rule, that are radial sum-rate monotone and provably throughput optimal. Our simulations for realistic wireless channels confirm the superiority of the Log rule which achieves up to 80% reduction in mean packet delays. However, recent asymptotic analysis showed that Exp rule is optimal in terms of minimizing the asymptotic probability of max-queue overflow. In turn, in a companion paper we have shown that an RSM policy minimizes the asymptotic probability of sum-queue overflow. Finally, we use extensive simulations to explore the various possible design objectives for opportunistic schedulers. When users see heterogenous channels, we find that minimizing the worst asymptotic exponent across users may excessively compromise the overall delay. Our simulations show that only if perfectly tuned to the load will the Exp rule achieve low homogenous tails across users. Otherwise the Log rule achieves a 20-75% reduction in the 99thpercentile for most, if not all, the users. We conclude that for wireless environments, where precise resource allocation is virtually impossible, the Log rule may be more desirable for its robust and graceful degradation to unpredicted changes.

A feedback scheme based on an iterative group splitting along with an opportunistic scheduling in a time division multiplexed wireless system with adaptive modulation is proposed in this paper. Considering a dynamic behavior of users in joining and leaving the multiuser networks, the proposed scheme does not assume any prior knowledge on users' channel statistics and therefore allows more robust and practical design. During a guard period, the proposed scheme exploits user feedback collisions in order to firstly find the signal-to-noise ratio (SNR) region in the adaptive modulation to which the best user belongs and secondly narrow down the range of user candidates by splitting user groups iteratively. As soon as one of the qualified users, whose channel quality falls into the SNR region for the best user, is found during the procedure, this user is selected by the scheduler and no more searching is pursued. Using an iterative group splitting, it is shown that the proposed scheme achieves a significant reduction in the number of feedbacks and thus scales with a large number of users.

This paper considers the interplay between rate adaptation and inter-session network coding gains in wireless mesh or ad hoc networks. Inter-session network coding opportunities at relay nodes depend on packets being overheard by surrounding nodes ? The more packets nodes overhear, the more opportunities relays have to combine packets, resulting in a potential increase in network throughput. Thus, by adapting its transmission rate, a node can increase the range over which its packets are overheard, enabling additional opportunities for coding and increased overall throughput. This paper considers inter-session coding, restricted to a single relay (bottleneck) node, or star network topology. Even for such simple topologies the optimal joint rate adaptation and network coding policy is known to be NP-hard. Optimal rate vector selection is a combinatorial optimization problem, which is NP-hard, and finding optimal coding scheme turns out to be a clique partitioning problem which is also NP-hard. So, we provide heuristics to find a suboptimal rate vector and coding scheme. Additionally, we provide a linear programming formulation for network coding when only pairwise intersession coding is allowed. We evaluate the averaged throughput in two different scenarios, in which relays have different access opportunities, giving some intuition on the impact of rate adaptation in lightly and heavily loaded systems. The gains of joint rate adaptation and network coding are marginal when the relay has a higher access opportunity than other nodes, or when the MAC operates ideally it ranges from 9% to 19% as compared to a network without network coding and 4% over a network using regular network coding. While, when the relay has equal access opportunity as other source nodes, which is more typical of todays MAC protocols under heavy loads, the gain ranges from 40% to 62% as compared to the standard relaying case and is upto around 20% as compared to a network with regular pairwise network coding. This can further be increased to a gain of 40% to 120% by replacing pairwise coding with sub-optimal general network coding scheme.

We study the performance of an opportunistic scheduling schememaximum quantile scheduling, i.e., scheduling a user whose current rate is in the highest quantile relative to its current rate distribution, in a wireless system. In a practical scenario it is unlikely that users' rate distributions are known at the scheduler, and have to be estimated via measurement. Under the assumption of fast fading, we prove a bound on the relative penalty associated with such estimates, showing that number of independent samples need only grow linearly with thenumber of active users. This is a fairly limited cost, suggesting one could track distributional changes in users' channels. By contrast other opportunistic scheduling schemes require estimating or setting weights/thresholds that implicitly depend not only on the number of users, but alsotheir rate distributions, andpossibly their traffic characteristics. In other words the penalty associated with tuning weights for other schemes can be higher than that associated with estimating users' rate distributions for maximum quantile scheduling. This statement is supported by our simulation results. Furthermore we prove that if rates are bounded and number of users is high, maximum quantile scheduling is sum average throughput maximizing subject to temporal fairness.

In this paper, we propose a mechanism to switch between multiple-input multiple-output (MIMO) with two transmit antennas and single-input multiple-output (SIMO) to conserve mobile terminals' energy. We focus on saving uplink RF transmission energy of mobile terminals in cellular systems supporting best effort traffic. The key idea is to judiciously slow down transmission rates when a base station is underutilized. We show that there exists a crossover point on the transmission rate below which SIMO consumes less power than MIMO when circuit power is included. The crossover point is an increasing function of the circuit power, the number of receive antennas and channel correlation, all of which increase the potential energy savings resulting from mode switching. We propose an adaptive mode switching algorithm combined with rate selection to maintain a user's target throughput while achieving energy efficiency. Extensive flow-level simulations under dynamic loads confirm that the proposed technique can reduce the transmission energy by more than 50% and enables an effective tradeoff between file transfer delay and energy conservation.

Next-generation cellular networks will provide higher cell capacity by adopting advanced physical layer techniques and broader bandwidth. Even in such networks, boundary users would suffer from low throughput due to severe intercell interference and unbalanced user distributions among cells, unless additional schemes to mitigate this problem are employed. In this paper, we tackle this problem by jointly optimizing partial frequency reuse and load-balancing schemes in a multicell network. We formulate this problem as a network-wide utility maximization problem and propose optimal offline and practical online algorithms to solve this. Our online algorithm turns out to be a simple mixture of inter- and intra-cell handover mechanisms for existing users and user association control and cell-site selection mechanisms for newly arriving users. A remarkable feature of the proposed algorithm is that it uses a notion of expected throughput as the decision making metric, as opposed to signal strength in conventional systems. Extensive simulations demonstrate that our online algorithm can not only closely approximate network-wide proportional fairness but also provide two types of gain, interference avoidance gain and load balancing gain, which yield 20∼100% throughput improvement of boundary users (depending on traffic load distribution), while not penalizing total system throughput.We also demonstrate that this improvement cannot be achieved by conventional systems using universal frequency reuse and signal strength as the decision making metric.

Two ways to substantially enhance wireless broadband capacity are full frequency reuse and smaller cells, both of which result in operational regimes that are highly dynamic and interference limited. This paper presents a system-level approach to interference management, that has reasonable backhaul communication and computation requirements. The basis for the approach is clustering and aggregation of measurements of the spatial diversity in sensitivity to interference associated with average user populations. This enables the system to exchange information and optimize coordinated transmission schedules using only coarse grained data. The paper explores various ways of optimizing such schedules: from a static, decoupled version to a dynamic version capturing user-level scheduling, fluctuating loads and inter-cell interference that couples base stations' performance. Based on extensive system-level simulations, we demonstrate reductions in file transfer delay ranging from 20-80%, from light to heavy loads, as compared to a simple baseline not unlike those in the field today. This improvement is achieved while providing more uniform coverage, and reducing base station power consumption by up to 45%.

This paper presents three algorithms that outperform all other published work for allocating a limited number of orthogonal frequency channels to access points (APs) in wireless networks. Unlike other work, we minimize interference seen by bothusersandAPs, we use aphysicalrather thanbinarymodel for interference, and we mitigate the impact of rogue RF interference. Our three algorithms have different mechanisms of switching the channels of APs based on the in- situ interference measured at clients and/or APs. The convergence of the algorithms is proven and characterized. Our algorithms consistently yield high throughput gains irrespective of network topology, the level of AP activity, and the number of controlled APs, rogue interferers, and available channels. We outperform the best published work by 15% and 18% for mean and median user throughputs respectively, and 81%, 168%, and 1011% for 25, 20, and 15 percentiles of user throughputs, respectively.

In this paper we evaluate interactions among flow-level performance metrics when integrating QoS and best effort flows in a wireless system using opportunistic scheduling. We introduce a simple flow-level model capturing the salient features of bandwidth sharing for an opportunistic scheduler which ensures a mean throughput to each QoS stream for every time slot. We then explore the flow-level performance showing that integration of QoS and best effort flows results in loss in opportunism, which in turn results in a reduction of the stability region, degradation in system throughput, and increased file transfer delay. These losses are shown to be proportional to opportunistic gains, the guaranteed bandwidth and number of QoS flows, but inversely proportional to SNR under a Rayleigh fading channel model. In an integrated system exploiting opportunism, local instability appears to be more severe than in wired networks and average delays experienced by best effort flows are prolonged. We suggest that a form of admission control for best effort flows is necessary to avoid local instability, and ensure adequate performance.

We propose a general family of MAC scheduling algorithms that achieve any rate-point on a uniform discrete-lattice within the throughput-region (i.e., lattice-throughput-optimal) under a physical interference model. Under the physical interference model, a centralized algorithm requires information on node locations (and distance among nodes) to determine a schedule that is provably throughput-optimal. In this paper, we propose a distributed, synchronous contention-based scheduling algorithm that (i) is lattice-throughput-optimal, (ii) does not require node location information, and (iii) has a signaling complexity that does not depend on network size. Thus, it is amenable to simple implementation, and is robust to network dynamics such as topology and load changes.

Ubiquitous computing promises to both assist us in everyday tasks and enhance our capabilities. Key elements towards fulfilling this goal are exploiting the physical and logical context in which computation occurs, in order to scope the interaction between users and applications. In this paper we describe an RFID-based platform allowing mobile entities to transparently associate with ubiquitous applications running within complex physical spaces. Entity- application associations occur only for applications within a physical space whose services are within predefined sets specified by an entity for that space type. Mobile entities in our platform are uniquely identified by a temporary ID, and further characterized by a set of attributes describing the above-mentioned set of services. Computation is mediated through the exchange of protocol messages guarded by such attributes. Furthermore, relevant application state is distributed on each mobile entity through a set of messaging boards, enabling a targeted form of communication and cooperation among ubiquitous applications. In this paper we report on our experience experimenting with this platform. Our initial results indicate that this platform is suitable for current RFID technology and exhibits low-cost, scalability and privacy.

This paper is the first analytical work to exhibit the substantial gains resulting from applying site specific knowledge to frequency allocation in wireless networks. Two new site-specific knowledge-based frequency allocation algorithms are shown to outperform all other published work. Site specific knowledge refers to knowledge of building layouts, the locations and electrical properties of APs, users, and physical objects. We assume that a central network controller communicates with all APs, and has site specific knowledge which enables the controller to predict, a priori, the received power from any transmitter to any receiver. Optimal frequency assignments are based on predicted powers to minimize interference and maximize throughput. Our algorithms consistently yield high throughput gains irrespective of network topology, AP activity level, and the number of APs, rogue interferers, and available channels. Our algorithms outperform the best published algorithm by up to 3.68%, 8.95%, 13.6%, 15.1%, 25.8%, and 84.9% for 50, 25, 20, 15, 10, and 5 percentiles of user throughputs, respectively.

Recounts the career of Dr. Margarida F. Jacome, a Professor with the Department of Electrical and Computer Engineering, University of Texas (UT), Austin. Also includes recollections from her colleagues and students.

In this paper, we propose a stochastic geometric model to study the energy burdens seen in a large scale hierarchical sensor network. The network makes use of aggregation nodes, for compression, filtering, and/or data fusion of locally sensed data. Aggregation nodes (AGNs) then relay the traffic to mobile sinks. While aggregation may substantially reduce the overall traffic on the network, it may have the deleterious effect of concentrating loads on paths between AGNs and the sinks—such inhomogeneities in the energy burden may in turn lead to nodes with depleted energy reserves. To remedy this problem, we consider how one might achieve a more balanced energy burden across the network by spreading traffic, i.e., using a multiplicity of paths between AGNs and sinks. The proposed model reveals, how various aspects of the task at hand impact the characteristics of energy burdens on the network and in turn the lifetime for the system. We show that the scale of aggregation and degree of spreading can be optimized. Additionally, if the sensing activity involves large amounts of data flowing to sinks, then inhomogeneities in the energy burdens seen by nodes around the sinks will be hard to overcome, and indeed the network appears to scale poorly. By contrast, if the sensed data is bursty in space and time, then one can reap substantial benefits from aggregation and balancing.

The transmission capacity (TC) of a wirelessad hocnetwork is defined as the maximum spatial intensity of successful transmissions such that the outage probability does not exceed some specified threshold. This work studies the improvement in TC obtainable with successive interference cancellation (SIC), an important receiver technique that has been shown to achieve the capacity of several classes of multiuser channels, but has not been carefully evaluated in the context ofad hocwireless networks. This paper develops closed-form upper bounds and easily computable lower bounds for the TC ofad hocnetworks with SIC receivers, for both perfect and imperfect SIC. The analysis applies to any multiuser receiver that cancels the$K$strongest interfering signals by a factor$z \in [0,1]$. In addition to providing the first closed-form capacity results for SIC inad hocnetworks, design-relevant insights are made possible. In particular, it is shown that SIC should be used with direct sequence spread spectrum. Also, any imperfections in the interference cancellation rapidly degrade its usefulness. More encouragingly, only a few—often just one—interfering nodes need to be canceled in order to get the vast majority of the available performance gain.

We study reducing feedback overhead of users' channel state information required for opportunistic scheduling at a base station while minimizing the throughput penalty incurred due to reduced feedback. We first propose a simple contention based scheme known as 'static splitting' for best effort traffic. The idea is to divide users into static groups, with users that belong to a group, and have their currently supported rate above a threshold, contending to send their current feedback to the base station. This is combined with maximum quantile scheduling -scheduling a user whose current rate is high relative to its distribution, to obtain thresholds that are independent of users' rate distributions even when they are heterogeneous, allowing off-line optimization of thresholds. Next we develop the insight that for a traffic mixture of best effort and real-time traffic one has to combine contention and polling to reduce feedback while providing quality of service. We propose a scheme based on this insight. Under this scheme we prove a lower bound on the service seen by a real-time when users' channel capacities are fast fading. Furthermore, we propose a heuristic modification that is able to exploit a larger fraction of opportunism. Simulation results illustrate the performance advantage of the proposed schemes.

This paper presents an efficient iterative load-balancing algorithm for time and bandwidth allocation among access points (APs) and users subject to heterogeneous fairness and application requirements. The algorithm can be carried out either at a central network switch with site-specific propagation predictions, or in a decentralized manner. The algorithm converges to maximum network resource utilization from any starting point, and usually converges in 3 to 9 iterations in various network conditions including users joining, leaving, and moving within a network and various network sizes. Such a fast convergence allows real-time implementations of our algorithm. Simulation results show that our algorithm has merits over other schemes especially when users exhibit clustered patterns: Our algorithm, when assuming multiple radios at each user, achieves 48% gain of median throughput as compared with the max-min fair load-balancing scheme (also with the multi-radio assumption) while losing 14% of fairness index; we also achieve 26% gain of median throughput and 52% gain of fairness index over the strongest-signal-first scheme (which assumes each user has only a single radio). When only a single radio is used, our algorithm is similar to the max-min fairness scheme, and is still better than SSF with 44% gain of 25-percentile throughput and 37% gain of fairness index

Device and interconnect fabrics at the nanoscale will have a density of defects and susceptibility to transient faults far exceeding those of current silicon technologies. In this paper we introduce a new performance optimization dimension at the microarchitecture level which can mitigate overheads introduced by fault tolerance. This is achieved by directly exposing reliability versus delay design trade-offs while incorporating novel forms of speculation which use faster but less reliable versions of a microarchitecture's performance critical components. Based on a parameterized microarchitecture, we exhibit the benefits of optimizing these tradeoffs.

In this paper we investigate the use of proactive multipath routing to achieve energy efficient operation of ad hoc wireless networks. The focus is on optimizing trade-offs between the energy cost of spreading traffic and the improved spatial balance of energy burdens. We first propose a simple scheme for multipath routing based on node proximity. Then combining stochastic geometric and queuing models we develop a continuum model for such networks, permitting consideration of different types of designs, i.e., with and without energy replenishing and storage capabilities. We propose a parameterized family of energy balancing strategies for grids and approximate the spatial distributions of energy burdens based on their associated second order statistics. Our analysis and simulations show the fundamental importance of the tradeoff explored in this paper, and how its optimization depends on the relative values of the energy reserves/storage, replenishing rates, and network load characteristics. Simulation results show that proactive multipath routing decreases the probability of energy depletion by orders of magnitude versus that of shortest path routing scheme when the initial energy reserve is high.

In this paper we investigate network design for a wireless service provider using two orthogonal technologies: a WAN technology with uniform spatial coverage and set of LAN access points each with limited coverage. We assume that the system is designed so that users (or their agents) independently and greedily select among the two options based on maximizing a specified utility function which may be a function of the quality of the wireless link, distance to the access points, and/or congestion on system resources. We focus on two complementary aspects of this problem. On the one hand we study system performance under such decision-making strategies. We show convergence of decision-making process to an equilibrium, and that a congestion-sensitive utility can provide substantial (300%) performance improvements over natural proximity-based criterion. On the other hand, we consider various problems associated with dimensioning typically expensive backhaul links, for the WAN and set of LAN hotspots. Our results show how to best jointly exploit technologies with different coverage scales so as to statistically multiplex spatial load fluctuations in order to reduce backhaul costs.

This paper proposes a new principle for designing MAC protocols for spread spectrum based ad hoc networks -- inducing spatial clustering in contending transmitters/receivers. We first highlight the advantages of spread spectrum in handling quality of service (QoS) requirements, enhancing energy efficiency, and enabling spatial multiplexing of bursty traffic. Then, based on stochastic geometric models and simulation, we show how idealized contention resolution among randomly distributed nodes results in clustering of successful transmitters and receivers, in turn leading to efficient spatial reuse. This motivates the central idea of the paper which is to explicitly induce clustering among contending nodes to achieve even better spatial reuse. We propose two distributed mechanisms to realize such clustering and show substantial capacity gains over simple random access/ALOHA-like and even RTS/CTS based protocols. We examine under what regimes such gains can be achieved, and how clustering and contention resolution mechanisms should be optimized to do so. We propose the design of ad hoc networks supporting hop-by-hop relaying on different spatial scales. By allowing nodes to relay beyond the set of nearest neighbors using varying transmission ranges (scales), one can reduce the number of hops between a source and destination so as to meet end-to-end delay requirements. To that end we propose a multi-scale MAC clustering and power control mechanism to support transmissions with different ranges while achieving high spatial reuse. The considerations, analysis and simulations included in this paper suggest that the principle of inducing spatial clustering in contention has substantial promise towards achieving high spatial reuse, QoS, and energy efficiency in spread spectrum ad hoc networks.

We determine the asymptotic scaling for the per user throughput in a large hybrid ad hoc network, i.e., a network with both ad hoc nodes, which communicate with each other via shared wireless links of capacity W bits/s, and infrastructure nodes which in addition are interconnected with each other via high capacity links. Specifically, we consider a network model where ad hoc nodes are randomly spatially distributed and choose to communicate with a random destination. We identify three scaling regimes, depending on the growth of the number of infrastructure nodes, m relative to the number of ad hoc nodes n, and show the asymptotic scaling for the per user throughput as n becomes large. We show that when m /spl lsim/ /spl radic/n/logn the per user throughput is of order W//spl radic/n log n and could be realized by allowing only ad hoc communications, i.e., not deploying the infrastructure nodes at all. Whenever /spl radic/n/log n /spl lsim/ m /spl lsim/ n/log n, the order for the per user throughput is Wm/n and, thus, the total additional bandwidth provided by m infrastructure nodes is effectively shared among ad hoc nodes. Finally, whenever m /spl gsim/ n/log n, the order of the per user throughput is only W/log n, suggesting that further investments in infrastructure nodes will not lead to improvement in throughput. The results are shown through an upper bound which is independent of the routing strategy, and by constructing scenarios showing that the upper bound is asymptotically tight.

Measurement of visual quality is of fundamental importance to numerous image and video processing applications. The goal of quality assessment (QA) research is to design algorithms that can automatically assess the quality of images or videos in a perceptually consistent manner. Traditionally, image QA algorithms interpret image quality as fidelity or similarity with a "reference" or "perfecft" image in some perceptual space. Such "full-referenc" QA methods attempt to achieve consistency in quality prediction by modeling salient physiological and psychovisual features of the human visual system (HVS), or by arbitrary signal fidelity criteria. In this paper, we approach the problem of image QA by proposing a novel information fidelity criterion that is based on natural scene statistics. QA systems are invariably involved with judging the visual quality of images and videos that are meant for "human consumption." Researchers have developed sophisticated models to capture the statistics of natural signals, that is, pictures and videos of the visual environment. Using these statistical models in an information-theoretic setting, we derive a novel QA algorithm that provides clear advantages over the traditional approaches. In particular, it is parameterless and outperforms current methods in our testing. We validate the performance of our algorithm with an extensive subjective study involving 779 images. We also show that, although our approach distinctly departs from traditional HVS-based methods, it is functionally similar to them under certain conditions, yet it outperforms them due to improved modeling. The code and the data from the subjective study are available at.

In this paper, upper and lower bounds on the transmission capacity of spread-spectrum (SS) wireless ad hoc networks are derived. We define transmission capacity as the product of the maximum density of successful transmissions multiplied by their data rate, given an outage constraint. Assuming that the nodes are randomly distributed in space according to a Poisson point process, we derive upper and lower bounds for frequency hopping (FH-CDMA) and direct sequence (DS-CDMA) SS networks, which incorporate traditional modulation types (no spreading) as a special case. These bounds cleanly summarize how ad hoc network capacity is affected by the outage probability, spreading factor, transmission power, target signal-to-noise ratio (SNR), and other system parameters. Using these bounds, it can be shown that FH-CDMA obtains a higher transmission capacity than DS-CDMA on the order of M/sup 1-2//spl alpha//, where M is the spreading factor and /spl alpha/>2 is the path loss exponent. A tangential contribution is an (apparently) novel technique for obtaining tight bounds on tail probabilities of additive functionals of homogeneous Poisson point processes.

This work investigates support of rate adaptive multimedia streams on communication networks. Optimal and practical mechanisms to maximize the customer average quality of service (QoS), defined in terms of a normalized time average received rate, are established. By scaling the arrival rate and link capacity, we obtain asymptotic expressions for customer average QoS in the case of networks with single bottleneck links. The optimal adaptation policy is identified as the solution to an integer program which has an intuitive "sort by volume" interpretation for the case of single bottleneck links, where stream volume is the total number of bits associated with a stream at its maximum resolution. Our asymptotic analysis shows the optimal adaptation policy may yield performance improvements of up to 42% over baseline policies. We demonstrate that a static multi-class admission control policy can achieve the same asymptotic QoS as that of the optimal adaptation policy. This implies that dynamic adaptation may be unnecessary for large capacity networks with appropriate call admission.

Recent successes in the development and self-assembly of nanoelectronic devices suggest that the ability to manufacture dense nanofabrics is on the near horizon. However, the tremendous increase in device density of nanoelectronics will be accompanied by a substantial increase in hard and soft faults, posing a major challenge to current design methodologies and tools. In this paper we propose a novel probabilistic design paradigm for defective but reconfigurable nanofabrics. The new design goal is to devise an appropriate structural/behavioral decomposition which improves scalability by constraining the reconfiguration process, while meeting a desired probability of successful instantiation, i.e, yield. Our approach not only addresses the scalability problem in configuring dense nanofabrics subject to defects, but gives a rich framework in which critical trade-offs among performance, yield, and per chip cost can be explored. We present a concrete instance of the approach and show extensive experimental results supporting these claims.

Upper and lower bounds on the transmission capacity of direct-sequence CDMA wireless ad hoc networks are derived. The transmission capacity is a stochastic measure of the allowable number of transmissions per unit area, and is a generalization of previous measures of ad hoc network capacity. Successive interference cancellation (SIC) is attractive for DS-CDMA ad hoc networks since the dominant nearby interferers can be cancelled. Our closed-form results cleanly summarize the dependence of ad hoc network capacity on pathloss, spreading, outage probability, and interference cancellation accuracy. Other multiple access schemes, such as CSMA and DS-CDMA without SIC, are special cases. Perfect interference cancellation increases transmission capacity by nearly two orders of magnitude. Furthermore, cancelling just the strongest interferer generally gives the majority of the capacity gain, so the latency and complexity cost of SIC should be negligible.

Internet traffic primarily consists of packets from elastic flows, i.e., Web transfers, file transfers (FTP), and e-mail, whose transfers are mediated via the transmission control protocol. We develop a conditional sampling technique to analyze throughput correlations among elastic flow classes based on flow level measurements from current network traffic monitoring tools. The primary contributions of the paper are: (1) a demonstration of throughput correlation among temporally overlapping flows on congested resources by using analytical/simulation models; (2) application of a multivariate statistical method (principal components) to infer network properties, such as the number of resources shared by flows in the network, from non-intrusive, flow level measurements collected at a single site. Our proposal for using flow level measurements to infer network properties differs significantly from previous network tomography research that has employed end-to-end packet level measurements for making inferences.

We develop methods to infer path or bottleneck sharing among TCP flow classes based on flow level measurements available from the current traffic monitoring tools. Our premise is that flows that temporally overlap on the congested resources have correlated throughputs. We propose to use factor analysis to explore the correlation structure of flow class throughputs in order to hypothesize which flow classes might share congested resources. The effectiveness of this "black box" approach is studied using the empirical data. We show that making such inferences based on flow level statistics is viable in practice, and can serve as an effective, novel tool for network design and configuration decisions. Our work on inferring bottleneck sharing differs significantly from the previous work in that we consider flow level instead of packet level statistics, and hence may potentially influence research in that area. Possible applications of this technique include network monitoring and root cause analysis of poor performance.

We study the 'service capacity' of peer to peer (P2P) file sharing applications. We begin by considering a transient regime which is key to capturing the ability of such systems to handle bursty traffic, e.g., flash crowds. In this context our models, based on age dependent branching processes, exhibit exponential growth in service capacity, and permit the study of sensitivity of this growth to system policies and parameters. Then we consider a model for such systems in steady state and show how the average delay seen by peers would scale in the offered load and rate at which peers exit the system. We find that the average delays scale well in the offered load. In particular the delays are upper bounded by some constant given any offered load and even decrease in the offered load if peers exit the system slowly. We validate many of our findings by analyzing traces obtained from a second generation P2P application called BitTorrent.

In this paper, we study how to reduce energy consumption in large-scale sensor networks, which systematically sample a spatio-temporal field. We begin by formulating a distributed compression problem subject to aggregation (energy) costs to a single sink. We show that the optimal solution is greedy and based on ordering sensors according to their aggregation costs-typically related to proximity-and, perhaps surprisingly, it is independent of the distribution of data sources. Next, we consider a simplified hierarchical model for a sensor network including multiple sinks, compressors/aggregation nodes, and sensors. Using a reasonable metric for energy cost, we show that the optimal organization of devices is associated with a Johnson-Mehl tessellation induced by their locations. Drawing on techniques from stochastic geometry, we analyze the energy savings that optimal hierarchies provide relative to previously proposed organizations based on proximity, i.e., associated Voronoi tessellations. Our analysis and simulations show that an optimal organization of aggregation/compression can yield 8%-28% energy savings depending on the compression ratio.

Most limitations in mechanisms geared at achieving quality-of-service (QoS) in wireless ad hoc networking can be traced to solutions based on mapping wireless networks to a wireline paradigm of nodes and links. We contend that this paradigm is not appropriate since links are not physical entities and do not accurately represent the radio frequency (RF) media. Using the link abstraction makes arbitration of the use of the RF media cumbersome leaving only overprovisioning techniques to deliver QoS. In this paper, we argue that an appropriate paradigm should match the physics of the network. The critical resource is electromagnetic spectrum in a space; in turn, this results in a complex paradigm since the part of the spectrum-space that each node wants to use is unique to that node and its destination and will overlap with parts that other nodes may want to use creating interdependences among nodes. This paper describes protocol approaches for access and routing that seek solutions within this wireless paradigm. Access is arbitrated using synchronous signaling and topology is resolved through the dissemination of node states. This approach provides an intuitive framework that provides mechanisms that can be exploited to arbitrate RF media use and implement traffic engineering techniques to deliver QoS. Our proposed approach provides a novel way of tracking the state of the network that can serve as a unified state dissemination mechanism to simultaneously support routing, multicasting, and most QoS heuristics.

With a view on improving user-perceived performance on networks supporting best effort flows, e.g., multimedia/data file transfers, we propose a family of bandwidth allocation criteria that depends on the residual work of on-going transfers. Analysis and simulations show that allocating bandwidth in this fashion can significantly improve the user-perceived delay, bit transmission delay, and throughput over traditional approaches, e.g., by 58% on an 80% loaded linear network. A simple implementation based on TCP Reno, exemplifies how one might approach practically realizing such gains. We discuss several other advantages of incorporating such differentiation at the transport level. In particular we make the case that favoring small transfers combined with user impatience or peak rate constraints, both of which are natural mechanisms for users to express the utility of completing transfers, offers a lightweight approach to achieving good overall network goodput and/or utility for best effort networks.

Rate adaptive multimedia streams offer significant system and client benefits over nonadaptive streams. These benefits come at the price of increased complexity in providing adequate network support and difficulty in understanding how rate adaptation protocols affect client perceived QoS. In this paper we define quality of service in terms of the mean rate seen by the client. We identify an intuitive optimal adaptation policy that maximizes QoS. We suggest an appropriate scaling regime for rate adaptive streams and identify asymptotic QoS for large capacity networks under the optimal adaptation policy. Implementation of the optimal adaptation policy presents several obstacles that render it infeasible. We define a multiclass admission control policy that achieves asymptotically equivalent QoS to that achieved under the optimal adaptation policy, but without the need for dynamic adaptation. Our work carries implications for network designers and content providers.

Multiple energy conserving approaches have been proposed for wireless networks that are exploited by the link layer and network layer protocols. Unfortunately, integrating these approaches in ad hoc networks is difficult. Due to the temporally random nature of access protocols, methods based on entering low energy states cause severe degradation of network capacity and also degrade the performance of routing protocols. Meanwhile, methods used by routing protocols that give preference to shorter links or attempt to balance load to prolong the longevity of the plurality of nodes require commitment to one or the other of these metrics without regard to link layer approaches. We show that through the integrated use of our access and routing protocols, synchronous collision resolution (SCR) and node state routing (NSR), that these types of energy conservation mechanisms can be managed simultaneously. We conclude with a simple simulation of the integrated use of these protocols. The simulations demonstrate that these protocols reduce the rate of energy consumption by the network but that in determining their effectiveness, the end-to-end throughput of the network must be considered.

With a view on improving user perceived performance on networks supporting elastic flows, e.g., multimedia/data file transfers, we identify the key properties that an online dynamic bandwidth allocation policy should have. We then propose a family of bandwidth allocation criteria which depends on the residual work of on-going transfers. Analysis and simulations show that allocating bandwidth in this fashion can improve the user perceived average bit transmission delay (BTD), i.e., delay/flow size, by up to 70% at 80% traffic load over traditional approaches. A simple implementation based upon TCP Reno, exemplifies how one might approach practically realizing such gains. Further studies on simple network topologies show that as the penetration of the proposed transport mechanism increases, users will have the proper incentives to upgrade from TCP Reno, and that the overall performance is better for all users once the penetration exceeds 20%.

Specialized clustered very large instruction word (VLIW) processors combined with effective compilation techniques enable aggressive exploitation of the high instruction-level parallelism inherent in many embedded media applications, while unlocking a variety of possible performance/cost tradeoffs. In this work, the authors propose a methodology to support early design space exploration of clustered VLIW datapaths, in the context of a specific target application. They argue that, due to the large size and complexity of the design space, the early design space exploration phase should consider only design space parameters that have a first-order impact on two key physical figures of merit: clock rate and power dissipation. These parameters were found to be: maximum cluster capacity, number of clusters, and bus (interconnect) capacity. Experimental validation of their design space exploration algorithm shows that a thorough exploration of the complex design space can be performed very efficiently in this abstract parameterized design space.

Clustering is an effective method to increase the available parallelism in VLIW datapaths without incurring severe penalties associated with a large number of register file ports. Efficient utilization of a clustered datapath requires careful binding/assignment of operations to clusters. The article proposes a binding algorithm that effectively explores trade-offs between in-cluster operation serialization and delays associated with data transfers between clusters. Extensive experimental evidence is provided showing that the algorithm generates high quality solutions for representative kernels, with up to 33% improvement over a state-of-the-art binding algorithm.

In order to meet the high throughput requirements of applications exhibiting high ILP, VLIW ASIPs may increasingly include large numbers of functional units(FUs). Unfortunately, ”switching“ data through register files shared by large numbers of FUs quickly becomes a dominant cost/ performance factor suggesting that clustering smaller number of FUs around local register files may be beneficial even if data transfers are required among clusters. With such machines in mind, we propose a compiler transformation, predicated switching, which enables aggressive speculation while leveraging the penalties associated with inter-cluster communication to achieve gains in performance. Based on representative benchmarks, we demonstrate that this novel technique is particularly suitable for application specific clustered machines aimed at supporting high ILP as compared to state-of-the-art approaches.

Clustering is an effective method to increase the available parallelism in VLIW datapaths without incurring severe penalties associated with large number of register file ports. Efficient utilization of a clustered datapath requires careful binding of operations to clusters. The paper proposes a binding algorithm that effectively explores tradeoffs between in-cluster operation serialization and delays associated with data transfers between clusters. Extensive experimental evidence is provided showing that the algorithm generates high quality solutions for basic blocks, with up to 29% improvement over a state-of-the-art advanced binding algorithm.

Previous work on congestion control in TCP/IP networks combines improved end-user transmission mechanisms with active queue management schemes at network routers. An active queue management scheme consists of two stages. In order to stabilize the queues at a router, one must first determine an appropriate packet marking probability given the current degree of congestion. Second, in order to realize the desired marking probability, an effective packet marking algorithm needs to be implemented to decide which packets should be marked. Researchers have increasingly focused on the first stage, namely determining the fraction of packets to mark, overlooking the fact that for a given marking probability, various possible marking algorithms result in different queue variance, and thus loss, delay, and jitter. We propose a marking algorithm DREAM. DREAM decouples the functions of reducing queue variance and randomizing the phases of flows. Compared to existing schemes, it significantly reduces queue variance while avoiding flow synchronization. Based on a simple Markov chain model we explain why our scheme is superior. Our simulation results confirm its effectiveness. Furthermore, DREAM is simple to implement and has a much lower overhead as compared with existing mechanisms.

Empirical work has shown that up to 20% of the volume transferred on data networks might correspond to 'aborted' connections, i.e., badput. With this in mind, we propose two generic models that capture a variety of user impatience behaviors and investigate their impact on user perceived and actual system performance achieved by various bandwidth sharing schemes. Our study suggests that differentiated bandwidth allocation based on job size, rather than using traditional fair share allocations, results in a more 'graceful' performance degradation and, particularly in the presence of impatient users, leads to better network efficiency as well as user perceived performance.

As the use of IP multicast sessions becomes widespread, the potential benefits derived from currently unavailable topological information on multicast distribution trees may become increasingly critical. We propose a framework for discovering the topology of shared multicast trees based on a novel fan-out decrement mechanism analogous to time-to-live (TTL) decrementing in IP. We propose an algorithm for topology discovery based on the matrix of path/fan-out distances among a set of E session members-the algorithm's computational complexity is O(|E|/sup 2/). We exhibit sufficient conditions for topology discovery based on a reduced distance matrix, and propose a practical protocol to acquire this information requiring the exchange of 2|E| multicast messages of size O(|E|). Finally, we show how the same approach permits nodes to discover the multicast distribution tree associated with members within their fan-out/TTL scoped neighborhoods. This permits one to reduce the computational costs while making the communication costs proportional to the size of neighborhoods.

We consider the stability and performance of a model for networks supporting services that adapt their transmission to the available bandwidth. Not unlike real networks, in our model, connection arrivals are stochastic, each has a random amount of data to send, and the number of ongoing connections in the system changes over time. Consequently, the bandwidth allocated to, or throughput achieved by, a given connection may change during its lifetime as feedback control mechanisms react to network loads. Ideally, if there were a fixed number of ongoing connections, such feedback mechanisms would reach an equilibrium bandwidth allocation typically characterized in terms of its "fairness" to users, e.g., max-min or proportionally fair. We prove the stability of such networks when the offered load on each link does not exceed its capacity. We use simulation to investigate performance, in terms of average connection delays, for various fairness criteria. Finally, we pose an architectural problem in TCP/IPs decoupling of the transport and network layer from the point of view of guaranteeing connection-level stability, which we claim may explain congestion phenomena on the Internet.

In this paper we study source routing in an environment where imperfect state information is the norm. The uncertainty involved in several aspects of the routing process renders the route choices less than "optimal". We start by conducting an experiment that compares the performance of an "inference"-based routing scheme to that of the traditional approach based on delayed link state broadcast. We then resort to a set of simple models to investigate to what extent the "crude" routing decisions based on limited statistical information conform to the ideal choices. In the conventional routing context, we identify a useful measure, the gap, which quantifies how successful a "crude" routing decision is likely to be. In the quality of service routing context we explore the possibility that a route choice based on limited statistical information is the "most likely" path to satisfy the user requirement. We also discuss the role of critical points, whose relative position affects the robustness of the routing decisions with respect to uncertain user requirement. Simulations establish the existence of gap and critical point in a realistic setup. The impacts of these observations on the effectiveness of a simple path caching scheme are then discussed.

VLIW ASIPs provide an attractive solution for increasingly pervasive real-time multimedia and signal processing embedded applications. In this paper we propose an algorithm to support trade-off exploration during the early phases of the design/specialization of VLIW ASIPs with clustered datapaths. For purposes of an early exploration step, we define a parameterized family of clustered datapaths D(m,n), where m and n denote interconnect capacity and cluster capacity constraints on the family. Given a kernel, the proposed algorithm explores the space of feasible clustered datapaths and returns: a datapath configuration; a binding and scheduling for the operations; and a corresponding estimate for the best achievable latency over the specified family. Moreover, we show how the parameters m and n, as well as a target latency optionally specified by the designer, can be used to effectively explore trade-offs among delay, power/energy, and latency. Extensive empirical evidence is provided showing that the proposed approach is strikingly effective at attacking this complex optimization problem.

Wireless network access protocols can assist nodes to conserve energy by identifying when they can enter a low energy doze state. The goal is to put all nodes not involved in a transmission into the doze state. However, in doing so, one must tradeoff the energy cost of coordinating dozing with the energy savings of putting nodes to sleep. In this paper, we define three alternative directory protocols that may be used by a central node to coordinate the transmission of data and the dozing of nodes. We attempt to optimize their performance by using scheduling and protocol parameter tuning. In addition, we consider the impact of errors and error recovery methods on energy consumption. Although one can argue that carefully scheduling transmissions will improve performance, ultimately, appropriately tuning protocols reduces scheduling significance. In most cases, scheduling transmissions between the same nodes continuously and ordering such transmissions shortest processing time first results in good performance. However, the ability of our protocols to conserve energy is highly dependent on 1) network size, 2) traffic type (e.g. down/uplink, and peer-to-peer) and 3) channel bit error rate. In particular, we show that when protocols are faced with packet errors, more elaborate schemes of coordinating the dozing of nodes can pay-off. Our simulations show that while energy savings can vary by a factor of 10 over the class of protocols we considered throughput varies by less than 20%.

We consider problems in traffic integration and routing for virtual path (VP)-based multiservice networks. The objective is to exploit statistical multiplexing among various traffic types in order to improve system utilization. Difficulties arise due to statistical multiplexing since a connection's bandwidth requirement depends on the characteristics of the interfering traffic. We first consider whether segregating heterogeneous traffic with different quality of service (QoS) requirements on separate VPs is desirable. Next we consider routing heterogeneous permanent connections given a predefined traffic type mix onto multiple VPs between a source destination pair. We show that it is not necessarily advantageous to have each VP carry every traffic type. In fact, perhaps surprisingly, an optimum solution to this problem suggests that only a small number of traffic types, or even homogeneous traffic, need be present on each VP. Based on this observation, we propose a simple alternative routing algorithm with routing sequences depending on the traffic mix.

We propose a novel explicit rate flow control algorithm intended for available-bit-rate (ABR) service on an ATM network subject to loss and fairness constraints. The goal is to guarantee low cell loss in order to avoid throughput collapse due to retransmission by higher level protocols. The mechanism draws on measuring the current queue length and bandwidth availability, as well as tracking the current number of active sessions contending for capacity, to adjust an explicit bound on the source transmission rates. We identify the factors that affect queue overflows and propose simple design rules aimed at achieving transmission with controlled loss in a dynamic environment. We also discuss how conservative design rules might be relaxed by accounting for statistical multiplexing in bandwidth sharing among bursty ABR sources and variable-bit-rate (VBR) sources.

Traditional lower bound estimates on latency for dataflow graphs assume no data transfer delays. While such approaches can generate tight lower bounds for datapaths with a centralized register file, the results may be uninformative for datapaths with distributed register file structures that are characteristic of VLIW ASIPs (very large instruction word application-specific instruction set processors). In this paper, we propose a latency bound that accounts for such data transfer delays. The novelty of our approach lies in constructing the "window dependency graph" and bounds associated with the problem which capture delay penalties due to operation serialization and/or data moves among distributed register files. Through a set of benchmark examples, we show that the bound is competitive with state-of-the-art approaches. Moreover, our experiments show that the approach can aid an iterative improvement algorithm in determining good functional unit assignments-a key step in code generation for VLIW ASIPs.

We consider the stability and performance of a model for networks supporting services that adapt their transmission to the available bandwidth. Not unlike real networks, in our model connection arrivals are stochastic and have a random amount of data to send, so the number of connections in the system changes over time. In turn the bandwidth allocated to, or throughput achieved by, a given connection, may change during its lifetime due to feedback control mechanisms that react to congestion and thus implicitly to the number of ongoing connections. Ideally, for a fixed number of connections, such mechanisms reach an equilibrium typically characterized in terms of its 'fairness' in allocating bandwidth to users, e.g., max-min fair. We prove the stability of such networks when the offered load on each link does not exceed its capacity. We use simulation to investigate the performance, in terms of average connection delays, for various network topologies and fairness criteria. Finally we pose an architectural problem in TCP/IP's decoupling of the transport and network layer from the point of view of guaranteeing connection level stability, which we claim may explain congestion phenomena on the Internet.

We propose an algorithm for assessing probabilistic performance constraints for systems including components with uncertain delays. We make a case for designing systems based on a probabilistic relaxation of performance constraints, as this has the potential for resulting in lower silicon area and/or power consumption. We consider a concrete example, an MPEG decoder, for which we discuss modeling and assessment of probabilistic throughput constraints.

Based on a loss network model, we present an adaptive source routing scheme for a large, hierarchically-organized network. To represent the "available" capacity of a cloud (subnetwork), we compute the average implied cost to go through or into the cloud. Such implied costs reflect the congestion in the cloud as well as the interdependencies among traffic streams in the network. We prove that both a synchronous and asynchronous distributed computation of the implied costs will converge to a unique solution under a light load condition. To assess accuracy, we derive a bound on the difference between our implied costs and those calculated for a flat network. In addition, we show how on-line measurements can be incorporated into the routing algorithm, and we present some representative computational results which demonstrate the ability of our scheme to appropriately route high level flows while significantly reducing complexity.

ATM-based integrated services networks are likely to rely on the virtual path (VP) concept as an intermediate resource management layer wherein key decisions concerning resource allocation, sharing, and flow aggregation are made. In this paper we consider the impact that statistically multiplexing heterogeneous services on VP connections will have on network design and management. Based on simple models we consider several questions including the following: given two traffic types with different quality of service requirements, should one segregate such flows on their own VPs, or is it to the network's advantage to multiplex the flows on a single VP guaranteeing the most stringent QoS requirement? Assuming two VPs have been set up between a given origin-destination pair and heterogeneous flows are to be carried, how should one route the connections to achieve good performance?.

In this paper we upper-bound the overflow probability of superpositions of off-line, e.g., stored video and real-time traffic streams based on deterministic traffic descriptors, e.g., leaky buckets. In the off-line scenario, we compute the empirical envelope function of the cumulative arrivals of a given traffic stream and use this envelope to bound the overflow probability for multiplexing N such streams at a single node. In the real-time scenario, we assume the traffic is policed by a dual leaky bucket and use the parameters of the device to give an upper bound for overflow probability without referring to the traffic statistics.

Efficient methods for congestion control in high-speed communication networks will be based on reasonable characterizations for traffic flows and time scale decompositions of the network dynamics. A key problem for modern network designers is to characterize/model the "bursty" traffic arising in broadband networks with a view to predicting and guaranteeing the performance. We attempt to unify several approaches ranging from histogram/interval based methods to "frequency domain" approaches by further investigating the asymptotic behavior of a multiplexer carrying a large number of streams. This analysis reveals the salient traffic/performance relationships which should guide us in selecting successful methods for traffic management and network dimensioning.

We consider the asymptotic behavior of the queue length distribution in segregated buffers sharing a deterministic server via a class of generalized processor sharing (GPS) policies. Such policies have been proposed as a means to guarantee individual quality of service constraints to heterogeneous streams in integrated services digital networks. These results exhibit the manner in which spare capacity is shared by statistically multiplexed traffic streams. The framework corresponds to a natural relaxation of a single GPS node subject to (/spl sigma/, /spl rho/)-constrained flows where, instead of studying the worst case behavior, we consider statistical bounds on the performance of individual traffic streams.

This paper is principally concerned with resource allocation for connections tolerating statistical quality of service (QoS) guarantees in a public wide-area ATM network. Our aim is to sketch a framework, based on effective bandwidths, for call admission schemes that are sensitive to individual QoS requirements and account for statistical multiplexing. Results approximating the effective bandwidth required by heterogeneous streams sharing buffered links, including results for the packetized generalized processor sharing service discipline, are described. Extensions to networks follow via the concept of decoupling bandwidths, motivated by a study of the input-output properties of queues. Based on these results we claim that networks with sufficient routing diversity will inherently satisfy nodal decoupling. We then discuss on-line methods for estimating the effective bandwidth of connection. Using this type of traffic monitoring we propose an approach to usage parameter control (i.e., policing) for effective bandwidth descriptors. Finally, we suggest how on-line monitoring might be combined with admission control to exploit unknown statistical multiplexing gains and thus increase utilization.>

The authors consider buffer asymptotics for feed-forward networks shared by heterogeneous traffic streams. This is done by identifying the effective bandwidth of the departure processes from shared queues. They introduce the idea of decoupling bandwidths and constraints which guarantee "decoupled" asymptotics within the network. They discuss these results in the context of resource management for ATM networks.>

The authors propose feedforward neural networks (NNs) as receivers for partial-response continuous-phase-modulation (CPM) systems. Their approach is to replace the entire receiver structure, excluding timing recovery, with a neural net unit whose inputs are time samples of the incoming baseband signals, and whose outputs are the decoded symbols. Simulation results for coherent and incoherent NN-based receivers are presented, and their performance is compared with that of the optimum maximum-likelihood receiver. The performance of NN-based receivers at large SNR is analyzed.>