In-context learning (ICL) is a new paradigm for natural language processing that utilizes Generative Pre-trained Transformer (GPT)-like models. This approach uses prompts that include in-context demonstrations to generate the corresponding output for a new query input. However, applying ICL in real cases does not scale with the number of samples, and lacks robustness to different prompt templates and demonstration permutations. In this paper, we first show that GPT-like models using ICL result in unreliable predictions based on a new metric based on Shannon entropy. Then, to solve this problem, we propose a new technique called the Linear Probe Calibration (LinC), a method that calibrates the model’s output probabilities, resulting in reliable predictions and improved performance, while requiring only minimal additional samples (as few as five labeled data samples). LinC significantly enhances the ICL test performance of GPT models on various benchmark datasets, with an average improvement of up to 21%, and up to a 50% improvement in some cases, and significantly boosts the performance of PEFT methods, especially in the low resource regime. Moreover, LinC achieves lower expected calibration error, and is highly robust to varying label proportions, prompt templates, and demonstration permutations.

In this paper we introduce a metalearning-based methodology for predicting the training runtime of various machine learning algorithms. This prediction is important for automated machine learning (AutoML) systems because they search by training and evaluating a large number of machine learning models in order to identify the best model for a given dataset. Our approach identifies the main factors that impact the runtime performance of state of the art algorithms used in AutoML systems and can be used to enhance their performance in resource-constrained settings.

We present an algorithm to estimate the trace of symmetric matrices that are available only via Matrix-Vector multiplication. The proposed algorithm constructs a series of trace estimates by applying the probing technique with an increasing number of vectors. These estimates are then treated as a converging sequence whose limit is the sought matrix trace, and we apply Aitken’s Δ2process to accelerate its convergence to the trace limit. Numerical experiments performed on covariance matrices demonstrate the competitiveness of the proposed scheme versus probing and randomized trace estimators.

We propose Quantum Graph Transformers (QGT), a novel approach for realizing the Transformer architecture for graph learning with quantum processors. QGT is built on top of the Graph Trans-former (GT) architecture and addresses the main challenge of mapping GT basic functions such as node encodings, graph structure, all-to-all connectivity, and message passing to quantum computing primitives and processors. We empirically demonstrate the training and inference efficacy of our proposed QGT architecture for the graph classification task on quantum devices over various graph datasets.

In this paper, we present FLASH, a framework which addresses for the first time the central AutoML problem of Combined Algorithm Selection and HyperParameter (HP) Optimization (CASH) in the context of Federated Learning (FL). To limit training cost, FLASH incrementally adapts the set of algorithms to train based on their projected loss rates, while supporting decentralized (federated) implementation of the embedded hyper-parameter optimization (HPO), model selection and loss calculation problems. We provide a theoretical analysis of the training and validation loss under FLASH, and their tradeoff with the training cost measured as the data wasted in training sub-optimal algorithms. The bounds depend on the degree of dissimilarity between the datasets of the clients, a result of FL restriction that client datasets remain private. Through extensive experimental investigation on several datasets, we evaluate three variants of FLASH, and show that FLASH performs close to centralized CASH methods.

An increasing number of mobile applications rely on Machine Learning (ML) routines for analyzing data. Executing such tasks at the user devices saves the energy spent on transmitting and processing large data volumes at distant cloud-deployed servers. However, due to memory and computing limitations, the devices often cannot support the required resource-intensive routines and fail to accurately execute such tasks. In this work, we address the problem of edge-assisted analytics in resource-constrained systems by proposing and evaluating a rigorous selective offloading framework. The devices execute their tasks locally and outsource them to cloudlet servers only when they predict a significant performance improvement. We consider the practical scenario where the offloading gains and resource costs are time-varying; and propose an online optimization algorithm that maximizes the service performance without requiring to know this information. Our approach relies on an approximate dual subgradient method combined with a primal-averaging scheme, and works under minimal assumptions about the system stochasticity. We fully implement the proposed algorithm in a wireless testbed and evaluate its performance using a state-of-the-art image recognition application, finding significant performance gains and cost savings.

Feature engineering is a crucial but tedious task that requires up to 80% of the total time in data science projects. A significant challenge is when data consists of tables from different data sources, thus data scientists need to wisely aggregate and join tables while performing feature engineering task. In this work, we demonstrate a novel system called OneBM (One Button Machine), that enables data scientists to increase their efficiency with automated feature engineering for relational data. OneBM takes as input a relational dataset with multiple tables and its entity relation diagram (ERD) which can be declared with a novel, easy-to-use drag-and-drop graphical user interface. The system then automatically identifies and executes relevant joins and aggregates in the data, and generates new features with a rich set of transformations for various types of data including but not limited to time-series, sequences, number sets and itemsets, etc. The generated features then can be used by automated model selection and hyper-parameter optimization algorithms to complete a fully end-to-end automated data science (or AutoDS) workflow. A follow-up user evaluation illustrated how data scientists can perform multi-table feature engineering tasks in minutes using our system, compared to repeatedly coding SQL-like queries to transform and aggregate relational data requiring weeks of manual labor for comparable performance. In the live demos we plan to show two use cases with real-world datasets (video demos are available at the links in the footnote): sale prediction1and call center user experience2. Pre-registered partcipants can play with these use-cases and the given datasets via Watson Studio on the cloud.

