We investigate a real-time remote inference system where multiple correlated sources transmit observations over a communication channel to a receiver. The receiver utilizes these observations to infer multiple time-varying targets. Due to limited communication resources, the delivered observations may not be fresh. To quantify data freshness, we employ the Age of Information (AoI) metric. To minimize the inference error, we aim to design a signal-agnostic scheduling policy that leverages AoI without requiring knowledge of the actual target values or the source observations. This scheduling problem is a restless multi-armed bandit (RMAB) problem with a non-separable penalty function. Unlike traditional RMABs, the correlation among sources introduces a unique challenge: the penalty function of each source depends on the AoI of other correlated sources, preventing the problem from decomposing into multiple independent Markov Decision Processes (MDPs), a key step in applying traditional RMAB solutions. To address this, we propose a novel approach that approximates the penalty function for each source and establishes an analytical bound on the approximation error. We then develop scheduling policies for two scenarios: (i) full knowledge of the penalty functions and (ii) no knowledge of the penalty functions. For the case of known penalty functions, we present an upper bound on the optimality gap that highlights the impact of the correlation parameter and the system size. For the case of unknown penalty functions and signal distributions, we develop an online learning approach that utilizes bandit feedback to learn an online Maximum Gain First policy. Simulation results demonstrate the effectiveness of our proposed policies in minimizing inference error and achieving scalability in the number of sources.

We investigate the control and optimization of vertical federated learning (VFL), a class of distributed machine learning (ML) methods in which edge/fog devices contain separate data features, in dynamic edge/fog networks. Owing to heterogeneous data features and hardware across edge/fog networks, devices’ contributions to VFL vary substantially, and, moreover, dynamic edge/fog networks can lead to the permanent exit or entry of select data features. In this setting, our proposed methodology, server controlled VFL in dynamic networks (SC-DN), first establishes the existence of a global first-order stationary point for every global round, and then leverages this result to jointly optimize ML model training and resource consumption based on four key control variables: (i) server placement, (ii) device-to-server transmit power, (iii) local device processor frequency, and (iv) local training iterations per global round. The resulting optimization formulation contains coupled variables as well as numerous forms of logarithmic constraints which we show is a mixed-integer signomial program, an NP-hard problem, and for which we develop a general solver. Finally, via experiments on both image and multi-modal datasets, we show that our methodology demonstrates superior classification/regression performance and resource consumption savings than even greedy methodologies.

We consider a setting where multiple correlated sources send real-time observations over a wireless communication channel to a receiver. The receiver uses the delivered observations to infer multiple time-varying targets. Due to limited communication resources, these observations may not always be fresh. To quantify data timeliness, we utilize the Age of Information (AoI) metric. Our goal is to minimize realtime inference error by developing signal-agnostic scheduling policies that leverage AoI without requiring knowledge of the actual target values or the specific source observations. For the two-source case, we obtain an optimal cyclic policy with low computational complexity. For more than two-sources, we establish an information-theoretic lower bound on inference error. Building upon this lower bound, we approximate the scheduling problem and propose an approximate Whittle index policy that is asymptotically optimal as the number of sources increases and the correlation among sources decreases. Our scheduling policies hold for arbitrary target and source processes and loss functions. Finally, we conduct simulations of a network of cameras with overlapping field of views tracking multiple mobile objects to demonstrate the effectiveness of our policies.

While network coverage maps continue to expand, many devices located in remote areas remain unconnected to terrestrial communication infrastructures, preventing them from getting access to the associated data-driven services. In this paper, we propose a cooperative ground-to-satellite federated learning (FL) methodology to facilitate machine learning service management over remote regions. Our methodology orchestrates satellite constellations to provide the following key functions during FL: (i) processing data offloaded from ground devices, (ii) aggregating models within device clusters, and (iii) relaying models/data to other satellites via inter-satellite links (ISLs). Due to the limited coverage time of each satellite over a particular remote area, we facilitate satellite transmission of trained models and acquired data to neighboring satellites via ISL, so that the incoming satellite can continue FL for the region. We also develop a training latency minimizer which optimizes over the amount of data to be offloaded from ground devices to satellites. Through experiments on benchmark datasets, we show that our scheme can significantly speed up the convergence of FL compared with terrestrial-only and other satellite baseline approaches.

Devices located in remote regions often lack coverage from well-developed terrestrial communication infrastructure. This not only prevents them from experiencing high quality communication services but also hinders the delivery of machine learning services in remote regions. In this paper, we propose a new federated learning (FL) methodology tailored to space-air-ground integrated networks (SAGINs) to tackle this issue. Our approach strategically leverages the nodes within space and air layers as both 1) edge computing units and 2) model aggregators during the FL process, addressing the challenges that arise from the limited computation powers of ground devices and the absence of terrestrial base stations in the target region. The key idea behind our methodology is the adaptive data offloading and handover procedures that incorporate various network dynamics in SAGINs, including the mobility, heterogeneous computation powers, and inconsistent coverage times of incoming satellites. We analyze the latency of our scheme and develop an adaptive data offloading optimizer, and also characterize the theoretical convergence bound of our proposed algorithm. Experimental results confirm the advantage of our SAGIN-assisted FL methodology in terms of training time and test accuracy compared with various baselines.

While network coverage maps continue to expand, many devices located in remote areas remain unconnected to terrestrial communication infrastructures, preventing them from getting access to the associated data-driven services. In this paper, we propose a ground-to-satellite cooperative federated learning (FL) methodology to facilitate machine learning service management over remote regions. Our methodology orchestrates satellite constellations to provide the following key functions during FL: (i) processing data offloaded from ground devices, (ii) aggregating models within device clusters, and (iii) relaying models/data to other satellites via inter-satellite links (ISLs). Due to the limited coverage time of each satellite over a particular remote area, we facilitate satellite transmission of trained models and acquired data to neighboring satellites via ISL, so that the incoming satellite can continue conducting FL for the region. We theoretically analyze the convergence behavior of our algorithm, and develop a training latency minimizer which optimizes over satellite-specific network resources, including the amount of data to be offloaded from ground devices to satellites and satellites’ computation speeds. Through experiments on three datasets, we show that our methodology can significantly speed up the convergence of FL compared with terrestrial-only and other satellite baseline approaches.

The demand for intelligent services at the network edge has introduced several research challenges. One is the need for a machine learning architecture that achieves personalization (to individual clients) and generalization (to unseen data) properties concurrently across different applications. Another is the need for an inference strategy that can satisfy network resource and latency constraints during testing-time. Existing techniques in federated learning have encountered a steep trade-off between personalization and generalization, and have not explicitly considered the resource requirements during the inference-stage. In this paper, we propose SplitGP, a joint edge-AI training and inference strategy that simultaneously captures generalization/personalization for efficient inference across resource-constrained clients. The training process of SplitGP is based on federated split learning, with the key idea of optimizing the client-side model to have personalization capability tailored to its main task, while training the server-side model to have generalization capability for handling out-of-distribution tasks. During testing-time, each client selectively offloads inference tasks to the server based on the uncertainty threshold tunable based on network resource availability. Through formal convergence analysis and inference time analysis, we provide guidelines on the selection of key meta-parameters in SplitGP. Experimental results confirm the advantage of SplitGP over existing baselines.

In this paper, we conduct a measurement study on operational 5G networks deployed across different frequency bands (mmWave and sub-6GHz) and server locations (mobile edge and Internet cloud). Specifically, we assess 5G performance in both uplink and downlink across multiple operators’ networks. We then carry out extensive comparisons of transport-layer protocols using ten different algorithms in full-fledged 5G networks, including an edge computing environment. Finally, we evaluate representative mobile applications over the 5G network with and without edge servers. Our comprehensive measurements provide several insights that affect the experience of 5G users: (i) With a 5G edge server, existing TCP congestion control algorithms can achieve throughput up to 1.8Gbps with only a single flow. (ii) The maximum TCP receive buffer size, which is set by off-the-shelf 5G phones, can limit the throughput performance of 5G networks, which is not observed in 4G LTE-A networks. (iii) Despite significant latency gains in download-centric applications, the 5G edge service provides limited benefits to CPU-intensive tasks or those that use significant uplink bandwidth. To our knowledge, this is the first measurement-driven understanding of 5G edge computing “in the wild,” which can provide an answer to how edge computing would perform in real 5G networks.

Federated learning (FedL) has emerged as a popular technique for distributing model training over a set of wireless devices, via iterative local updates (at devices) and global aggregations (at the server). In this paper, we develop parallel successive learning (PSL), which expands the FedL architecture along three dimensions: (i) Network, allowing decentralized cooperation among the devices via device-to-device (D2D) communications. (ii) Heterogeneity, interpreted at three levels: (ii-a) Learning: PSL considers heterogeneous number of stochastic gradient descent iterations with different mini-batch sizes at the devices; (ii-b) Data: PSL presumes a dynamic environment with data arrival and departure, where the distributions of local datasets evolve over time, captured via a new metric for model/concept drift. (ii-c) Device: PSL considers devices with different computation and communication capabilities. (iii) Proximity, where devices have different distances to each other and the access point. PSL considers the realistic scenario where global aggregations are conducted with idle times in-between them for resource efficiency improvements, and incorporates data dispersion and model dispersion with local model condensation into FedL. Our analysis sheds light on the notion of cold vs. warmed up models, and model inertia in distributed machine learning. We then propose network-aware dynamic model tracking to optimize the model learning vs. resource efficiency tradeoff, which we show is an NP-hard signomial programming problem. We finally solve this problem through proposing a general optimization solver. Our numerical results reveal new findings on the interdependencies between the idle times in-between the global aggregations, model/concept drift, and D2D cooperation configuration.

The conventional federated learning (FedL) architecture distributes machine learning (ML) across worker devices by having them train local models that are periodically aggregated by a server. FedL ignores two important characteristics of contemporary wireless networks, however: (i) the network may contain heterogeneous communication/computation resources, and (ii) there may be significant overlaps in devices’ local data distributions. In this work, we develop a novel optimization methodology that jointly accounts for these factors via intelligent device sampling complemented by device-to-device (D2D) offloading. Our optimization methodology aims to select the best combination of sampled nodes and data offloading configuration to maximize FedL training accuracy while minimizing data processing and D2D communication resource consumption subject to realistic constraints on the network topology and device capabilities. Theoretical analysis of the D2D offloading subproblem leads to new FedL convergence bounds and an efficient sequential convex optimizer. Using these results, we develop a sampling methodology based on graph convolutional networks (GCNs) which learns the relationship between network attributes, sampled nodes, and D2D data offloading to maximize FedL accuracy. Through evaluation on popular datasets and real-world network measurements from our edge testbed, we find that our methodology outperforms popular device sampling methodologies from literature in terms of ML model performance, data processing overhead, and energy consumption.

Semi-decentralized federated learning blends the conventional device-to-server (D2S) interaction structure of federated model training with localized device-to-device (D2D) communications. We study this architecture over practical edge networks with multiple D2D clusters modeled as time-varying and directed communication graphs. Our investigation results in an algorithm that controls the fundamental trade-off between (a) the rate of convergence of the model training process towards the global optimizer, and (b) the number of D2S transmissions required for global aggregation. Specifically, in our semi-decentralized methodology, D2D consensus updates are injected into the federated averaging framework based on column-stochastic weight matrices that encapsulate the connectivity within the clusters. To arrive at our algorithm, we show how the expected optimality gap in the current global model depends on the greatest two singular values of the weighted adjacency matrices (and hence on the densities) of the D2D clusters. We then derive tight bounds on these singular values in terms of the node degrees of the D2D clusters, and we use the resulting expressions to design a threshold on the number of clients required to participate in any given global aggregation round so as to ensure a desired convergence rate. Simulations performed on real-world datasets reveal that our connectivity-aware algorithm reduces the total communication cost required to reach a target accuracy significantly compared with baselines depending on the connectivity structure and the learning task.

Network sharing is widely accepted as a cost effective approach for mobile network deployment. It remains uncertain, however, how regulators will evaluate network sharing agreements (NSA) for future networks in the context of the current competition law. For example, 5G mobile network operators (MNOs) seeking to enter NSAs may risk legal challenges, as regulators have not given MNOs sufficient guidance for self-evaluation of their NSAs. One way for MNOs to reduce the risk of legal challenge is to avoid sharing variable costs in the NSA. However, constraining costs to be non-variable (i.e., fixed) rules out the use of most pricing mechanisms that have been widely adopted for dynamic resource trading between MNOs. In this article, we propose a network sharing framework to allow dynamic resource sharing without the use of resource pricing. To incentivize sharing without pricing, our framework presents sharing as a means for MNOs to differentiate services and better compete in the service market for profit. We evaluate our framework in a duopoly market model and demonstrate the economic and regulatory viability of our framework.

We investigate training machine learning (ML) models across a set of geo-distributed, resource-constrained clusters of devices through unmanned aerial vehicles (UAV) swarms. The presence of time-varying data heterogeneity and computational resource inadequacy among device clusters motivate four key parts of our methodology: (i)stratified UAV swarmsof leader, worker, and coordinator UAVs, (ii)hierarchical nested personalized federated learning(HN-PFL), a distributed ML framework for personalized model training across the worker-leader-core network hierarchy, (iii)cooperative UAV resource poolingto address computational inadequacy of devices by conducting model training among the UAV swarms, and (iv)model/concept driftto model time-varying data distributions. In doing so, we consider bothmicro(i.e., UAV-level) andmacro(i.e., swarm-level) system design. At the micro-level, we propose network-awareHN-PFL, where we distributively orchestrate UAVs inside swarms to optimize energy consumption and ML model performance with performance guarantees. At the macro-level, we focus on swarm trajectory and learning duration design, which we formulate as a sequential decision making problem tackled via deep reinforcement learning. Our simulations demonstrate the improvements achieved by our methodology in terms of ML performance, network resource savings, and swarm trajectory efficiency.

We propose cooperative edge-assisted dynamic federated learning (CE-FL).CE-FLintroduces a distributed machine learning (ML) architecture, where data collection is carried out at the end devices, while the model training is conducted cooperatively at the end devices and the edge servers, enabled via data offloading from the end devices to the edge servers through base stations.CE-FLalso introduces floating aggregation point, where the local models generated at the devices and the servers are aggregated at an edge server, which varies from one model training round to another to cope with the network evolution in terms of data distribution and users’ mobility.CE-FLconsiders the heterogeneity of network elements in terms of communication/computation models and the proximity to one another.CE-FLfurther presumes a dynamic environment with online variation of data at the network devices which causes a drift at the ML model performance. We model the processes taken duringCE-FL, and conduct analytical convergence analysis of its ML model training. We then formulate network-awareCE-FLwhich aims to adaptively optimize all the network elements via tuning their contribution to the learning process, which turns out to be a non-convex mixed integer problem. Motivated by the large scale of the system, we propose a distributed optimization solver to break down the computation of the solution across the network elements. We finally demonstrate the effectiveness of our framework with the data collected from a real-world testbed.

Federated learning (FL) has been recognized as one of the most promising solutions for distributed machine learning (ML). In most of the current literature, FL has been studied for supervised ML tasks, in which edge devices collect labeled data. Nevertheless, in many applications, it is impractical to assume existence of labeled data across devices. To this end, we develop a novel methodology, Cooperative Federated unsupervised Contrastive Learning (CF-CL), for FL across edge devices with unlabeled datasets. CF-CL employs local device cooperation where data are exchanged among devices through device-to-device (D2D) communications to avoid local model bias resulting from non-independent and identically distributed (non-i.i.d.) local datasets. CF-CL introduces a push-pull smart data sharing mechanism tailored to unsupervised FL settings, in which, each device pushes a subset of its local datapoints to its neighbors as reserved datapoints, and pulls a set of datapoints from its neighbors, sampled through a probabilistic importance sampling technique. We demonstrate that CF-CL leads to (i) alignment of unsupervised learned latent spaces across devices, (ii) faster global convergence, allowing for less frequent global model aggregations; and (iii) is effective in extreme non-i.i.d. datasettings across the devices.

Edge computing promises to exploit underlying computation resources closer to users to help run latency-sensitive applications such as augmented reality and video analytics. However, one key missing piece has been how to incorporate personally owned, unmanaged devices into a usable edge computing system. The primary challenges arise due to the heterogeneity, lack of interference management, and unpredictable availability of such devices. In this paper we propose an orchestration framework IBDASH, which orchestrates application tasks on an edge system that comprises a mix of commercial and personal edge devices. IBDASH targets reducing both end-to-end latency of execution and probability of failure for applications that have dependency among tasks, captured by directed acyclic graphs (DAGs). IBDASH takes memory constraints of each edge device and network bandwidth into consideration. To assess the effectiveness of IBDASH, we run real application tasks on real edge devices with widely varying capabilities. We feed these measurements into a simulator that runs IBDASH at scale. Compared to three state-of-the-art edge orchestration schemes and two intuitive baselines, IBDASH reduces the end-to-end latency and probability of failure, by 14% and 41% on average respectively. The main takeaway from our work is that it is feasible to combine personal and commercial devices into a usable edge computing platform, one that delivers low and predictable latency and high availability.

Error correcting codes are a fundamental component in modern day communication systems, demanding extremely high throughput, ultra-reliability and low latency. Recent approaches using machine learning (ML) models as decoders offer both improved performance and great adaptability to unknown environments, where traditional decoders struggle. We introduce a general framework to further boost the performance and applicability of ML models. We propose to combine ML decoders with a competing discriminator network that tries to distinguish between codewords and noisy words, and, hence, guides the decoding models to recover transmitted codewords. Our framework is game-theoretic, motivated by generative adversarial networks (GANs), with the decoder and discriminator competing in a zero-sum game. The decoder learns to simultaneously decode and generate codewords while the discriminator learns to tell the difference between decoded outputs and codewords. Thus, the decoder is able to decode noisy received signals into codewords, increasing the probability of successful decoding. We show a strong connection of our framework with the optimal maximum likelihood decoder by proving that this decoder defines a Nash equilibrium point of our game. Hence, training to equilibrium has a good possibility of achieving the optimal maximum likelihood performance. Moreover, our framework does not require training labels, which are typically unavailable during communications, and, thus, seemingly can be trained online and adapt to channel dynamics. To demonstrate the performance of our framework, we combine it with recent neural decoders and show improved performance compared to the original models and traditional decoding algorithms on various codes.

Edge computing has revolutionized the world of mobile and wireless networks world thanks to its flexible, secure, and performing characteristics. Lately, we have witnessed the increasing use of it to make more performing the deployment of machine learning (ML) techniques such as federated learning (FL). FL was debuted to improve communication efficiency compared to conventional distributed machine learning (ML). The original FL assumes a central aggregation server to aggregate locally optimized parameters and might bring reliability and latency issues. In this paper, we conduct an in-depth study of strategies to replace this central server by a flying master that is dynamically selected based on the current participants and/or available resources at every FL round of optimization. Specifically, we compare different metrics to select this flying master and assess consensus algorithms to perform the selection. Our results demonstrate a significant reduction of runtime using our flying master FL framework compared to the original FL from measurements results conducted in our EdgeAI testbed and over real 5G networks using an operational edge testbed.

In recent years, the research community started to extensively study how edge computing can enhance the provisioning of a seamless and performing Machine Learning (ML) experience. Boosting the performance of ML inference at the edge became a driving factor especially for enabling those use-cases in which proximity to the data sources, near real-time requirements, and need of a reduced network latency represent a determining factor. The growing demand of edge-based ML services has been also boosted by an increasing market release of small-form factor inference accelerators devices that feature, however, heterogeneous and not fully interoperable software and hardware characteristics. A key aspect that has not yet been fully investigated is how to discover and efficiently optimize the provision of ML inference services in distributed edge systems featuring heterogeneous edge inference accelerators - not neglecting also that the limited devices computation capabilities may imply the need of orchestrating the inference execution provisioning among the different system's devices. The main goal of this demo is to showcase how ML inference services can be agnostically discovered, provisioned, and orchestrated in a cluster of heterogeneous and distributed edge nodes.

The conventional federated learning (FedL) architecture distributes machine learning (ML) across worker devices by having them train local models that are periodically aggregated by a server. FedL ignores two important characteristics of contemporary wireless networks, however: (i) the network may contain heterogeneous communication/computation resources, while (ii) there may be significant overlaps in devices' local data distributions. In this work, we develop a novel optimization methodology that jointly accounts for these factors via intelligent device sampling complemented by device-to-device (D2D) offloading. Our optimization aims to select the best combination of sampled nodes and data offloading configuration to maximize FedL training accuracy subject to realistic constraints on the network topology and device capabilities. Theoretical analysis of the D2D offloading subproblem leads to new FedL convergence bounds and an efficient sequential convex optimizer. Using this result, we develop a sampling methodology based on graph convolutional networks (GCNs) which learns the relationship between network attributes, sampled nodes, and resulting offloading that maximizes FedL accuracy. Through evaluation on real-world datasets and network measurements from our IoT testbed, we find that our methodology while sampling less than 5% of all devices outperforms conventional FedL substantially both in terms of trained model accuracy and required resource utilization.

We study how to schedule data sources in a wireless time-sensitive information system with multiple heterogeneous and unreliable channels to minimize the total expected Age-of-Information (AoI). Although one could formulate this problem as a discrete-time Markov Decision Process (MDP), such an approach suffers from the curse of dimensionality and lack of insights. For single-channel systems, prior studies have developed lower-complexity solutions based on the Whittle index. However, Whittle index has not been studied for systems with multiple heterogeneous channels, mainly because indexability is not well defined when there are multiple dual cost values, one for each channel. To overcome this difficulty, we introduce new notions of partial indexability and partial index, which are defined with respect to one channel's cost, given all other channels' costs. We then combine the ideas of partial indices and max-weight matching to develop a Sum Weighted Index Matching (SWIM) policy, which iteratively updates the dual costs and partial indices. The proposed policy is shown to be asymptotically optimal in minimizing the total expected AoI, under a technical condition on a global attractor property. Extensive performance simulations demonstrate that the proposed policy offers significant gains over conventional approaches by achieving a near-optimal AoI. Further, the notion of partial index is of independent interest and could be useful for other problems with multiple heterogeneous resources.

Federated learning has emerged recently as a promising solution for distributing machine learning tasks through modern networks of mobile devices. Recent studies have obtained lower bounds on the expected decrease in model loss that is achieved through each round of federated learning. However, convergence generally requires a large number of communication rounds, which induces delay in model training and is costly in terms of network resources. In this paper, we propose a fast-convergent federated learning algorithm, called$\mathsf {FOLB}$, which performs intelligent sampling of devices in each round of model training to optimize the expected convergence speed. We first theoretically characterize a lower bound on improvement that can be obtained in each round if devices are selected according to the expected improvement their local models will provide to the current global model. Then, we show that$\mathsf {FOLB}$obtains this bound through uniform sampling by weighting device updates according to their gradient information.$\mathsf {FOLB}$is able to handle both communication and computation heterogeneity of devices by adapting the aggregations according to estimates of device’s capabilities of contributing to the updates. We evaluate$\mathsf {FOLB}$in comparison with existing federated learning algorithms and experimentally show its improvement in trained model accuracy, convergence speed, and/or model stability across various machine learning tasks and datasets.

Analyzing the DNS traffic of Internet hosts has been a successful technique to counter cyberattacks and identify connections to malicious domains. However, recent stealthy attacks hide malicious activities within seemingly legitimate connections to popular web services made by benign programs. Traditional DNS monitoring and signature-based detection techniques are ineffective against such attacks. To tackle this challenge, we present a new program-level approach that can effectively detect such stealthy attacks. Our method builds a fine-grained Program-DNS profile for each benign program that characterizes what should be the “expected” DNS behavior. We find that malware-injected processes have DNS activities which significantly deviate from the Program-DNS profile of the benign program. We then develop six novel features based on the Program-DNS profile, and evaluate the features on a dataset of over 130 million DNS requests collected from a real-world enterprise and 8 million requests from malware-samples executed in a sandbox environment. We compare our detection results with that of previously-proposed features and demonstrate that our new features successfully detect 190 malware-injected processes which fail to be detected by previously-proposed features. Overall, our study demonstrates that fine-grained Program-DNS profiles can provide meaningful and effective features in building detectors for attack campaigns that bypass existing detection systems.

Running intensive compute tasks across the fifth generation mobile network of edge devices introduces distributed computing challenges: edge devices are heterogeneous in the compute, storage, and communication capabilities; and can exhibit unpredictable straggler effects and failures. In this work, we propose an error-correcting-code inspired strategy to execute computing tasks in edge computing environments, which is designed to mitigate variability in response times and errors caused by edge devices' heterogeneity and lack of reliability. Unlike prior coding approaches, we incorporate partially unfinished coded tasks into our computation recovery, which allows us to achieve smooth performance degradation with low-complexity decoding when the coded tasks are run on edge devices with a fixed deadline. By further carrying out coding on edge devices as well as a master node, the proposed computing scheme also alleviates communication bottlenecks during data shuffling and is amenable to distributed implementation in a highly variable and limited network. Such distributed encoding forces us to solve new decoding challenges. Using a representative implementation based on federated multi-task learning frameworks, extensive performance simulations are carried out, which demonstrate that the proposed strategy offers significant gains in latency and accuracy over conventional coded computing schemes.