A large number of emerging IoT applications rely on machine learning routines for analyzing data. Executing such tasks at the user devices improves response time and economizes network resources. However, due to power and computing limitations, the devices often cannot support such resource-intensive routines and fail to accurately execute the analytics. In this work, we propose to improve the performance of analytics by leveraging edge infrastructure. We devise an algorithm that enables the IoT devices to execute their routines locally; and then outsource them to cloudlet servers, only if they predict they will gain a significant performance improvement. It uses an approximate dual subgradient method, making minimal assumptions about the statistical properties of the system's parameters. Our analysis demonstrates that our proposed algorithm can intelligently leverage the cloudlet, adapting to the service requirements.

We address energy-efficient placement of data and analytics components of composite analytics services on a wireless network to minimize execution-time energy consumption (computation and communication) subject to compute, storage and network resource constraints. We introduce an expressive analytics service hypergraph model for representing k-ary composability relationships (k ≥ 2) between various analytics and data components and leverage binary quadratic programming (BQP) to minimize the total energy consumption of a given placement of the analytics hypergraph nodes on the network subject to resource availability constraints. Then, after defining a potential energy functional Φ(·) to model the affinities of analytics components and network resources using analogs of attractive and repulsive forces in physics, we propose a decentralized Metropolis Monte Carlo (MMC) sampling method which seeks to minimize Φ by moving analytics and data on the network. Although Φ is non-convex, using a potential game formulation, we identify conditions under which the algorithm provably converges to a local minimum energy equilibrium placement configuration. Trace-based simulations of the placement of a deep-neural-network analytics service on a realistic wireless network show that for smaller problem instances our MMC algorithm yields placements with total energy within a small factor of BQP and more balanced workload distributions; for larger problems, it yields low-energy configurations while the BQP approach fails.

This paper studies the problem of allocating band-width and computation resources to data analytics tasks in Internet of Things (IoT) networks. IoT nodes are powered by batteries, can process (some of) the data locally, and the quality grade or performance of how data analytics tasks are carried out depends on where these are executed. The goal is to design a resource allocation algorithm that jointly maximizes the network lifetime and the performance of the data analytics tasks subject to energy constraints. This joint maximization problem is challenging with coupled resource constraints that induce non-convexity. We first show that the problem can be mapped to an equivalent convex problem, and then propose an online algorithm that provably solves the problem and does not require any a priori knowledge of the time-varying wireless link capacities and data analytics arrival process statistics. The algorithm's optimality properties are derived using an analysis which, to the best of our knowledge, proves for the first time the convergence of the dual subgradient method with time-varying sets. Our simulations seeded by real IoT device energy measurements, show that the network connectivity plays a crucial role in network lifetime maximization, that the algorithm can obtain both maximum network lifetime and maximum data analytics performance in addition to maximizing the joint objective, and that the algorithm increases the network lifetime by approximately 50% compared to an algorithm that minimizes the total energy consumption.

We study the problem of cooperative execution of IoT data analytics at the edge nodes. We propose an auction mechanism that allows the nodes to trade their tasks in a way that optimizes execution accuracy and delay, without requiring information about the nodes' accuracy/delay priorities, and yields the optimal task outsourcing policy. Testbed-driven evaluation shows gains in both accuracy and delay compared to heuristic/greedy policies.

Emerging technologies and applications including Internet of Things, social networking, and crowd-sourcing generate large amounts of data at the network edge. Machine learning models are often built from the collected data, to enable the detection, classification, and prediction of future events. Due to bandwidth, storage, and privacy concerns, it is often impractical to send all the data to a centralized location. In this paper, we consider the problem of learning model parameters from data distributed across multiple edge nodes, without sending raw data to a centralized place. Our focus is on a generic class of machine learning models that are trained using gradient-descent-based approaches. We analyze the convergence bound of distributed gradient descent from a theoretical point of view, based on which we propose a control algorithm that determines the best tradeoff between local update and global parameter aggregation to minimize the loss function under a given resource budget. The performance of the proposed algorithm is evaluated via extensive experiments with real datasets, both on a networked prototype system and in a larger-scale simulated environment. The experimentation results show that our proposed approach performs near to the optimum with various machine learning models and different data distributions.

This paper presents Swing, a framework that aggregates a swarm of mobile devices to perform collaborative computation on sensed data streams. It endows performance and efficiency to the new generation of mobile sensing applications, in which the computation is overly intensive for a single device. After studying the source of performance slowdown of the sensing applications on a single device, we design and implement Swing to manage (i) parallelism in stream processing, (ii) dynamism from mobile users, and (iii) heterogeneity from the swarm devices. We build an Android-based prototype and deploy sensing apps - face recognition and language translation - on a wireless testbed. Our evaluations show that with proper management policies, such a distributed processing framework can achieve up to 2.7x improvement in throughput and 6.7x reduction in latency, allowing intensive sensing apps to reach real-time performance goals under different device usages, network conditions and user mobility.

Emerging technologies and applications including Internet of Things (IoT), social networking, and crowd-sourcing generate large amounts of data at the network edge. Machine learning models are often built from the collected data, to enable the detection, classification, and prediction of future events. Due to bandwidth, storage, and privacy concerns, it is often impractical to send all the data to a centralized location. In this paper, we consider the problem of learning model parameters from data distributed across multiple edge nodes, without sending raw data to a centralized place. Our focus is on a generic class of machine learning models that are trained using gradient-descent based approaches. We analyze the convergence rate of distributed gradient descent from a theoretical point of view, based on which we propose a control algorithm that determines the best trade-off between local update and global parameter aggregation to minimize the loss function under a given resource budget. The performance of the proposed algorithm is evaluated via extensive experiments with real datasets, both on a networked prototype system and in a larger-scale simulated environment. The experimentation results show that our proposed approach performs near to the optimum with various machine learning models and different data distributions.