We study low-overhead uplink multi-access algorithms for massive Internet-of-Things (IoT) that can exploit the MIMO performance gain. Although MIMO improves system capacity, it usually requires high overhead due to Channel State Information (CSI) feedback, which is unsuitable for IoT. Recently, a Pseudo-Random Beam-Forming (PRBF) scheme was proposed to exploit the MIMO performance gain for uplink IoT access with uniform channel and load, without collecting CSI at the BS. For non-uniform channel and load, new adaptive beamselection and random-access algorithms are needed to efficiently utilize the system capacity with low overhead. Most existing algorithms for a related multi-channel scheduling problem require each node to at least know some information of the queue length of all contending nodes. In contrast, we propose a new Low-overhead Multi-Channel Joint Channel-Assignment and Random-Access (L-MC-JCARA) algorithm that reduces the overhead to be independent of the number of interfering nodes. A key novelty is to let the BS estimate the total backlog in each contention group by only observing the random-access events, so that no queue-length feedback is needed from IoT devices. We prove that L-MC-JCARA can achieve at least `0.24`` of the capacity region of the optimal centralized scheduler for the corresponding multi-channel system.

The growing demand for mobile data and the evolution of next-generation networks, particularly fifth-generation (5G) wireless networks, has called for new approaches to pricing and managing the limited capacity of existing network resources and infrastructures. In particular, emerging mobile applications like autonomous vehicles, augmented/virtual reality, and more broadly the Internet-of-Things will have heterogeneous demand patterns and service requirements, raising questions on how they should pay for their data usage and how next-generation networks can meet their demands with limited resources. Several recent policy changes and regulatory initiatives have been proposed to address the shift in demands due to next-generation networks and technologies. These include the FCC’s “5G Fast Plan,” which outlines strategies for modifying spectrum policies, infrastructure policies, and existing regulations, in light of emerging 5G technologies. This plan has included the rollback of net neutrality rules in June 2018, allowing broadband providers to offer a wider variety of service options.

A pseudo-random beamforming (PRBF) based random access (RA) system is proposed to enable uplink (UL) machine-type communications (MTC) with ultra low signaling overheads. Specifically, a pseudo random (PR) sequence is used as public information to coordinate the beamforming vectors used at the base station (BS) and the devices. Within the coherence time window, each device distributively determines in advance the ''good'' time slots and receiving beams for transmission. This UL protocol reduces the overheads due to the feedback of channel state information and the control signals for centralized scheduling. This paper derives the throughput and user scaling of the proposed M- PRBF-CA protocol for achieving spatial multiplexing gain, under both an i.i.d. slow fading channel and a correlated slow fading channel. Our simulation results confirm the analysis in both fading channel models.

We consider the problem of jointly predicting the quality and timing of responses to questions asked in online discussion forums. While prior work has focused on identifying users most likely to answer and/or to provide the highest quality answers to a question, the promptness of the response is also a key factor of user satisfaction. To address this, we propose point process and neural network-based algorithms for three prediction tasks regarding a user's response to a question: whether the user will answer, the net votes that will be received on the answer, and the time that will elapse before the answer. These algorithms learn over a set of 20 features we define for each pair of user and question that quantify both topical and structural aspects of the forums, including discussion post similarities and social centrality measures. Through evaluation on a Stack Overflow dataset consisting of 20,000 question threads, we find that our method outperforms baselines on each prediction task by more than 20%. We also find that the importance of the features varies depending on the task and the amount of historical data available for inference. At the end, we design a question recommendation system that incorporates these predictions to jointly optimize response quality and timing in forums subject to user constraints.

Urban environments are a particularly important application scenario for the Internet of Things (IoT). These environments are usually dense and dynamic; in contrast, IoT devices are resource-constrained, thus making reliable data collection and scalable coordination a challenge. This work leverages the fog networking paradigm to devise a multi-tier data offloading protocol suitable for diverse data-centric applications in urban IoT scenarios. Specifically, it takes advantage of heterogeneity in the network so that sensors can collaboratively offload data to each other or to mobile gateways. Second, it evaluates the performance of this offloading process through the amount of data successfully reported to the cloud. In detail, it provides an analytical characterization of data drop-off rates as a random process and derives a light-weight yet efficient method for collaborative data offloading. Finally, it shows that the proposed fog-based solution significantly decreases the data drop-off rate through both analysis and extensive trace-driven simulations based on human mobility data from real urban settings.

We study a multi-agent partially observable environment in which autonomous agents aim to coordinate their actions, while also learning the parameters of the unknown environment through repeated interactions. In particular, we focus on the role of communication in a multi-agent reinforcement learning problem. We consider a learning algorithm in which agents make decisions based on their own observations of the environment, as well as the observations of other agents, which are collected through communication between agents. We first identify two potential benefits of this type of information sharing when agents' observation quality is heterogeneous: (1) it can facilitate coordination among agents, and (2) it can enhance the learning of all participants, including the better informed agents. We show however that these benefits of communication depend in general on its timing, so that delayed information sharing may be preferred in certain scenarios.

The explosive growth of multimedia data traffic in wired and wireless networks have led Internet service providers (ISPs) to use penalty mechanisms like throttling, capping, overage fees to manage network congestion; however, such measures are harmful to the Internet ecosystem. Therefore, we use ideas from economics to create incentive-based, as opposed to penalty-based, solutions for data plans. In particular, we explore time-dependent pricing (TDP) - a form of dynamic pricing that manages congestion by offering time-varying discounts to incentivize users to shift some data traffic temporally. To realize TDP data plans in practice, we provide (i) an optimization model to compute time-dependent prices, (ii) a system implementation for deployment in operational networks, and (iii) experiments with two cellular networks for demonstrating feasibility. Our results show that the users respond to such pricing plans by using higher volume of traffic in lower-priced (off-peak) periods and benefit from a lower $/GB fee, while the ISPs benefit from a higher revenue due to increase in off-peak usage and lower peak-to-average traffic ratio in their network. This suggests that such a pricing solution can incentivize users to modify their usage behavior and enable better revenue management in multimedia-rich networks.

It is of crucial importance to simultaneously protect against sensitive attributes in data while building predictive models. In this paper, we tackle the problem of learning representations from raw data that are i) informative and predictive of desirable variables, and ii) private and protect against adversaries that attempt to recover sensitive variables. We cast this problem under the generative adversarial network (GAN) framework and design three components: an encoder, an ally that predicts the desired variables, and an adversary that predicts the sensitive ones. As a use case, we apply our approach to learn representations of raw student clickstream event data captured as they watch lecture videos in massive open online courses (MOOCs). Through experiments on a real-world dataset collected from a MOOC, we demonstrate that our method can learn a low-dimensional representation of each user that i) excels at classifying whether a user will answer a quiz question correctly, and ii) prevents an adversary from recovering each user's identity. Our results indicate that our approach is effective in learning representations that are both informative and private.

Deep neural networks (DNNs) have enabled success in learning tasks such as image classification, semantic image segmentation and steering angle prediction which can be key components of the computer vision pipeline of safety-critical systems such as autonomous vehicles. However, previous work has demonstrated the feasibility of using physical adversarial examples to attack image classification systems. \par In this work, we argue that the success of realistic adversarial examples is highly dependent on both the structure of the training data and the learning objective. In particular, realistic, physical-world attacks on semantic segmentation and steering angle prediction constrain the adversary to add localized perturbations, since it is very difficult to add perturbations in the entire field of view of input sensors such as cameras for applications like autonomous vehicles. We empirically study the effectiveness of adversarial examples generated under strict locality constraints imposed by the aforementioned applications. Even with image classification, we observe that the success of the adversary under locality constraints depends on the training dataset. With steering angle prediction, we observe that adversarial perturbations localized to an off-road patch are significantly less successful compared to those on-road. For semantic segmentation, we observe that perturbations localized to small patches are only effective at changing the label in and around those patches, making non-local attacks difficult for an adversary. We further provide a comparative evaluation of these localized attacks over various datasets and deep learning models for each task.

The Rasch model is widely used for item response analysis in applications ranging from recommender systems to psychology, education, and finance. While a number of estimators have been proposed for the Rasch model over the last decades, the associated analytical performance guarantees are mostly asymptotic. This paper provides a framework that relies on a novel linear minimum mean-squared error (L-MMSE) estimator which enables an exact, nonasymptotic, and closed-form analysis of the parameter estimation error under the Rasch model. The proposed framework provides guidelines on the number of items and responses required to attain low estimation errors in tests or surveys. We furthermore demonstrate its efficacy on a number of real-world collaborative filtering datasets, which reveals that the proposed L-MMSE estimator performs on par with state-of-the-art nonlinear estimators in terms of predictive performance.

As infrastructure-as-a-service clouds become more popular, cloud providers face the complicated problem of maximizing their resource utilization by handling the dynamics of user demand. Auction-based pricing, such as Amazon EC2 spot pricing, provides an option for users to use idle resources at highly reduced yet dynamic prices; under such a pricing scheme, users place bids for cloud resources, and the provider chooses a threshold “spot” price above which bids are admitted. In this paper, we propose a nonlinear dynamical system model for the time-evolution of the spot price as a function of latent states that characterize user demand in the spot and on-demand markets. This model enables us to adaptively predict future spot prices given past spot price observations, allowing us to derive user bidding strategies for heterogeneous cloud resources that minimize the cost to complete a job with negligible probability of interruption. Along the way, the model also yields novel, empirically verifiable insights into cloud provider behavior. We experimentally validate our model and bidding strategy on two months of Amazon EC2 spot price data and find that our proposed bidding strategy is up to 4 times closer to the optimal strategy in hindsight compared to a baseline regression approach while incurring the same negligible probability of interruption.

As the U.S. mobile data market matures, Internet service providers (ISPs) generally charge their users with some variation on a quota-based data plan with overage charges. Common variants include unlimited, prepaid, and usage-based data plans. However, despite a recent flurry of research on optimizing mobile data pricing, few works have considered how these data plans affect users' consumption behavior. In particular, while users with such plans have a strong incentive to plan their usage over the month, they also face uncertainty in their future data usage needs that would make such planning difficult. In this work, we develop a dynamic programming model of users' consumption decisions over the month that takes this uncertainty into account. We use this model to quantify which types of users would benefit from different types of data plans, using these conditions to extrapolate the optimal types of data plans that ISPs should offer. Our theoretical findings are complemented by numerical simulations on a dataset of user usage from a large U.S. ISP. The results help mobile users to choose data plans that maximize their utilities and ISPs to gain profit by understanding their user behavior while choosing what data plans to offer.

This paper introduces an analytical framework to investigate optimal design choices for the placement of virtual controllers along the cloud-to-things continuum. The main application scenarios include low-latency cyber-physical systems in which real-time control actions are required in response to the changes in states of an Internet of Things (IoT) node. In such cases, deploying controller software on a cloud server is often not tolerable due to delay from the network edge to the cloud. Hence, it is desirable to trade reliability with latency by moving controller logic closer to the network edge. Modeling the IoT node as a dynamical system that evolves linearly in time with quadratic penalty for state deviations, recursive expressions for the optimum control policy and the resulting minimum cost value are obtained by taking virtual fog controller reliability and response time latency into account. Our results indicate that latency is more critical than reliability in provisioning virtualized control services over fog endpoints, as it determines the swiftness of the fog control system as well as the timeliness of state measurements. Based on a drone trajectory tracking model, an extensive simulation study is also performed to illustrate the influence of reliability and latency on the control of autonomous vehicles over fog.

Abstract Many recent proposals for anonymous communication omit from their security analyses a consideration of the effects of time on important system components. In practice, many components of anonymity systems, such as the client location and network structure, exhibit changes and patterns over time. In this paper, we focus on the effect of such temporal dynamics on the security of anonymity networks. We present Tempest, a suite of novel attacks based on (1) client mobility, (2) usage patterns, and (3) changes in the underlying network routing. Using experimental analysis on real-world datasets, we demonstrate that these temporal attacks degrade user privacy across a wide range of anonymity networks, including deployed systems such as Tor; pathselection protocols for Tor such as DeNASA, TAPS, and Counter-RAPTOR; and network-layer anonymity protocols for Internet routing such as Dovetail and HORNET. The degradation is in some cases surprisingly severe. For example, a single host failure or network route change could quickly and with high certainty identify the client’s ISP to a malicious host or ISP. The adversary behind each attack is relatively weak – generally passive and in control of one network location or a small number of hosts. Our findings suggest that designers of anonymity systems should rigorously consider the impact of temporal dynamics when analyzing anonymity.

Cloud Infrastructure as a Service (IaaS) providers continually seek higher resource utilization to better amortize capital costs. Higher utilization not only can enable higher profit for IaaS providers but also provides a mechanism to raise energy efficiency; therefore creating greener cloud services. Unfortunately, achieving high utilization is difficult mainly due to infrastructure providers needing to maintain spare capacity to service demand fluctuations.

We study the resource allocation problem in RAN-level integrated HetNets. This emerging HetNets paradigm allows for dynamic traffic splitting across radio access technologies for each client, and then for aggregating the traffic inside the network to improve the overall resource utilization. We focus on the max-min fair service rate allocation across the clients, and study the properties of the optimal solution. Based on the analysis, we design a low complexity distributed algorithm that tries to achieve max-min fairness. We also design a hybrid network architecture that leverages opportunistic centralized network supervision to augment the distributed solution. We analyze the performance of our proposed algorithms and prove their convergence. We also derive conditions under which the outcome is optimal. When the conditions are not satisfied, we provide constant upper and lower bounds on the optimality gap. Finally, we study the convergence time of our distributed solution and show that leveraging appropriate policies in its design significantly reduces the convergence time.

A network of drone cameras can be deployed to cover live events, such as high-action sports game played on a large field, but managing networked drone cameras in real-time is challenging. Distributed approaches yield suboptimal solutions from lack of coordination but coordination with a centralized controller incurs round-trip latencies of several hundreds of milliseconds over a wireless channel. We propose a fog-networking based system architecture to automatically coordinate a network of drones equipped with cameras to capture and broadcast the dynamically changing scenes of interest in a sports game. We design both optimal and practical algorithms to balance the tradeoff between two metrics: coverage of the most important scenes and streamed video bitrate. To compensate for network round-trip latencies, the centralized controller uses a predictive approach to predict which locations the drones should cover next. The controller maximizes video bitrate by associating each drone to an optimally matched server and dynamically re-assigns drones as relay nodes to boost the throughput in low-throughput scenarios. This dynamic assignment at centralized controller occurs at slower time-scale permitted by round-trip latencies, while the predictive approach and drones' local decision ensures that the system works in real-time. Experimental results over tens of flights on the field suggest our system can achieve really good performance, for example, 8 drones can achieve a tradeoff of 94% coverage and (on average) 2K video support at 20 Mbps by optimizing between coverage and throughput. By dynamically allocating drones to cover the game or act as relays, our system also demonstrates a 2x gain over systems maximizing static coverage alone that achieves only 9 Mbps video throughput.

We study learning outcome prediction for online courses. Whereas prior work has focused on semester-long courses with frequent student assessments, we focus on short-courses that have single outcomes assigned by instructors at the end. The lack of performance data makes the behavior of learners, captured as they interact with course content and with one another in Social Learning Networks (SLN), essential for prediction. Our method defines several (machine) learning features based on behaviors collected on the modes of (human) learning in a course, and uses them in appropriate classifiers. Through evaluation on data captured from three two-week courses hosted through our delivery platforms, we make three key observations: (i) behavioral data is predictive of learning outcomes in short-courses (our classifiers achieving AUCs ≥ 0.8 after the two weeks), (ii) it has an early detection capability (AUCs ≥ 0.7 with the first week of data), and (iii) the content features have an “earliest” detection capability (with higher AUC in the first few days), while the SLN features become the more predictive set over time, as the network matures. We also discuss how our method can generate behavioral analytics for instructors.

A cloud computing cluster equipped with a deadline-aware job scheduler faces fairness and efficiency challenges when greedy users falsely advertise the urgency of their jobs. Penalizing such untruthfulness without demotivating users from using the cloud service calls for advanced mechanism design techniques that work together with deadline-aware job scheduling. We propose a Bayesian incentive compatible pricing mechanism based on matching by replica-surrogate valuation functions. User valuations can be discovered by the mechanism, even when the users themselves do not fully understand their own valuations. Furthermore, users who are charged a Bayesian incentive compatible price have no reason to lie about the urgency of their jobs. The proposed mechanism achieves multiple desired truthful properties such as Bayesian incentive compatibility and ex-post individual rationality. We implement the proposed pricing mechanism. Through experiments in a Hadoop cluster with real-world datasets, we show that our prototype is capable of suppressing untruthful behavior from users.

Growing mobile data usage has led to end users paying substantial data costs, while Internet service providers (ISPs) struggle to upgrade their networks to keep up with demand and maintain high quality-of-service (QoS). This problem is particularly severe for smaller ISPs with less capital. Instead of simply upgrading their network infrastructure, ISPs can pool their networks to provide a good QoS and attract more users. Such a vISP (virtual ISP), for example, Google's Project Fi, allows users to access any of its partner ISPs' networks. We provide the first systematic analysis of a vISP's economic impact, showing that the vISP provides a viable solution for smaller ISPs attempting to attract more users, but may not maintain a positive profit if users' data demands evolve. To do so, we consider users' decisions of whether to defect from their current ISP to the vISP, as well as ISPs' decisions on whether to partner with the vISP. We derive the vISP's dependence on user behavior and partner ISPs: users with very light or very heavy usage are the most likely to defect, while ISPs with heavy-usage customers can benefit from declining to partner with the vISP. Our analytical results are verified with extensive numerical simulations.

Fog computing, the distribution of computing resources closer to the end devices along the cloud-to-things continuum, is recently emerging as an architecture for scaling of the Internet of Things (IoT) sensor networking applications. Fog computing requires novel computing program decompositions for heterogeneous hierarchical settings. To evaluate these new decompositions, we designed, developed, and instrumented a fog computing testbed that includes cloud computing and computing gateway execution points collaborating to finish complex data analytics operations. In this interactive demonstration we present one fog-specific algorithmic decomposition we recently examined and adapted for fog computing: a multi-execution point linear regression decomposition that jointly optimizes operation latency, quality, and costs. The demonstration highlights the role fog computing can play in future sensor networking architectures, and highlights some of the challenges of creating computing program decompositions for these architectures. An annotated video of the demonstration is available at [5].

Tor is vulnerable to network-level adversaries who can observe both ends of the communication to deanonymize users. Recent work has shown that Tor is susceptible to the previously unknown active BGP routing attacks, called RAPTOR attacks, which expose Tor users to more network-level adversaries. In this paper, we aim to mitigate and detect such active routing attacks against Tor. First, we present a new measurement study on the resilience of the Tor network to active BGP prefix attacks. We show that ASes with high Tor bandwidth can be less resilient to attacks than other ASes. Second, we present a new Tor guard relay selection algorithm that incorporates resilience of relays into consideration to proactively mitigate such attacks. We show that the algorithm successfully improves the security for Tor clients by up to 36% on average (up to 166% for certain clients). Finally, we build a live BGP monitoring system that can detect routing anomalies on the Tor network in real time by performing an AS origin check and novel detection analytics. Our monitoring system successfully detects simulated attacks that are modeled after multiple known attack types as well as a real-world hijack attack (performed by us), while having low false positive rates.

With growing data demand and the current dearth of spectrum, mobile operators are looking for new frequency bands to satisfy data-hungry users. One promising avenue of expansion is TV white spaces, which are currently available to secondary users as long as they do not interfere with primary (i.e., incumbent) users. In this work, we explore the benefits of offloading cellular traffic onto TV white spaces. We develop an analytical model and efficient algorithms to assign users to the cellular network or white space channels by considering their channel gains, multi-user interference on white space channels, and the cost of switching between different networks. We perform extensive data-driven simulations in two representative urban scenarios based on publicly available datasets. Our results show that white spaces can increase capacity by 16-62%, depending on the environment, but careful network selection is necessary to ensure that maximum capacity gains are realized. Moreover, we show that white spaces provide a significant benefit in serving indoor users where cellular channel conditions are poor. Specifically, our algorithms can offload up to 40% of cellular traffic to white spaces for indoor scenarios.

Internet service providers (ISPs) struggle to invest in upgrading their networks to catch up with growing mobile data demand, while users have to face significant data overage fees. Pooling ISPs' network infrastructures can potentially enable better user experience and lower prices. For example, Google recently launched a cross-carrier MVNO (mobile virtual network operator) data plan called Project Fi, where users' devices can automatically access either of two partner cellular networks or any available open WiFi network. We consider the economic impact of cross-carrier MVNOs on the mobile data market. We begin by analyzing a network selection strategy that optimizes cross-carrier users' costs. We then study ISPs' behavior, deriving the prices that partner ISPs charge the cross-carrier MVNO and that the cross-carrier MVNO charges its end users. Although the cross-carrier MVNO may lose money from selling data, it can offset this loss with side revenue, e.g., advertisement revenue when users consume more content. We derive conditions under which the cross-carrier MVNO achieves a profit and its users reduce their costs. Finally, we use a real-world network quality dataset to simulate users' network selection behavior and demonstrate the benefits of the ISP competition brought by the cross-carrier MVNO.

The growing volume of mobile data traffic has led many Internet service providers (ISPs) to cap the monthly data usage of their users and to charge overage fees, when the data caps are exceeded. Yet data caps imperfectly capture the reality of heterogeneous data usage over a month-even the same user may have varied requirements from month to month. In response, some ISPs are providing alternative avenues for users to customize data plans to their needs. In this paper, we examine a secondary data market, as for example created by China Mobile Hong Kong, in which users can buy and sell leftover data caps from one another. While similar to an auction in that users submit bids to buy and sell data, it differs from traditional double auctions in that the ISP serves as the middleman between buyers and sellers. Such a market faces two questions. First, can users learn each others' trading behavior well enough for the market to function, and second, do ISPs have a financial incentive to offer such a market? Different users' abilities to trade data depend on others, thus forcing users to not only optimize the amounts of data they bid, but also to learn and adjust for other users' trading behavior. We derive users' optimal behavior and propose an algorithm for ISPs to match buyers and sellers. We compare the optimal matchings for different ISP objectives and derive conditions under which the secondary market increases ISP revenue: while the ISP loses revenue from overage fees, it can assess administration fees and profit from the differences between the buyer and seller prices. Finally, we use one year of usage data from 100 U.S. mobile users to simulate the market dynamics and to illustrate that sustainable conditions for a revenue increase for the ISP can hold in practice.

We study the dynamics of network selection in heterogeneous wireless networks based on client-side control. Clients in such networks selfishly select the best radio access technology (RAT) that maximizes their own throughputs. We study two general classes of throughput models that capture the basic properties of random access (e.g., Wi-Fi) and scheduled access (e.g., WiMAX, LTE, and 3G) networks. Formulating the problem as a non-cooperative game, we study its existence of equilibria, convergence time, efficiency, and practicality. Our results reveal that: 1) single-class RAT selection games converge to Nash equilibria, while an improvement path can be repeated infinitely with a mixture of classes; 2) we provide tight bounds on the convergence time of these games; 3) we analyze the Pareto-efficiency of the Nash equilibria of these games, deriving the conditions under which Nash equilibria are Pareto-optimal, and quantifying the distance of equilibria with respect to the set of Pareto-dominant points when the conditions are not satisfied; and 4) with extensive measurement-driven simulations, we show that RAT selection games converge to Nash equilibria in a small number of steps, and are amenable to practical implementation. We also investigate the impact of noisy throughput estimates, and propose solutions to handle them.

We address the problem of scheduling jobs with utilities that depend solely upon their completion-times in a shared cloud that imposes considerable uncertainty on the jobs' runtime. However, it is very hard to estimate the jobs' runtime in a shared cloud where jobs are often delayed due to reasons such as slow I/O performance and variations in memory availability. Unlike prior works, we acknowledge that runtime estimates are often erroneous and instead shift the burden of robustness to the job scheduler. Specifically, we present a scheduling problem that jointly accounts for: (i) job utilities specified as functions of their completion-time, and (ii) uncertainty in the jobs' runtime. Our proposed solution to this problem achieves lexicographic max-min fairness among the job utilities. We implement this as a robust scheduler, named RUSH, for YARN in Hadoop. Our experiments, using real-world data sets, illustrate RUSH's efficacy when compared with other commonly used schedulers.

A Social Learning Network (SLN) emerges when users exchange information on educational topics with structured interactions. The recent proliferation of massively scaled online (human) learning, such as Massive Open Online Courses (MOOCs), has presented a plethora of research challenges surrounding SLN. In this paper, we ask: How efficient are these networks? We propose a framework in which SLN efficiency is determined by comparing user benefit in the observed network to a benchmark of maximum utility achievable through optimization. Our framework defines the optimal SLN through utility maximization subject to a set of constraints that can be inferred from the network. Through evaluation on four MOOC discussion forum datasets and optimizing over millions of variables, we find that SLN efficiency can be rather low (from 68% to 82% depending on the specific parameters and dataset), which indicates that much can be gained through optimization. We find that the gains in global utility (i.e., average across users) can be obtained without making the distribution of local utilities (i.e., utility of individual users) less fair. We also discuss ways of realizing the optimal network in practice, through curated news feeds in online SLN.

We model and analyze a User-Equipment (UE) based wireless network selection method where individuals act on their stochastic knowledge of the expected behavior off their available networks. In particular, we focus on networks with millimeter-wave (mmWave) radio. Modeling mmWave radio access technologies (RATs) as a stochastic 3-state process based on their physical layer characteristics in Line-of-Sight (LOS), Non-Line-of-Sight (NLOS), and Outage states, we make the realistic assumption that users have no knowledge of the statistics of the RATs and must learn these while maximizing the throughput obtained. We develop an online learning-based approach to access network selection: a user-centric Multi-Armed Bandit Problem that incorporates the cost of switching access networks. We develop an online learning policy that groups network access to minimize costs for RAT selection, analyze the regret (loss due to uncertainty) of our algorithm. We also show that our algorithm obtains optimal regret and in numerical examples achieves 24% increase in total throughput compared to existing techniques for high throughput mmWave RATs that vary over a fast timescale.

Cloud service providers (CSPs) often face highly dynamic user demands for their resources, which can make it difficult for them to maintain consistent quality-of-service. Some CSPs try to stabilize user demands by offering sustained-use discounts to jobs that consume more instance-hours per month. These discounts present an opportunity for users to pool their usage together into a single ``job.'' In this paper, we examine the viability of a middleman, the cloud virtual service provider (CVSP), that rents cloud resources from a CSP and then resells them to users. We show that the CVSP's business model is only viable if the average job runtimes and thresholds for sustained-use discounts are sufficiently small; otherwise, the CVSP cannot simultaneously maintain low job waiting times while qualifying for a sustained-use discount. We quantify these viability conditions by modeling the CVSP's job scheduling and then use this model to derive users' utility-maximizing demands and the CVSP's profit-maximizing price, as well as the optimal number of instances that the CVSP should rent from the CSP. We verify our results on a one-month trace from Google's production compute cluster, through which we first validate our assumptions on the job arrival and runtime distributions, and then show that the CVSP is viable under these workload traces. Indeed, the CVSP can earn a positive profit without significantly impacting the CSP's revenue, indicating that the CSP and CVSP can coexist in the cloud market.

Fog is an emergent architecture for computing, storage, control, and networking that distributes these services closer to end users along the cloud-to-things continuum. It covers both mobile and wireline scenarios, traverses across hardware and software, resides on network edge but also over access networks and among end users, and includes both data plane and control plane. As an architecture, it supports a growing variety of applications, including those in the Internet of Things (IoT), fifth-generation (5G) wireless systems, and embedded artificial intelligence (AI). This survey paper summarizes the opportunities and challenges of fog, focusing primarily in the networking context of IoT.

To efficiently support and manage massive number of Internet of Things (IoT) short and bursty sessions, current long-term evolution (LTE) system needs to reduce signal load generated by IoT session setup/synchronization, while balancing the system performance, such as UE power consumption and delays to time-sensitive traffic. In LTE, radio resource control (RRC) and discontinuous reception (DRX) affect power consumption, signal load, and delay. We provide a session management methodology suitable for IoT traffic over LTE. Our analysis starts with a Markov chain analysis of the impact of DRX parameters. This is followed by an optimal uplink scheduler design and an IoT-aware adaptive DRX algorithm at the client, both of which modulate the tradeoff among signal load, delay, and power consumption. Scalability is also considered by providing a high-priority clustering-based adaptive DRX algorithm at eNB. Simulation results show that for packets with 0.1 s delay, our scheduler outperforms “Tx now” (and “Wait Till Deadline”) by 50% (and 30%) in power saving and by 60% (and 15%) in signal saving. With knowledge of the traffic pattern, IoT-aware adaptive DRX can further reduce signal load by 25%, especially for delay-sensitive traffic.

The widespread use of online social networks (OSNs) to disseminate information and exchange opinions, by the general public, news media, and political actors alike, has enabled new avenues of research in computational political science. In this paper, we study the problem of quantifying and inferring the political leaning of Twitter users. We formulate political leaning inference as a convex optimization problem that incorporates two ideas: (a) users are consistent in their actions of tweeting and retweeting about political issues, and (b) similar users tend to be retweeted by similar audience. We then apply our inference technique to 119 million election-related tweets collected in seven months during the 2012 U.S. presidential election campaign. On a set of frequently retweeted sources, our technique achieves 94 percent accuracy and high rank correlation as compared with manually created labels. By studying the political leaning of 1,000 frequently retweeted sources, 232,000 ordinary users who retweeted them, and the hashtags used by these sources, our quantitative study sheds light on the political demographics of the Twitter population, and the temporal dynamics of political polarization as events unfold.

To cope with recent exponential increases in demand for mobile data, wireless Internet service providers (ISPs) are increasingly changing their pricing plans and deploying Wi-Fi hotspots to offload their mobile traffic. However, these ISP-centric approaches for traffic management do not always match the interests of mobile users. Users face a complex, multi-dimensional tradeoff between cost, throughput, and delay in making their offloading decisions: while they may save money and receive a higher throughput by waiting for Wi-Fi access, they may not wait for Wi-Fi if they are sensitive to delay. To navigate this tradeoff, we develop Adaptive bandwidth Management through USer-Empowerment (AMUSE), a functional prototype of a practical, cost-aware Wi-Fi offloading system that takes into account a user's throughput-delay tradeoffs and cellular budget constraint. Based on predicted future usage and Wi-Fi availability, AMUSE decides which applications to offload to what times of the day. Since nearly all traffic flows from mobile devices are TCP flows, we introduce a new receiver-side bandwidth allocation mechanism to practically enforce the assigned rate of each TCP application. Thus, AMUSE users can optimize their bandwidth rates according to their own cost-throughput-delay tradeoff without relying on support from different apps’ content servers. Through a measurement study of 20 smartphone users’ traffic usage traces, we observe that though users already offload a large amount of some application types, our framework can offload a significant additional portion of users’ cellular traffic. We implement AMUSE on Windows 7 tablets and evaluate its effectiveness with 3G and Wi-Fi usage data obtained from a trial with 37 mobile users. Our results show that AMUSE improves user utility; when compared with AMUSE, other offloading algorithms yield 14 and 27 percent lower user utilities for light and heavy users, respectively. Intelligently managing users’ competing interests for cost, throughput, and delay can therefore improve their offloading decisions.

This paper proposes a new protocol called Optimal DCF (O-DCF). O-DCF modifies the rule of adapting CSMA parameters, such as backoff time and transmission length, based on a function of the demand-supply differential of link capacity captured by the local queue length. O-DCF is fully compatible with 802.11 hardware, so that it can be easily implemented only with a simple device driver update. O-DCF is inspired by the recent analytical studies proven to be optimal under assumptions, which often generates a big gap between theory and practice. O-DCF effectively bridges such a gap, which is implemented in off-the-shelf 802.11 chipset. Through extensive simulations and real experiments with a 16-node wireless network testbed, we evaluate the performance of O-DCF and show that it achieves near-optimality in terms of throughput and fairness and outperforms other competitive ones, such as 802.11 DCF, optimal CSMA, and DiffQ for various scenarios. Also, we consider the coexistence of O-DCF and 802.11 DCF and show that O-DCF fairly shares the medium with 802.11 via its parameter control.

We study a fundamental question that arises in social recommender systems: whether it is possible to simultaneously maximize: 1) an individual's benefit from using a social network, and 2) the efficiency of the network in disseminating information. To tackle this question, our study consists of three components. First, we introduce a stylized stochastic model for recommendation diffusion. Such a model allows us to highlight the connection between user experience at the individual level, and network efficiency at the macroscopic level. We also propose a set of metrics for quantifying both user experience and network efficiency. Second, based on these metrics, we extensively study the tradeoff between the two factors in a Yelp dataset, concluding that Yelp's social network is surprisingly efficient, though not optimal. Finally, we design a friend recommendation and news feed curation algorithm that can simultaneously address individuals' need to connect to high-quality friends, and service providers' need to maximize network efficiency in information propagation.

As sharing agreements are being ratified by the Federal Communications Commission (FCC) for various spectrum bands for commercial broadband use, it also opens up an equally challenging problem of enforcing these policies. The efficacy of an enforcement system greatly depends on the accuracy of evidential information and the speed of adjudication. The inherent unguided and unbounded nature of radio wave propagation allows spectrum infractions to cause widespread damage and makes it hard to locate at the same time. On the other hand, it also lends itself to distributed methods for efficient enforcement of spectrum etiquette. We leverage a crowd of mobile users to implement a paradigm of “eye-witness” for detecting violations of spectrum policies. We design and analyze the crowdsourced enforcement architecture and show three main results: 1) it detects an infraction with a consistent high degree of accuracy (> 90%); 2) it is able to accurately locate the source of infraction and 3) it lowers the frequency of policy infractions over time.

Public cloud storage has recently surged in popularity. However, cloud storage providers (CSPs) today offer fairly rigid services, which cannot be customized to meet individual users' needs. We propose a distributed, client-defined architecture that integrates multiple autonomous CSPs into one unified cloud and allows individual clients to specify their desired performance levels and share files. We design, implement, and deploy CYRUS (Client-defined privacY-protected Reliable cloUd Service), a practical system that realizes this architecture. CYRUS ensures user privacy and reliability by scattering files into smaller pieces across multiple CSPs, so that no one CSP can read users' data. We develop an algorithm that sets reliability and privacy parameters according to user needs and selects CSPs from which to download user data so as to minimize latency. To accommodate multiple autonomous clients, we allow clients to upload simultaneous file updates and detect conflicts after the fact from the client. We finally evaluate the performance of a CYRUS prototype that connects to four popular commercial CSPs in both lab testbeds and user trials, and discuss CYRUS's implications for the cloud storage market.

We study student performance prediction in Massive Open Online Courses (MOOCs), where the objective is to predict whether a user will be Correct on First Attempt (CFA) in answering a question. In doing so, we develop novel techniques that leverage behavioral data collected by MOOC platforms. Using video-watching clickstream data from one of our MOOCs, we first extract summary quantities (e.g., fraction played, number of pauses) for each user-video pair, and show how certain intervals/sets of values for these behaviors quantify that a pair is more likely to be CFA or not for the corresponding question. Motivated by these findings, our methods are designed to determine suitable intervals from training data and to use the corresponding success estimates as learning features in prediction algorithms. Tested against a large set of empirical data, we find that our schemes outperform standard algorithms (i.e., without behavioral data) for all datasets and metrics tested. Moreover, the improvement is particularly pronounced when considering the first few course weeks, demonstrating the “early detection” capability of such clickstream data. We also discuss how CFA prediction can be used to depict graphs of the Social Learning Network (SLN) of students, which can help instructors manage courses more effectively.

With recent standardization and deployment of LTE eMBMS, cellular multicast is gaining traction as a method of efficiently using wireless spectrum to deliver large amounts of multimedia data to multiple cell sites. Cellular operators still seek methods of performing optimal resource allocation in eMBMS based on a complete understanding of the complex interactions among a number of mechanisms: the multicast coding scheme, the resources allocated to unicast users and their scheduling at the base stations, the resources allocated to a multicast group to satisfy the user experience of its members, and the number of groups and their membership, all of which we consider in this work. We determine the optimal allocation of wireless resources for users to maximize proportional fair utility. To handle the heterogeneity of user channel conditions, we efficiently and optimally partition multicast users into groups so that users with good signal strength do not suffer by being grouped together with users of poor signal strength. Numerical simulations are performed to compare our scheme to practical heuristics and state-of-the-art schemes. We demonstrate the tradeoff between improving unicast user rates and improving spectrum efficiency through multicast. Finally, we analyze the interaction between the globally fair solution and individual user's desire to maximize its rate. We show that even if the user deviates from the global solution in a number of scenarios, we can bound the number of selfish users that will choose to deviate.

There is an increasing need for cloud service performance that can be tailored to customer requirements. In the context of jobs submitted to cloud computing clusters, a crucial requirement is the specification of job completion-times. A natural way to model this specification, is through client/job utility functions that are dependent on job completion-times. We present a method to allocate and schedule heterogeneous resources to jointly optimize the utilities of jobs in a cloud. Specifically: (i) we formulate a completion-time optimal resource allocation (CORA) problem to apportion cluster resources across the jobs that enforces max-min fairness among job utilities, and (ii) starting with an integer programming problem, we perform a series of steps to transform it into an equivalent linear programming problem, and (iii) we implement the proposed framework as a utility-aware resource scheduler in the widely used Hadoop data processing framework, and finally (iv) through extensive experiments with real-world datasets, we show that our prototype achieves significant performance improvement over existing resource-allocation policies.

In January 2014, AT&T introduced sponsored data to the U.S. mobile data market, allowing content providers (CPs) to subsidize users' cost of mobile data. As sponsored data gains traction in industry, it is important to understand its implications. This work considers CPs' choice of how much content to sponsor and the implications for users, CPs, and ISPs (Internet service providers). We first formulate a model of user, CP, and ISP interaction for heterogeneous users and CPs and derive their optimal behaviors. We then show that these behaviors can reverse our intuition as to how user demand and utility change with different user and CP characteristics. While all three parties can benefit from sponsored data, we find that sponsorship disproportionately favors less cost-constrained CPs and more cost-constrained users, exacerbating CP inequalities but making user demand more even. We also show that users' utilities increase more than CPs' with sponsored data. We finally illustrate these results in practice through numerical simulations with data from a commercial pricing trial and introduce a framework for CPs to decide which, in addition to how much, content to sponsor.

We study the convergence properties of distributed network selection in HetNets with priority-based service. Clients in such networks have different priority weights (e.g., QoS requirements, scheduling policies, etc.) for different access networks and act selfishly to maximize their own throughput. We formulate the problem as a non-cooperative game, and study its convergence for two models: (i) A purely client-centric model where each client uses its own preference to select a network, and (ii) a hybrid client-network model that uses a combination of client and network preferences to arrive at pairings. Our results reveal that: (a) Pure client-centric network selection with generic weights can result in infinite oscillations for any improvement path (i.e., shows strongly cyclic behavior). However, we show that under several classes of practical priority weights (e.g., weights that achieve different notions of fairness) or under additional client-side policies, convergence can be guaranteed; (b) We study convergence time under client-centric model and provide tight polynomial and linear bounds; (c) We show that applying a minimal amount of network control in the hybrid model, guarantees convergence for clients with generic weights. We also introduce a controllable knob that network controller can employ to balance between convergence time and its network-wide objective with predictable tradeoff.

The recently proposed 3-Tier access model for Whitespace by the Federal Communications Commission (FCC) mandates certain classes of devices to share frequency bands in space and time. These devices are envisioned to be a heterogeneous mixture of licensed (Tier-1 and Tier-2) and unlicensed, opportunistic devices (Tier-3). The hierarchy in accessing the channel calls for superior adaptation of Tier-3 devices with varying spectral opportunity. While policies are being ratified for efficient sharing, it also calls for redesigning many common applications to adapt to this novel paradigm. In this paper, we focus on the ever-increasing demand for video streaming and present a methodology suitable for Tier-3 devices in the shared access model. Our analysis begins with a stress test of commonly adopted video streaming methods under the new sharing model. This is followed by the design of a robust MDP-based solution that proactively adapts to fast-varying channel conditions, providing better user quality of experience when compared to existing solutions, such as MPEG-DASH. We evaluate our solution on an experimental testbed and find that our MDP-based algorithm outperforms DASH, and partial information of Tier-2 dynamics improves video quality.

We study a fundamental question that arises in social recommender systems: whether it is possible to simultaneously maximize (a) an individual's benefit from using a social network and (b) the efficiency of the network in disseminating information. To tackle this question, our study consists of three components. First, we introduce a stylized stochastic model for recommendation diffusion. Such a model allows us to highlight the connection between user experience at the individual level, and network efficiency at the macroscopic level. We also propose a set of metrics for quantifying both user experience and network efficiency. Second, based on these metrics, we extensively study the tradeoff between the two factors in a Yelp dataset, concluding that Yelp's social network is surprisingly efficient, though not optimal. Finally, we design a friend recommendation and news feed curation algorithm that can simultaneously address individuals' need to connect to high quality friends, and service providers' need to maximize network efficiency in information propagation.

The growing volume of mobile data traffic has led many Internet service providers (ISPs) to cap their users' monthly data usage, with overage fees for exceeding their caps. In this work, we examine a secondary data market in which users can buy and sell leftover data caps from each other. China Mobile Hong Kong recently introduced such a market. While similar to an auction in that users submit bids to buy and sell data, it differs from traditional double auctions in that the ISP serves as the middleman between buyers and sellers. We derive the optimal prices and amount of data that different buyers and sellers are willing to bid in this market and then propose an algorithm for ISPs to match buyers and sellers. We compare the optimal matching for different ISP objectives and derive conditions under which an ISP can obtain higher revenue with the secondary market: while the ISP loses revenue from overage fees, it can assess administration fees and take the differences between the buyer and seller prices. Finally, we use one year of usage data from 100 U.S. mobile users to illustrate that the conditions for a revenue increase can hold in practice.

Recent increases in network traffic have led to severe congestion in broadband networks. We propose to mitigate this problem with a two-level edge-based solution that incentivizes users to moderate their bandwidth usage based on their actual needs. In the first level, home gateways are given QoE (quality of experience) credits that they can spend to receive more bandwidth at congested times; to ensure fairness, the credits are redistributed to other gateways after they are spent. We show that this scheme guarantees long-term fairness and maximizes users' total satisfaction at the equilibrium. In the second level, each gateway allocates bandwidth among its users and apps according to its own priorities. Gateways can thus customize their bandwidth allocation depending on individual preferences. We develop a prototype of this second-level allocation on commodity wireless routers. We then consider an example scenario and show by simulation and implementation results that our solution outperforms an equal bandwidth allocation, increasing users' overall utility and fairly allocating bandwidth across users.

In anticipation of the increasing demand of wireless traffic, WiFi standardization efforts have recently focused on two key technologies for capacity improvement: multi-user MIMO and wider bandwidth. However, users experience heterogeneous channel orthogonality characteristics across sub-carriers in the same channel bandwidth, which prevents ideal multi-user gain. Moreover, frequency selectivity increases as bandwidth scales and correspondingly severely deteriorates multi-user MIMO performance. In this work, we consider the frequency selectivity of current and emerging WiFi channel bandwidths to optimize multi-user MIMO by dividing the occupied channel bandwidth into equally-sized sub-channels according to the level of frequency selectivity. In our selectivity-aware multi-user MIMO design, SAMU, each sub-channel is allocated according to the largest bandwidth that can be considered frequency-flat, and an optimal subset of users is chosen to serve in each sub-channel according to spatial orthogonality, achieving a significant performance improvement for all users in the network. Additionally, we propose a selectivity-aware very high throughput (SA-VHT) mode, which is based on and an extension to the existing IEEE 802.11ac standard. Over emulated and real indoor channels, even with minimal mobility, SAMU achieves as much as 80 percent throughput improvement compared to existing multi-user MIMO schemes, which could serve as a lower bound as bandwidth scales.

Amazon's Elastic Compute Cloud (EC2) uses auction-based spot pricing to sell spare capacity, allowing users to bid for cloud resources at a highly reduced rate. Amazon sets the spot price dynamically and accepts user bids above this price. Jobs with lower bids (including those already running) are interrupted and must wait for a lower spot price before resuming. Spot pricing thus raises two basic questions: how might the provider set the price, and what prices should users bid? Computing users' bidding strategies is particularly challenging: higher bid prices reduce the probability of, and thus extra time to recover from, interruptions, but may increase users' cost. We address these questions in three steps: (1) modeling the cloud provider's setting of the spot price and matching the model to historically offered prices, (2) deriving optimal bidding strategies for different job requirements and interruption overheads, and (3) adapting these strategies to MapReduce jobs with master and slave nodes having different interruption overheads. We run our strategies on EC2 for a variety of job sizes and instance types, showing that spot pricing reduces user cost by 90% with a modest increase in completion time compared to on-demand pricing.

In this paper, we optimize the use of existing DSL low-power sleeping modes (L2 and L3) in order to improve the energy efficiency of DSL access networks. Given that switching on a DSL line can cause instability by increasing the amount of time-varying crosstalk in the cable bundle, and that it takes energy and time to switch a DSL line on and off, we develop a method to optimally choose the appropriate sleeping state based on the line and traffic characteristics. We further develop and prove the structural properties of the optimal policy for switching to the appropriate sleeping state, allowing transitions between submodes with different power and transmit rate characteristics. We also present techniques that guarantee stable sleep mode operation. Using a realistic DSL simulator, we demonstrate the three-way tradeoff among energy consumption, delay performance, and stability. The increased flexibility of control introduced by our approach improves the energy-delay Pareto optimal tradeoff, and results in a more energy efficient and stable DSL operation compared to existing power saving policies.

Presents corrections to the paper, “Link-state routing with hop-by-hop forwarding can achieve optimal traffic engineering,” (Xu, D., et al)IEEE/ACM Trans. Netw., vol. 19, no. 6, pp. 1717–1730, Dec. 2011).

We revisit the problem of predicting directional movements of stock prices based on news articles: here our algorithm uses daily articles from The Wall Street Journal to predict the closing stock prices on the same day. We propose a unified latent space model to characterize the "co-movements" between stock prices and news articles. Unlike many existing approaches, our new model is able to simultaneously leverage the correlations: (a) among stock prices, (b) among news articles, and (c) between stock prices and news articles. Thus, our model is able to make daily predictions on more than 500 stocks (most of which are not even mentioned in any news article) while having low complexity. We carry out extensive back testing on trading strategies based on our algorithm. The result shows that our model has substantially better accuracy rate (55.7%) compared to many widely used algorithms. The return (56%) and Sharpe ratio due to a trading strategy based on our model are also much higher than baseline indices.

Given a set of files that show a certain degree of similarity, we consider a novel problem of deduplicating them (eliminating redundant chunks) across a set of distributed servers in a manner that is: (i) space-efficient: the total space needed to deduplicate and store the files is minimized and, (ii) access-efficient: each file can be accessed by communicating with a bounded number of servers, thereby minimizing network-access times in congested data center networks. A space-optimal solution in which we first deduplicate all the files and then distribute them across the servers (referred to as chunk-distribution), may require communication with many servers to access each file. On the other hand, an access-efficient solution in which we randomly partition the files cross the servers, and then store their unique chunks on each server may not exploit the similarities across files to reduce the space overhead. In this paper, we first show that finding an access-efficient, space optimal solution is an NP-Hard problem. Following this, we present the similarity-aware-partitioning (SAP) algorithms that find access-efficient solutions within polynomial time complexity and guarantees bounded space overhead for arbitrary files. Our experimental verification on files from Dropbox and CNN confirm that the SAP technique is much more space-efficient than random partitioning, while maintaining compression ratio close to the chunk-distribution solution.

Frequently, client-side wireless devices have a view of multiple WiFi access points, whether from open residential and commercial networks, corporate networks, or mesh networks. Given the increasing number of radios and antennas in today's wireless devices, residual capacity from these multiple APs could be leveraged if client devices communicate with multiple APs simultaneously. In this paper, we exploit multi-user multi-input multi-output (MU-MIMO) technology to improve throughput and reliability in both directions of a wireless connection. For uplink, we use multi-user beamforming to enable the client devices to send multiple data streams to multiple APs simultaneously. For downlink, we leverage interference nulling technology to allow the client devices to decode parallel packets from multiple APs. This iBeam system requires no changes to existing APs or backhaul networks and is compatible with the IEEE 802.11 standards. We experimentally evaluate iBeam and show significant throughput improvements over both single-AP connections and multi-AP connections in a time division mode. The client's reliability and stability are also significantly improved due to the multi-AP diversity gain.

We consider the problem of reconstructing a specific connected community S ⊂V in a graph G = (V, E), where each node v is associated with a signal whose strength grows with the likelihood that v belongs to S. This problem appears in social or protein interaction network, the latter also referred to as the signaling pathway reconstruction problem. We study this community reconstruction problem under several natural generative models, and make the following two contributions. First, in the context of social networks, where the signals are modeled as bounded-supported random variables, we design an efficient algorithm for recovering most members in S with well-controlled false positive overhead, by utilizing the network structure for a large family of “homogeneous” generative models. This positive result is complemented by an information theoretic lower bound for the case where the network structure is unknown or the network is heterogeneous. Second, we consider the case in which the graph represents the protein interaction network, in which it is customary to consider signals that have unbounded support, we generalize our first contribution to give the first theoretical justification of why existing Steiner-tree type heuristics work well in practice.

In an era of 108% annual growth in demand for mobile data and $10/GB overage fees, Internet Service Providers (ISPs) are experiencing severe congestion and in turn are hurting consumers with aggressive pricing measures. But smarter practices, such as time-dependent pricing (TDP), reward users for shifting their non-critical demand to off-peak hours and can potentially benefit both users and ISPs. Although dynamic TDP ideas have existed for many years, dynamic pricing for mobile data is only now gaining interest among ISPs. Yet TDP plans require not only systems engineering but also an understanding of economic incentives, user behavior and interface design. In particular, the HCI aspects of communicating price feedback signals from the network and the response of mobile data users need to be studied in the real world. But investigating these issues by deploying a virtual TDP data plan for real ISP customers is challenging and rarely explored. To this end, we carried out the first TDP trial for mobile data in the US with 10 families. We describe the insights gained from the trial, which can help the HCI community as well as ISPs, app developers and designers create tools that empower users to better control their usage and save on their monthly bills, while also alleviating network congestion.

We study the dynamics of network selection in heterogeneous wireless networks (HetNets). Users in such networks selfishly select the best radio access technology (RAT) with the objective of maximizing their own throughputs. We propose two general classes of throughput models that capture the basic properties of random access (e.g., Wi-Fi) and scheduled access (e.g., WiMAX, LTE, 3G) networks. Next, we formulate the problem as a non-cooperative game, and study its convergence, efficiency, and practicality. Our results reveal that: (i) Single-class RAT selection games converge to Nash equilibria, while an improvement path can be repeated infinitely with a mixture of classes. We next introduce a hysteresis mechanism in RAT selection games, and prove that with appropriate hysteresis policies, convergence can still be guaranteed; (ii) We analyze the Pareto-efficiency of the Nash equilibria of these games. We derive the conditions under which Nash equilibria are Pareto-optimal, and we quantify the distance of Nash equilibria with respect to the set of Pareto-dominant points when the conditions are not satisfied; (iii) Finally, with extensive measurement-driven simulations we show that RAT selection games converge to Nash equilibria in a small number of steps, and hence are amenable to practical implementation. We also investigate the impact of noisy throughput measurements, and propose solutions to handle them.

Mobile users face a tradeoff between cost, throughput, and delay in making their offloading decisions. To navigate this tradeoff, we propose AMUSE (Adaptive bandwidth Management through USer-Empowerment), a practical, costaware WiFi offloading system that takes into account a user's throughput-delay tradeoffs and cellular budget constraint. Based on predicted future usage and WiFi availability, AMUSE decides which applications to offload to what times of the day. To practically enforce the assigned rate of each TCP application, we introduce a receiver-side TCP bandwidth control algorithm that adjusts the rate by controlling the TCP advertisement window from the user side. We implement AMUSE on Windows 7 tablets and evaluate its effectiveness with 3G and WiFi usage data obtained from a trial with 25 mobile users. Our results show that AMUSE improves user utility.

Today's data centers are shared among multiple tenants running a wide range of applications. These applications require a network with a scalable and robust layer-2 network management solution that enables load-balancing and QoS provisioning. Ensemble routing was proposed to achieve management scalability and robustness by using Virtual Local Area Networks (VLANs) and operating on the granularity of flow ensembles, i.e. group of flows. The key challenge of intra-data-center traffic engineering with ensemble routing is the combinatorial optimization of VLAN assignment, i.e., optimally assigning flow ensembles to VLANs to achieve load balancing and low network costs. Based on the Markov approximation framework, we solve the VLAN assignment problem with a general objective function and arbitrary network topologies by designing approximation algorithms with close-to-optimal performance guarantees. We study several properties of our algorithms, including performance optimality, perturbation bound, convergence of algorithms and impacts of algorithmic parameter choices. Then we extend these results to variants of VLAN assignment problem, including interaction with TCP congestion and QoS considerations. We validate our analytical results by conducting extensive numerical experiments. The results show that our algorithms can be tuned to meet different temporal constraints, incorporate fine-grained traffic management, overcome traffic measurement limitations, and tolerate imprecise and incomplete traffic matrices.

As the growth of mobile video traffic outpaces that of cellular network speed, industry is adopting HTTP-based adaptive video streaming technology which enables dynamic adaptation of video bit-rates to match changing network conditions. However, recent measurement studies have observed problems in fairness, stability, and efficiency of resource utilization when multiple adaptive video flows compete for bandwidth on a shared wired link. Through experiments and simulations, we confirm that such undesirable behavior manifests itself in cellular networks as well. To overcome these problems, we design an in-network resource management framework, AVIS, that schedules HTTP-based adaptive video flows on cellular networks. AVIS effectively manages the resources of a cellular base station across adaptive video flows. AVIS also provides a framework for mobile operators to achieve a desired balance between optimal resource allocation and user quality of experience. AVIS has three key differentiating features: (1) It optimally computes the bit-rate allocation for each user, (2) It includes a scheduler and per-flow shapers to enforce bit-rate stability of each flow and (3) It leverages the resource virtualization technique to separate resource management of adaptive video flows from regular video flows. We implement a prototype system of AVIS and evaluate it on both a WiMAX network testbed and a LTE system simulator to show its efficacy and scalability.

This paper proposes a new wireless MAC protocol called Optimal DCF (O-DCF). O-DCF modifies the rule of adapting CSMA parameters, such as backoff time and transmission length, based on a function of the supply-demand differential captured by the local queue length. O-DCF is fully compatible with 802.11 hardware, so that it can be easily implemented only with a simple device driver update. O-DCF is inspired by the recent theoretical studies on queue-based CSMA for high throughput and fairness. O-DCF effectively bridges the gap between theory and practice, implemented and tested in an off-the-shelf 802.11 chipset. Through extensive simulations and real experiments with a 16-node wireless network testbed, we evaluate the performance of O-DCF and show that it outperforms other competitive ones, such as 802.11 DCF, optimal CSMA, and DiffQ for various scenarios.

Social networks overlaid on technological networks account for a significant fraction of Internet use. Through graph theoretic and functionality models, this paper examines social network analysis and potential implications for the design of technological networks, and vice versa. Such interplay between social networks and technological networks suggests new directions for future research in networking.

Quantifying the notion of fairness is underexplored when there are multiple types of resources and users request different ratios of the different resources. A typical example is data centers processing jobs with heterogeneous resource requirements on CPU, memory, network bandwidth, etc. In such cases, a tradeoff arises between equitability, or “fairness,” and efficiency. This paper develops a unifying framework addressing the fairness-efficiency tradeoff in light of multiple types of resources. We develop two families of fairness functions that provide different tradeoffs, characterize the effect of user requests' heterogeneity, and prove conditions under which these fairness measures satisfy the Pareto efficiency, sharing incentive, and envy-free properties. Intuitions behind the analysis are explained in two visualizations of multiresource allocation. We also investigate people's fairness perceptions through an online survey of allocation preferences.

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

This paper investigates pricing-based spectrum access control in cognitive radio networks, where primary users (PUs) sell the temporarily unused spectrum and secondary users (SUs) compete via random access for such spectrum opportunities. Compared to existing market-based approaches with centralized scheduling, pricing-based spectrum management with random access provides a platform for SUs contending for spectrum access and is amenable to decentralized implementation due to its low complexity. We focus on two market models, one with a monopoly PU market and the other with a multiple-PU market. For the monopoly PU market model, we devise decentralized pricing-based spectrum access mechanisms that enable SUs to contend for channel usage. Specifically, we first consider SUs contending via slotted Aloha. Since the revenue maximization problem therein is nonconvex, we characterize the corresponding Pareto-optimal region and obtain a Pareto-optimal solution that maximizes the SUs' throughput subject to their budget constraints. To mitigate the spectrum underutilization due to the “price of contention,” we revisit the problem where SUs contend via CSMA, which results in more efficient spectrum utilization and higher revenue. We then study the tradeoff between the PU's utility and its revenue when the PU's salable spectrum is controllable. Next, for the multiple-PU market model, we cast the competition among PUs as a three-stage Stackelberg game, where each SU selects a PU's channel to maximize its throughput. We explore the existence and the uniqueness of Nash equilibrium, in terms of access prices and the spectrum offered to SUs, and develop an iterative algorithm for strategy adaptation to achieve the Nash equilibrium. Our findings reveal that there exists a unique Nash equilibrium when the number of PUs is less than a threshold determined by the budgets and elasticity of SUs.

Two emerging trends of Internet applications, video traffic becoming dominant and usage-based pricing becoming prevalent, are at odds with each other. Given this conflict, is there a way for users to stay within their monthly data plans (data quotas) without suffering a noticeable degradation in video quality? In this work, we develop an online video adaptation system, called Quota Aware Video Adaptation (QAVA), that manages this tradeoff by leveraging the compressibility of videos and by predicting consumer usage behavior throughout a billing cycle. We propose the QAVA architecture and develop its main modules, including Stream Selection, User Profiling, and Video Profiling. Online algorithms are designed through dynamic programming and evaluated using real video request traces. Empirical results suggest that QAVA can provide an effective solution to the dilemma of usage-based pricing of heavy video traffic.

Switching off a DSL line to a low-power sleeping state is becoming an important method to enhance energy efficiency of DSL broadband access networks. Although a low-power (L2) state and an off (L3) state are already defined in DSL standards, they have not been fully exploited due to concern about the resulting time-varying crosstalk. In this paper, we develop a method to optimally choose the appropriate sleeping state based on the modem's switching cost characteristics and the power consumption incurred during each sleeping state. We further develop the optimal policy for switching to the appropriate sleeping state, allowing transitions between operating modes with different power and transmit rate. Numerical results on our realistic DSL simulator show that more flexibility in control, introduced by our approach, improves the energy-delay Pareto optimal tradeoff, and results in a more energy efficient and stable DSL system compared to the existing power saving policies.

Today's data centers need efficient traffic management to improve resource utilization in their networks. In this work, we study a joint tenant (e.g., server or virtual machine) placement and routing problem to minimize traffic costs. These two complementary degrees of freedom—placement and routing—are mutually-dependent, however, are often optimized separately in today's data centers. Leveraging and expanding the technique of Markov approximation, we propose an efficient online algorithm in a dynamic environment under changing traffic loads. The algorithm requires a very small number of virtual machine migrations and is easy to implement in practice. Performance evaluation that employs the real data center traffic traces under a spectrum of elephant and mice flows, demonstrates a consistent and significant improvement over the benchmark achieved by common heuristics.

Quantifying the notion of fairness is under-explored when users request different ratios of multiple distinct resource types. A typical example is datacenters processing jobs with heterogeneous resource requirements on CPU, memory, etc. A generalization of max-min fairness to multiple resources was recently proposed in [1], but may suffer from significant loss of efficiency. This paper develops a unifying framework addressing this fairness-efficiency tradeoff with multiple resource types. We develop two families of fairness functions which provide different tradeoffs, characterize the effect of user requests' heterogeneity, and prove conditions under which these fairness measures satisfy the Pareto efficiency, sharing incentive, and envy-free properties. Intuitions behind the analysis are explained in two visualizations of multi-resource allocation.

Given that full duplex (FD) and MIMO both employ multiple antenna resources, an important question that arises is how to make the choice between MIMO and FD? We show that optimal performance requires a combination of both to be used. Hence, we present the design and implementation of MIDU, the first MIMO full duplex system for wireless networks. MIDU employs antenna cancellation with symmetric placement of transmit and receive antennas as its primary RF cancellation technique. We show that MIDU's design provides large amounts of self-interference cancellation with several key advantages: (i) It allows for two stages of additive antenna cancellation in tandem, to yield as high as 45 dB self-interference suppression; (ii) It can potentially eliminate the need for other forms of analog cancellation, thereby avoiding the need for variable attenuator and delays; (iii) It easily scales to MIMO systems, therefore enabling the coexistence of MIMO and full duplex. We implemented MIDU on the WARP FPGA platform, and evaluated its performance against half duplex (HD)-MIMO. Our results reveal that, with the same number of RF chains, MIDU can potentially double the throughput achieved by half duplex MIMO in a single link; and provide median gains of at least 20% even in single cell scenarios, where full duplex encounters inter-client interference. Based on key insights from our results, we also highlight how to efficiently enable scheduling for a MIDU node.

ISPs around the world have begun to offer new pricing plans for wireless data, such as usage-based pricing in the U.S., to mitigate recent growth in bandwidth demand. Time Dependent Pricing (TDP) represents a next step in this direction [1, 2]. With TDP, ISPs can shift traffic to off-peak periods, thus reducing their cost, while consumers save money by choosing the time of usage. TDP uses a feedback control loop between an ISP and its users to account for users' responses to offered prices in optimizing the future prices. We have implemented such a TDP system and are presently conducting a user trial at Princeton while planning larger trials with commercial ISPs. This demo will introduce the audience to our system's ISP- and user-side features. On the ISP side, we show the current network congestion, while on the user side, we show device UIs displaying the offered prices, the device usage history, and automated scheduling of applications to keep users within a specified budget.

The two largest U.S. wireless ISPs have recently moved towards usage-based pricing to better manage the growing demand on their networks. Yet usage-based pricing still requires ISPs to over-provision capacity for demand at peak times of the day. Time-dependent pricing (TDP) addresses this problem by considering when a user consumes data, in addition to how much is used. We present the architecture, implementation, and a user trial of an end-to-end TDP system called TUBE. TUBE creates a price-based feedback control loop between an ISP and its end users. On the ISP side, it computes TDP prices so as to balance the cost of congestion during peak periods with that of offering lower prices in less congested periods. On mobile devices, it provides a graphical user interface that allows users to respond to the offered prices either by themselves or using an "autopilot" mode. We conducted a pilot TUBE trial with 50 iPhone or iPad 3G data users, who were charged according to our TDP algorithms. Our results show that TDP benefits both operators and customers, flattening the temporal fluctuation of demand while allowing users to save money by choosing the time and volume of their usage.

The performance of interactive cloud services depends heavily on which data centers handle client requests, and which wide-area paths carry traffic. While making these decisions, cloud service providers also need to weigh operational considerations like electricity and bandwidth costs, and balancing server loads across replicas. We argue that selecting data centers and network routes independently, as is common in today's services, can lead to much lower performance or higher costs than a coordinated decision. However, fine-grained joint control of two large distributed systems---e.g., DNS-based replica-mapping and data center multi-homed routing---can be administratively challenging. In this paper, we introduce the design of a system that jointly optimizes replica-mapping and multi-homed routing, while retaining the functional separation that exists between them today. We show how to construct a provably optimal distributed solution implemented through local computations and message exchanges between the mapping and routing systems.

This paper analyzes layer 2 contention resolution strategies for wireless networks with multipacket reception by using noncooperative game theory. Necessary and sufficient conditions are obtained for a strategy profile to be a Nash equilibrium. Applications of the derived equilibrium conditions to predict selfish behavior and the resulting equilibrium performance are illustrated in specific communication scenarios along with various design insights. The collective equilibrium behavior of wireless networks with large user populations is also studied, and a Poisson-Bernoulli type approximation is obtained for the total number of packet arrivals. Finally, random access control with imperfect information structure is considered, the form of equilibrium strategies as well as uniqueness and existence results for general wireless channel models are obtained, and the best-response learning dynamics achieving an equilibrium are illustrated in specific instances.

Smart grids are capable of two-way communication between individual user devices and the electricity provider, enabling providers to create a control-feedback loop using time-dependent pricing. By charging users more in peak and less in off-peak hours, the provider can induce users to shift their consumption to off-peak periods, thus relieving stress on the power grid and the cost incurred from large peak loads. We formulate the electricity provider's cost minimization problem in setting these prices by considering consumers' device-specific scheduling flexibility and the provider's cost structure of purchasing electricity from an electricity generator. Consumers' willingness to shift their device usage is modeled probabilistically, with parameters that can be estimated from real data. We develop an algorithm for computing day-ahead prices, and another algorithm for estimating and refining user reaction to the prices. Together, these two algorithms allow the provider to dynamically adjust the offered prices based on user behavior. Numerical simulations with data from an Ontario electricity provider show that our pricing algorithm can significantly reduce the cost incurred by the provider.

Transmit power control in wireless networks has long been recognized as an effective mechanism to mitigate co-channel interference. Due to the highly non-convex nature, optimal power control is known to be difficult to achieve if a system utility is to be maximized. In our earlier paper , we have proposed a centralized optimal power control algorithm that obtains the global optimal solution for both concave and non-concave system utility functions. A question remained unanswered is whether such global optimal solution can be achieved in a distributed manner. This paper addresses the question by developing a Gibbs Sampling based Asynchronous distributed power control algorithm (referred to as GLAD). The proposed algorithm quickly converges to the global optimal solution regardless of the concavity, differentiability and monotonicity of the utility function. To further enhance the practicality of the algorithm, this paper proposes two variants of the GLAD algorithm, namely I-GLAD and NI-GLAD, to reduce message passing in two dimensions of communication complexity, i.e., time and space. In particular, I-GLAD, where the prefix "I" stands for Infrequent message passing, reduces the "time overhead" of message passing. The convergence of I-GLAD can be proved regardless of the reduction in the message passing rate. Meanwhile, NI-GLAD, where the prefix "N" stands for Neighborhood message passing, restricts the computation overhead related to message passing to a small neighborhood space. Our results show that the optimality of the solution obtained by NI-GLAD depends on the selection of the neighborhood size.

DSL broadband access suffers from crosstalk among different lines within the same cable bundle. Dynamic spectrum management (DSM) refers to a set of techniques to mitigate the impact of crosstalk leading to spectacular performance gains. DSM research has mainly aimed at physical layer performance metrics, such as data rates and transmit powers. However, for many applications higher-layer performance metrics, such as throughput and delay, may be much more important to improve user satisfaction. In this paper, we provide a cross-layer DSM framework to study throughput and delay performance by looking at scheduling and DSM together. We show how optimal scheduling can be combined with both optimal and suboptimal DSM and provide throughput-optimal scheduling algorithms which require only polynomial complexity. We analytically study the impact on delay performance of achieving throughput-optimality with suboptimal DSM compared to optimal DSM. We then present extensions that significantly improve delay performance by exploiting the specific structure of the problem, such as the temporal-spectral correlation property. Furthermore, we propose a second cross-layer DSM framework that achieves throughput-optimal scheduling with suboptimal DSM, but in addition also significantly reduces overall power consumption. Finally, we analyze and quantify the tradeoff between throughput, delay and power consumption for concrete DSL scenarios.

Recent advances in network coding have shown great potential for efficient information multicasting in communication networks, in terms of both network throughput and network management. In this paper, the problem of flow control at end-systems for network-coding-based multicast flows is addressed. Optimization-based models are formulated for network resource allocation, based on which two sets of decentralized controllers at sources and links/nodes for congestion control are developed for wired networks with given coding subgraphs and without given coding subgraphs, respectively. With random network coding, both sets of controllers can be implemented in a distributed manner, and work at the transport layer to adjust source rates and at network layer to carry out network coding. The convergence of the proposed controllers to the desired equilibrium operating points is proved, and numerical examples are provided to complement the theoretical analysis. The extension to wireless networks is also briefly discussed.

For indoor location estimation based on wireless local area networks fingerprinting, how to reduce the offline calibration effort while maintaining high location estimation accuracy is of major concern. In this paper, a hybrid generative/discriminative semi-supervised learning algorithm is proposed that utilizes a large number of unlabeled samples to supplement a small number of labeled samples. This hybrid method allows us to combine the modeling power and flexibility of generative models with the superior performance of discriminative approaches. Other related issues, such as learning efficiency enhancement and distribution estimation smoothing, are also discussed. Extensive experimental results show that our proposed method can effectively reduce the calibration effort and exhibit superior performance in terms of localization accuracy and robustness.

High-resolution video is defining a new age of peer-assisted video streaming over the public Internet. Streaming over 1-Mbps videos in a scalable and global manner presents a challenging milestone. In this work, we examine the feasibility of 1-Mbps streaming through a global measurement study. In contrast to previous measurement studies that crawl commercial applications, we conduct fine-grain, controlled experiments on a configurable platform. We developed and deployed FastMesh-SIM, a novel peer-assisted streaming system that leverages proxies, scalable streaming trees and IP multicast to achieve 1-Mbps streaming at a global scale. With the configurability-enabled design, we are allowed to conduct controlled experiments by varying design decisions under a wide range of operating conditions, and measuring in-depth, finegrain metrics at a per-hop, per-segment level. We collected hundreds of hours of streaming traces that broadcast live TV channels to more than 120 peers and 30 proxies, with a global geographic footprint over 8 different countries. Data analysis demonstrates how a set of design decisions collectively overcome the 1-Mbps barrier. The various operational issues we uncovered provide insights to service providers that want to deploy a commercial system at a larger scale and a higher streaming rate. By comparing theory and practice, we also confirm theory-inspired architectural decisions, and show that our system indeed achieves throughputs close to theoretical upper-bound calculated under many ideal assumptions.

The deployment of cognitive radio networks enables efficient spectrum sharing and opportunistic spectrum access. It also presents new challenges to the classical problem of interference management in wireless networks. This paper develops an axiomatic framework for power allocation in cognitive radio networks based on four goals: QoS protection to primary users, opportunism to secondary users, admissibility to secondary users, and autonomous operation by individual users. Two additional goals, licensing and versatility, which are desirable rather than essential, are also presented. A general class of Duo Priority Class Power Control (DPCPC) policies that satisfy such goals is introduced. Through theoretical analysis and simulation, it is shown that a specific interference-aware power-control algorithm reaches such goals.

Energy efficient and stable operation of the DSL broadband access infrastructure has become an essential part of the emerging trend towards green communications. One promising means to obtain energy savings is the use of low power "sleep modes", putting DSL modems to sleep when they are not used. Executing the optimal sleeping policies is, however, not straightforward since turning the modem ON and OFF consumes both energy and time, and it also impacts the stability of the DSL network. We present an analytic framework providing optimal sleeping policies that achieve a Pareto-optimal tradeoff between energy consumption and delay performance. Furthermore, we present mechanisms achieving stable sleep mode operation that improve overall stability of DSL systems. Using a realistic DSL simulator, we demonstrate the three-way tradeoff between energy consumption, delay performance and stability.

Charging different prices for Internet access at different times induces users to spread out their bandwidth consumption across times of the day. Potential impact on ISP revenue, congestion management, and consumer behavior can be significant, yet some fundamental questions remain: is it feasible to operate time dependent pricing and how much benefit can it bring? We develop an efficient way to compute the cost-minimizing time-dependent prices for an Internet service provider (ISP), using both a static session-level model and a dynamic session model with stochastic arrivals. A key step is choosing the representation of the optimization problem so that the resulting formulations remain computationally tractable for large-scale problems. We next show simulations illustrating the use and limitation of time-dependent pricing. These results demonstrate that optimal prices, which "reward'' users for deferring their sessions, roughly correlate with demand in each period, and that changing prices based on real-time traffic estimates may significantly reduce ISP cost. The degree to which traffic is evened out over times of the day depends on the time-sensitivity of sessions, cost structure of the ISP, and amount of traffic not subject to time-dependent prices. Finally, we present our system integration and implementation, called TUBE, and proof-of-concept experimentation.

By `optimal CSMA' we denote a promising approach to maximize throughput-based utility in wireless networks without message passing or synchronization among nodes. Despite the theoretical guarantees on the performance of these protocols, their evaluation in real networking scenarios has been preliminary. In this paper, we propose a methodical approach for the first comprehensive evaluation of optimal CSMA, via experimentation with a custom implementation. Example findings include; 1) hidden terminals with symmetric channels can drive the protocol to a state of extreme contention aggressiveness due to the low service received by flows. Since increasing aggressiveness does not mitigate collisions but actually aggravates them, optimal CSMA enters a positive-feedback loop eventually reaching a deadlock state of total flow starvation; 2) however, the use of RTS/CTS in such scenarios can reduce collisions to lower levels, restoring throughput and preventing an excessive contention aggressiveness by optimal CSMA flows; 3) in practical hidden terminal scenarios with physical layer capture optimal CSMA reduces the aggressiveness of dominant flows, but the contention window sizes used by such adaptation mechanism are not long enough to solve competing flows' starvation when carrier sensing fails; 4) topologies with a “flow-in-the-middle” yield starvation in traditional CSMA but fairness in optimal CSMA, because its contention aggressiveness adaptation creates frequent transmission opportunities for the central (otherwise starved) flow; 5) optimal CSMA excessively prioritizes links with low channel quality, due to queue-based control that does not otherwise incorporate channel conditions; 6) in its current design, optimal CSMA conflicts with window-based end-to-end congestion control, and leads to a efficiency-fairness tradeoff in TCP performance. This study deepens our understanding of optimal CSMA and the general adaptation philosophy behind its design, and the derived insights suggest enhancements to optimal CSMA theory.

In this paper, we study the revenue sharing and rate allocation for Internet Service Providers (ISPs) that jointly provide network connectivity between content providers and end-users. Without colluding, each ISP may selfishly set a high transit-price to cover its cost and maximize its own profit, which inevitably results in a loss in social profit. We model this noncooperative interaction between an “eyeball” ISP and a “content” ISP as a Stackelberg game and quantify the resulting loss in social profit. To recover the profit loss, we propose a revenue sharing contract between ISPs by modeling them as a supply chain to deliver traffic in a two-sided market. Parameterized by the profit division factor, the sharing contract coordinates ISPs' objectives such that they aim to maximize the social profit self-incentively. We further propose a Nash bargaining process to determine the profit division factor such that all ISPs are simultaneously better off compared to the noncooperative equilibrium.

Market-based mechanisms offer promising approaches for spectrum access in cognitive radio networks. In this paper, we focus on two market models, one with a monopoly primary user (PU) market and the other with a multiple PU market, where each PU sells its temporarily unused spectrum to secondary users (SUs). We propose a pricing-based spectrum trading mechanism that enables SUs to contend for channel usage by random access, in a distributed manner, which naturally mitigates the complexity and time overhead associated with centralized scheduling. For the monopoly PU market model, we first consider SUs contending via slotted Aloha. The revenue maximization problems here are nonconvex. We first characterize the Pareto optimal region, and then obtain a Pareto optimal solution that maximizes the SUs' throughput subject to the SUs' budget constraints. To mitigate the spectrum underutilization due to the “price of contention,” we revisit the problem where SUs contend via CSMA, and show that spectrum utilization is enhanced, resulting in higher revenue. When the PU's unused spectrum is a control parameter, we study further the tradeoff between the PU's utility and its revenue. For the multiple PU market model, we cast the competition among PUs as a three-stage Stackelberg game, where each SU selects a PU's channel to maximize its throughput. We characterize the Nash equilibria, in terms of access prices and the spectrum offered to SUs. Our findings reveal that the number of equilibria exhibits a phase transition phenomenon, in the sense that when the number of PUs is greater than a threshold, there exist infinitely many equilibria; otherwise, there exists a unique Nash equilibrium, where the access prices and spectrum opportunities are determined by the budgets/elasticity of SUs and the utility level of PUs.