The emergence of delay sensitive and computationally demanding data analytic applications has burdened the core network with huge data transfers and increased computation load. Furthermore, the increasing number of Internet of Things deployments rely significantly on the execution of such applications. We propose an architecture where devices collaboratively execute data analytic tasks in order to improve their execution delay and accuracy. This is possible by exploiting the aggregate computation capabilities of the abundance of small devices. We design an optimization framework where the nodes decide where their data analytic tasks will be executed, in order to jointly optimize their average execution delay and accuracy, while respecting power consumption constraints. We propose a distributed dual ascent solution to the formulated convex problem, so that the nodes can make the outsourcing decisions by exchanging local information. The results indicate that the nodes can achieve better performance when collaborating than when they locally compute the tasks, depending on the network load.

We consider the problem of proactive retention aware caching in a heterogeneous wireless edge network consisting of mobile users accessing content from a server and associated to one or more edge caches. Our goal is to design a caching policy that minimizes the sum of content storage costs and server access costs over two design variables: the retention time of each cached content and the probability that a user routes content requests to each of its associated caches. We develop a model that captures multiple aspects such as cache storage costs and several capabilities of modern wireless technologies, such as server multicast/unicast transmissions, device multi-path routing, and cache access constraints. We formulate the problem of Proactive Retention Routing Optimization as a non-convex, non-linear mixed-integer program. We prove that it is NP-hard under both multicast/unicast modes-even when the caches have a large capacity and storage costs are linear-and develop greedy algorithms that have provable performance bounds for the case of uncapacitated caches. Finally, we propose heuristics with low computational complexity for the capacitated cache case as well as for the case of convex storage costs. Systematic evaluations based on real-world data demonstrate the effectiveness of our approach, compared to the existing caching schemes.

In an edge deployment model, Internet-of-Things (IoT) applications, e.g. for building automation or video surveillance, must process data locally on IoT devices without relying on permanent connectivity to a cloud backend. The ability to harness the combined resources of multiple IoT devices for computation is influenced by the quality of wireless network connectivity. An open challenge is how practical edge-based IoT applications can be realised that are robust to changes in network bandwidth between IoT devices, due to interference and intermittent connectivity. We present Frontier , a distributed and resilient edge processing platform for IoT devices. The key idea is to express data-intensive IoT applications as continuous data-parallel streaming queries and to improve query throughput in an unreliable wireless network by exploiting network path diversity : a query includes operator replicas at different IoT nodes, which increases possible network paths for data. Frontier dynamically routes stream data to operator replicas based on network path conditions. Nodes probe path throughput and use backpressure stream routing to decide on transmission rates, while exploiting multiple operator replicas for data-parallelism. If a node loses network connectivity, a transient disconnection recovery mechanism reprocesses the lost data. Our experimental evaluation of Frontier shows that network path diversity improves throughput by 1.3×−2.8×for different IoT applications, while being resilient to intermittent network connectivity.

Edge computing is an increasingly popular paradigm, wherein computation comes closer to the sources of data. A key challenge for edge computing is discovering and utilizing the heterogeneous resources of the vast number of mobile devices at the network edge. Mobile edge devices hide behind private networks, they are mobile and their owners hesitate to share them due to privacy considerations. We propose Kinaara a framework for discovering and allocating collective resources for edge computing applications. First, Kinaara uses a multi-tier architecture to organize geographically proximal edge devices in clusters and provide their resources via trusted mediator entities. Second, it uses a novel resource representation to name and encode devices in terms of the resources advertised by their users. Third, it uses a novel distributed indexing scheme to organize devices in a proximal cluster on a ring logical structure based on their resource similarity. Our extensive experimental evaluation on a large Wi-Fi mobility dataset of 150K users and 345 APs show that compared to existing approaches Kinaara reduces resource discovery overhead by up to 70% and is robust to device mobility.

We consider the problem of proactive retention aware caching in a heterogeneous wireless edge network consisting of mobile users connected to a server and associated to one or more edge caches. Our goal is to design a caching policy that minimizes the sum of content storage costs and server access transmissions costs over two design variables: the retention time of each cached content and the probability that a user routes content requests to its associated caches. We develop a model that captures multiple aspects such as cache storage costs and several capabilities of modern wireless technologies, such as server multicast/unicast transmissions, device multipath routing, and cache access constraints. We formulate the problem of Proactive Retention Routing Optimization (PRRO) as a non-convex, non-linear mixed-integer program. We prove that it is NP-Hard under both multicast/unicast modes, even when the caches have a large capacity, and develop a greedy algorithm that has provable performance bounds. Finally, we propose a heuristic for the capacitated cache case that has low computational complexity. Systematic evaluations including real data sets demonstrate the effectiveness of our approach, compared to the existing caching schemes.