In this paper, frequency-domain relay processing in a two-hop transmission system is investigated. The relay is constrained to be "non-regenerative"; that is, the relay is only allowed to perform a symbol-by-symbol memoryless transformation of its received signals. Multicarrier modulation, e.g., orthogonal frequency division multiplexing (OFDM), is utilized to convert each hop into a collection of non-interfering parallel subcarriers. In contrast to conventional scalar amplify-and-forward (AF) relays that scale all the subcarriers uniformly, it is possible to suppress relay noise and to exploit frequency-domain diversity by optimizing the relay scaling coefficients of different subcarriers jointly with subcarrier power allocation at the source transmitter. This type of scheme is denoted by multicarrier amplify-and-forward (MCAF). Although the end-to-end achievable rate of MCAF is a non-concave function of the power allocation vectors, its optimization is accomplished with an algorithm (O-MCAF) whose computational complexity grows only quadratically with the number of subcarriers, by utilizing a structural property of the problem. Further motivated by the problem structure, a suboptimal algorithm (WF-MCAF) with a linear complexity is also proposed, in which each hop performs waterfilling separately over a selected subset of subcarriers. For hops with a frequency-flat channel response, the maximum achievable rate is explicitly derived from the associated optimization. For hops with Rayleigh fading frequency-domain channel responses, numerical results are presented and it is illustrated that the proposed low-complexity WF-MCAF algorithm usually achieves near-optimal performance.