In-network content caching has been deployed in both the Internet and cellular networks to reduce content-access delay. We investigate the problem of developing optimal joint routing and caching policies in a network supporting in-network caching with the goal of minimizing expected content-access delay. Here, needed content can either be accessed directly from a back-end server (where content resides permanently) or be obtained from one of multiple in-network caches. To access content, users must thus decide whether to route their requests to a cache or to the back-end server. In addition, caches must decide which content to cache. We investigate two variants of the problem, where the paths to the back-end server can be considered as either congestion-sensitive or congestion-insensitive, reflecting whether or not the delay experienced by a request sent to the back-end server depends on the request load, respectively. We show that the problem of optimal joint caching and routing is NP-complete in both cases. We prove that under the congestion-insensitive delay model, the problem can be solved optimally in polynomial time if each piece of content is requested by only one user, or when there are at most two caches in the network. We also identify the structural property of the user-cache graph that makes the problem NP-complete. For the congestion-sensitive delay model, we prove that the problem remains NP-complete even if there is only one cache in the network and each content is requested by only one user. We show that approximate solutions can be found for both cases within a $(1-1/e)$ factor from the optimal, and demonstrate a greedy solution that is numerically shown to be within 1% of optimal for small problem sizes. Through trace-driven simulations, we evaluate the performance of our greedy solutions to joint caching and routing, which show up to 50% reduction in average delay over the solution of optimized routing to least recently used caches.

Emerging mobile applications involve continuous sensing and complex computations on sensed data streams. Examples include cognitive apps (e.g., speech recognition, natural language translation, as well as face, object, or gesture detection and recognition) and anticipatory apps that proactively track and provide services when needed. Unfortunately, today's mobile devices cannot keep pace with such apps, despite advances in hardware capability. Traditional approaches address this problem by computation offloading. One approach offloads by sending sensed streams to remote cloud servers via cellular networks or to cloudlets via Wi-Fi, where a clone of the app runs [2, 3, 4]. However, cloudlets may not be widely deployed and access to cloud infrastructure may yield high network delays and can be intermittent due to mobility. Morever, users might hesitate to upload private sensing data to the cloud or cloudlet. A second approach offloads to accelerators by rewriting code to use DSP or GPU within mobile devices. However, using accelerators requires substantial programming effort and produces varied benefits for diverse codes on heterogeneous devices.

Mobile edge clouds (MECs) are small cloud-like infrastructures deployed in close proximity to users, allowing users to have seamless and low-latency access to cloud services. When users move across different locations, their service applications often need to be migrated to follow the user so that the benefit of MEC is maintained. In this paper, we propose a layered framework for migrating running applications that are encapsulated either in virtual machines (VMs) or containers. We evaluate the migration performance of various real applications under the proposed framework.

Federated stream processing systems, which utilise nodes from multiple independent domains, can be found increasingly in multi-provider cloud deployments, internet-of-things systems, collaborative sensing applications and large-scale grid systems. To pool resources from several sites and take advantage of local processing, submitted queries are split into query fragments, which are executed collaboratively by different sites. When supporting many concurrent users, however, queries may exhaust available processing resources, thus requiring constant load shedding. Given that individual sites have autonomy over how they allocate query fragments on their nodes, it is an open challenge how to ensure global fairness on processing quality experienced by queries in a federated scenario.

We investigate the problem of optimal request routing and content caching in a heterogeneous network supporting in-network content caching with the goal of minimizing average content access delay. Here, content can either be accessed directly from a back-end server (where content resides permanently) or be obtained from one of multiple in-network caches. To access a piece of content, a user must decide whether to route its request to a cache or to the back-end server. Additionally, caches must decide which content to cache. We investigate the problem complexity of two problem formulations, where the direct path to the back-end server is modeled as i) a congestion-sensitive or ii) a congestion-insensitive path, reflecting whether or not the delay of the uncached path to the back-end server depends on the user request load, respectively. We show that the problem is NP-complete in both cases. We prove that under the congestion-insensitive model the problem can be solved optimally in polynomial time if each piece of content is requested by only one user, or when there are at most two caches in the network. We also identify a structural property of the user-cache graph that potentially makes the problem NP-complete. For the congestion-sensitive model, we prove that the problem remains NP-complete even if there is only one cache in the network and each content is requested by only one user. We show that approximate solutions can be found for both models within a (1 - 1/e) factor of the optimal solution, and demonstrate a greedy algorithm that is found to be within 1% of optimal for small problem sizes. Through trace-driven simulations we evaluate the performance of our greedy algorithms, which show up to a 50% reduction in average delay over solutions based on LRU content caching.

Consider the problem of reliable multicast over a network in the presence of adversarial errors. In contrast to traditional network error correction codes designed for a given network capacity and a given number of errors, we study an arguably more realistic setting that prior knowledge on the network and adversary parameters is not available. For this setting we propose efficient and throughput-optimal error correction schemes, provided that the source and terminals share randomness that is secret form the adversary. We discuss an application of cryptographic pseudorandom generators to efficiently produce the secret randomness, provided that a short key is shared between the source and terminals. Finally we present a secure key distribution scheme for our network setting.