Peer-to-peer (P2P) systems provide a scalable way to stream content to multiple receivers over the Internet. The maximum rate achievable by all receivers is the capacity of a P2P streaming session. We provide a taxonomy of sixteen problem formulations, depending on whether there is a single P2P session or there are multiple concurrent sessions, whether the given topology is a full mesh graph or an arbitrary graph, whether the number of peers a node can have is bounded or not, and whether there are nonreceiver relay nodes or not. In each formulation, computing P2P streaming capacity requires the computation of an optimal set of multicast trees, with an exponential complexity, except in three simplest formulations that have been recently solved with polynomial time algorithms. These solutions, however, do not extend to the other more general formulations. In this paper, we develop a family of constructive, polynomial-time algorithms that can compute P2P streaming capacity and the associated multicast trees, arbitrarily accurately for seven formulations, to a factor of 4-approximation for two formulations, and to a factor of log of the number of receivers for two formulations. The optimization problem is reformulated in each case so as to convert the combinatorial problem into a linear program with an exponential number of variables. The linear program is then solved using a primal-dual approach. The algorithms combine an outer loop of primal-dual update with an inner loop of smallest price tree construction, driven by the update of dual variables in the outer loop. We show that when the construction of smallest price tree can be carried out arbitrarily accurately in polynomial time, so can the computation of P2P streaming capacity. We also develop several efficient algorithms for smallest price tree construction. Using the developed algorithms, we investigate the impact of several factors on P2P streaming capacity using topologies derived from statistics of uplink capacities of Internet hosts.

Network utility maximization has been widely used to model resource allocation and network architectures. However, in practice, often it cannot be solved optimally due to complexity reasons. Thus motivated, we address the following two questions in this paper: 1) Can suboptimal utility maximization maintain queue stability? 2) Can underoptimization of utility objective function in fact benefit other network design objectives? We quantify the following intuition: A resource allocation that is suboptimal with respect to a utility maximization formulation maintains maximum flow-level stability when the utility gap is sufficiently small and information delay is bounded, and it can still provide a guaranteed size of stability region otherwise. Utility-suboptimal rate allocation can also enhance other network performance metrics, e.g., it may reduce link saturation. These results provide a theoretical support for turning attention from optimal but complex solutions of network optimization to those that are simple even though suboptimal.

This paper settles an open question with a positive answer: Optimal traffic engineering (or optimal multicommodity flow) can be realized using just link-state routing protocols with hop-by-hop forwarding. Today's typical versions of these protocols, Open Shortest Path First (OSPF) and Intermediate System-Intermediate System (IS-IS), split traffic evenly over shortest paths based on link weights. However, optimizing the link weights for OSPF/IS-IS to the offered traffic is a well-known NP-hard problem, and even the best setting of the weights can deviate significantly from an optimal distribution of the traffic. In this paper, we propose a new link-state routing protocol, PEFT, that splits traffic over multiple paths with an exponential penalty on longer paths. Unlike its predecessor, DEFT, our new protocol provably achieves optimal traffic engineering while retaining the simplicity of hop-by-hop forwarding. The new protocol also leads to a significant reduction in the time needed to compute the best link weights. Both the protocol and the computational methods are developed in a conceptual framework, called Network Entropy Maximization, that is used to identify the traffic distributions that are not only optimal, but also realizable by link-state routing.

This paper studies the problem of energy conservation of mobile terminals in a multi-cell TDMA network supporting real-time sessions. The corresponding optimization problem involves joint scheduling, rate control, and power control, which is often highly complex to solve. To reduce the solution complexity, we decompose the overall problem into two sub-problems: intra-cell energy optimization and inter-cell interference control. The solution of the two subproblems results in a "win-win" situation: both the energy consumptions and inter-cell interference are reduced simultaneously. We simulate our decomposition method with the typical parameters in WiMAX system, and the simulation results show that our decomposition method can achieve an energy reduction of more than 70% compared with the simplistic maximum transmit power policy. Furthermore, the inter-cell interference power can be reduced by more than 35% compared with the maximum transmit power policy. We find that the interference power stays largely constant throughout a TDMA frame in our decomposition method. Based on this premise, we derive an interesting decoupling property: if the idle power consumption of terminals is no less than their circuit power consumption, or when both are negligible, then the energy-optimal transmission rates of the users are independent of the inter-cell interference power.

In the use of a wearable GPS and cellular tracker for applications such as elderly tracking, device power consumption is an important consideration. To save power, assisted GPS (AGPS) location fixes should not be performed frequently. On the other hand, we also do not want to lose important information about the user's mobility patterns and routines. To solve this dilemma, in this paper, we present the design of a system that intelligently schedules on-line AGPS location fixes only when necessary based on information extracted from user's historical mobility data, and then reconstruct the user path based on these sparsely taken on-line location fixes. Experimental results show that our on-line algorithm can significantly reduce the number of AGPS fixes needed and the reconstruction method works well without a priori knowledge of a map and streets information.

We consider a distributed power control algorithm for infrastructureless ad hoc wireless networks, where each link distributively and asynchronously updates its transmission power with limited message passing among links. This algorithm provably converges to the set of global optimal solutions despite the non-convexity of the power control problem. In contrast with existing distributed power control algorithms, our algorithm makes no stringent assumptions on the system utility functions. In particular, the utility function is allowed to be concave or non-concave, differentiable or non-differentiable, continuous or discontinuous, and monotonic or non-monotonic.

Although peer-to-peer (P2P) streaming can efficiently deliver live video content to large user populations, existing applications often suffer from limited video quality, periodic hiccups, and high delays. To overcome some of the limitations of today's unstructured (mesh-based) designs, we have developed and deployed FastMesh-SIM, a novel P2P streaming system that leverages proxies, push-mechanism and IP multicast to achieve lower playback delay and better stream continuity. Having control over a real P2P streaming system also gives us a rare opportunity to conduct controlled experiments where we vary major design parameters (e.g., push vs. pull delivery, IP multicast support, streaming rate, and video segment size) under a range of operating conditions (e.g., dynamics of peer churn, and different network configurations), while collecting detailed, fine-granular measurements (e.g., the various components of end-to-end delay). Analysis of the measurement data, consisting of seven trials of streaming several live TV channels for more than 100 hours to 140 peers, sheds light on how design decisions and the operating environment affect important performance metrics. Our experiments show that a push-based, proxy-P2P system can achieve low delay and good video quality, though network bottlenecks on long-haul connections can sometimes cause disruptions in a global deployment. Theory-practice gaps observed from the data are also discussed. Large-scale, global experiments are now being carried out.

Two of the fundamental problems in peer-to-peer (P2P) streaming are as follows: what is the maximum streaming rate that can be sustained for all receivers, and what peering algorithms can achieve close to this maximum? These problems of computing and approaching the P2P streaming capacity are often challenging because of the constraints imposed on overlay topology. In this paper, we focus on the limit of P2P streaming rate under node degree bound, i.e., the number of connections a node can maintain is upper bounded. We first show that the streaming capacity problem under node degree bound is NP Complete in general. Then, for the case of node out-degree bound, through the construction of a “Bubble algorithm”, we show that the streaming capacity is at least half of that of a much less restrictive and previously studied case, where we bound the node degree in each streaming tree but not the degree across all trees. Then, for the case of node total-degree bound, we develop a “Cluster-Tree algorithm” that provides probabilistic guarantee of achieving a rate close to the maximum rate achieved under no degree bound constraint, when the node degree bound is logarithmic in network size. The effectiveness of these algorithms in approaching the capacity limit is demonstrated in simulations using uplink bandwidth statistics of Internet hosts. Both analysis and numerical experiments show that peering in a locally dense and globally sparse manner achieves near-optimal streaming rate if the degree bound is at least logarithmic in network size.

This paper investigates pricing of Internet connectivity services in the context of a monopoly ISP selling broadband access to consumers. We first study the optimal combination of flat-rate and usage-based access price components for maximization of ISP revenue, subject to a capacity constraint on the data-rate demand. Next, we consider time-varying consumer utilities for broadband data rates that can result in uneven demand for data-rate over time. Practical considerations limit the viability of altering prices over time to smoothen out the demanded data-rate. Despite such constraints on pricing, our analysis reveals that the ISP can retain the revenue by setting a low usage fee and dropping packets of consumer demanded data that exceed capacity. Regulatory attention on ISP congestion management discourages such ``technical" practices and promotes economics based approaches. We characterize the loss in ISP revenue from an economics based approach. Regulatory requirements further impose limitations on price discrimination across consumers, and we derive the revenue loss to the ISP from such restrictions. We then develop partial recovery of revenue loss through non-linear pricing that does not explicitly discriminate across consumers. While determination of the access price is ultimately based on additional considerations beyond the scope of this paper, the analysis here can serve as a benchmark to structure access price in broadband access networks.

We present five axioms for fairness measures in resource allocation. A family of fairness measures satisfying the axioms is constructed. Special cases of this family include ¿-fairness, Jain's index, and entropy. Properties of fairness measures satisfying the axioms are proven, including Schur-concavity. Among the engineering implications is a generalized Jain's index that tunes the resolution of fairness measure, a new understanding of ¿-fair utility functions, and an interpretation of "larger ¿ is more fair". We also construct an alternative set of axioms to capture system efficiency and feasibility constraints.

We consider a widely applicable model of resource allocation where two sequences of events are coupled: on a continuous time axis (t), network dynamics evolve over time. On a discrete time axis [t], certain control laws update resource allocation variables according to some proposed algorithm. The algorithmic updates, together with exogenous events out of the algorithm's control, change the network dynamics, which in turn changes the trajectory of the algorithm, thus forming a loop that couples the two sequences of events. In between the algorithmic updates at [t-1] and [t], the network dynamics continue to evolve randomly as influenced by the previous variable settings at time [t-1]. The standard way used to avoid the subsequent analytic difficulty is to assume the separation of timescales, which in turn unrealistically requires either slow network dynamics or high complexity algorithms. In this paper, we develop an approach that does not require separation of timescales. It is based on the use of stochastic approximation algorithms with continuous-time controlled Markov noise. We prove convergence of these algorithms without assuming timescale separation. This approach is applied to develop simple algorithms that solve the problem of utility-optimal random access in multi-channel, multi-radio wireless networks.

Two questions on the theory of content distribution capacity are addressed in this paper: What is the worst user delay performance bound in a chunk-based P2P streaming systems under peer fanout degree constraint? Can we achieve both the minimum delay and the maximum streaming rate simultaneously? In the homogeneous user scenario, we propose a tree-based algorithm called Inverse Waterfilling, which schedules the chunk transmission following an optimal transmitting structure, under fanout degree bound. We show that the algorithm guarantees the delay bound for each chunk of the stream and maintains the maximum streaming rate at the same time.

Usage-based pricing has been recognized as a network congestion management tool. Internet Service Providers (ISPs), however, have limited ability to set time-adaptive usage-price to manage congestion arising from time-varying consumer utility for data. To achieve the maximum revenue, ISP can set its time-invariant usage-price low enough to aggressively encourage consumer's traffic demand. The downside is that ISP has to drop consumer's excessive traffic demand through congestion management (i.e., packet dropping), which may degrade Quality of Service (QoS) of consumer's traffic. Alternatively, to protect consumer's QoS, ISP can set its time-invariant usage-price high enough to reduce consumer's traffic demand, thus minimizing the need for congestion management through packet dropping. The downside is that ISP suffers a revenue loss due to the inefficient usage of its network. The tradeoff between ISP's revenue maximization and consumer's QoS protection motivates us to study ISP's revenue maximization subject to QoS constraint in terms of the number of packets dropped. We investigate two different QoS measures: short-term per-slot packet dropping constraint and long-term packet dropping constraint. The short-term constraint can be interpreted as a more transparent congestion management practice compared to the long-term constraint. We analyze ISP's optimal time-invariant pricing for both constraints, and develop an upper bound for the optimal revenue by considering the specified packet dropping threshold. We quantify the impact of consumer's price elasticity on ISP's optimal revenue and show that ISP should carry out a differentiated QoS protection strategy based on consumer's price elasticity in order to mitigate the revenue loss1.

Providing real-time multimedia services over a besteffort network is challenging due to the stringent delay requirements in the presence of complex network dynamics. Multiple description (MD) coding is one approach to transmit the media over diverse (multiple) paths to reduce the detrimental effects caused by path failures or delay. The novelty of this work is to investigate the resource allocation in a network, where there are several competing MD coded streams. This is done by considering a framework that chooses the operating points for asymmetric MD coding to maximize total quality of the users, while these streams are sent over multiple routing paths. The framework is based on the theoretical modeling where we consider two descriptions and high source coding rate region approximated within small constants. We study the joint optimization of multimedia (source) coding and congestion control in wired networks. These ideas are extended to joint source coding and channel coding in wireless networks. In both situations, we propose distributed algorithms for optimal resource allocation. In the presence of path loss and competing users, the service quality to any particular MD stream could be uncertain. In such circumstances it might be tempting to expect that we need greater redundancy in the MD streams to protect against such failures. However, one surprising aspect of our study reveals that for large number of users who compete for the same resources, the overall system could benefit through opportunistic (hierarchical) strategies. In general networks, our studies indicate that the user composition varies from conservative to opportunistic operating points, depending on the number of users and their network vantage points.

This paper introduces a new model, the octopus model, for studying small-world networks. The model is proposed for general measure-metric spaces and parametrizes the generation of complex networks in terms of the distribution of long-range connections per node. This model allows for the generation of a wide spectrum of complex networks including the ones possessing the clustering features of the Watts-Strogatz model and those possessing the scale-free features of the Barabási model. Analytical expressions for the average message delivery time in small-world networks as a function of source-target separation are derived. These analytical formulas show that nodes tend to communicate with one another only through their short-range contacts, and the average message delivery time rises linearly when the separation between source and target is small. On the other hand, as this separation increases, long-range connections are more commonly used, and the average message delivery time rapidly saturates to a constant value and stays almost the same for large values of the separation. These results are consistent with previous experimental observations made by Travers and Milgram in 1969, as well as by others. Other somewhat surprising conclusions of the paper are that hubs have a limited effect in reducing the average message delivery time and that the variance of connectivity in small-world networks adversely affects this time.

When heterogeneous congestion control protocols that react to different pricing signals share the same network, the current theory based on utility maximization fails to predict the network behavior. The pricing signals can be different types of signals such as packet loss, queueing delay, etc, or different values of the same type of signal such as different ECN marking values based on the same actual link congestion level. Unlike in a homogeneous network, the bandwidth allocation now depends on router parameters and flow arrival patterns. It can be non-unique, suboptimal and unstable. InTang(“Equilibrium of heterogeneous congestion control: Existence and uniqueness,”IEEE/ACM Trans. Netw., vol. 15, no. 4, pp. 824–837, Aug. 2007), existence and uniqueness of equilibrium of heterogeneous protocols are investigated. This paper extends the study with two objectives: analyzing the optimality and stability of such networks and designing control schemes to improve those properties. First, we demonstrate the intricate behavior of a heterogeneous network through simulations and present a framework to help understand its equilibrium properties. Second, we propose a simple source-based algorithm to decouple bandwidth allocation from router parameters and flow arrival patterns by only updating a linear parameter in the sources' algorithms on a slow timescale. It steers a network to the unique optimal equilibrium. The scheme can be deployed incrementally as the existing protocol needs no change and only new protocols need to adopt the slow timescale adaptation.

Abstract It has been recently suggested by Jiang and Walrand that adaptive carrier sense multiple access (CSMA) can achieve optimal utility without any message passing in wireless networks. In this paper, after a survey of recent work on random access, a generalization of this algorithm is considered. In the continuous‐time model, a proof is presented of the convergence of these adaptive CSMA algorithms to be arbitrarily close to utility optimality, without assuming that the network dynamics converge to an equilibrium in between consecutive CSMA parameter updates. In the more realistic, slotted‐time model, the impact of collisions on the utility achieved is characterized, and the tradeoff between optimality and short‐term fairness is quantified. Copyright © 2009 John Wiley & Sons, Ltd.

It has been recently suggested by Jiang andWalrand that adaptive carrier sense multiple access (CSMA) can achieve optimal utility without any message passing in wireless networks. In this paper, a generalization of this algorithm is considered. In the continuous-time model, a proof is presented of t

The Peer-to-Peer (P2P) streaming has shown as an effective solution for wireline video applications, while for the wireless video streaming applications, the limited radio resource and battery energy are the main constraints on the way of P2P applications. An important issue in live video streaming quality of service is to avoid playback buffer underflow, and a challenge from wireless applications is the desire of energy efficiency. The problem we try to solve is how to utilize P2P schemes in video streaming and schedule the video transmission among peers to minimize the "freeze-ups" in playback caused by buffer underflow. In this work, we propose energy-efficient algorithm for the video transmission scheduling in wireless P2P live streaming system, to minimize the playback freeze-ups among peers. Further the algorithm is extended to two scenarios: peers' reluctance of consuming battery energy and allowing overhearing, with alternative energy-efficient algorithms proposed for the second scenario. Numerical results show the effectiveness of the proposed algorithms. The results also demonstrate that peers' selfishness may reduce the energy efficiency, but allowing overhearing could increase energy efficiency.

With the advances in wireless technology and explosive growth of mobile devices and wireless networks, mobile TV is becoming a popular application. The main technical challenge to wireless video broadcast is to provide the best quality of service possible under the radio resource constraints. In this paper we propose an application layer middleware solution that utilizes the scalability in video coding with rateless erasure correction codes to achieve a balance in the quality of service (QoS) and radio resource efficiency. Simulation results demonstrate the effectiveness of the solution.

Several proposals on P2P-ISP cooperation have recently been developed using information sharing for locality-based peering. Their benefits in terms of P2P efficiency, ISP cost, and traffic localization have been demonstrated in the single ISP case. However, potential risks associated with such cooperation have not been well examined. This paper develops a taxonomy and a mathematical model to explore the unintended and counter-intuitive behaviors emerging out of these cooperations in the multiple ISP case. Through both numerical examples and analytical results, we illustrate how such behaviors may become damaging to both P2P providers and ISPs, and how they might be mitigated so that the full benefit of cooperation can be maintained.

Secure communications in wireless ad hoc networks require setting up end-to-end secret keys for communicating node pairs. Due to physical limitations and scalability requirements, full key-connectivity can not be achieved by key pre-distribution. In this paper, we develop an analytical framework for the on-demand key establishment approach. We propose a novel security metric, called REM resilience vector to quantify the resilience of any key establishment schemes against Revealing, Erasure, and Modification (REM) attacks. Our analysis shows that previous key establishment schemes are vulnerable under REM attacks. Relying on the new security metric, we prove a universal bound on achievable REM resilience vectors for any on-demand key establishment scheme. This bound that characterizes the optimal security performance analytically is shown to be tight, as we propose a REM-resilient key establishment scheme which achieves any vector within this bound. In addition, we develop a class of low complexity key establishment schemes which achieve nearly-optimal REM-attack resilience.

Dynamic spectrum management (DSM) has been recognized as a key technology for tackling multi-user crosstalk interference for DSL broadband access. Up to now, DSM design has mainly been focusing on maximization of data rates. However, recently, reducing the total power has become a main target, as IT power consumption has been identified as a significant contributor to global warming. In this paper we extend traditional DSM design towards a much wider energy-efficient scope and show how to tackle the corresponding optimization problems. The impact of this 'green DSL' approach is evaluated for practice with some surprisingly good numerical results. Furthermore bounds are provided on the trade-off between data rate performance and power saving.

The growth of video content and diversification of content-sharing methods in the Internet lead to an exciting range of new problems in networking, communications, and signal processing. This informal note outlines the opportunities arising out of the ldquocontent-pipe dividerdquo and presents some of the recent work from my research group and collaborators.

Pricing content-providers for connectivity to end- users and setting connection parameters based on the price is an evolving model on the Internet. The implications are heavily debated in telecom policy circles, and some advocates of "Network Neutrality" have opposed price based differentiation in connectivity. However, pricing content providers can possibly subsidize the end-user's cost of connectivity, and the consequent increase in end-user demand can benefit ISPs and content providers. This paper provides a framework to quantify the precise trade-off in the distribution of benefits among ISPs, content-providers, and end-users. The framework generalizes the well-known utility maximization based rate allocation model, which has been extensively studied as an interplay between the ISP and the end-users, to incorporate pricing of content-providers. We derive the resulting equilibrium prices and data rates in two different ISP market conditions: competition and monopoly. Network neutrality based restriction on content-provider pricing is then modeled as a constraint on the maximum price that can be charged to content-providers. We demonstrate that, in addition to gains in total and end- user surplus, content-provider experiences a net surplus from participation in rate allocation under low cost of connectivity. The surplus gains are, however, limited under monopoly conditions in comparison to competition in the ISP market.

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

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

We address the following question in this study: Can a network application detect not only the occurrence, but also the location of congestion? Answering this question will not only help the diagnostic of network failure and monitor server's QoS, but also help developers to engineer transport protocols with more desirable congestion avoidance behavior. The paper answers this question through new analytic results on the two underlying technical difficulties: 1) synchronization effects of loss and delay in TCP, and 2) distributed hypothesis testing using only local loss and delay data. We present a practical Congestion Location Detection (CLD) algorithm that effectively allows an end host to distributively detect whether congestion happens in the local access link or in more remote links. We validate the effectiveness of CLD algorithm with extensive experiments.

Distributed scheduling algorithms for wireless ad hoc networks have received substantial attention over the last decade. The complexity levels of these algorithms span a wide spectrum, ranging from no message passing to constant/polynomial time complexity, or even exponential complexity. However, by and large it remains open to quantify the impact of message passing complexity on throughput and delay. In this paper, we study the effective throughput and delay performance in wireless scheduling by explicitly considering complexity through a vacation model, where signaling complexity is treated as "vacations" and data transmissions as "services," with a focus on delay analysis in heavy traffic regimes. We analyze delay performance in two regimes of vacation models, depending on the relative lengths of data transmission and vacation periods. State space collapse properties proved here enable a significant dimensionality reduction in the challenging problem of delay characterization. We then explore engineering implications and quantify intuitions based on the heavy traffic analysis.

Scheduling algorithms have been extensively studied in wireless network design. We first present a comprehensive taxonomy of this research area, including optimality and robustness issues in the frameworks of Layering as Optimization Decomposition and Stochastic NUM. Then we discuss the stability-delay-complexity tradeoff, as well as delay characterizations, in networks with non-saturated traffic. We conclude with reverse and forward engineering of random access protocols in networks with saturated traffic, including convergence and short-term fairness of utility-optimal CSMA with no message passing.

This paper addresses the following question: how reliable is it to use the unbounded path-loss model G(d) = d-α, where α is the path-loss exponent, to model the decay of transmitted signal power in wireless networks? G(d) is a good approximation for the path-loss in wireless communications for large values of d but is not valid for small values of d due to the singularity at 0. This model is often used along with a random uniform node distribution, even though in a group of uniformly distributed nodes some may be arbitrarily close to one another. The unbounded path-loss model is compared to a more realistic bounded path-loss model, and it is shown that the effect of the singularity on the total network interference level is significant and cannot be disregarded when nodes are uniformly distributed. A phase transition phenomenon occurring in the interference behavior is analyzed in detail. Several performance metrics are also examined by using the computed interference distributions. In particular, the effects of the singularity at 0 on bit error rate, packet success probability and wireless channel capacity are analyzed.