Network tomography aims to infer the individual performance of networked elements (e.g., links) using aggregate measurements on end-to-end paths. Previous work on network tomography focuses primarily on developing estimators using the given measurements, while the design of measurements is often neglected. We fill this gap by proposing a framework to design probing experiments with focus on probe allocation, and applying it to two concrete problems: packet loss tomography and packet delay variation (PDV) tomography. Based on the Fisher Information Matrix (FIM), we design the distribution of probes across paths to maximize the best accuracy of unbiased estimators, asymptotically achievable by the maximum likelihood estimator. We consider two widely-adopted objective functions: determinant of the inverse FIM (D-optimality) and trace of the inverse FIM (A-optimality). We also extend the A-optimal criterion to incorporate heterogeneity in link weights. Under certain conditions on the FIM, satisfied by both loss and PDV tomography, we derive explicit expressions for both objective functions. When the number of probing paths equals the number of links, these lead to closed-form solutions for the optimal design; when there are more paths, we develop a heuristic to select a subset of paths and optimally allocate probes within the subset. Observing the dependency of the optimal design on unknown parameters, we further propose an algorithm that iteratively updates the design based on parameter estimates, which converges to the design based on true parameters as the number of probes increases. Using packet-level simulations on real datasets, we verify that the proposed design effectively reduces estimation error compared with the common approach of uniformly distributing probes.

Contemporary wireless multihop networks operate much below their capacity due to the poor coordination among transmitting nodes. In this paper, we present XPRESS, a cross-layer backpressure architecture designed to reach the capacity of wireless multihop networks. Instead of a collection of poorly coordinated wireless routers, XPRESS turns a mesh network into a wireless switch. Transmissions over the network are scheduled using a throughput-optimal backpressure algorithm. Realizing this theoretical concept entails several challenges, which we identify and address with a cross-layer design and implementation on top of our wireless hardware platform. In contrast to previous work, we implement and evaluate backpressure scheduling over a TDMA MAC protocol, as it was originally proposed in theory. Our experiments in an indoor testbed show that XPRESS can yield up to 128% throughput gains over 802.11.

The design of efficient Demand Response (DR) mechanisms for the residential sector entails significant challenges, due to the large number of home users and the negligible impact of each of them on the market. In this paper, we introduce a hierarchical market model for the smart grid where a set of competing aggregators act as intermediaries between the utility operator and the home users. The operator seeks to minimize the smart grid operational cost and offers rewards to aggregators toward this goal. Profit-maximizing aggregators compete to sell DR services to the operator and provide compensation to end-users in order to modify their preferable consumption pattern. Finally, end-users seek to optimize the tradeoff between earnings received from the aggregator and discomfort from having to modify their pattern. Based on this market model, we first address the benchmark scenario from the point of view of a cost-minimizing operator that has full information about user demands. Then, we consider a DR market, where all entities are self-interested and non-cooperative. The proposed market scheme captures the diverse objectives of the involved entities and, compared to flat pricing, guarantees significant benefits for each. Using realistic demand traces, we quantify the arising DR benefits. Interestingly, users that are extremely willing to modify their consumption pattern do not derive maximum benefit.

A class of carrier sense multiple access (CSMA) protocols used in a broad range of wireless applications uses synchronized contention where nodes periodically contend at intervals of fixed duration. While several models exist for asynchronous CSMA contention used in protocols like IEEE 802.11 MAC, no model exists for synchronized CSMA contention that also incorporates realistic factors like clock drifts. In this paper, we introduce a model that quantifies the interplay of clock drifts with contention window size, control packet size, and carrier sense regulated by usage of guard time. Using a field programmable gate array (FPGA)-based MAC protocol implementation and controlled experiments on a wireless testbed, we evaluate the model predictions on the isolated and combined impact of these key performance factors to per-flow throughput and fairness properties in both single-hop and multihop networks. Our model and experimental evaluation reveal conditions on protocol parameters under which the throughput of certain flows can exponentially decrease; while at the same time, it enables solutions that can offset such problems in a predictable manner.

We perform an experimental characterization of an indoor MIMO system with directional antennas (our prototype multi-sector antennas). The study reveals that, even without antenna directivity gain, the directionality of signals changes the MIMO channel structure and provides a way to improve MIMO throughput performance. It also shows that it is sufficient for the improvement to consider only a small subset out of all possible antenna direction combinations. Finally, our study shows that it is possible to achieve both throughput gains and interference reduction, thus increasing network spatial reuse.

The IEEE 802.11n standard supports very high physical layer data rates using Multiple Input Multiple Output (MIMO) antenna technologies. Despite such high rates, High Definition (HD) video streaming is still challenging in WLAN deployments. In this paper, we show that the wireless channel probing overhead of existing 802.11n data rate adaptation mechanisms can be detrimental to HD video performance. We propose VARA, a Video-Aware Rate Adaptation protocol that addresses this problem by adapting the frequency and timing of wireless probing to both video encoding rate variations and wireless channel variations. In addition, VARA employs novel strategies that multiplex several Variable Bit Rate (VBR) HD video streams by minimizing their aggregate peak rate requirement. Our experimental evaluations for static and mobile scenarios in a MIMO 802.11n wireless testbed demonstrate the practical benefits of VARA over state-of-the-art 802.11n rate adaptation protocols.

Contemporary wireless multi-hop networks operate much below their capacity due to the poor coordination among transmitting nodes. In this paper we present XPRESS, a cross-layer backpressure architecture designed to reach the full capacity of wireless multi-hop networks. Instead of a collection of poorly coordinated wireless routers, XPRESS turns a mesh network into a wireless switch. Transmissions over the network are scheduled using a throughput-optimal backpressure algorithm. Realizing this theoretical concept entails several challenges, which we identify and address with a cross-layer design and implementation on top of our wireless hardware platform. In contrast to previous work, we implement and evaluate backpressure scheduling over a TDMA MAC protocol, as it was originally proposed in theory. Our experiments in an indoor testbed show that XPRESS can yield up to 128% throughput gains over 802.11.