Networks need to accommodate diverse applications with different quality-of-service (QoS) requirements. New ideas at the physical layer are being developed for this purpose, such as diversity embedded coding, which is a technique that combines high rates with high reliability. We address the problem of how to fully utilize different rate-reliability characteristics at the physical layer to support different types of traffic over a network and to jointly maximize their utilities. We set up a new framework based on utility maximization for networks with composite links, meaning that each link consists of sub-links that can attain different rate-reliability characteristics simultaneously. We incorporate delay, in addition to rate and reliability, into the utility functions. To accommodate different types of traffic, we propose distributed algorithms converging to the optimal rate-reliability-delay tradeoff based on capacity division and priority queueing. Numerical results show that compared with traditional codes, the new codes can provide higher network utilities for all traffic types simultaneously. The results also show that priority queueing achieves higher network utility than capacity division.

We consider the problem of scheduling and resource allocation for multiuser video streaming over downlink orthogonal frequency division multiplexing (OFDM) channels. The video streams are precoded using the scalable video coding (SVC) scheme that offers both quality and temporal scalabilities. The OFDM technology provides the flexibility of resource allocation in terms of time, frequency, and power. We propose a gradient-based scheduling and resource allocation algorithm, which prioritizes the transmissions of different users by considering video contents, deadline requirements, and transmission history. Simulation results show that the proposed algorithm outperforms the content-blind and deadline-blind algorithms with a gain of as much as 6 dB in terms of average PSNR when the network is congested.

The flow-level stability and performance of data networks with utility-maximizing allocations are studied in this paper. Similarly to prior works on flow-level models, exogenous data arrivals with finite workloads are considered. However, to model many realistic situations, the rate region, which constrains the feasibility of resource allocation, may be either nonconvex or time-varying. When the rate region is fixed but nonconvex, sufficient and necessary conditions are characterized for stability for a class ofalpha-fair allocation policies, which coincide when the set of allocated rate vectors have continuous contours. When the rate region is time-varying according to a Markovian stationary and ergodic process, the precise stability region is obtained. In both cases, the size of the stability region depends on the resource allocation policy, in particular, on the fairness parameteralphainalpha-fair utility maximization. This is in sharp contrast with the substantial existing literature on stability under fixed and convex rate regions, in which the stability region coincides with the rate region for many utility-based resource allocation schemes, independent of the value of the fairness parameter. It is further shown that for networks which consist of flows from two different classes underalpha-fair allocations, there exists a tradeoff between the stability region and the fairness parameteralpha. Moreover, the impact of this fairness-stability tradeoff on the system performance, e.g., average throughput and mean flow response time, is studied, and numerical experiments that illustrate the new stability region and the performance versus fairness tradeoff are presented.

A model for wireless networks with slotted-Aloha-type random access and with multihop flow routes is considered. The goal is to devise distributed algorithms for utility-optimal end-to-end throughput allocation and queueing stability. A class of queue back-pressure random access algorithms (QBRAs), in which actual queue lengths of the flows in each node's close neighborhood are used to determine the nodes' channel access probabilities, is studied. This is in contrast to some previously proposed algorithms, which are based on deterministic optimization formulations and are oblivious to actual queues. QBRA is also substantially different from the well-studied ldquoMaxWeightrdquo type scheduling algorithms, even though both use the concept of back-pressure. For the model with infinite backlog at each flow source, it is shown that QBRA, combined with simple congestion control local to each source, leads to optimal end-to-end throughput allocation within the network saturation throughput region achievable by random access, without end-to-end message passing. This scheme is generalized to the case with minimum flow rate constraints. For the model with stochastic exogenous arrivals, it is shown that QBRA ensures stability of the queues as long as nominal loads of the nodes are within the saturation throughput region. Simulation comparison of QBRA and the queue oblivious random-access algorithms, shows that QBRA reduces end-to-end delays.

Internet is experiencing a substantial growth of video traffic. Given the limited network bandwidth resources, how to provide Internet users with good video playback quality-of-service (QoS) is a key problem. For video clips competing bandwidth, we propose an approach of Content-Aware distortion-Fair (CAF) video delivery scheme, which is aware of the characteristics of video frames and ensures max-min distortion-fair sharing among video flows. CAF leverages content-awareness to prioritize packet dropping during congestion. Different from bandwidth fair sharing, CAF targets end-to-end video playback quality fairness among users. The proposed CAF approach does not require rate-distortion modeling of the source, which is difficult to estimate. Instead, it exploits the temporal prediction structure of the video sequences along with a frame drop distortion metric to guide resource allocations and coordinations. Experimental results show that the proposed approach operates with limited overhead in computation and communication, and yields better QoS, especially when the network is congested.

In this paper, we propose two distributed contention-based medium access control (MAC) algorithms for solving a network utility maximization (NUM) problem in wireless ad hoc networks. Most of the previous NUM-based random access algorithms have one or more of the following performance bottlenecks: (1) extensive signaling among the nodes to achieve semi-distributed implementations, (2) synchronous updates of contention probabilities, (3) small update stepsizes to ensure convergence but with typically slow speed, and (4) supporting a limited range of utility functions under which the NUM is shown to be convex. Our proposed algorithms overcome the bottlenecks in all four aspects. First, only limited amount of message passing among nodes is required. Second, fully asynchronous updates of contention probabilities are allowed. Furthermore, our algorithms are robust to arbitrary large message passing delay and message loss. Third, we do not utilize any stepsize during updates, thus our algorithms can achieve faster convergence. Finally, our proposed algorithms have provable convergence, optimality, and robustness properties under a wider range of utility functions, even if the NUM problem is non-convex. Simulation results show the optimality and fast convergence of our algorithms, performance improvements compared with the subgradient-based MAC, and better efficiency-fairness tradeoff compared with the IEEE 802.11 distributed coordination function.

Random access has been studied for decades as a simple and practical wireless medium access control (MAC). Some of the recently developed distributed scheduling algorithms for throughput or utility maximization also take the form of random access, although extensive message passing among the nodes is required. In this paper, we would like to answer this question: is it possible to design a MAC algorithm that can achieve the optimal network utility without message passing? We provide the first positive answer to this question through a simple Aloha-type random access protocol. We prove the convergence of our algorithm for certain sufficient conditions on the system parameters, e.g., with a large enough user population. If each wireless node is capable of decoding the source MAC address of the transmitter from the interferring signal, then our algorithm indeed converges to the global optimal solution of the NUM problem. If such decoding is inaccurate, then the algorithm still converges, although optimality may not be always guaranteed. Proof of these surprisingly strong performance properties of our simple random access algorithm leverages the idea from distributed learning: each node can learn as much about the contention environment through the history of collision as through instantaneous but explicit message passing.

Running multiple virtual networks, customized for different performance objectives, is a promising way to support diverse applications over a shared substrate. Despite being simple, a static division of resources between virtual networks can be highly inefficient, while dynamic resource allocation runs the risk of instability. This paper uses optimization theory to show that adaptive resource allocation can be stable and can maximize the aggregate performance across the virtual networks. In the DaVinci architecture, each substrate link periodically reassigns bandwidth shares between its virtual links; while at a smaller timescale, each virtual network runs a distributed protocol that maximizes its own performance objective independently. Numerical experiments with a mix of delay-sensitive and throughput-sensitive traffic show that the bandwidth shares converge quickly to the optimal values. We demonstrate that running several custom protocols in parallel and allocating resource adaptively can be more efficient, more flexible, and easier to manage than a compromise one-size-fits-all design.

Internet is experiencing an explosive growth of video traffic. Given the limited network bandwidth resources, how to provide Internet users with good video playback quality is a key problem. For video clips competing bandwidth, we propose an approach of content-aware distortion-fair (CAF) video delivery scheme, which is assumed to be aware of the characteristics of video frames and ensures max-min distortion fair sharing among video flows. Different from bandwidth fair sharing, CAF targets video playback quality fairness for the reason that users care about video quality rather than bandwidth. The proposed CAF approach does not need an analytical rate-distortion function which is difficult to estimate, but instead, it uses the explicit distortion of every frame which is induced by frame drop. Our CAF approach is fast and practical with content-aware cooperation. Experimental results show that the proposed approach yields better quality of service when the network is congested compared with the approach not rate-distortion optimized, and it makes competing video clips help each other to get fair playback quality.

To provide real-time multimedia services over a network is challenging due to the stringent delay requirements in the presence of complex network dynamics. Yet such services are beginning to be deployed over best effort networks. Multiple description (MD) coding is one approach to transmit the media over diverse (multiple) paths to reduce the detrimental effects caused by path failures or delay. The novelty of this work is to investigate the resource allocation in a network, where there are several competing MD coded streams. This is done by considering a framework that chooses the operating points for asymmetric MD coding to maximize total quality of the users, while these streams are sent over multiple routing paths. We study the joint optimization of multimedia (source) coding and congestion control in wired networks. These ideas are extended to joint source coding and channel coding in wireless networks. In both situations, we propose distributed algorithms for optimal resource allocation. In the presence of path loss and competing users, the service quality to any particular MD stream could be uncertain. In such circumstances it might be tempting to expect that greater redundancy in the MD streams is needed to protect against such failures. However, one surprising aspect of our study reveals that for large number of users competing for the same resources, the overall system could benefit through opportunistic (hierarchical) strategies. In general networks, our studies indicate that the user composition varies from conservative to opportunistic operating points, depending on the number of users and their network vantage points.

In modern DSL networks, crosstalk among different lines (i.e., users) is the major source of performance degradation. Dynamic spectrum management (DSM) refers to a set of techniques to mitigate the effect of crosstalk leading to spectacular performance gains. However the main research efforts in DSM aim at only physical layer performance whereas the true end user experience depends on what they see at the application rather than the physical layer. Upper layer performance metrics like throughput and delay may be much more important to improve the user satisfaction. To that end, we provide a framework to study upper layer performance by looking at scheduling and DSM together. We show how optimal scheduling can be combined with optimal DSM and provide throughput-optimal scheduling algorithms which require only polynomial complexity. We furthermore present extentions that significantly improve delay performance by using the specific structure of the underlying problem.

Resource allocation is considered for cooperative transmissions in multiple-relay wireless networks. Two auction mechanisms, SNR auctions and power auctions, are proposed to distributively coordinate the allocation of power among multiple relays. In the SNR auction, a user chooses the relay with the lowest weighted price. In the power auction, a user may choose to use multiple relays simultaneously, depending on the network topology and the relays' prices. Sufficient conditions for the existence (in both auctions) and uniqueness (in the SNR auction) of the Nash equilibrium are given. The fairness of the SNR auction and efficiency of the power auction are further discussed. It is also proven that users can achieve the unique Nash equilibrium distributively via best response updates in a completely asynchronous manner.

Efficient delivery of multimedia contents over wireless network is essential for future communication networks. However, content distribution and network engineering are traditionally studied separately, which leads to suboptimal network performance. In this paper, we consider the problem of scheduling and resource allocation for multi-user video streaming over downlink OFDM channels. The video streams are preceded with the SVC coding scheme, which offers both quality and temporal scalabilities. The OFDM technology provides the maximum flexibility of resource allocation in terms of time, frequency, and power. We propose a gradient-based scheduling and resource allocation algorithm, which explicitly takes account of video contents, deadline requirements, and the previous transmission results when calculating users' priority weights. Simulation results show that our proposed algorithm always outperforms the content- blind and deadline-blind algorithms, with a performance gain as much as 6 dB in terms of average user PSNR improvement in a congested network.

We develop a family of distributed wireless scheduling algorithms that requires only O(1) complexity for M-hop interference model, for any finite M. The recent technology advances and heterogeneity in wireless networks lead to various interference patterns. Thus, a scheduling algorithm geared into a specific interference model (typically one-hop or two-hop in literature) may be limited in its applicability. In this paper, we tackle this problem, and develop a family of scheduling algorithms (which guarantees throughput and delay performance) for M-hop interference models. To achieve such a goal, we use the concept of vertex augmentation, and for a given M, the family of parameterized algorithms are proposed and the tradeoffs among throughput, complexity, and delay are studied.

For Internet based video broadcasting applications such as IPTV, the peer-to-peer (P2P) streaming scheme has been found to be an effective solution. An important issue in live broadcasting is to avoid playback buffer underflow. How to utilize the playback buffer and upload bandwidth of peers to minimize the freeze-ups in playback, is the problem we try to solve. In this work, we propose a successive water-filling (SWaF) algorithm for the video transmission scheduling in P2P live streaming system, to minimize the playback freeze-ups among peers. SWaF algorithm only needs each peer to optimally transmit (within its uploading bandwidth) part of its available video segments in the buffer to other peers requiring the content and pass small amount message to some other peers. Moreover, SWaF has low complexity and provable optimality. Numerical results demonstrated the effectiveness of the proposed algorithm.

Not too bad. A rate allocation that is suboptimal with respect to a utility maximization formulation still maintains the maximum flow-level stability when the utility gap is sufficiently small, and provides a minimum size of stability region otherwise. Utility-suboptimal allocation may also enhance other network performance metrics, e.g., it may increase network throughput and reduce link saturation. Quantifying these intuitions, this paper provides a theoretical support for turning attention from optimal but complex solutions of network optimization to those that are simple even though suboptimal.

With economic constraints and limited routing capability, the structure of an access network is typically a "fat tree", where the terminal has to relay the traffic from another terminal of the same or higher level. New graph theory problems naturally arise from such features of access network models, different from those targeted towards survivable backbone (mesh) networks. We model the important problem of provisioning survivability to an existing single-level fat tree through two graph theory problem formulations: the Terminal Backup problem and the simplex cover problem, which we show to be equivalent. We then develop two polynomial-time approaches, indirect and direct, for the simplex cover problem. The indirect approach of solving the matching version of simplex cover is convenient in proving polynomial-time solvability though it is prohibitively slow in practice. In contrast, leveraging the special properties of simplex cover itself, we demonstrate that the direct approach can solve the simplex cover problem very efficiently even for large networks. Extensive numerical results of applying our algorithms are also reported for designing survivable access networks over different types of topologies.

Link-state routing with hop-by-hop forwarding is widely used in the Internet today. The current versions of these protocols, like OSPF, split traffic evenly over shortest paths based on link weights. However, optimizing the link weights for OSPF to the offered traffic is an NP-hard problem, and even the best setting of the weights can deviate significantly from an optimal distribution of the traffic. In this paper, we propose a new link-state routing protocol, PEFT, that splits traffic over multiple paths with an exponential penalty on longer paths. Unlike its predecessor, DEFT, our new protocol provably achieves optimal traffic engineering while retaining the simplicity of hop-by-hop forwarding. A gain of 15 % in capacity utilization over OSPF is demonstrated using the Abilene topology and traffic traces. The new protocol also leads to significant reduction in the time needed to compute the best link weights. Both the protocol and the computational methods are developed in a new conceptual framework, called network entropy maximization, which is used to identify the traffic distributions that are not only optimal but also realizable by link-state routing.

Small-world networks are networks in which the graphical diameter of the network is as small as the diameter of random graphs but whose nodes are highly clustered when compared with the ones in a random graph. Examples of small-world networks abound in sociology, biology, neuroscience and physics as well as in human-made networks. This paper analyzes the average delivery time of messages in dense small-world networks constructed on a plane. Iterative equations for the average message delivery time in these networks are provided for the situation in which nodes employ a simple greedy geographic routing algorithm. It is shown that two network nodes communicate with each other only through their short-range contacts, and that the average message delivery time rises linearly if the separation between them is small. On the other hand, if their separation increases, the average message delivery time rapidly saturates to a constant value and stays almost the same for all large values of their separation.

This paper analyzes the asymptotic behavior of a multiple-access network comprising a large number of selfish transmitters competing for access to a common wireless communication channel, and having different utility functions for determining their strategies. A necessary and sufficient condition is given for the total number of packet arrivals from selfish transmitters to converge in distribution. The asymptotic packet arrival distribution at Nash equilibrium is shown to be a mixture of a Poisson distribution and finitely many Bernoulli distributions.

The multi-carrier interference channel where interference is treated as additive white Gaussian noise, is a very active topic of research, particularly important in the area of Dynamic Spectrum Management (DSM) for Digital Subscriber Lines (DSL). Here, multiple users optimize their transmit power spectra so as to maximize the total weighted sum of data rates. The corresponding optimization problem is however nonconvex and thus computationally intractable, i.e. a certificate of global optimality requires exponential time complexity algorithms. This paper shows that under certain channel conditions, this nonconvex problem can be solved in polynomial time with a certificate of global optimality. The channel conditions are discussed consisting of different interference models including synchronous and asynchronous DSL transmission. Simulations demonstrate its applicability to realistic DSL scenarios.

It has been an important research topic since 1992 to maximize stability region in constrained queueing systems, which includes the study of scheduling over wireless ad hoc networks. In this paper, we propose a framework to study a wide range of existing and future scheduling algorithms and characterize the achieved tradeoffs in stability, delay, and complexity. These characterizations reveal interesting properties hidden in the study of any one or two dimensions in isolation. For example, decreasing complexity from exponential to polynomial, while keeping stability region the same, generally comes at the expense of exponential growth of delays. Investigating trade-offs in the 3-dimensional space allows a designer to fix one dimension and vary the other two jointly. For example, incentives for using scheduling algorithms with only partial throughput-guarantee can be quantified with regards to delay and complexity. Trade-off analysis is then extended to systems with congestion control through utility maximization for non-stabilizable arrival inputs, where the complexity-utility-delay trade-off is shown to be different from the complexity-stability-delay tradeoff. Finally, we analyze more practical models with bounded message size, and consider "effective throughput" which reflects resource occupied by control messages. We show that effective throughput may degrade significantly in certain scheduling algorithms, and suggest a mechanism to avoid this problem in light of the 3D tradeoff framework.

Peer-assisted streaming is a promising way for service providers to offer high-quality IPTV to consumers at reasonable cost. In peer-assisted streaming, the peers exchange video chunks with one another, and receive additional data from the central server as needed. In this paper, we analyze how to provision resources for the streaming system, in terms of the server capacity, the video quality, and the depth of the distribution trees that deliver the content. We derive the performance bounds for minimum server load, maximum streaming rate, and minimum tree depth under different peer selection constraints. Furthermore, we show that our performance bounds are actually tight, by presenting algorithms for constructing trees that achieve our bounds.