Multi-User MIMO promises to increase the spectral efficiency of next generation wireless systems and is currently being incorporated in future industry standards. Although a significant amount of research has focused on theoretical capacity analysis, little is known about the performance of such systems in practice. In this paper, we present the design and implementation of the first multi-user beamforming system and experimental framework for wireless LANs. Using extensive measurements in an indoor environment, we evaluate the impact of receiver separation distance, outdated channel information due to mobility and environmental variation, and the potential for increasing spatial reuse. For the measured indoor environment, our results reveal that two receivers achieve close to maximum performance with a minimum separation distance of a quarter of a wavelength. We also show that the required channel information update rate is dependent on environmental variation and user mobility as well as a per-link SNR requirement. Assuming that a link can tolerate an SNR decrease of 3 dB, the required channel update rate is equal to 100 and 10 ms for non-mobile receivers and mobile receivers with a pedestrian speed of 3 mph respectively. Our results also show that spatial reuse can be increased by efficiently eliminating interference at any desired location; however, this may come at the expense of a significant drop in the quality of the served users.

802.11 wireless mesh networks are ubiquitous, but suffer from severe performance degradations due to poor synergy between the 802.11 CSMA MAC protocol and higher layers. Several solutions have been proposed that either involve significant modifications to the 802.11 MAC or legacy higher layer protocols, or rely on 802. MAC models seeded with off-line measurements performed during network downtime.

We introduce a measurement-based optimization framework for topology control in dense 802.11 networks using sectorized antennas. We first formulate a topology control optimization problem, where nodes activate their sectorized antenna patterns to minimize network interference and maximize network capacity. In contrast to previous approaches, our formulation is based on a physical interference model that relies on received signal strength (RSS) measurements on multiple antenna patterns of each link. We then introduce a distributed measurement protocol to measure RSS of these antenna patterns and a greedy distributed topology control protocol that uses this information to achieve topologies of minimal interference. The protocols are experimentally evaluated on a dense 802.11 wireless testbed. Extensive measurements show that the protocols operate very close to optimal and yield significant increase in network throughput compared to omni-directional antennas. These results hold for various traffic scenarios in both wireless LAN and mesh network configurations.

A class of CSMA protocols used in a broad range of wireless applications uses synchronized contention where nodes periodically contend at intervals of fixed duration. While several models exist for asynchronous CSMA contention used in protocols like IEEE 802.11 MAC, no model exists for synchronized CSMA contention that also incorporates realistic factors like clock drifts. In this paper, we introduce a model that quantifies the interplay of clock drifts with contention window size, control packet size, and carrier sense regulated by usage of guard time. Using an FPGA-based MAC protocol implementation and controlled experiments on a wireless testbed we evaluate the model predictions on the isolated and combined impact of these key performance factors to per-flow throughput and fairness properties in both single-hop and multi-hop networks. Our model and experimental evaluation reveal conditions on protocol parameters under which the throughput of certain flows can exponentially decrease; while at the same time, it enables solutions that can offset such problems in a predictable manner.

Sectorized antennas provide an attractive solution to increase wireless network capacity through higher spatial reuse. Despite their increasing popularity, the real-world performance characteristics of such antennas in dense wireless mesh networks are not well understood. In this demo, we demonstrate our multi-sector antenna prototypes and their performance through video streaming over an indoor wireless network in the presence of interfering nodes. We use our graphical tool to vary the sender, receiver, and interferer antenna configurations and the resulting performance is directly visible in the video quality displayed at the receiver.

Sectorized antennas can increase wireless network capacity through greater spatial reuse. Despite their increasing popularity, their real-world performance characteristics in dense wireless mesh networks are not well understood. This paper conducts a systematic experimental study on a mesh network testbed using commodity 802.11 hardware and multi-sector antennas.

We present the design, implementation, and evaluation of a Time Division Multiplex (TDM) MAC protocol for multi-hop wireless mesh networks using a programmable wireless platform. Extensive research has been devoted to optimal scheduling algorithms for multi-hop wireless networks assuming a perfect TDM MAC protocol. However, the problem of designing and implementing such a protocol has not received due attention. We introduce a design framework that addresses the three main challenges that comprise this problem: (i) How to calibrate and optimize the TDM MAC protocol parameters given a wireless platform, (ii) how to achieve network-wide synchronization with high accuracy, minimal overhead, and most importantly, bounded delay, and (iii) how to integrate the synchronization algorithm with the TDM MAC protocol state machine using minimal hardware resources. We apply our design framework to our platform and evaluate the resulting TDM MAC protocol through controlled experiments in a wireless mesh testbed. The results demonstrate the protocol's ability to provide fairness and graceful performance degradation under packet losses and multi-hop traffic patterns that arise in mesh network deployments.

We address the problem of congestion control in multi-radio, multi-channel, wireless mesh networks. Compared to its single radio counterpart for which solutions exist, this problem is significantly more complex because it requires the radio channel assignments and the traffic allocations per channel be jointly optimized. We address the problem by introducing a formulation that allows its decomposition in two subproblems: A congestion control subproblem for traffic allocation to a fixed channel assignment over a node path and a discrete combinatorial channel assignment subproblem. We solve the conditional congestion control subproblem by mapping it to an optimization problem of traffic distribution to a set of radio paths. The solution provides channel congestion information that is utilized to address the channel assignment subproblem. This leads to an iterative procedure which guarantees successive increases to overall network utilization. Compared to existing work on multi- radio, multi-channel mesh networks, we show that our approach can yield significant gains both in terms of network utilization and establishing fairness.

We present Cross-layer Unicast Transmission Time (X-UTT), a MAC-aware load-independent link cost metric for 802.11-based wireless mesh networks. X-UTT utilizes information acquired from a network-layer unicast probing system and a MAC-layer monitoring system. It is designed to capture the wireless link capacity and be independent of the load induced by self-interference and cross-interference in a mesh network. We present experiments that validate these two properties on our mesh network testbed. These properties can be further exploited in the design of stable path metrics and routing protocols for wireless mesh networks.

We address the problem of identifying high throughput paths in 802.11 wireless mesh networks. We introduce an analytical model that accurately captures the 802.11 MAC protocol operation and predicts both throughput and delay of multi-hop flows under changing traffic load or routing decisions. The main idea is to characterize each link by the packet loss probability and by the fraction of busy time sensed by the link transmitter, and to capture both intra-flow and inter-flow interference. Our model reveals that the busy time fraction experienced by a node, a locally measurable quantity, is essential in finding maximum throughput paths. Furthermore, metrics that do not take this quantity into account can yield low throughput by routing over congested paths or by filtering-out non-congested paths. Based on our analytical model, we propose a novel routing metric that can be used to discover high throughput path in a congested network. Using city-wide mesh network topologies we demonstrate that our model-based metric can achieve significant performance gains with respect to existing metrics.

We introduce a low-complexity distributed slotted MAC protocol that can support all feasible arrival rates in a wireless backhaul network (WBN). For arbitrary wireless networks, such a maximum throughput protocol has been notoriously hard to realize because even if global topology information is available, the problem of computing the optimal link transmission set at each slot is NP-complete. For the logical tree structures induced by WBN traffic matrices, we first introduce a centralized algorithm that solves the optimal scheduling problem in a number of steps at most linear in the number of nodes in the network. This is achieved by discovering and exploiting a novel set of graph-theoretical properties of WBN contention graph. Guided by the centralized algorithm, we design a distributed protocol where, at the beginning of each slot, nodes coordinate and incrementally compute the optimal link transmission set. We then introduce an algorithm to compute the minimum number of steps to complete this computation, thus minimizing the per-slot overhead. Using both analysis and simulations, we show that in practice our protocol yields low overhead when implemented over existing wireless technologies and significantly outperforms existing suboptimal distributed slotted scheduling mechanisms.

Multi-hop wireless networks employing random access protocols have been shown to incur large discrepancies in the throughputs achieved by the flows sharing the network. Indeed, flow throughputs can span orders of magnitude from near starvation to many times greater than the mean. In this paper, we address the foundations of this disparity. We show that the fundamental cause is not merely differences in the number of contending neighbors, but a generic coordination problem of CSMA-based random access in a multi-hop environment. We develop a new analytical model that incorporates this lack of coordination, identifies dominating and starving flows and accurately predicts per-flow throughput in a large-scale network. We then propose metrics that quantify throughput imbalances due to the MAC protocol operation. Our model and metrics provide a deeper understanding of the behavior of CSMA protocols in arbitrary topologies and can aid the design of effective protocol solutions to the starvation problem.

Existing multi-channel protocols have been demonstrated to significantly increase aggregate throughput compared to single-channel protocols. However, we show that despite such improvements in aggregate throughput, existing protocols can lead to flow starvation in a multi-hop network, a phenomenon that also occurs with single-channel protocols. In this paper, we devise Asynchronous Multi-channel Coordination Protocol (AMCP), a distributed medium access protocol that not only increases aggregate throughput, but more importantly, addresses the fundamental coordination problems that lead to starvation. Based on AMCP's counter-starvation mechanisms, we analytically derive and experimentally validate an ap-proximate lower bound on the throughput of any flow in an arbitrary topology. We also demonstrate that AMCP can deliver significantly higher per-flow throughput than both IEEE 802.11 and existing multi-channel solutions. In addition to its performance properties, AMCP is both simple in that it operates using the primitives of IEEE 802.11 DCF, and cost-effective in that it requires only a single half-duplex transceiver and no infrastructure support.

We present a novel framework for the provision of deterministic end-to-end bandwidth guarantees in wireless ad hoc networks. Guided by a set of local feasibility conditions, multi-hop sessions are dynamically offered allocations, further translated to link demands. Using a distributed TDMA protocol, nodes adapt to the demand changes on their adjacent links by local, conflict-free slot reassignments. As soon as the changes stabilize, the nodes must incrementally converge to a TDMA schedule that realizes the global link (and session) demand allocation. We first identify an inherent trade-off between the degree of topology control and fraction of feasible allocations that can be captured by the local conditions. We show that tree topologies can be maximally utilized in this respect and that a converging distributed link scheduling algorithm exists in this case. Decoupling end-to-end bandwidth allocation from link scheduling allows support of various end-to-end QoS objectives. Focusing on Available Bit Rate (ABR) service, we design an asynchronous distributed algorithm for sharing bandwidth to the sessions in a maxmin fair (MMF) manner. Finally, we present the implementation of this framework over Bluetooth, an existing wireless technology that enables the formation of ad hoc networks. This implementation is free of the usual restrictive assumptions of previous TDMA approaches: it does not require any a-priori knowledge on the number of nodes in the network nor even network-wide slot synchronization.