Distributed and efficient resource allocation is critical for fully realizing the benefits of cooperative communications in large scale communication networks. This paper proposes two auction mechanisms, the SNR auction and the power auction, that determine relay selection and relay power allocation in a distributed fashion. A single-relay network is considered first, and the existence and uniqueness of the Nash Equilibrium (i.e., the auction's outcome) are proved. It is shown that the power auction achieves the efficient allocation by maximizing the total rate increase, and the SNR auction is flexible in trading off fairness and efficiency. For both auctions, the distributed best response bid updates globally converge to the unique Nash Equilibrium in a completely asynchronous manner. The analysis is then generalized to networks with multiple relays, and the existence of the Nash Equilibrium is shown under appropriate conditions. Simulation results verify the effectiveness and robustness of the proposed algorithms.

Service availability is one of the most closely scrutinized metrics in offering network services. It is important to cost- effectively provision a managed and differentiated network with various service availability guarantees under a unified platform. In particular, demands for availability may be elastic and such elasticity can be leveraged to improve cost-effectiveness. In this paper, we establish the framework of provisioning elastic service availability through network utility maximization, and propose an optimal and distributed solution using differentiated failure recovery schemes. First, we develop a utility function with configurable parameters to represent the satisfaction perceived by a user upon service availability as well as its allowed source rate. Second, adopting Quality of Protection [1] and shared path protection, we transform optimal provisioning of elastic service availability into a convex optimization problem. The desirable service availability and source rate for each user can be achieved using a price-based distributed algorithm. Finally, we numerically show the tradeoff between the throughput and the service availability obtained by users in various network topologies. This investigation quantifies several engineering implications. For example, indiscriminately provisioning service availabilities for different kinds of users within one network leads to noteworthy sub-optimality in total network utility. The profile of bandwidth usage also illustrates that provisioning high service availability exclusively for critical applications leads to significant waste in bandwidth resource.

Multi-user video streaming over wireless channels is a challenging problem, where the demand for better video quality and small transmission delays needs to be reconciled with the limited and often time-varying communication resources. This paper presents a framework for joint network optimization, source adaptation, and deadline-driven scheduling for multi-user video streaming over wireless networks. We develop a joint adaptation, resource allocation and scheduling (JARS) algorithm, which allocates the communication resource based on the video users' quality of service, adapts video sources based on smart summarization, and schedules the transmissions to meet the frame delivery deadlines. The proposed algorithm leads to near full utilization of the network resources and satisfies the delivery deadlines for all video frames. Substantial performance improvements are achieved compared with heuristic schemes that do not take the interactions between multiple users into consideration.

The implementation of distributed network utility maximization (NUM) algorithms hinges heavily on information feedback through message passing among network elements. In practical systems the feedback is often obtained using error-prone measurement mechanisms and suffers from random errors. In this paper, we investigate the impact of noisy feedback on distributed NUM. We first study the distributed NUM algorithms based on the Lagrangian dual method, and focus on the primal-dual (P-D) algorithm, which is a single time-scale algorithm in the sense that the primal and dual parameters are updated simultaneously. Assuming strong duality, we study both cases when the stochastic gradients are unbiased or biased, and develop a general theory on the stochastic stability of the P-D algorithms in the presence of noisy feedback. When the gradient estimators are unbiased, we establish, via a combination of tools in Martingale theory and convex analysis, that the iterates generated by distributed P-D algorithms converge with probability one to the optimal point, under standard technical conditions. In contrast, when the gradient estimators are biased, we show that the iterates converge to a contraction region around the optimal point, provided that the biased terms are asymptotically bounded by a scaled version of the true gradients. We also investigate the rate of convergence for the unbiased case, and find that, in general, the limit process of the interpolated process corresponding to the normalized iterate sequence is a stationary reflected linear diffusion process, not necessarily a Gaussian diffusion process. We apply the above general theory to investigate stability of cross-layer rate control for joint congestion control and random access. Next, we study the impact of noisy feedback on distributed two time-scale NUM algorithms based on primal decomposition. We establish, via the mean ODE method, the convergence of the stochastic two time-scale algorithm under mild conditions, for the cases where the gradient estimators in both time scales are unbiased. Numerical examples are used to illustrate the finding that compared to the single time-scale counterpart, the two time-scale algorithm, although having lower complexity, is less robust to noisy feedback.

In the Internet today, traffic management spans congestion control (at end hosts), routing protocols (on routers), and traffic engineering (by network operators). Historically, this division of functionality evolved organically. In this paper, we perform a top-down redesign of traffic management using recent innovations in optimization theory. First, we propose an objective function that captures the goals of end users and network operators. Using all known optimization decomposition techniques, we generate four distributed algorithms that divide traffic over multiple paths based on feedback from the network links. Combining the best features of the algorithms, we construct TRUMP: a traffic management protocol that is distributed, adaptive, robust, flexible and easy to manage. Further, TRUMP can operate based on implicit feedback about packet loss and delay. We show that using optimization decompositions as a foundation, simulations as a building block, and human intuition as a guide can be a principled approach to protocol design.

In lightweight mobile ad hoc networks, both probabilistic and deterministic key management schemes are fragile to node fabrication attacks. Our simulation results show that the Successful Attack Probability (SAP) can be as high as 42.6% with the fabrication of only 6 copies from captured nodes comprising only 3% of all nodes. In this paper, we propose two low-cost secure-architecture-based techniques to improve the security against such node fabrication attacks. Our new architectures, specifically targeted at the sensor-node platform, protect long-term keys using a root of trust embedded in the hardware System-on-a-Chip (SoC). This prevents an adversary from extracting these protected long-term keys from a captured node to fabricate new nodes. The extensive simulation results show that the proposed architecture can significantly decrease the SAP and increase the security level of key management for mobile ad hoc networks.

Cooperative transmission can greatly improve communication system performance by taking advantage of the broadcast nature of wireless channels. Most previous work on resource allocation for cooperation transmission is based on centralized control. In this paper, we propose two share auction mechanisms, the SNR auction and the power auction, to distributively coordinate the resource allocation among users. We prove the existence, uniqueness and effectiveness of the auction results. In particular, the SNR auction leads to a fair resource allocation among users, and the power auction achieves a solution that is close to the efficient allocation.

We study the congestion control in a network where the users may have different types of traffic, such as the traffic with fixed/variable rate, delay sensitive/insensitive, etc. To reflect the different requirements on delay by different applications, explicit terms of delay are added to the utility function. We analyze the essential dynamics for the network utility maximization (NUM) with the new utility functions. Compared with the basic NUM where the utility function is only a function of rate, the dynamics for link price is now related to the delay term added in the utility function. The analysis is applied to the system with voice and data traffic, and distributed algorithms are proposed to allocate the resource such that the utility of voice and data is jointly optimized. The numerical results show that by the new price dynamics, we can accomplish optimal congestion control for users with delay sensitive/insensitive traffic in a network. In particular, in a network with data and voice traffic with priority queueing, the algorithm can lead the network to achieve higher quality of voice traffic and higher throughput of data traffic, with the sacrifice of the packet delay of data traffic.

This is an overview of the ongoing FAST Copper project, which is aimed at substantial improvements in rate, reach, reliability, and quality in copper-last-mile broadband access through fiber/DSL deployment, engineering innovations, and fundamental research. The project is funded by NSF, and is currently pursued jointly by Princeton University, Stanford University, and Fraser Research Lab. In this article, we outline the motivations, challenges, and research issues associated with the project, and report some of the recent results by the Princeton team in each of the four dimensions: frequency, amplitude, space, and time.

Recent advances in network coding have shown great potential for efficient information multicasting in communication networks, in terms of both network throughput and network management. In this paper, we address the problem of rate control at end-systems for network coding based multicast flows. We develop two adaptive rate control algorithms for the networks with given coding subgraphs and without given coding subgraphs, respectively. With random network coding, both algorithms can be implemented in a distributed manner, and work at transport layer to adjust source rates and at network layer to carry out network coding. We prove that the proposed algorithms converge to the globally optimal solutions for intra-session network coding. Some related issues are discussed, and numerical examples are provided to complement our theoretical analysis.

Most previous work in statistical multiplexing only considered the case where the link transmission rates are fixed. In this paper, we consider statistical multiplexing in networks with adaptive transmission rates, with focus on DSL broadband access networks. This requires a jointly optimized allocation of buffer space and transmission bandwidth to traffic flows, which takes the flow traffic characteristics, the user QoS requirements, and the user interactions at the physical layer into consideration. Using the effective bandwidth concept, we propose a class of alternate maximization (AM) algorithms (AM-D and AM-M), which solve the statistical multiplexing problem for both delay insensitive data traffic and delay sensitive multimedia traffic. With low complexity as a design goal, the AM algorithms incorporate our recently proposed autonomous spectrum balancing (ASB) algorithm, which was originally designed for DSL physical layer spectrum management. Our numerical results show that the AM algorithms combines the gain due to statistical multiplexing and that due to spectrum management.

Networks need to accommodate diverse applications with different quality-of-service (QoS) requirements. New ideas at the physical layer are being developed for this purpose, such as diversity embedded coding, which is a technique that combines high rates with high reliability. We address the problem of how to fully utilize different rate-reliability characteristics at the physical layer to support different types of traffic over a network and to jointly maximize their utilities. We set up a new framework based on utility maximization for networks with composite links, meaning that each link consists of sub-links that can attain different rate-reliability characteristics simultaneously. We incorporate delay, in addition to rate and reliability, into the utility functions. To accommodate different types of traffic, we propose distributed algorithms for the optimal rate-reliability-delay tradeoff based on capacity division and priority queueing. Numerical results show that compared with traditional codes, the new codes can provide higher network utilities for all traffic types simultaneously. The results also show that priority queueing achieves higher network utility than capacity division.

A systematic approach to solve seemingly nonconvex resource allocation problems in wireless cellular networks is studied in this paper. By revealing and exploiting the hidden convexity in the problem formulations, we obtain solutions that can tackle a variety of objective functions, provide robustness to resource allocations such as power, and be obtained often through distributed algorithms. The advantages of such flexibility and robustness are demonstrated through comparisons with the state-of-the-art in recent research literature. First we show how to distributively solve a variety of resource allocation problems in CDMA and interference limited CDMA channels with quality of service constraints, such as meeting minimum queueing delay or energy per bit requirement. Then, for uplink transmission in a CDMA cellular network, we propose an optimal power control scheme with congestion-aware active link protection. In particular, the tradeoff between power expenditure and the protection margin of the SIR-balancing power algorithm is optimized.

Network operators control the flow of traffic through their networks by adapting the configuration of the underlying routing protocols. For example, they tune the integer link weights that interior gateway protocols like OSPF and ISIS use to compute shortest paths. The resulting optimization problem -to find the best link weights for a given topology and traffic matrix -is computationally intractable even for the simplest objective functions, forcing the use of local-search techniques. The optimization problem is difficult in part because these protocols split traffic evenly along shortest paths, with no ability to adjust the splitting percentages or direct traffic on other paths. In this paper, we propose an extension to these protocols, called Distributed Exponentially-weighted Flow SpliTting (DEFT), where the routers can direct traffic on non-shortest paths, with an exponential penalty on longer paths. DEFT leads not only to an easier-to-solve optimization problem, but also to weight settings that provably perform no worse than OSPF and IS-IS. Furthermore, in our optimization problem, both link weights and flows of traffic are integrated as optimization variables into the formulation and jointly solved by a two-stage iterative method. Our novel formulation leads to a much more efficient way to identify good link weights than the local-search heuristics used for OSPF and IS-IS today. DEFT retains the simplicity of having routers compute paths based on configurable link weights, while approaching the performance of more complex routing protocols that can split traffic arbitrarily over any paths.

Service availability is one of the most closely scrutinized metrics in offering network services. The network vendor can earn more revenue from the customers by guaranteeing higher service availability at the cost of higher operational expense. It is important to cost-effectively provision a managed and differentiated network with various service availability guarantees under a unified platform. In this paper, we establish the framework of provisioning elastic service availability through network utility maximization, and propose an optimal and distributed solution using differentiated failure recovery schemes. First, we develop a utility function with configurable parameters to represent the satisfaction perceived by a user upon service availability as well as its allowed source rate. Second, adopting quality of protection [1] and shared path protection, we transform optimal provisioning of elastic service availability into a convex optimization problem. The desirable service availability and source rate for each user can be achieved using a price-based distributed algorithm. Finally, we numerically show the tradeoff between the throughput and the service availability obtained by users in various network topologies. Several quantitative observations are made from this investigation. For example, indiscriminately provisioning service availabilities for different kinds of users within one network leads to noteworthy sub-optimality in total network utility. The profile of bandwidth usage also illustrates that provisioning high service availability exclusively for critical applications leads to significant waste in bandwidth resource.

The implementation of distributed network utility maximization (NUM) algorithms hinges heavily on information feedback through message passing among network elements. In practical systems the feedback is often obtained using error-prone measurement mechanisms and suffers from random errors. There has been little work in this direction, and by and large the impact of noisy feedback remains unclear. A main objective of this study is to fill this void and to obtain a rigorous and systematic understanding of the impact of stochastic noisy feedback. In this paper, we consider distributed NUM in multi-hop wireless networks, and focus on the impact of noisy feedback on the distributed algorithms based on the Lagrangian dual method. These algorithms can in general be regarded as some form of gradient (or sub-gradient) based methods. Assuming strong duality, we study both cases when the stochastic gradients are unbiased or biased, and develop a general theory on the stochastic stability of these algorithms in the presence of noisy feedback. When the gradient estimator is unbiased, we establish, via a combination of the stochastic Lyapunov Stability Theorem and local analysis, that the iterates generated by distributed NUM algorithms converge with probability one to the optimal point, under standard technical conditions. In contrast, when the gradient estimator is biased, we show that the iterates converge to a contraction region around the optimal point, provided that the biased terms are asymptotically bounded by a scaled version of the true gradients. We also investigate the rate of convergence for the unbiased case, and find that, in general, the limit process of the interpolated process corresponding to the normalized iterate sequence is a stationary reflected linear diffusion process, not necessarily a Gaussian diffusion process. We also apply the above general theory to investigate stability of cross-layer rate control for joint congestion control and random access. Our numerical examples corroborate the theoretic findings well.

This paper considers the nonconvex and globally coupled problem of joint antenna beamforming and transmit power control, in order to maximize the network-wide utility as a function of attained SIRs. Using a spillage-load characterization for power control [13], we assign utility as a function of attained SIRs and formulate the joint optimization as a utility maximization problem. Despite the highly coupled structure of the problem, we propose an efficient distributed algorithm that is proved to be convergent in general. Despite nonconvexity in the joint optimization, we prove global optimality in the two user case. We find in simulations the algorithm always converges to the global optimal allocation, and the Pareto-optimal tradeoff between power and antenna beamforming in maximizing network utility is illustrated.

It is widely believed that although being more complex, a probabilistic key predistribution scheme is much more resilient against node capture than a deterministic one in lightweight wireless ad hoc networks. Backed up by the surprisingly large successful attack probabilities computed in this paper, we show that the probabilistic approaches have only limited performance advantages over deterministic approaches. We first consider a static network scenario as originally considered in the seminal paper by Eschenauer and Gligor [1], where any node capture happens after the establishment of all pairwise links, and show that the deterministic approach can achieve a performance as good as the probabilistic one. Furthermore in a mobile network, the probabilistic key management as described in [1] can lead to a successful attack probability of one order of magnitude larger than the one in a static network.

In this paper we characterize flow-level stochastic stability for networks with non-convex or time-varying rate regions underresource allocation based on utility maximization. Similar to prior works on flow-level stability, we consider exogenous data arrivals with finite workloads. However, to model many realistic situations, the rate region, which constrains the feasibility of resource allocation, may be either non-convex or time-varying. When the rate region is fixed but non-convex, we derive sufficient and necessary conditions for stability, which coincide when the set of allocated rate vectors has continuous contours. When the rate region is time-varying according to some stationary, ergodic process, we derive the precise stability region. In both cases,the size of the stability region depends on the resource allocation policy, in particular, on the fairness parameter in ∝-fair utility maximization. This is in sharp contrast with the substantial existing literature on stability under fixed and convex rate regions, in which the stability region coincides with the rate region for many utility-based resource allocation schemes, independently of the value of the fairness parameter. We further investigate the tradeoff between fairness and stability when rate region is non-convex or time-varying. Numerical examples of both wired and wireless networks are provided to illustrate the new stability regions and tradeoffs proved in the paper.

In the Internet today, traffic engineering is performed assuming that the offered traffic is inelastic. In reality, end hosts adapt their sending rates to network congestion, and network operators adapt the routing to the measured traffic. This raises the question of whether the joint system of congestion control (transport layer) and routing (network layer) is stable and optimal. Using the established optimization models for TCP and traffic engineering as a basis, we find the joint system can be stablized and often maximizes aggregate user utility. We prove that both stability and optimality of the joint system can be guaranteed for sufficiently elastic traffic simply by tuning the cost function used for traffic engineering. Then, we present a new algorithm that adapts on a smaller timescale to changes in traffic distribution and is more robust to large traffic bursts. Uniting the network and transport layers in a multi-layer approach, this algorithm, Distributed Adaptive Traffic Engineering (DATE), jointly optimizes the goals of end users and network operators and reacts quickly to avoid bottlenecks. Simulations demonstrate that DATE converges quickly.

This paper reverse-engineers backoff-based random-access MAC protocols in ad-hoc networks. We show that the contention resolution algorithm in such protocols is implicitly participating in a non-cooperative game. Each link attempts to maximize a selfish local utility function, whose exact shape is reverse-engineered from the protocol description, through a stochastic subgradient method in which the link updates its persistence probability based on its transmission success or failure. We prove that existence of a Nash equilibrium is guaranteed in general. Then we establish the minimum amount of backoff aggressiveness needed, as a function of density of active users, for uniqueness of Nash equilibrium and convergence of the best response strategy. Convergence properties and connection with the best response strategy are also proved for variants of the stochastic-subgradient-based dynamics of the game. Together with known results in reverse-engineering TCP and BGP, this paper further advances the recent efforts in reverse-engineering layers 2-4 protocols. In contrast to the TCP reverse-engineering results in earlier literature, MAC reverse-engineering highlights the non-cooperative nature of random access.

Network protocols in layered architectures have historically been obtained on anad hocbasis, and many of the recent cross-layer designs are also conducted through piecemeal approaches. Network protocol stacks may instead be holistically analyzed and systematically designed as distributed solutions to some global optimization problems. This paper presents a survey of the recent efforts towards a systematic understanding of “layering” as “optimization decomposition,” where the overall communication network is modeled by a generalized network utility maximization problem, each layer corresponds to a decomposed subproblem, and the interfaces among layers are quantified as functions of the optimization variables coordinating the subproblems. There can be many alternative decompositions, leading to a choice of different layering architectures. This paper surveys the current status of horizontal decomposition into distributed computation, and vertical decomposition into functional modules such as congestion control, routing, scheduling, random access, power control, and channel coding. Key messages and methods arising from many recent works are summarized, and open issues discussed. Through case studies, it is illustrated how “Layering as Optimization Decomposition” provides a common language to think about modularization in the face of complex, networked interactions, a unifying, top-down approach to design protocol stacks, and a mathematical theory of network architectures.

In wireless cellular or ad hoc networks where Quality of Service (QoS) is interference-limited, a variety of power control problems can be formulated as nonlinear optimization with a system-wide objective, e.g., maximizing the total system throughput or the worst user throughput, subject to QoS constraints from individual users, e.g., on data rate, delay, and outage probability. We show that in the high Signal-to- interference Ratios (SIR) regime, these nonlinear and apparently difficult, nonconvex optimization problems can be transformed into convex optimization problems in the form of geometric programming; hence they can be very efficiently solved for global optimality even with a large number of users. In the medium to low SIR regime, some of these constrained nonlinear optimization of power control cannot be turned into tractable convex formulations, but a heuristic can be used to compute in most cases the optimal solution by solving a series of geometric programs through the approach of successive convex approximation. While efficient and robust algorithms have been extensively studied for centralized solutions of geometric programs, distributed algorithms have not been explored before. We present a systematic method of distributed algorithms for power control that is geometric-programming-based. These techniques for power control, together with their implications to admission control and pricing in wireless networks, are illustrated through several numerical examples.

This paper designs medium access control (MAC) protocols for wireless networks through the network utility maximization (NUM) framework. A network-wide utility maximization problem is formulated, using a collision/persistence-probabilistic model and aligning selfish utility with total social welfare. By adjusting the parameters in the utility objective functions of the NUM problem, we can also control the tradeoff between efficiency and fairness of radio resource allocation. We develop two distributed algorithms to solve the utility-optimal random-access control problem, which lead to random access protocols that have slightly more message passing overhead than the exponential-backoff protocols, but significant potential for efficiency and fairness improvement. We provide readily-verifiable sufficient conditions under which convergence of the proposed algorithms to a global optimality of network utility can be guaranteed, and numerical experiments that illustrate the value of the NUM approach to the complexity-performance tradeoff in MAC design.

Power control mitigates interference and maintains required QoS levels in cellular wireless networks. An important class of distributed power control (DPC) was proposed by Foschini and Miljanic in 1993, with many variants developed since. Almost all related work focuses on the equilibrium and asymptotic convergence properties. However, for many applications transient behavior is more important. If a link's SIR drops below a critical threshold for too long, the connections over this link will be dropped, rendering the entire concept of equilibrium resource allocation meaningless. This paper proposes a systematic approach to the analysis of transient properties of DPC algorithms, in particular Foschini-Miljanic, based on tools from control theory. Analytically, we present a sufficient condition to ensure that after links reach their minimum SIR levels, their SIR requirements can be guaranteed for future time steps. Computationally, we pose this problem as verifying the invariance of certain regions in the SIR space, which for the basic DPC algorithm can be cast as a Linear Program (LP). Furthermore, using insights gained from the analysis, we propose a preliminary design framework for new iterative power control schemes.

In the Internet today, traffic engineering is performed assuming that the offered traffic is inelastic. In reality, end hosts adapt their sending rates to network congestion, and network operators adapt the routing to the measured traffic. This raises the question of whether the joint system of congestion control and routing is stable and optimal. Using established optimization models for TCP and traffic engineering as a basis, we find the joint system is stable and typically maximizes aggregate user utility through simulation. The joint system may deviate from this solution when the topology is not uniform. A modification to the joint system will guarantee stability and optimality for applications that are sufficiently elastic, but at the cost of robustness.

In Network Utility Maximization (NUM) problems, it is generally assumed that user utilities are uncoupled, i.e., each utility depends only on local variables. Then the coupling in constraint functions among users sharing common resources can be decoupled by standard methods such as dual decomposition. However, in problems where cooperation or competition is modeled through the objective function, such as rate allocation in clustered system and power control in interference limited system, each utility may depend not only on its local variables but also on the local variables of other utilities. Applications of this coupled utility model include wireless power control and DSL spectrum management, where the utilities are functions of the Signal-to-Interference Ratios (SIR) that depend on the transmit powers of other users. We present a systematic approach of consistency pricing to decouple NUM problems with coupled utilities, obtaining distributed algorithms that efficiently handle couplings in utilities with two alternative timescales, as well as a method to reduce message passing overhead in the case of interference-based coupling.

Despite the large body of work studying congestion control and adaptive routing in isolation, much less attention has been paid to whether these two resource-allocation mechanisms work well together to optimize user performance. Most analysis of congestion control assumes static routing, and most studies of adaptive routing assume that the offered traffic is fixed. In this paper, we analyze the interaction between congestion control and adaptive routing, and study the stability and optimality of the joint system. Previous work has shown that the system can be modelled as a joint optimization problem that naturally leads to a primal-dual algorithm with shortest-path routing using congestion prices as the link weights. In practice, the algorithm is commonly unstable. We consider three alternative timescale separations and examine the stability and optimality of each system. Our analytic characterizations and simulation experiments demonstrate how the step size of the congestion-control algorithm affects the stability of the system, and how the timescale of each control loop and homogeneity of link capacities affect system stability and optimality. The stringent conditions imposed for stability suggests that congestion price would be a poor feedback mechanism in practice.

The performance of wireless sensor network applications is typically a function of the amount of data collected by the individual sensors and delivered to a set of sinks through multihop routing within the network. However, the energy-constrained nature of the nodes limits the operational lifetime of the network since energy is dissipated both in sensing and in communicating data across the network. There is thus an inherent trade-off in simultaneously maximizing the network lifetime and the application performance (characterized here by a network utility function). In this paper, we characterize this trade-off by considering a cross-layer design problem in a wireless sensor network with orthogonal link transmissions. We compute an optimal set of source rates, network flows, and radio resources at the transport, network, and radio resource layers respectively, while jointly maximizing the network utility and lifetime. Using dual decomposition techniques, we show that the cross-layer optimization problem decomposes vertically into three subproblems - a joint transport and routing problem, a radio resource allocation problem, and a network lifetime maximization problem, all of which interact through the dual prices for capacities of links and battery capacities of nodes.

Abstract — This paper considers jointly optimal design of cross-layer congestion control, routing and scheduling for ad hoc wireless networks. We first formulate the rate constraint and scheduling constraint using multicommodity flow variables, and formulate resource allocation in networks with fixed wireless channels (or single-rate wireless devices that can mask channel variations) as a utility maximization problem with these con-straints. By dual decomposition, the resource allocation problem naturally decomposes into three subproblems: congestion control, routing and scheduling that interact through congestion price. The global convergence property of this algorithm is proved. We next extend the dual algorithm to handle networks with time-varying channels and adaptive multi-rate devices. The stability of the resulting system is established, and its performance is characterized with respect to an ideal reference system which has the best feasible rate region at link layer. We then generalize the aforementioned results to a general model of queueing network served by a set of interdependent parallel servers with time-varying service capabilities, which models many design problems in communication networks. We show that for a general convex optimization problem where a subset of variables lie in a polytope and the rest in a convex set, the dual-based algorithm remains stable and optimal when the constraint set is modulated by an irreducible finite-state Markov chain. This paper thus presents a step toward a systematic way to carry out cross-layer design in the framework of “layering as optimization decomposition ” for time-varying channel models. I.

The current framework of network utility max- imization for rate allocation and its price-based algorithms assumes that each link provides a fixed-size transmission 'pipe' and each user's utility is a function of transmission rate only. These assumptions break down in many practical systems, where, by adapting the physical layer channel coding or transmission diversity, different tradeoffs between rate and reliability can be achieved. In network utility maximization problems formu- lated in this paper, the utility for each user depends on both transmission rate and signal quality, with an intrinsic tradeoff between the two. Each link may also provide a higher (lower) rate on the transmission 'pipes' by allowing a higher (lower) decoding error probability. Despite non-separability and non- convexity of these optimization problems, we propose new price- based distributed algorithms and prove their convergence to the globally optimal rate-reliability tradeoff under readily-verifiable sufficient conditions. We first consider networks in which the rate-reliability tradeoff is controlled by adapting channel code rates in each link's physical layer error correction codes, and propose two distributed algorithms based on pricing, which respectively implement the 'integrated' and 'differentiated' policies of dynamic rate- reliability adjustment. In contrast to the classical price-based rate control algorithms, in our algorithms each user provides an of- fered price for its own reliability to the network while the network provides congestion prices to users. The proposed algorithms converge to a tradeoff point between rate and reliability, which we prove to be a globally optimal one for channel codes with sufficiently large coding length and utilities whose curvatures are sufficiently negative. Under these conditions, the proposed algorithms can thus generate the Pareto optimal tradeoff curves between rate and reliability for all the users. The distributed algorithms and convergence proofs are extended for wireless MIMO multi-hop networks, in which diversity and multiplexing gains of each link are controlled to achieve the optimal rate- reliability tradeoff.

This paper analyzes and designs medium access control (MAC) protocols for wireless ad-hoc networks through the network utility maximization (NUM) framework. We first reverse-engineer the current exponential backoff (EB) type of MAC protocols such as the BEB (binary exponential backoff) in the IEEE 802.11 standard through a non-cooperative game- theoretic model. This MAC protocol is shown to be implicitly maximizing, using a stochastic subgradient, a selfish local utility at each link in the form of expected net reward for successful transmission. While the existence of a Nash equilibrium can be established, neither convergence nor social welfare optimality is guaranteed due to the inadequate feedback mechanism in the EB protocol. This motivates the forward-engineering part of the paper, where a network-wide utility maximization problem is for- mulated, using a collision and persistence probability model and aligning selfish utility with total social welfare. By adjusting the parameters in the utility objective functions of the NUM problem, we can also control the tradeoff between efficiency and fairness of radio resource allocation through a rigorous and systematic design. We develop two distributed algorithms to solve the MAC design NUM problem, which lead to random access protocols that have slightly more message passing overhead than the current EB protocol, but significant potential for efficiency and fairness improvement. We provide readily-verifiable sufficient conditions under which convergence of the proposed algorithms to a global optimality of network utility can be guaranteed, and through numerical examples illustrate the value of the NUM approach to the complexity-performance tradeoff in MAC design.

Abstract — Network utility maximization (NUM) problems provide an important approach to conduct network resource management such as end-to-end rate allocation. In the existing literature, distributed implementations are typically achieved by the means of the so-called dual decomposition technique. However, the span of decomposition possibilities includes many other elements which thus far have not been fully exploited such as the use of the primal decomposition technique, the versatile introduction of auxiliary variables, and the potential of multilevel decompositions. This paper presents a systematic framework to exploit the potential of the alternative decomposition structures as a way to obtain different distributed algorithms, each with a different tradeoff among convergence speed, message passing amount and asymmetry, and distributed computation architecture. Many specific applications are considered to illustrate the proposed framework, including resource-constrained and directcontrol rate allocation, and rate allocation among QoS classes and with multipath routing. For each of these applications, the associated generalized NUM formulation is first presented, followed by the development of novel alternative decompositions and numerical experiments on the resulting new distributed algorithms.

For frequency selective interference channels where interference is treated as noise, distributively attaining the boundary of the rate region is an open problem, and is particularly important for broadband DSL access. This paper develops, analyzes, and simulates a new algorithm for power allocation in frequency selective interference channels called autonomous spectrum balancing (ASB). It utilizes the concept of a "reference line", which mimics a typical victim line in the interference channel. Compared with the state-of-the-art iterative watefilling and optimum spectrum balancing methods, the ASB algorithm is completely autonomous, has linear complexity in both the number of users and tones, and gives close to near-optimal performance. Convergence of a version of ASB is proven for any number of users

Network protocols in layered architectures have historically been obtained primarily on an ad-hoc basis. Recent research has shown that network protocols may instead be holistically analyzed and systematically designed as distributed solutions to some global optimization problems in the form of Network Utility Maximization (NUM), providing insight into what they optimize and structures of the network protocol stack. This paper presents a short survey of the recent efforts towards a systematic understanding of 'layering' as 'optimization decomposition', where the overall communication network is modeled by a generalized NUM problem, each layer corresponds to a decomposed subproblem, and the interfaces among layers are quantified as functions of the optimization variables coordinating the sub-problems. Different decompositions lead to alternative layering architectures. We summarize several examples of horizontal decomposition into distributed computation and vertical decomposition into functional modules such as congestion control, routing, scheduling, random access, power control, and coding.

When heterogeneous congestion control protocols that react to different pricing signals share the same network, the resulting equilibrium may no longer be interpreted as a solution to the standard utility maximization problem. We prove the existence of equilibrium in general multi-protocol networks under mild assumptions. For almost all networks, the equilibria are locally unique, and finite and odd in number. They cannot all be locally stable unless it is globally unique. Finally, we show that if the price mapping functions that map link prices to effective prices observed by the sources are similar, then global uniqueness is guaranteed.

We study joint end-to-end congestion control and per-link medium access control (MAC) in ad-hoc wireless networks. We use a network utility maximization formulation, in which by adjusting the types of utility functions, we can accommodate multi-class services as well as exploit the tradeoff between efficiency and fairness of resource allocation. Despite the inherent difficulties of non-convexity and non-separability of the optimization problem, we show that, under readily-verifiable sufficient conditions, we can develop a distributed algorithm that converges to the globally and jointly optimal rate allocation and persistence probabilities. A key contribution is that our results can accommodate general concave utility function rather than just the logarithmic utility function in existing results.

This paper reverse engineers backoff-based random-access MAC protocols in ad-hoc networks. We show that the contention resolution algorithm in such protocols is implicitly participating in a non-cooperative game. Each link attempts to maximize a selfish local utility function, whose exact shape is reverse engineered from the protocol description, through a stochastic subgradient method in which the link updates its persistence probability based on its transmission success or failure. We prove that existence of a Nash equilibrium is guaranteed in general. The minimum amount of backoff aggressiveness needed for uniqueness of Nash equilibrium and convergence of the best response strategy are established as a function of user density. Convergence properties and connection with the best response strategy are also proved for variants of the stochastic-subgradient-based dynamics of the game. Together with known results in reverse engineering TCP and BGP, this paper completes the recent efforts in reverse engineering the main protocols in layers 2-4.

The current framework of network utility maximization for rate allocation and its price-based algorithms assumes that each link provides a fixed-size transmission "pipe" and each user's utility is a function of transmission rate only. These assumptions break down in many practical systems, where, by adapting the physical layer channel coding or transmission diversity, different tradeoffs between rate and reliability can be achieved. In network utility maximization problems formulated in this paper, the utility for each user depends on both transmission rate and signal quality, with an intrinsic tradeoff between the two. Each link may also provide a higher (or lower) rate on the transmission "pipes" by allowing a higher (or lower) decoding error probability. Despite nonseparability and nonconvexity of these optimization problems, we propose new price-based distributed algorithms and prove their convergence to the globally optimal rate-reliability tradeoff under readily-verifiable sufficient conditions. We first consider networks in which the rate-reliability tradeoff is controlled by adapting channel code rates in each link's physical-layer error correction codes, and propose two distributed algorithms based on pricing, which respectively implement the "integrated" and "differentiated" policies of dynamic rate-reliability adjustment. In contrast to the classical price-based rate control algorithms, in our algorithms, each user provides an offered price for its own reliability to the network, while the network provides congestion prices to users. The proposed algorithms converge to a tradeoff point between rate and reliability, which we prove to be a globally optimal one for channel codes with sufficiently large coding length and utilities whose curvatures are sufficiently negative. Under these conditions, the proposed algorithms can thus generate the Pareto optimal tradeoff curves between rate and reliability for all the users. In addition, the distributed algorithms and convergence proofs are extended for wireless multiple-inpit-multiple-output multihop networks, in which diversity and multiplexing gains of each link are controlled to achieve the optimal rate-reliability tradeoff. Numerical examples confirm that there can be significant enhancement of the network utility by distributively trading-off rate and reliability, even when only some of the links can implement dynamic reliability.

A game-theoretic model for studying power control in multicarrier code-division multiple-access systems is proposed. Power control is modeled as a noncooperative game in which each user decides how much power to transmit over each carrier to maximize its own utility. The utility function considered here measures the number of reliable bits transmitted over all the carriers per joule of energy consumed and is particularly suitable for networks where energy efficiency is important. The multidimensional nature of users' strategies and the nonquasi-concavity of the utility function make the multicarrier problem much more challenging than the single-carrier or throughput-based-utility case. It is shown that, for all linear receivers including the matched filter, the decorrelator, and the minimum-mean-square-error detector, a user's utility is maximized when the user transmits only on its "best" carrier. This is the carrier that requires the least amount of power to achieve a particular target signal-to-interference-plus-noise ratio at the output of the receiver. The existence and uniqueness of Nash equilibrium for the proposed power control game are studied. In particular, conditions are given that must be satisfied by the channel gains for a Nash equilibrium to exist, and the distribution of the users among the carriers at equilibrium is characterized. In addition, an iterative and distributed algorithm for reaching the equilibrium (when it exists) is presented. It is shown that the proposed approach results in significant improvements in the total utility achieved at equilibrium compared with a single-carrier system and also to a multicarrier system in which each user maximizes its utility over each carrier independently.

A systematic understanding of the decomposability structures in network utility maximization is key to both resource allocation and functionality allocation. It helps us obtain the most appropriate distributed algorithm for a given network resource allocation problem, and quantifies the comparison across architectural alternatives of modularized network design. Decomposition theory naturally provides the mathematical language to build an analytic foundation for the design of modularized and distributed control of networks. In this tutorial paper, we first review the basics of convexity, Lagrange duality, distributed subgradient method, Jacobi and Gauss-Seidel iterations, and implication of different time scales of variable updates. Then, we introduce primal, dual, indirect, partial, and hierarchical decompositions, focusing on network utility maximization problem formulations and the meanings of primal and dual decompositions in terms of network architectures. Finally, we present recent examples on: systematic search for alternative decompositions; decoupling techniques for coupled objective functions; and decoupling techniques for coupled constraint sets that are not readily decomposable.

Network utility maximization problems provide an important approach to conduct network resource management such as power and rate allocation. In the existing literature, distributed implementations are typically achieved by the means of the so-called dual decomposition technique. However, the span of decomposition possibilities includes many other elements which thus far have not been fully exploited, such as the use of the primal decomposition technique, the versatile introduction of auxiliary variables, and the potential of multilevel decompositions. This paper presents in a systematic way how to apply these decomposition techniques to network utility maximization problems. The presentation is based on a general network optimization model that unifies existing works, and then is particularized to two concrete examples of recent interest: generalized water-filling algorithms and wireless cellular downlink power control. We can thus obtain a variety of distributed algorithms with different characteristics to suit the needs of specific applications. Both primal and dual decomposition techniques are considered at many different hierarchy levels, leading to a range of choices of hybrid, multi-level, primal/dual decomposition schemes. Each particular combination provides a different distributed algorithm for resource allocation. The choice of decomposition method and distributed algorithm for a particular problem depends on factors such as the amount of signalling required for proper coordination, asymmetry of computational load, and speed of convergence.

In wireless cellular networks that are interference-limited, a variety of power control problems can be formulated as nonlinear optimization with a system-wide objective subject to many QoS constraints from individual users. Previous work have been done in the high SIR regime by solving these problems with nonlinear objectives and constraints as geometric programs. However, in the medium to low SIR regime, these problems cannot be transformed into tractable convex optimization problems. This paper makes two contributions: (1) In the low SIR regime, we propose a method with centralized computation to obtain the globally optimal solution by solving a series of geometric programs. (2) While efficient and robust algorithms have been extensively studied for centralized solutions of geometric programs, distributed algorithms have not been investigated before this paper. We present a systematic method of distributed algorithms for power control based on geometric programs in high SIR regime. These two contributions can be readily combined to distributively solve nonlinear power control problems in general SIR regime

A common assumption behind most of the recent research on network utility maximization is that traffic flows are elastic, which implies that their utility functions are concave and there are no hard limits on the rate allocated to each flow. These critical assumptions lead to tractability of the analytic models of utility maximization, but also limits applicability of the resulting rate allocation protocols. This paper focuses on inelastic flows and removes these restrictive and often invalid assumptions. We present several optimization frameworks, optimality conditions, and optimal algorithms. First, we consider nonconcave utility functions, which turn utility maximization into nonconvex, constrained optimization problems that are well-known to be difficult. We present conditions under which the current standard price-based distributed algorithm can still converge to the globally optimal rate allocation despite nonconcavity of utility functions. In particular, continuity of price-based rate allocation at all the optimal prices is a sufficient condition for global convergence of rate allocation by the standard algorithm, and continuity at at least one optimal price is a necessary condition. In the second part of the paper, we provide a general problem formulation of rate allocation among time-sensitive flows from real-time and streaming applications, as well as a decomposition into subproblems coordinated by pricing. After simplifying the subproblems by leveraging the optimization structures, we highlight the difficult issues of causality and time-scale, and propose an effective price-based heuristics for admission control and an optimal algorithm for a special case formulation.

When heterogeneous congestion control protocols that react to different pricing signals share the same network, the resulting equilibrium may no longer be interpreted as a solution to the standard utility maximization problem. We prove the existence of equilibrium under mild assumptions. Then we show that multi-protocol networks whose equilibria are locally non-unique or infinite in number can only form a set of measure zero. Multiple locally unique equilibria can arise in two ways. First, unlike in the single-protocol case, the set of bottleneck links can be non-unique with heterogeneous protocols even when the routing matrix has full row rank. The equilibria associated with different sets of bottleneck links are necessarily distinct. Second, even when there is a unique set of bottleneck links, network equilibrium can still be non-unique, but is always finite and odd in number. They cannot all be locally stable unless it is globally unique. Finally, we provide various sufficient conditions for global uniqueness. Numerical examples are used throughout the paper to illustrate these results.

The current framework of network utility maximization for distributed rate allocation assumes fixed channel code rates. However, by adapting the physical layer channel coding, different rate-reliability tradeoffs can be achieved on each link and for each end user. Consider a network where each user has a utility function that depends on both signal quality and data rate, and each link may provide a 'fatter' ('thinner') information 'pipe' by allowing a higher (lower) decoding error probability. We propose two distributed, pricing-based algorithms to attain optimal rate-reliability tradeoff, with an interpretation that each user provides its willingness to pay for reliability to the network and the network feeds back congestion prices to users. The proposed algorithms converge to a tradeoff point between rate and reliability, which is proved to be globally optimal for codes with sufficiently large codeword lengths and user utilities with sufficiently negative curvatures

Recently, there has been a surge in research activities that utilize the power of recent developments in nonlinear optimization to tackle a wide scope of work in the analysis and design of communication systems, touching every layer of the layered network architecture, and resulting in both intellectual and practical impacts significantly beyond the earlier frameworks. These research activities are driven by both new demands in the areas of communications and networking, and new tools emerging from optimization theory. Such tools include new developments of powerful theories and highly efficient computational algorithms for nonlinear convex optimization, as well as global solution methods and relaxation techniques for nonconvex optimization.Optimization theory can be used to analyze, interpret, or design a communication system, for both forward-engineering and reverse-engineering. Over the last few years, it has been successfully applied to a wide range of communication systems, from the high speed Internet core to wireless networks, from coding and equalization to broadband access, and from information theory to network topology models. Some of the theoretical advances have also been put into practice and started making visible impacts, including new versions of TCP congestion control, power control and scheduling algorithms in wireless networks, and spectrum management in DSL broadband access networks.Under the theme of optimization and control of communication networks, this Hot Topic Session consists of five invited talks covering a wide range of issues, including protocols, pricing, resource allocation, cross layer design, traffic engineering in the Internet, optical transport networks, and wireless networks.

Network Utility Maximization (NUM) has significantly extended the classical network flow problem and provided an emerging framework to design resource allocation algorithms such as TCP congestion control and to understand layering as optimization decomposition. We present a summary of very recent results in the theory and applications of NUM. We show new distributed algorithms that converge to the globally optimal rate allocation for NUM problems with nonconcave utility functions representing inelastic flows, with coupled utility functions representing interference effects or hybrid social-selfish utilities, and with rate-reliability tradeoff through adaptive channel coding in the physical layer. We conclude by discussing how do different decompositions of a generalized NUM problem correspond to different layering architectures.

Convex relaxations of the optimal finger selection algorithm are proposed for a minimum mean square error (MMSE) RAKE receiver in an impulse radio ultra-wideband system. First, the optimal finger selection problem is formulated as an integer programming problem with a non-convex objective function. Then, the objective function is approximated by a convex function and the integer programming problem is solved by means of constraint relaxation techniques. The proposed algorithms are suboptimal due to the approximate objective function and the constraint relaxation steps. However, they can be used in conjunction with the conventional finger selection algorithm, which is suboptimal on its own since it ignores the correlation between multipath components, to obtain performances reasonably close to that of the optimal scheme that cannot be implemented in practice due to its complexity. The proposed algorithms leverage convexity of the optimization problem formulations, which is the watershed between 'easy' and 'difficult' optimization problems.

In the power control game proposed for MC-CDMA systems, each user needs to decide how much power to transmit over each carrier to maximize its overall utility. The utility function considered measures the number of reliable bits transmitted per joule of energy consumed. It is shown that the user's utility is maximized when the user transmits only on the carrier with the best "effective channel". The existence and uniqueness of Nash equilibrium for the proposed game are investigated and the properties of equilibrium are studied. Also, an iterative and distributed algorithm for reaching equilibrium (if it exists) is presented. It is shown that the proposed approach results in a significant improvement in the total utility achieved at equilibrium compared to the case in which each user maximizes its utility over each carrier independently.

In a wireless network with multihop transmissions and interference-limited link rates, can we balance power control in the physical layer and congestion control in the transport layer to enhance the overall network performance while maintaining the architectural modularity between the layers? We answer this question by presenting a distributed power control algorithm that couples with existing transmission control protocols (TCPs) to increase end-to-end throughput and energy efficiency of the network. Under the rigorous framework of nonlinearly constrained utility maximization, we prove the convergence of this coupled algorithm to the global optimum of joint power control and congestion control, for both synchronized and asynchronous implementations. The rate of convergence is geometric and a desirable modularity between the transport and physical layers is maintained. In particular, when congestion control uses TCP Vegas, a simple utilization in the physical layer of the queueing delay information suffices to achieve the joint optimum. Analytic results and simulations illustrate other desirable properties of the proposed algorithm, including robustness to channel outage and to path loss estimation errors, and flexibility in trading off performance optimality for implementation simplicity. This work presents a step toward a systematic understanding of "layering" as "optimization decomposition," where the overall communication network is modeled by a generalized network utility maximization problem, each layer corresponds to a decomposed subproblem, and the interfaces among layers are quantified as the optimization variables coordinating the subproblems. In the case of the transport and physical layers, link congestion prices turn out to be the optimal "layering prices.".

We formulate a problem of state information transmission over a state-dependent channel with states known at the transmitter. In particular, we solve a problem of minimizing the mean-squared channel state estimation error E/spl par/S/sup n/ - S/spl circ//sup n//spl par/ for a state-dependent additive Gaussian channel Y/sup n/ = X/sup n/ + S/sup n/ + Z/sup n/ with an independent and identically distributed (i.i.d.) Gaussian state sequence S/sup n/ = (S/sub 1/, ..., S/sub n/) known at the transmitter and an unknown i.i.d. additive Gaussian noise Z/sup n/. We show that a simple technique of direct state amplification (i.e., X/sup n/ = /spl alpha/S/sup n/), where the transmitter uses its entire power budget to amplify the channel state, yields the minimum mean-squared state estimation error. This same channel can also be used to send additional independent information at the expense of a higher channel state estimation error. We characterize the optimal tradeoff between the rate R of the independent information that can be reliably transmitted and the mean-squared state estimation error D. We show that any optimal (R, D) tradeoff pair can be achieved via a simple power-sharing technique, whereby the transmitter power is appropriately allocated between pure information transmission and state amplification.

In a wireless ad hoc network with multihop transmissions and interference-limited link rates, can we balance power control in the physical layer and congestion control in the transport layer to enhance the overall network performance, while maintaining the stability, robustness, and architectural modularity of the network? We present a distributive power control algorithm that couples with the original TCP protocols to increase the end-to-end throughput and energy efficiency of the network. Under the rigorous framework of nonlinearly constrained optimization, we prove the convergence of this coupled system to the global optimum of joint power control and congestion control, for both synchronized and asynchronous implementations. The rate of convergence is geometric and a desirable modularity between the transport and physical layers is maintained. In particular, when the congestion control mechanism is TCP Vegas, that a simple utilization in the physical layer of the router buffer occupancy information suffices to achieve the joint optimum of this cross layer design. Both analytic results and simulations illustrate other desirable properties of the proposed algorithm, including robustness to channel outage and to path loss estimation errors, and flexibility in trading-off performance optimality for implementation simplicity.

In wireless cellular networks and wireless local area networks, nonlinear network utility maximization need to be conducted over both user rates and transmit powers. For each of the three cases considered in this paper, we present an algorithm that converges to the jointly optimal pair of rate vector and power vector. For the simple case when data rates are not limited by interferences, for example in single-cell downlink transmissions, we propose algorithm 1, which is an iterative bidding mechanism between the base station and mobile users, where knowledge about channel conditions and individual user utility functions is only needed locally at each user but not needed at the base station. In the case when data rates are limited by interferences, the utility maximization problem is complicated both by nonlinear coupling between powers and rates, and by interference among powers. Through centralized iterative steps, we propose algorithm 2, which converges to a joint and global optimum over the solution space of rates and powers. We then consider end-to-end transmissions in cellular networks, which traverse both wireless fading channels and many hops of wired links shared by other traffic. There is a tradeoff between attaining air-interface capacity in the wireless hop and controlling congestion in the wired backbone wide area network. We formulate this end-to-end resource allocation problem in such hybrid networks, and present a solution to obtain the Pareto optimal tradeoff between attaining wireless multi-access fading channel capacity and maximizing global network utility.

In this paper, we consider a hybrid wireless-wired network consisting of two distinct parts: a wireless hop and a wired mesh backbone network shared by wireless and wires sources. The wireless air-interface is often modeled as time-varying fading channels, and the primary objective is to make the most efficient use of the available bandwidth and power. In this hybrid network model, trade-off between rate-power allocation local to the wireless hop and global congestion control that regulate both wireless and wired sources sharing wired links in the backbone. To resolve a potential conflict between maximizing 'global utility' for end-to-end transmissions and achieving 'local capacity' at the air-interface, wireless source is needed. Global and joint convergence method is used for the end-to-end resource allocation algorithm

We show that the Lagrange dual problems of the channel capacity problem with input cost and the rate distortion problem are simple geometric programs. Upper bounds on channel capacity and lower bounds on rate distortion can be efficiently generated from their duals. For channel capacity, the geometric programming dual characterization is shown to be equivalent to the minmax Kullback-Leibler (KL) characterization in Csiszar et al. (1981). For rate distortion, the geometric programming dual is extended to rate distortion with two-sided state information. A "duality by mapping" is then given between the Lagrange dual problems of channel capacity with input cost and rate distortion, which resolves several apparent asymmetries between their primal problems in the familiar form of mutual information optimization problems. Both the primal and dual problems can be interpreted in a common framework of free energy optimization from statistical physics.

Power control can significantly enhance the performance of congestion control mechanisms, such as TCP, in wireless networks. We present a distributed power control algorithm that works together with the original TCP protocol to increase end- to-end throughput and energy efficiency of multihop data transmissions in CDMA wireless ad hoc networks. We prove that the resulted nonlinear coupled system converges to the global optimality of network utility maximization with elastic link capacities. This cross-layer algorithm can be interpreted as using link queuing delays as shadow prices to coordinate bandwidth demand and supply. Various simulations show desirable properties of the algorithms, including robustness to channel variations and fading estimation errors, and flexibility in the tradeoff between performance optimally and algorithmic simplicity.

We present an efficient method to optimize network resource allocations under nonlinear quality of service (QoS) constraints. We first propose a suite of generalized proportional allocation schemes that can be obtained by minimizing the information-theoretic function of relative entropy. We then optimize over the allocation parameters, which are usually design variables an engineer can directly vary, either for a particular user or for the worst-case user, under constraints that lower bound the allocated resources for all other users. Despite the nonlinearity in the objective and constraints, we show that this suite of resource allocation optimization can be efficiently solved for global optimality through a convex optimization technique called geometric programming. This general method and its extensions are applicable to a wide array of resource allocation problems, including processor sharing, congestion control, admission control, and wireless network power control. We provide a specific example of efficiently optimizing an admission control scheme.

Sum product algorithm on graphs is a general message passing algorithm that unifies many algorithms in channel coding, signal processing, Bayesian inference, and statistical physics. We show that, by extending the underlying algebraic and graphical structures of sum product algorithm, it also provides a unifying perspective for important distributed algorithms in communication networks. Examples treated here include Bellman-Ford (1957, 1962) routing, traffic shaping, wireless network power control, and congestion control. Through local message passing in the form of sum product algorithm on graphs, each of these network control algorithms solves a corresponding global optimization problem. This common framework also leads to new distributed algorithms, such as joint optimization of power control and utility maximization through distributed gradient descent.

We present a systematic treatment of efficient nonlinear optimizations of queuing systems. The suite of formulations uses the computational tool of convex optimization, with fast polynomial time algorithms to obtain the global optimum for these nonlinear problems under various constraints. We first show convexity structures of several queuing systems, including some surprising transition patterns, followed by formulating and showing numerical examples of several convex performance optimizations for both single queues and queuing networks. Blocking probability minimization and service rate allocation through the effective bandwidth approach is also presented.

We present two novel algorithms at the ingress and egress of packet switches with QoS provisioning and fairness constraints. We first provide a suite of generalized weighted fair queuing formulations for output link scheduling, where the weights can be dynamically optimized under QoS constraints using the tool of geometric programming. We then provide a suite of active queue management formulations for flexible ingress buffer management, using the tool of semifinite programming. Both sets of formulations are nonlinear, and are special cases of convex optimization problems, which can be solved globally and as efficiently as linear problems.

For wireless cellular and ad hoc networks with QoS constraints, we propose a suite of problem formulations that allocate network resources to optimize SIR, maximize throughput and minimize delay. The distinguishing characteristics of these resource allocation formulations is that, by using convex optimization, they accommodate a variety of realistic QoS and fairness constraints. Their globally optimal solutions can be computed efficiently through polynomial time interior point methods, even though they use nonlinear objectives and constraints. Through power control in wireless cellular networks, we optimize SIR and delay for a particular QoS class, subject to QoS constraints for all other QoS classes. For wireless ad hoc networks with multihop transmissions and Rayleigh fading, we optimize various objectives, such as the overall system throughput, subject to constraints on power, probability of outage, and data rates. These formulations can also be used for admission control and relative pricing. Both proportional and minmax fairness can be implemented under the convex optimization framework, where fairness parameters can be jointly optimized with QoS criteria. Simple heuristics are also shown and tested using the convex optimization tools.

We show that the duality between channel capacity and data compression is retained when state information is available to the sender, to the receiver, to both, or to neither. We present a unified theory for eight special cases of channel capacity and rate distortion with state information, which also extends existing results to arbitrary pairs of independent and identically distributed (i.i.d.) correlated state information (S/sub 1/, S/sub 2/) available at the sender and at the receiver, respectively. In particular, the resulting general formula for channel capacity C = max/sub p/(u,x|s/sub 1/) [I(U; S/sub 2/, Y) I(U; S/sub 1/)] assumes the same form as the generalized Wyner-Ziv (1976) rate distortion function R(D) = min/sub p/(u|x, s/sub 1/)p(x/spl I.cap/|u, s/sub 2/) [I(U; S/sub 1/, X) 1(U; S/sub 2/)].

We present two novel Locally Optimal Routing Algorithms (LORA) for ad hoc mobile wireless networks with fast changing topology. Instead of modifying globally optimal shortest path routing algorithms, we propose two new algorithms that are designed to match the characteristics of wireless physical channels in a network with dynamic ad hoc topology and mobile users. Motivated by practical constraints, we design LORA to be simple to implement at each node, requiring very low computational load and a small amount of memory, and can provide fast rerouting under distributed control when nodes or links fail. The first algorithm, LORA1, is designed for networks with slowly moving users, using a new random graphical model and randomized algorithms. The second algorithm, LORA2, is designed for fast moving users, building upon LORA1 with an additional mobility diversity feature. Various properties of the algorithms are tested by simulations. Analytic results bound the performances of LORA. We also outline several extensions of LORA.

We present two novel Locally Optimal Routing Algorithms (LORA) for ad hoc mobile wireless networks with fast changing topology. Instead of modifying globally optimal shortest path routing algorithms, we propose two new algorithms that are designed to match the characterisitics of wireless physical channels in a network with dynamic ad hoc topology and mobile users. Motivated by practical constraints, we design LORA to be simple to implement at each node, requiring very low computational load and a small amount of memory, and can provide fast rerouting under distributed control when nodes or links fail. The first algorithm, LORAl, is designed for networks with slowly moving users, using a new random graphical model and randomized algorithms. The second algorithm, LORAB, is designed for fast moving users, building upon LORAl with an additional mobility diversity feature. Various properties of the algorithms are tested by simulations. Analytic results bound the performances of LORA. We also outline several extensions of LORA.

For wireless ad hoc networks with multihop, transmissions and Rayleigh fading, this paper maximizes the overall system throughput subject to QoS constraints on power, probability of outage, and data rates. Formulations are also given which minimize delay and optimize network resources in a wireless ad hoc network, where each link is shared by multiple streams of traffic from different QoS classes, and each traffic traverses many links. Although these optimal resource allocation problems are non-linear, they can be posed as geometric programs, which are transformed into convex optimizations, and can be solved globally and efficiently through interior-point methods.

For ad hoc wireless mobile networks, we present several criteria and algorithms to control the admission of new transceivers and to balance the tradeoff between power consumption and link maintenance. From a random graph theoretic perspective, we first propose an admission control scheme based on the evolution of ad hoc networks. This also provides analyses on QoS assurance and pricing schemes. For the power control problem, based on thresholding phenomena in random graph models, we balance power conservation and interference mitigation with network performance criteria such as robust routing, multicasting, transmission delay and length of multi-hop transmissions.

Power control in wireless cellular networks is crucial in minimizing power consumption, mitigating interference, increasing network capacity and maintaining link quality of service (QoS). Robustness to variation in noise level and accommodation of QoS constraints are particularly important practical issues. These issues in power control are transformed into two convex optimization problems that have efficient algorithms. The first convex power control formulation is robust optimization and its variation: robust Pareto optimization. The second convex formulation is QoS constrained optimization and its two extensions on proportional and minmax fairness implementations. These results also lead to new admission control and relative pricing schemes. As concurred by simulations, these convex optimization formulations optimize power and control QoS in a robust, optimal, fast, scalable and versatile way.