Bluetooth, a wireless technology based on a frequency-hopping physical layer, enables portable devices to form short-range wireless ad hoc networks. Bluetooth hosts are not able to communicate unless they have previously discovered each other through synchronization of their timing and frequency-hopping patterns. Thus, even if all nodes are within proximity of each other, only those nodes which are synchronized with the transmitter can hear the transmission. To support any-to-any communication, nodes must be synchronized so that the pairs of nodes, which can communicate with each other, form a connected graph. Using Bluetooth as an example, we first provide deeper insights into the issue of link establishment in frequency-hopping wireless systems. We then introduce an asynchronous distributed protocol that begins with nodes having no knowledge of their surroundings and terminates with the formation of a connected network topology satisfying all constraints posed by Bluetooth. An attractive protocol feature is its ease in implementation using the communication primitives offered by the Bluetooth Specification.

Caching is a popular mechanism for enhancing performance in various layers and applications of computer networking. We introduce both a model and algorithms for caching routing information in large, memory-limited wireless ad hoc networks. Each host can cache only a small fraction of the network and must rely on flooding to acquire information that has not been locally cached. To constrain flooding, the network uses a cooperative caching model where every node provides its route cache contents to others when they flood. Given the host memory capacity limitations, we are faced with the problem of allocating destinations to caches in an efficient manner. We propose the class of best state/best cost (BSBC) cooperative caching algorithms that aim to minimize the overall network search effort.

This paper proposes an algorithm for design and on the fly modification of the schedule of a wireless ad hoc network for provision of fair service guarantees under topological changes. The primary objective is to derive a distributed coordination method for schedule construction and modification for any wireless ad-hoc network operating under a schedule where transmissions at each slot are explicitly specified over a time period of length T. We first introduce a fluid model of the system where the conflict avoidance requirements of neighboring links are relaxed while the aspect of local channel sharing is captured. In this model we propose an algorithm where the nodes asynchronously re-adjust the rates allocated to their adjacent links using only local information. We prove that, from any initial condition, the algorithm finds the max-min fair rate allocation in the fluid model. Hence, if the iteration is performed constantly the rate allocation will track the optimal even in regimes of constant topology changes. Then we consider the slotted system and propose a modification method that applies directly on the slotted schedule, emulating the effect of the rate re-adjustment iteration of the fluid model. Through extensive experiments in networks with both fixed and time varying topologies we show that the latter algorithm achieves balanced rate allocations in the actual slotted system that are very close to the max-min fair rates. The experiments also show that the algorithm is very robust on topology variations, with very good tracking properties of the max-min fair rate allocation.

Wireless ad hoc networks have been a growing area of research. While there has been considerable research on the topic of routing in such networks, the topic of topology creation has not received due attention. This is because almost all ad hoc networks to date have been built on top of a single channel, broadcast based wireless media, such as 802.11 or IR LANs. For such networks the distance relationship between the nodes implicitly (and uniquely) determines the topology of the ad hoc network. Bluetooth is a promising new wireless technology, which enables portable devices to form short-range wireless ad hoc networks and is based on a frequency hopping physical layer. This fact implies that hosts are not able to communicate unless they have previously discovered each other by synchronizing their frequency hopping patterns. Thus, even if all nodes are within direct communication range of each other, only those nodes which are synchronized with the transmitter can hear the transmission. To support any-to-any communication, nodes must be synchronized so that the pairs of nodes (which can communicate with each other) together form a connected graph. Using Bluetooth as an example, this paper first provides deeper insights into the issue to link establishment in frequency hopping wireless systems. It then introduces the Bluetooth topology construction protocol (BTCP), an asynchronous distributed protocol for constructing scatternets which starts with nodes that have no knowledge of their surroundings and terminates with the formation of a connected network satisfying all connectivity constraints posed by the Bluetooth technology. To the best of our knowledge, the work presented in this paper is the first attempt at building Bluetooth scatternets using distributed logic and is quite "practical" in the sense that it can be implemented using the communication primitives offered by the Bluetooth 1.0 specifications.

Proximity awareness in Bluetooth technology is implemented via an asymmetric point to point "sender-receiver" protocol where "senders" are trying to discover "receivers" in the vicinity. This paper tries to shed some light on the link formation delay by first identifying the delay bottlenecks in the asymmetric neighborhood discovery process and then discussing the factors that affect certain parameter decisions. A symmetric technique for establishing ad hoc connectivity is introduced which imposes each node to alternate between the "sender" and "receiver" state in a random fashion. The results show that the connection establishment delay can be reduced if appropriate decisions are made in the choice of parameters.

This paper deals with robust speech recognition in the GSM mobile environment. Our focus is on the voice degradation due to the losses in the GSM coding scheme. Thus, we initially propose an experimental framework of network topologies that consists of various coding-decoding systems placed in tandem. After measuring the recognition performance for each of these network scenarios, we try to increase the recognition accuracy by using feature compensation and model adaptation algorithms. We first compare the different methods for all the network topologies assuming the topology is known. We then investigate the more realistic case, in which we do not know the network topology the voice has passed through. The results show that robustness can be achieved even in this case.