Multi-tenant GPU clusters are designed to concurrently run multiple distributed ML training workloads. However, frequent data transfers among GPUs via collective operations can slow down training, as collectives from different tenants compete for network bandwidth. Recent work (e.g., CASSINI) has considered collective coordination to prevent network contention, but primarily focused on static job-level optimizations at deployment time, oblivious to runtime network conditions and the specific traffic pattern of each workload. In this paper, we present Symphony, an application-layer solution that dynamically coordinates collective operations across tenants at runtime. Symphony integrates seamlessly with existing clusters with minimal modifications to the collective communication library and includes a lightweight online scheduling mechanism that requires no advance information about the workloads or their collectives. We evaluate Symphony using both a real GPU testbed implementation and trace-driven simulations. Specifically, using realistic ML workloads in our testbed, we observe improvements of up to 13.2% in average communication time and 9.6% in training time compared to state-of-the-art solutions.

As modern networks grow in scale and speed, sketch-based algorithms have become essential tools for accurate and low-overhead network monitoring. Existing solutions for sketch-based network monitoring assume that traffic rates in the network are fixed and known a priori. However, this assumption fails to reflect the real-world scenario of dynamic traffic rates, leading to degraded monitoring accuracy. In this paper, we introduce a novel approach for coordinated sketch placement on programmable network devices such as switches and SmartNICs without relying on the fixed traffic rate assumption. Instead, we consider scenarios with only statistical information about rates, such as their means and variances. To this end, we show that the problem can be formulated as a second-order optimization problem. Given the computational challenges of solving such optimization problems, we present an approximation technique to derive a linear formulation which can be solved efficiently even for large instances of the problem. Our evaluations using realistic workloads and network settings reveal that, by accounting for dynamic traffic rates, our approach can increase monitoring accuracy in the network by up to 2 x across different workloads compared to the existing solutions that do not explicitly consider these dynamics.

Traffic sampling has become an indispensable tool in network management. While there exists a plethora of sampling systems, they generally assume flow rates are stable and predictable over a sampling period. Consequently, when deployed in networks with dynamic flow rates, some flows may be missed or under-sampled, while others are over-sampled. This paper presents the design and evaluation of dSamp, a network-wide sampling system capable of handling dynamic flow rates in Software-Defined Networks (SDNs). The key idea in dSamp is to consider flow rate fluctuations when deciding on which network switches and at what rate to sample each flow. To this end, we develop a general model for sampling allocation with dynamic flow rates, and then design an efficient approximate integer linear program called APX that can be used to compute sampling allocations even in large-scale networks. To show the efficacy of dSamp for network monitoring, we have implemented APX and several existing solutions in ns-3 and conducted extensive experiments using model-driven simulations. Our results indicate that, by considering dynamic flow rates, APX outperforms the existing solutions by up to 10% in sampling more flows at a given sampling rate.

Decentralized federated learning (DFL) enables collaborative training of machine learning models without sharing sensitive data. As such, its application in vehicular networks has gained significant attention. At the core of DFL is the so-called model aggregation, in which each vehicle combines its locally trained model with those received from its neighboring vehicles to generate an updated model that, over time, converges to a global model shared by all vehicles. However, due to high mobility and wireless communication, vehicle-to-vehicle communication is lossy. As a result, a vehicle may receive its neighboring vehicle models only partially. A technical challenge in DFL is how to efficiently utilize such partial models to speed up model training without increasing the training overhead. In this paper, we present an Adaptive Model Aggregation (AMA) algorithm to address this challenge. Our algorithm runs asynchronously on each vehicle and uses a threshold to decide whether to use a partially received model for aggregation. We show that due to the mobility of vehicles, a static threshold is not sufficient and subsequently develop an algorithm based on the contextual multi-arm bandit theory to adaptively compute an optimal threshold for each vehicle based on the dynamics of the network. We evaluate the performance of AMA in realistic environments that include different mobility patterns. Our results show that AMA can decrease DFL aggregation overhead by 83% without reducing the training accuracy compared to non-adaptive aggregation.

Disaggregated Data Center (DDC) is a modern datacenter architecture that decouples hardware resources from monolithic servers into pools of resources that can be dynamically composed to match diverse workload requirements. While disaggregation improves resource utilization, it could negatively impact workload slowdown due to the latency of accessing disaggregated resources over the datacenter network. To this end, we consider CPU and memory disaggregation and conduct measurements to experimentally profile several popular datacenter workloads in order to characterize the impact of disaggregation on workload execution slowdown. We then develop a workload placement algorithm, called Iterative Rounding-based Placement (IRoP), that given a set of workloads, determines where to place each workload (i.e., on which CPU) and how much local and remote memory allocate to it. The key insight in designing IRoP is that the impact of remote memory latency on slowdown can be substantially masked by assigning workloads to higher-performing CPUs, albeit at the cost of higher energy consumption. As such, IRoP aims to find a workload placement that minimizes the DDC energy consumption while respecting a bounded slowdown for each workload. We provide extensive simulation results to demonstrate the flexibility of IRoP in providing a wide range of trade-offs between energy consumption and workload slowdown. We also compare IRoP with several existing baselines. Our results indicate that IRoP can reduce energy consumption and slowdown in the considered scenarios by up to 8% and 12%, respectively.

Virtual private clouds have become a huge trend because of their cost-efficiency. However, the complex and virtualized nature of clouds limits the ability of cloud tenants to pinpoint and amend performance degradation problems, such as packet drops. Existing monitoring systems are either designed for the physical network or insufficient to present the concrete reason for packet loss with low overhead. In this paper, we present a Packet Loss Diagnosis (PLD) system, a specific monitoring service designed to detect packet drops on cloud networks and report diagnosis information to tenants. PLD is based on the modern capabilities of P4 data plane programmable NICs and has a limited footprint in the network. It provides detailed information that enables tenants to locate and resolve their issues with respect to the abstraction of the services. It also meets the requirements of a monitoring system designed for large-scale multi-tenant clouds. We implemented the proposed scheme in P4 to demonstrate its viability and investigate its performance and overhead through extensive experiments and Mininet simulation. Our results show that PLD ensures full packet drop detection coverage and can notify tenants in real-time while imposing low overhead.

Edge computing provides computational resources in the vicinity of end-users to reduce delay compared to traditional remote clouds. However, the capacity of edge resources usually is not sufficient for the required computational demands. Therefore, it is necessary to design methods for employing these resources in an efficient manner. On the other hand, network function virtualization (NFV) is a promising solution to use the network resources in a more flexible way than traditional schemes. Although more focus has been on realization of NFV systems via virtual machines so far, recent studies show that container-based solutions can improve efficiency thanks to lightweight implementation and layered structure of containers. Nonetheless, to the best of our knowledge, there is no comprehensive study on the problem of orchestrating services composed of a chain of containerized network functions in edge networks. In this paper, we consider this scenario when service requests are submitted to the system and address important aspects of this problem such as downloading and sharing container layers and steering traffic among network functions. We present the formulation of the problem as an integer linear program (ILP) and prove its NP-hardness. Then, to handle this problem, we propose RCCO, a polynomial-time algorithm based on ideas from deterministic and randomized rounding framework. Our results from extensive evaluations show that the bandwidth consumption of the proposed algorithm compared to the optimal algorithm is higher by only about 4% while it can outperform baselines from literature by more than 37%.

As the scale and speed of modern networks continue to increase, traffic sampling has become an indispensable tool in network management. While there exist a plethora of sampling solutions, they either provide limited flow visibility or have poor scalability in large networks. This paper presents the design and evaluation of FlowShark, a high-visibility per-flow sampling system for Software-Defined Networks (SDNs). The key idea in FlowShark is to separate sampling decisions on short and long flows, whereby sampling short flows is managed locally on edge switches, while a central controller optimizes sampling decisions on long flows. To this end, we formulate flow sampling as an optimization problem and design an online algorithm with a bounded competitive ratio to solve the problem efficiently. To show the feasibility of our design, we have implemented FlowShark in a small OpenFlow network using Mininet. We present experimental results of our Mininet implementation as well as performance benchmarks obtained from packet-level simulations in larger networks. Our experiments with a machine learning based Traffic Classifier application show up to 27% and 19% higher classification recall and precision, respectively, with FlowShark compared to existing sampling approaches.

This paper introduces Traffic Encoding Matrices (TEMs) as an alternative to traditional Traffic Matrices (TMs) for representing network traffic demands. While TMs only capture average demand information, TEMs are designed to capture distributional demand information by learning representations whose variations capture most of the structure of the distribution of demands. We present a practical approach based on off-the-shelf neural autoencoders to efficiently construct TEMs at the edge of the network. We then present the design and evaluation of NeuroTE, a DRL-based framework for delay-aware traffic engineering in SD-WANs using TEMs. Using real traffic traces, we present experimental results to demonstrate the advantages of using TEMs instead of TMs in traffic engineering. Our results show that, when traffic demands are dynamic, TEM-based control leads to: 1) improved network performance, and 2) faster convergence to the optimal solution compared to TM-based control using exactly the same DRL control algorithm.

The Controller Area Network (CAN) bus has been a widely implemented standard for in-vehicle communication between vehicle subsystems. However, since CAN was never designed with a focus on security, attackers can exploit the lack of message authentication in CAN to inject crafted malicious payloads to disable critical systems onboard the vehicle. While previous works in literature focus on detecting deviations in the normal behavior of the bus, they merely focus on individual sensors. Hence they fail to identify stealthy attacks that do not cause individual sensors to deviate substantially from their expected behavior but still have a significant impact on the bus state. Further, such approaches often impose a computational strain on the deployed system due to the high magnitude of consumed resources at run-time. To this end, we propose CANLite, a lightweight anomaly detection system utilizing multitask learning to detect such subtle deviations while significantly reducing the memory footprint. We trained and evaluated our model against a state-of-the-art baseline approach. Our results indicate that CANLite reduces the memory footprint by 50% while still achieving the same level of detection performance as the baseline.

The fundamental limits of covert communication, where a message is sent from transmitter Alice to intended recipient Bob without detection by an attentive adversary warden Willie, has been considered extensively in recent years at the physical layer. The covert throughput depends critically on the warden's understanding of the characteristics of the radio environment and the type of receiver that he employs, and, as expected, the throughput increases when the warden has some uncertainty about the environment or some non-idealities in his receiver. In this paper, we consider the covert throughput when the adversary is only able to observe the medium access control (MAC) layer in a wireless communication system. In particular, given that the system has a rate of$\lambda$packets per slot transmitted over$n$channels by allowable system users, we study the allowable rate$\lambda _a$by covert users while maintaining covertness from an attentive warden observing the channel status in a slotted ALOHA system. We characterize performance for wardens with different abilities to discern the number of packets on a given channel, ranging from simple receivers that detect only whether there was a packet present to complicated receivers that can determine the number of packets involved in any collision, and also consider intended recipients Bob with varying abilities to perform multi-packet reception. In contrast to prior work in covert communications, the application considered motivates the consideration of results for finite (often small) observation vector lengths$n$at the adversary. Numerical results are provided both to illustrate the tightness of our achievability regions for the packet transmission rate of the covert transmitters and to demonstrate the covert throughput of the system as a function of$\lambda$and$n$.

Efficient and consistent update of the network routing rules is a challenging task that significantly affects the performance, correctness, and security of Software-Defined Networks (SDN). In this work, we consider the problem of minimizing the makespan of updating the routing rules in SDNs, while guaranteeing three crucial consistency requirements: (1) WayPoint Enforcement, (2) Loop Freedom, and (3) Conflict Freedom. This problem is known to be NP-hard, and thus we focus on designing approximate algorithms that run in polynomial time without incurring TCAM storage overhead. To compute consistent rule-update schedules, we propose two algorithms, calledTimeXandRMS.TimeXemploys the solution of a linear program (LP) to address the makespan minimization goal systematically.RMSis an LP-independent heuristic that provides higher scalability. We demonstrate and utilize a property of rule-updates, called reversibility, to reduce the makespan in RMS. Extensive simulations show that our algorithms reduce the makespan by 2% to 18% and attain a 4.9$\times$speedup compared to previous studies. Moreover, Mininet experiments reveal that the proposed algorithms can mitigate the transient congestion caused by conflicting flows.

As network virtualization becomes ubiquitous, legacy hardware-based traffic monitoring systems are no longer viable for dynamic traffic inspection at arbitrary locations in virtual networks. In this paper, we present the design and evaluation of Open Virtual Tap (OVT), a software-defined solution to replace hardware taps for traffic monitoring in OpenFlow virtual networks by utilizing mirroring capabilities of OpenFlow switches. The key idea behind OVT is the joint configuration of all switches in the substrate physical network in order to efficiently mirror flows from all virtual networks. We show that such a design avoids inefficiencies that result from existing software-based traffic mirroring solutions in which each virtual network configures its own switches independently of other virtual networks. We evaluate OVT using model-driven simulations as well as Mininet experiments with realistic applications for intrusion detection and video telephony analysis. Specifically, in our experiments, we observe that OVT can achieve up to 20% improvement in flow coverage compared to existing traffic mirroring approaches.

Covert communication considers the ability of transmitter Alice to communicate reliably to intended receiver Bob without being detected by adversary warden Willie. One collection of approaches to covert signaling is for Alice to alter the state of a system in such a way that the altered state conveys information to Bob. Motivated by recent work on the foundations of covert communications that has largely considered the physical layer, we provide a fundamental characterization of one approach to covert signaling via activity: employing a codebook pre-shared with Bob, Alice encodes a message by selecting from the codebook the appropriate pattern of slots to insert innocuous packets into a slotted ALOHA system in the presence of other users. The intended recipient Bob detects patterns in the activity of the slotted ALOHA system to determine which codeword was sent. We provide a fundamental analysis of the performance of such a system under a covertness constraint. First, we consider signaling schemes derived specifically for the proposed channel when Bob or Willie has various abilities to discern the number of packets in a given slot. Given the challenges in such design, we next recognize that techniques from optical communications, although designed for a different channel, can potentially be employed and thus yield a large class of schemes that provide lower bounds on the achievable rate. Numerical results are provided to support the analytical development and to demonstrate the potential of covert signaling through such an approach.

In Mobile Edge Computing (MEC), the network's edge is equipped with computing and storage resources in order to reduce latency by minimizing communication with remote clouds. However, the available computing capacity at the edge is limited compared to that of remote clouds. A promising solution for efficient utilization of the limited capacity at the edge is fine-grained processing of user demands via Virtual Network Functions (VNFs). In this approach, user service demands are expressed as Service Function Chains (SFCs), which are composed of virtual network functions. Such service composition allows constituent VNFs to be flexibly deployed at the edge or in the cloud such that the service latency is minimized. The increasing number of users, however, challenges the scalability of system-managed SFC orchestration. To address this problem, we propose a user-managed online SFC orchestration framework at the edge of the network, called CHANGE, that minimizes service latency by jointly considering the effect of user mobility, edge capacity and service migration. We first present the theoretical foundations of CHANGE and then evaluate its performance via model-driven simulations and realistic Mininet-WiFi emulations. Our results show that CHANGE can improve latency performance by nearly 20% compared to other approaches.

This paper considers the problem of joint radio and computing resource allocation in Cloud Radio Access Network (C-RAN) architecture. We develop a resource allocation scheme to maximize weighted sum-rate of the system, while minimizing total power consumption. For power consumption, we consider both static and dynamic power consumption in Remote Radio Heads (RRHs), fronthaul links, and Base Band processing Units (BBUs). Our model considers quality of service requirements, fronthaul capacity, maximum transmission power, and computing capacity constraints in a comprehensive formulation. The joint resource allocation problem is non-convex, which is shown to be NP-hard, and thus we apply a number of techniques to convexify the problem. Then, using the Karush-Kuhn-Tucker (KKT) conditions, we show that the problem can be decomposed into two sub-problems that can be efficiently solved using an iterative Quadratically Constrained Quadratic Program (QCQP) and a bin packing algorithm, respectively. The performance of the proposed scheme is evaluated through simulation studies, which shows the proposed scheme outperforms the existing approaches in BBU minimization, total power consumption, and system utility which is defined as the weighted sum-rate minus power consumption.

With widespread deployment of virtualization technologies in datacenter networks, traditional tools used for network monitoring, such as hardware taps, become unfit. This is due to the inability of hardware solutions for dynamic deployment and virtual network monitoring. This paper presents the design and evaluation of SoftTap, a scalable alternative to hardware taps which is capable of operating over both physical and virtual switches. SoftTap is based on port and flow mirroring capabilities of commodity OpenFlow switches and is not limited to a specific network architecture or topology. A key design challenge in SoftTap is the fast computation of switch mirroring configurations in large-scale deployments. Our design is based on novel polynomial time approximation algorithms that are shown to achieve bounded approximation ratios compared to optimal solutions. We evaluate SoftTap using model-driven simulations as well as realistic Mininet experiments. Specifically, our simulations consider large networks to show the scalability of SoftTap. Mininet experiments, on the other hand, consider its real-world utility by implementing an intrusion detection system (IDS) and a VoIP metering application on top of SoftTap. In our experiments, under SoftTap, IDS achieves up to 25% higher detection recall, while VoIP metering achieves up to 23% less packet loss compared to existing mirroring-based traffic monitoring approaches.

Virtual Network Embedding (VNE) is an essential component of network virtualization technology. Prior works on VNE mainly focused on resource efficiency and did not address the scalability as a first-grade objective. Consequently, the ever-increasing demand and size render them less-practical. The few existing designs for mitigating this problem either do not extend to multi-resource settings or do not consider the physical servers and network simultaneously. In this work, we develop GraphViNE, a parallelizable VNE solution based on spatial Graph Neural Networks (GNN) that clusters the servers to guide the embedding process towards an improved runtime and performance. Our experiments using simulations show that the parallelism of GraphViNE reduces its runtime by a factor of 8. Also, GraphViNE improves the revenue-to-cost ratio by about 18%, compared to other simulated algorithms.

In LoRa, leading communication technology for the Internet of Things (IoT), the so-called Class A devices are proposed for applications that require low energy consumption. However, the MAC layer of Class A devices is based on pure ALOHA, which performs poorly when the network includes a large number of devices. In this paper, we propose a Lightweight Carrier Sensing (LSC) mechanism for LoRa end devices, which does not include back-off and, thus, results in negligible overhead on end devices. LCS is based on the Channel Activity Detection (CAD) procedure already implemented at the hardware level in all modems based on the standard LoRa chipset. We first theoretically analyze the benefits of LCS on a simplified LoRa network to understand its benefits over pure ALOHA. We present the design and implementation of the proposed LCS and provide measurement results to demonstrate its feasibility in real-world LoRa networks. We have also implemented LCS in a detailed custom-build LoRa simulator to study LCS impact on network energy consumption and scalability in large-scale LoRa networks. Our results show that not only LCS supports more end devices, but also results in significantly lower energy consumption compared to ALOHA, thus efficiently improving network scalability without additional complexity or overhead.

In network function virtualization, a service function chain (SFC) specifies a sequence of virtual network functions that user traffic has to traverse to realize a network service. The problem of SFC orchestration has been extensively studied in the literature. However, most existing works assume deterministic demands and resort to costly runtime resource reprovisioning to deal with dynamic demands. In this work, we formulate the deadline-aware co-located and geo-distributed SFC orchestration with demand uncertainty as robust optimization problems and develop exact and approximate algorithms to solve them. A key feature of our formulation is the consideration of end-to-end delay in service chains by carefully modeling load-independent propagation delay as well as load-dependent queueing and processing delays. To avoid frequent resource reprovisioning, our algorithms utilize uncertain demand knowledge to compute proactive SFC orchestrations that can withstand fluctuations in dynamic service demands. Extensive simulations are conducted to evaluate the performance of our algorithms in terms of ability to cope with demand fluctuations, scalability, and relative performance against other recent algorithms.

In content distribution networks, a key objective is the efficient utilization of the network that interconnects geographically distributed datacenters. This is a challenging problem due to vastly different characteristics and requirements of bulk and realtime transfers that share the interconnection network. Bulk transfers aim at delivering a copy of a usually large file to multiple datacenters before a deadline, while realtime transfers are absolutely delay-intolerant with unsteady and dynamic demands. In this paper, we consider the problem of multicasting deadline-critical bulk transfers in an inter-datacenter network in the presence of unknown and fluctuating demand by realtime transfers. Specifically, we develop a joint admission control and routing algorithm called PMDx, which anticipates future realtime demands and proactively reserves just the right amount of network resources in order to serve future realtime transfers without adversely affecting network utilization or bulk transfer deadlines. We show that the PMDx algorithm is a 2/δ-approximation with probability 1 - ϵ, and runs in polynomial time proportional to ln(1/ϵ)/(1 - δ)2, for 0 < δ,ϵ < 1. We also provide extensive model-driven simulation results to study the behaviour of our algorithms in real world network topologies. Our results confirm that PMDx is very close to the optimal, and improves the utilization of the network by 14% compared to a recently proposed algorithm.

In network function virtualization, network services are implemented as service function chains (SFCs). An extensive body of work exists on SFC orchestration, although a vast majority of them consider reactive algorithms that reprovision resources in response to service demand fluctuations. As such, they result in unpredictable and often significant delays that negatively affect the performance of delay-sensitive SFCs. In this paper, we consider proactive SFC orchestration and develop exact and approximate algorithms that perform well under general service demands without requiring frequent resource reprovisioning. Specifically, we first formulate SFC orchestration with deadline as a mixed integer non-linear program and show that it can be reduced to a second-order cone program, which can be solved using standard optimization software, albeit for small problem instances. We then design an approximate algorithm for large problem instances by applying iterative rounding and variable fixing techniques to the exact problem formulation. We present extensive model-driven simulation results to study the behavior of our algorithms in small and large problem instances and demonstrate their ability to achieve any desired provisioning-reprovisioning trade-off. We further compare the performance of our approximate algorithm against two recently proposed algorithms called FFCA and MaxZ.

Covert communications, where a transmitter Alice wishes to hide the presence of her transmitted signal from a watchful adversary Willie, has been considered extensively in recent years. Those investigations have generally considered physical-layer models, where the adversary has access to a sophisticated (often optimal) receiver to determine whether a transmission has taken place, and have addressed the question of what rate can information be communicated covertly. More recent investigations have begun to consider the change in covert rate when Willie has uncertainty about the physical layer environment. Here, we move up the protocol stack to consider the covert rate when Willie is watching the medium-access control (MAC) layer in a network employing a random access MAC such as slotted ALOHA. Based on the rate of collisions and potentially the number of users involved in those collisions, Willie attempts to determine whether unauthorized (covert) users are accessing the channel. In particular, we assume different levels of sophistication in Willie's receiver, ranging from a receiver that only can detect whether there was a collision or not, to one that can always tell exactly how many packets were on the channel in the random access system. In each case, we derive closed-form expressions for the achievable covert rates in the system. The achievable rates exhibit significantly different behavior than that observed in the study of covert systems at the physical layer.

This paper considers the problem of mapping virtual links to physical network paths, referred to as Virtual Link Embedding (VLE), under the condition that bandwidth demands of virtual links are uncertain. To realize virtual links with predictable performance, the mapping is required to guarantee a bound on the congestion probability of the physical paths that embed the virtual links. To this end, we consider a general uncertainty model in which bandwidth demands of virtual links are expressed by random variables for which only the mean and variance (or a range) are known. We formulate the VLE problem as a nonlinear optimization program and design an algorithm called Equal Partition VLE (epVLE) to solve the problem by employing an approximate formulation that results in a second-order cone program (SOCP) that can be solved efficiently even for large networks. We then provide simulation results as well as model-driven and trace-driven experimental results from an SDN testbed to show the utility and efficiency of the epVLE algorithm in various network scenarios. We apply epVLE to commonly studied small networks as well as randomly generated large networks. Our results show that epVLE is able to satisfy the required link congestion constraint, and that it produces results that are very close to those obtained from the exact optimization model.

This paper considers energy management on LTE-enabled Internet of Things (IoT) devices. A characteristic feature of IoT applications is the periodic generation of small messages, whose transmission over LTE is highly energy inefficient. In this paper, we consider application message bundling to alleviate the effect of short message transmissions on energy consumption. Specifically, we model the interplay between energy consumption and the extended DRX mechanism introduced in LTE to deal with IoT traffic. We formulate bundling as a cost minimization problem and develop an online algorithm to solve the problem. Detailed analysis shows that, depending on DRX and application parameters, our algorithm is 1, 2, or 4-competitive with respect to the optimal offline algorithm that knows the entire sequence of application messages a priori. We evaluate the performance of the proposed algorithm and the accuracy of our analysis in a range of realistic scenarios using both model-driven simulations and real experiments on an IoT testbed. Our results show that, i) depending on application requirements, energy savings ranging from zero to about 100% can be achieved using our algorithm, and ii) ignoring DRX could significantly overestimate or underestimate energy consumption.

LoRa is a leading Low-Power Wide-Area Network (LPWAN) technology for Internet of Things (IoT). While LoRa networks are rapidly being deployed around the world, it is important to understand the capabilities and limitations of this technology in terms of its throughput, coverage and scalability. Using a combination of real-world measurements and high fidelity simulations, this paper aims at characterizing the performance of LoRa. Specifically, we present and analyze measurement data collected from a city-wide LoRa deployment in order to characterize the throughput and coverage of LoRa. Moreover, using a custom-built simulator tuned based on our measurement data, we present extensive simulation results in order to characterize the scalability of LoRa under a variety of traffic and network settings. Our measurement results show that as few as three gateways are sufficient to cover a dense urban area within an approximately 15 Km radius. Also, a single gateway can support as many as 105end devices, each sending 50 bytes of data every hour with negligible packet drops. On the negative side, while a throughput of up to 5.5 Kbps can be achieved over a single 125 KHz channel at the physical layer, the throughput achieved at the application layer is substantially lower, less than 1 Kbps, due to the network protocols overhead.

In the last decade, underwater wireless sensor networks (UWSNs) have attracted a lot of attention from the research community thanks to their wide range of applications that include seabed mining, military and environmental monitoring. With respect to terrestrial networks, UWSNs pose new research challenges such as the three-dimensional node deployment and the use of acoustic signals. Despite the large number of routing protocols that have been developed for UWSNs, there are very few analytical results that study their optimal configurations given the system's parameters (density of the nodes, frequency of transmission, etc.). In this paper, we make one of the first steps to cover this gap. We study an abstraction of an opportunistic routing protocol and derive its optimal working conditions based on the network characteristics. Specifically, we prove that using a depth threshold, i.e., the minimum length of one transmission hop to the surface, is crucial for the optimality of opportunistic protocols and we give a numerical method to compute it. Moreover, we show that there is a critical depth threshold above which no packet can be transmitted successfully to the surface sinks in large networks, which further highlights the importance of properly configuring the routing protocol. We discuss the implications of our results and validate them by means of stochastic simulations on NS3.

In covert communication, Alice tries to communicate with Bob without being detected by a warden Willie. When the distance between Alice and Bob becomes large compared with the distance between Alice and Willie(s), the performance of covert communication will be degraded. In this case, multi-hop message transmission via intermediate relays can help to improve the performance. Hence, in this paper, multi-hop covert communication over a moderate size network and in the presence of multiple collaborating Willies is considered. The relays can transmit covertly using either a single key for all relays or different independent keys at the relays. For each case, we develop efficient algorithms to find optimal paths with maximum throughput and minimum end-to-end delay between Alice and Bob. As expected, employing multiple hops significantly improves the ability to communicate covertly versus the case of a single-hop transmission. Furthermore, at the expense of more shared key bits, analytical results and numerical simulations demonstrate that the multi-hop covert communication with different independent keys at the relays has better performance than the multi-hop covert communication with a single key.

To reduce the energy consumption of a smartphone, multiple data transfer requests from applications can be bundled together and granted at once in order to reduce the time the radio interface is on. The side effect of bundling is the increased delay experienced by mobile applications. While several bundling algorithms have been proposed in the literature, a general and systematic solution to balance the energy-delay tradeoff is missing. In this paper, we formulate bundling as a cost minimization problem, in which the tradeoff between energy and delay is captured by a cost function. We then propose an online algorithm for minimizing the bundling cost and show that the algorithm is 4-competitive with respect to the optimal offline algorithm that knows the entire sequence of data transfer requests a priori. We evaluate the performance of the proposed algorithm and the accuracy of our results in a range of realistic scenarios using both model-driven simulations and real experiments on a smartphone. Our results show that depending on the delay tolerance level of a user, energy savings ranging from zero (delay intolerant) to about 100% (delay tolerant) can be achieved using our algorithm.

This paper considers secure energy-efficient routing in the presence of multiple passive eavesdroppers. Previous work in this area has considered secure routing assuming probabilistic or exact knowledge of the location and channel-state-information (CSI) of each eavesdropper. In wireless networks, however, the locations and CSIs of passive eavesdroppers are not known, making it challenging to guarantee secrecy for any routing algorithm. We develop an efficient (in terms of energy consumption and computational complexity) routing algorithm that does not rely on any information about the locations and CSIs of the eavesdroppers. Our algorithm guarantees secrecy even in disadvantaged wireless environments, where multiple eavesdroppers try to eavesdrop each message, are equipped with directional antennas, or can get arbitrarily close to the transmitter. The key is to employ additive random jamming to exploit inherent non-idealities of the eavesdropper's receiver, which makes the eavesdroppers incapable of recording the messages. We have simulated our proposed algorithm and compared it with the existing secrecy routing algorithms in both single-hop and multi-hop networks. Our results indicate that when the uncertainty in the locations of eavesdroppers is high and/or in disadvantaged wireless environments, our algorithm outperforms existing algorithms in terms of energy consumption and secrecy.

In this paper, we develop and evaluate a distributed algorithm to efficiently balance the trade-off between network throughput and energy consumption in a heterogeneous cellular network. We formulate the problem as a joint optimization of base station activation, power control and user association. To solve the problem, which is a non-convex optimization problem, we design a self-optimizing algorithm based on Gibbs sampling in which each base station individually optimizes its configuration without the involvement of any central controller. In our algorithm, base stations only need to exchange information in a locally defined neighborhood, yet the network state eventually converges to the global optimal. Simulation results are also provided, which show that, i) the proposed algorithm indeed converges to a state that is close to optimal, and ii) by dynamically activating base stations, we see about 10% reduction in network energy consumption without penalizing the network throughput.

To stream video using HTTP, a client device sequentially requests and receives chunks of the video file from the server over a TCP connection. It is well-known that TCP performs poorly in networks with high latency and packet loss such as wireless networks. On mobile devices, in particular, using a single TCP connection for video streaming is not efficient, and thus, the user may not receive the highest video quality possible. In this paper, we design and analyze a system called ParS that uses parallel TCP connections to stream video on mobile devices. Our system uses parallel connections to fetch each chunk of the video file using HTTP range requests. We present measurement results to characterize the performance of ParS under various network conditions in terms of latency, loss rate and bandwidth. Given the limited communication and computational resources of mobile devices, we then focus on determining the minimum number of TCP connections required to achieve high utilization of the wireless bandwidth.

This paper studies the network-wide spectrum sharing problem in virtual cellular networks applicable to Cloud Radio Access Network architecture. Virtual wireless networks share network resources such as time-frequency resources on the same physical infrastructure. A critical problem is then the allocation of shared physical resources to the virtual networks so that the utilization of the resources is maximized. We formulate the problem as a linear integer maximization problem, which is shown to be NP-hard. We then develop a polynomial time heuristic algorithm called Non-balancing Spectrum Sharing (NSS), which is guaranteed to achieve a solution whose resource utilization approaches half of that of the optimal solution in the worst-case. Two additional heuristic algorithms are also proposed to improve the worst-case performance of NSS by enabling load balancing among adjacent base stations. We have simulated the proposed algorithms and the optimal algorithm under different network configurations. The simulation results confirm that i) NSS performs remarkably close to the optimal algorithm, and ii) the two other heuristic algorithms outperform NSS, and consequently are even closer to the optimal algorithm in the simulated scenarios.

The effectiveness and the simple implementation of physical layer jammers make them an essential threat for wireless networks. In a multihop wireless network, where jammers can interfere with the transmission of user messages at intermediate nodes along the path, one can employ jamming oblivious routing and then employ physical-layer techniques (e.g., spread spectrum) to suppress jamming. However, whereas these approaches can provide significant gains, the residual jamming can still severely limit system performance. This motivates the consideration of routing approaches that account for the differences in the jamming environment between different paths. First, we take a straightforward approach where an equal outage probability is allocated to each link along a path and develop a minimum energy routing solution. Next, we demonstrate the shortcomings of this approach and then consider the joint problem of outage allocation and routing by employing an approximation to the link outage probability. This yields an efficient and effective routing algorithm that only requires knowledge of the measured jamming at each node. Numerical results demonstrate that the amount of energy saved by the proposed methods with respect to a standard minimum energy routing algorithm, especially for parameters appropriate for terrestrial wireless networks, is substantial.

In this paper, we study resource reservation in virtual wireless networks with the aim of minimizing the operational cost. With this regard, the main constraint facing the operator is that only limited information about future traffic demand is typically available to the operator. To address this issue, we investigate reservation policies that are robust to the worst-case traffic demand which fits the available information i.e., the policies that minimize the worst-case expected operational cost. The problem is formulated for several resource reservation options that are commonly offered in practice. For each case, convexity of the problem is discussed and the its dual form is presented as a semidefinite program. While, semidefinite programs can be solved in polynomial time, the optimal closed-form reservation policies are obtained for several practical cases. Moreover, the worst-case cost of these policies are analytically compared to the expected cost of the algorithm that has full knowledge of the future demand. The theoretical analysis is supplemented with numerical results to demonstrate the behavior of our algorithms in terms of cost in some example traffic scenarios.

To load a webpage, a web browser first downloads the base HTML file of the page in order to discover the list of objects referenced in the page. This process takes roughly one round-trip time and constitutes a significant portion of the web browsing delay on mobile devices as wireless networks suffer from longer transmission and access delays compared to wired networks. In this work, we propose a solution for eliminating this initial delay, which is transparent to end systems, does not require modifying HTTP, and is well suited for web browsing on mobile devices. Our solution, called WebPro, relies on a network proxy that builds an up-to-date database of resource lists for the websites visited frequently by network users. The proxy resides in the wired part of the network, and hence can afford to pro-actively build and refresh the resource list database periodically. When a request for a webpage comes to the proxy, it simultaneously fetches the base HTML and all referenced objects required to render the webpage using the corresponding resource list stored in the local database. We have built a working prototype of WebPro and have conducted live experiments over WiFi and LTE networks. Our results show an average of 26% reduction in page load time for a mix of popular web sites chosen from categories such as news, sports and shopping. Moreover, in comparison to another best known proxy-based solution, WebPro provides delay reductions ranging from 5% to 51% for a variety of web sites.

In this work, using ns-3 and different mobility models, we simulate realistic LTE network scenarios to study the effect of handover on two popular schedulers, namely the Proportional Fair (PF) and Max Weight (MW) scheduler. The performances of these schedulers are widely studied in the literature via simulation and mathematical analysis in the absence of handovers. Specifically, it has been shown that MW is throughput optimal among all scheduling policies that stabilize the system in the sense of bounding the user queues. In our experiments, however, we observe that such general conclusions may not be accurate in the presence of mobile users that hand over across multiple cells. To this end, we show that: i) MW achieves higher throughput than PF when users are confined to a single cell, but ii) when there is handover in the network across multiple cells, PF achieves a throughput similar to that of MW, and in some cases even slightly outperforms MW. Furthermore, these observations are consistent across a wide range of network scenarios in terms of round-trip delay, buffer size and channel fading.

This paper studies the problem of minimum delay scheduling in wireless networks with multi-packet transmission capability. Specifically, we assume that the network employs superposition coding at the physical layer in order to implement multi-packet transmission. While most studies on superposition coding assume that unbounded number of packets can be coded together, physical and MAC layer limitations restrict the number of concurrent packets in a transmission set. Taking this constraint into consideration, we formulate the minimum delay scheduling as a combinatorial optimization problem and study its computational complexity under different transmission set sizes. We show that, when the transmission set size is limited to 2 packets, the problem can be solved optimally in polynomial time. Moreover, while the complexity of the problem for larger transmission set sizes is unknown, we present close-to-optimal heuristic algorithms that compute efficient solutions for the problem in polynomial time. Numerical results are also presented to study the efficiency and utility of the presented scheduling algorithms. Our results show that the heuristic algorithms are highly efficient, achieving delays that are less than 2% away from the optimal values.

There is a rich recent literature on information-theoretically secure communication at the physical layer of wireless networks, where secret communication between a single transmitter and receiver has been studied extensively. In this paper, we consider how single-hop physical layer security techniques can be extended to multi-hop wireless networks. We show that guaranteed security can be achieved in multi-hop networks by augmenting physical layer security techniques, such as cooperative jamming, with the higher layer network mechanisms, such as routing. Specifically, we consider the secure minimum energy routing problem, in which the objective is to compute a minimum energy path between two network nodes subject to constraints on the end-to-end communication secrecy and goodput over the path. This problem is formulated as a constrained optimization of transmission power and link selection, which is proved to be NP-hard. Nevertheless, we show that efficient algorithms exist to compute both exact and approximate solutions for the problem. In particular, we develop an exact solution of pseudo-polynomial complexity, as well as an ε-optimal approximation of polynomial complexity. Simulation results are also provided to show the utility of our algorithms and quantify their energy savings compared to a combination of (standard) security-agnostic minimum energy routing and physical layer security. In the simulated scenarios, we observe that, by jointly optimizing link selection at the network layer and cooperative jamming at the physical layer, our algorithms reduce the network energy consumption by half.

Dynamic particle swarm optimization (PSO) problems are generally characterized by the exhaustively examined issues of the changing location of optima, the changing fitness of optima, and measurement noise/errors. However, the challenging issue of continuously changing problem dimensionality has not been similarly examined. Given that in anytime dynamic resource allocation it is necessary to maintain a high quality solution, we argue that, rather than restarting the PSO algorithm, a more appropriate approach is to design an algorithm that robustly handles changing problem dimensionality. Specifically, we propose an indirect particle encoding scheme specifically designed for a dynamic multi-dimensional PSO algorithm for proportional fair constrained resource allocation. This PSO algorithm is implemented for the proportional fair allocation of power and users to channels within a simulation of an Orthogonal Frequency-Division Multiple Access (OFDMA) wireless network with mobile users switching cells as they traverse the simulation environment. The proposed PSO algorithm is evaluated using simulations, which demonstrate the ability of the proposed indirect encoding scheme to maximize the overall proportional fair optimization goal, without unfairly penalizing the individual components of the solution related to newly introduced problem dimensions.

The effectiveness and straightforward implementation of physical layer jammers make them an essential security threat for wireless networks. In this paper, reliable communication in a wireless multi-hop network in the presence of multiple malicious jammers is considered. Since energy consumption is an important issue in wireless ad hoc networks, minimum energy routing with and without security constraints has received significant attention in the literature; however, energy-aware routing in the presence of active adversary (jammers) has not been considered. We propose an efficient algorithm for minimum energy routing between a source and a destination in the presence of both static and dynamic malicious jammers such that an end-to-end probability of outage is guaranteed. The percentage of energy saved by the proposed method with respect to a shortest path routing benchmark is evaluated. It is shown that the amount of energy saved, especially in terrestrial wireless networks with path-loss exponents greater than two, is substantial.

Dynamic base station activation and transmission power control are the key mechanisms to reduce energy consumption in cellular networks. In this work, we consider employing these methods for the purpose of minimizing long-term energy cost in cellular networks. Based on the two-timescale Lyapunov optimization technique, we formulate an online control problem to ensure achieving minimal energy cost while stabilizing use queues. While the control problem can be solved in a centralized manner, we limit our attention to distributed solutions which are highly attractive in the design of next generation mobile networks. Due to the combinatorial nature of the problem and the complex relation of achievable rates to interfering signals, the problem is non-convex. Consequently, conventional duality methods cannot be employed to achieve the distributed solution. Thus, we design a distributed solution for the problem based on Gibbs sampling method. The proposed algorithm can be implemented in a fully distributed manner, does not depend on the convexity or continuity of the energy cost functions, and guarantees solution optimality. Numerical results are provided to demonstrate the behavior of the solution in some example network scenarios.

Recently beamforming WiFi access points (APs) have been commercially available from multiple vendors. The promise of beamforming APs is the enhanced range and data transmission rate, albeit at a premium price for the AP which can be an order of magnitude more expensive than regular omnidirectional APs. In this work, through live measurements, we study the throughput performance of beamforming APs and compare it with that of regular omnidirectional APs. We consider two systems with multiple WiFi clients and: 1) a single expensive beamforming AP, and 2) multiple low-cost omnidirectional APs. We find that while in some situations the beamforming AP outperforms multiple regular APs when downloading data, in other scenarios typical of home and office use, multiple regular APs results in higher throughput and service quality. Moreover, multiple regular APs always outperforms the beamforming AP when uploading data.

In this paper, we investigate dynamic base station activation with the aim of reducing energy consumption in cellular networks. Using the two-timescale Lyapunov optimization approach, we develop an online control algorithm to choose active set of base stations so as to satisfy users' demands while incurring minimum energy consumption. The algorithm selects the minimum cardinality subset of base stations that ensures stabilization of user queues. Our algorithm achieves stabilization without relying on instantaneous feedback about the network conditions, instead it only requires information about the average load and demand over a coarse time scale. The formulated problem which consists of joint base station activation and user association is generally intractable. However, we show that it features submodularity, and consequently present a near-optimal solution for certain instances of the problem. We further develop a greedy algorithm to solve general cases of the problem. We supplement our theoretical analysis with numerical results to demonstrate the behavior of our algorithm in terms of energy and delay in some example network scenarios.

Designing scheduling algorithms that work in synergy with TCP is a challenging problem in wireless networks. Extensive research on scheduling algorithms has focused on inelastic traffic, where there is no correlation between traffic dynamics and scheduling decisions. In this work, we study the performance of several scheduling algorithms in LTE networks, where the scheduling decisions are intertwined with wireless channel fluctuations to improve the system throughput. We use ns-3 simulations to study the performance of several scheduling algorithms with a specific focus on Max Weight (MW) schedulers with both UDP and TCP traffic, while considering the detailed behavior of OFDMA-based resource allocation in LTE networks. We show that, contrary to its performance with inelastic traffic, MW schedulers may not perform well in LTE networks in the presence of TCP traffic, as they are agnostic to the TCP congestion control mechanism. We then design a new scheduler called “Queue MW” (Q-MW) which is tailored specifically to TCP dynamics by giving higher priority to TCP flows whose queue at the base station is very small in order to encourage them to send more data at a faster rate. We have implemented Q-MW in ns-3 and studied its performance in a wide range of network scenarios in terms of queue size at the base station and round-trip delay. Our simulation results show that Q-MW achieves peak and average throughput gains of 37% and 10% compared to MW schedulers if tuned properly.

In this paper, we study the problem of uplink scheduling in wireless networks with successive interference cancellation (SIC). With SIC, concurrent transmissions, if properly scheduled, can be successfully decoded at a receiver. The scheduler decides: i. in which time-slot to schedule, and ii. in what order in a time-slot to decode each transmission in order to maximize the system utility and/or satisfy a system constraint. These two scheduling decisions effectively determine the rates allocated to concurrent transmissions, which in turn determine the throughput and fairness of the system. We consider several different scheduling problems in this context. The objective of the problems is to either maximize the throughput of the system or to obtain some kind of fairness among the users. We formulate and study each problem from the perspective of computational complexity. For each problem, we either propose a polynomial time algorithm, if any exists, or show that the problem is NP-hard.

Dynamic base station activation (DBA) has recently emerged as a viable solution for reducing energy consumption in cellular networks. While most of the works on this topic focused on centralized decision making algorithms, in this paper we investigate distributive solutions. These solutions are particularly desirable due to importance of self-organization and self-optimization in future cellular networks. The goal of DBA is to achieve an optimal trade-off between network operator's revenue and operational cost while guaranteeing coverage for network users. The problem is posed as a network utility maximization aiming to find the optimal activation schedule of each base station. Using Lagrangian duality, the problem is decomposed into smaller subproblems, where each subproblem is solved locally at its associated base station. Controlled message passing among base stations ensures convergence to the global optimal solution. Moreover, this general solution is further extended to capture the combinatorial nature of DBA. Finally, numerical results are provided to demonstrate the behavior of our solution in terms of utility and cost trade-off and convergence in some example network scenarios.

There is a rich recent literature on how to assist secure communication between a single transmitter and receiver at the physical layer of wireless networks through techniques such as cooperative jamming. In this paper, we consider how these single-hop physical layer security techniques can be extended to multi-hop wireless networks and show how to augment physical layer security techniques with higher layer network mechanisms such as coding and routing. Specifically, we consider the secure minimum energy routing problem, in which the objective is to compute a minimum energy path between two network nodes subject to constraints on the end-to-end communication secrecy and goodput over the path. This problem is formulated as a constrained optimization of transmission power and link selection, which is proved to be NP-hard. Nevertheless, we show that efficient algorithms exist to compute both exact and approximate solutions for the problem. In particular, we develop an exact solution of pseudo-polynomial complexity, as well as an o-optimal approximation of polynomial complexity. Simulation results are also provided to show the utility of our algorithms and quantify their energy savings compared to a combination of (standard) security-agnostic minimum energy routing and physical layer security. In the simulated scenarios, we observe that, by jointly optimizing link selection at the network layer and cooperative jamming at the physical layer, our algorithms reduce the network energy consumption by half.

Redundant Traffic Elimination (RTE) detects and removes repeated chunks of data across network flows, protocols, and applications, with the purpose of reducing bandwidth usage. In this paper, we explore the effectiveness of RTE in WLAN, compare it to RTE in Ethernet, and investigate specific issues affecting RTE in WLAN. Our results show that applying RTE to WLAN links is promising and can potentially yield high bandwidth savings, although RTE is not as effective in WLAN as in wired networks. However, to exploit the full potential of RTE, it is necessary to deal with specific challenges, such as longer headers, control and management frames, retransmissions, and dropped frames. We find that including parts of MAC headers in RTE can increase overall bandwidth savings by up to 53% in a public WLAN. To handle dropped frames, which can severely compromise the effectiveness of RTE, we make a case for MAC-layer RTE, which detects frame loss at the sender. This preserves 23% more savings than a previous approach. However, frame retransmissions generate additional traffic at MAC layer, which reduces the effectiveness of RTE in general case.

Successive Interference Cancellation (SIC) is a physical-layer technique that enables reception of multiple overlapping transmissions. While SIC has the potential to boost the network throughput, if the MAC protocol employed in the network is agnostic to such a capability at the physical-layer, the full potential of SIC can not be utilized in the network. There have been a number of studies to design new SIC-aware MAC protocols or adjust the existing protocols to exploit SIC. Despite that, the exact effect of MAC protocols on the throughput of SIC-enabled networks is unknown. In this paper, we propose a novel SIC-aware MAC protocol based on the disparity of user channels in a wireless network and analyze its performance. We consider a simple random access protocol with no SIC as the base configuration and compare it with three other configurations with different levels of SIC-awareness. We show that while a SIC-enabled physical layer without a SIC-aware MAC protocol can increase the throughput of the network by 1.5×, a specifically designed MAC protocol is far more efficient achieving up to 3.3× improvement in throughput. Our SIC-aware MAC protocol is fully distributed and hence subject to selfish behavior of users. Thus, we also consider the case where the users behave selfishly. We model our proposed protocol as a one-shot simultaneous move game and derive a mixed strategy Nash equilibrium. We also show that we can set the cost of packet transmission in such a way that we get the optimal system throughput at the Nash equilibrium.

Energy efficient secure communication in wireless networks in the presence of eavesdroppers is considered. For a secure transmission to the destination, a set of intermediate "jammer" nodes are chosen to generate artificial noise that confuses the eavesdropper. We consider two jamming strategies: beamforming and cooperative diversity. Previous research has focused largely on cooperative beamforming strategies, but we demonstrate a number of scenarios where a cooperative diversity strategy is desirable. This motivates approaches which selectively switch between the two strategies, from which significant energy savings can often be realized. In our simulations, energy savings of up to 60% are observed in the simulated networks.

This paper considers the problem of indoor wireless planning using smart antennas. Smart antennas have gained much attention in wireless networking because of their capability in providing more spatial reuse and increased network capacity. Recent research has demonstrated their effectiveness in indoor environments where omni-directional antennas have been traditionally the dominant technology. Much of the work, however, assumes that a network is already deployed and focuses on scheduling antenna patterns. In this work, we investigate finding a wireless plan for an indoor environment where the wireless plan specifies minimum number of antennas required to provide complete coverage of the environment as well as the location, transmission power and beam pattern for each antenna. This problem is more challenging than radio planning using omnidirectional antennas because of the special shape of antenna beams. Both single-beam and multi-beam antenna patterns are considered and Integer Linear Programming formulations are provided for computing the minimum cost wireless plan. Moreover, to solve large-scale instances of the problem an efficient polynomial-time heuristic is proposed.

Protocol-independent redundant traffic elimination (RTE) is an "on the fly" method for detecting and removing redundant chunks of data from network-layer packets traversing a constrained link or path. Efficient algorithms are needed to sample data chunks and detect redundancy, so that RTE does not hinder network throughput. A recently proposed static algorithm samples chunks based on highly-redundant trigger bytes observed in data content. While this algorithm is fast, it requires pre-computed traffic information for the configuration of its static parameters, and it tends to either under-sample (reducing byte savings) or over-sample (increasing processing cost) on heterogeneous traffic. We propose a dynamic sampling algorithm for redundant content detection. Our algorithm is adaptive and self-configuring, and can precisely match the specified sampling rate. Furthermore, it offers byte savings comparable to the static algorithm, with very low additional processing overhead.

This paper considers the problem of uplink scheduling in wireless networks supporting successive interference cancellation (SIC) at the physical layer. By allowing concurrent interfering transmissions, SIC enables multi-packet reception at the receiver resulting in increased network throughput. Specifically, we consider maximum throughput scheduling and proportional fair scheduling problems and study optimal and heuristic algorithms for these problems. We prove that the maximum throughput scheduling problem is NP-hard and develop a throughput efficient polynomial time greedy algorithm for the problem. While being throughput efficient, the maximum throughput scheduling can lead to highly unfair rates among the users. The proportional fair scheduling, on the other hand, is not throughput optimal but achieves proportional fairness among the users. For scheduling multiple users in a single time-slot, we show that there exists an algorithm that solves the proportional fair scheduling problem in polynomial time. For scheduling in multiple time-slots, we develop a greedy algorithm that computes a highly fair schedule in polynomial time. Numerical results are also provided to show the utility and efficiency of the proposed scheduling algorithms in various simulated networks.

This paper considers the problem of finding minimum-energy cooperative routes in a wireless network with variable wireless channels. We assume that each node in the network is equipped with a single omnidirectional antenna and, motivated by the large body of physical layer research indicating its potential utility, that multiple nodes are able to coordinate their transmissions at the physical layer in order to take advantage of spatial diversity. Such coordination, however, is intrinsically intertwined with routing decisions, thus motivating the work. We first formulate the energy cost of forming a cooperative link between two nodes based on a two-stage transmission strategy assuming that only statistical knowledge about channels is available. Utilizing the link cost formulation, we show that optimal static routes in a network can be computed by running Dijkstra's algorithm over an extended network graph created by cooperative links. However, due to the variability of wireless channels, we argue that a many-to-one cooperation model in static routing is suboptimal. Hence, we develop an opportunistic routing algorithm based on many-to-many cooperation, and show that optimal routes in a network can be computed by a stochastic version of the Bellman-Ford algorithm. We use static and opportunistic optimal algorithms as baselines to develop heuristic link selection algorithms that are energy efficient while being computationally simpler than the optimal algorithms. We simulate our algorithms and show that while optimal cooperation and link selection can reduce energy consumption by almost an order of magnitude compared to non-cooperative approaches, our simple heuristics achieve similar energy savings while being computationally efficient as well.

In this paper, we address the problem of low-latency routing in a vehicular highway network. To cover long highways while minimizing the number of required roadside access points, we utilize vehicle-to-vehicle communication to propagate data in the network. Vehicular networks are highly dynamic, and hence routing algorithms that require global network state information or centralized coordination are not suitable for such networks. Instead, we develop a novel distributed routing algorithm that requires minimal coordination among vehicles, while achieving a highly efficient throughput-delay tradeoff. Specifically, we show that the proposed algorithm achieves a throughput that is within a factor of 1/e of the throughput of an algorithm that centrally coordinates vehicle transmissions in a highly dense network, and yet its end-to-end delay is approximately half of that of a widely studied ALOHA-based randomized routing algorithm. We evaluate our algorithm analytically and through simulations and compare its throughput-delay performance against the ALOHA-based randomized routing.

We consider the problem of optimal cluster-based data gathering in Wireless Sensor Networks (WSNs) when nearby readings are spatially correlated. Due to the dense nature of WSNs, data samples taken from nearby locations are statistically similar. We show how this data correlation can be exploited to reduce the amount of data to be transmitted in the network and thus conserve energy. While much attention in recent years has been paid to analyzing and optimizing cluster-based WSNs from various perspectives, the problem of energy-efficient clustering of WSNs in presence of data correlation is not yet fully explored. In this paper, we model a single-cluster network and analytically characterize the optimal cluster size subject to its distance from the sink as well as the degree of correlation. Contrary to existing approaches, our findings show that heterogeneous-sized clusters, where the clusters further from the sink are larger, are more energy-efficient. We also propose a heuristic greedy clustering algorithm to find a near-optimal solution to the problem of energy-efficient clustering. Simulation results confirm the effectiveness of having heterogeneous-sized clusters in WSNs.

Modern cellular networks commonly deploy rapid channel rate adaptation to vary the wireless capacity in response to channel conditions while maintaining a fixed target error rate (typically 1%). Although desirable in terms of throughput for inelastic applications that do not adapt to network conditions, a low fixed target error rate incurs the expense of significant power consumption, especially at high transmission rates. In this work, we show that elastic traffic, in particular TCP, benefits greatly from the perspective of power efficiency when we also incorporate target error rate adaptation. More specifically, TCP behavior, although sensitive to packet errors, is not uniformly so. When TCP has a small window, it requires extremely low packet error rates. However, for large windows, especially with a buffer, TCP can tolerate larger loss rates. The contribution of this work is in conducting a detailed and realistic investigation into how beneficial target error rate adaptation is for TCP in terms of reducing power and impact on throughput. Our work differs from past contributions in that we explicitly take into account the impact of the buffer and a variable channel. We devise simple local power-adaptation policies based on TCP behavior and study them with the help of a numerical model. Finally, we present a detailed investigation of our policies using actual modulation schemes and real channel traces collected on a commercial 1xEV-DO network. The results show that compared to the existing scheme, our policies save typically about 20% to 30% power with marginal or no reduction in throughput.

This paper explores the use of rate adaptation in cellular networks to maximize throughput of long-lived TCP sessions. We focus on the problem of maximizing the throughput of TCP connections and propose a joint optimization of MAC and physical layer parameters with respect to TCP sending rate. In particular, we propose a simple TCP-aware channel scheduler that adapts the wireless channel rate to changes in the TCP sending rate and explore its performance for both single and multiple concurrent sessions. In the case of a single TCP session, we develop a fluid model of its steady-state behavior in such a system that adapts between two channel rates. Our results indicate that a two-rate scheme improves TCP throughput by 15% to 20% over a system that does not exploit rate adaptation and that little additional benefit accrues from the addition of a third channel rate. Finally, we extend the framework to scenarios where bandwidth is shared by multiple TCP sessions. We propose two channel allocation algorithms and explore their performance through simulation. Our results indicate that TCP throughput is relatively insensitive to either channel allocation algorithm and adaptive rate variation is the dominant factor in performance.

The capacity gain of network coding has been extensively studied in wired and wireless networks. Recently, it has been shown that network coding improves network reliability by reducing the number of packet retransmissions in lossy networks. However, the extent of the reliability benefit of network coding is not known. This paper quantifies the reliability gain of network coding for reliable multicasting in wireless networks, where network coding is most promising. We define the expected number of transmissions per packet as the performance metric for reliability and derive analytical expressions characterizing the performance of network coding. We also analyze the performance of reliability mechanisms based on rateless codes and automatic repeat request (ARQ), and compare them with network coding. We first study network coding performance in an access point model, where an access point broadcasts packets to a group of K receivers over lossy wireless channels. We show that the expected number of transmissions using ARQ, compared to network coding, scales as ominus (log K) as the number of receivers becomes large. We then use the access point model as a building block to study reliable multicast in a tree topology. In addition to scaling results, we derive expressions for the expected number of transmissions for finite multicast groups as well. Our results show that network coding significantly reduces the number of retransmissions in lossy networks compared to an ARQ scheme. However, rateless coding achieves asymptotic performance results similar to that of network coding.

This paper investigates the benefit of network coding for TCP traffic in a wireless mesh network. We implement network coding in a real 802.11a wireless mesh network and measure TCP throughput in such a network. Unlike previous implementations of network coding in mesh networks, we use off-the-shelf hardware and software and do not modify TCP or the underlying MAC protocol. Therefore, our implementation can be easily exported to any operational wireless mesh network with minimal modifications. Furthermore, the TCP throughput improvement reported in this paper is due solely to network coding and is orthogonal to other improvements that can be achieved by optimizing other system components such as the MAC protocol. We conduct extensive measurements to understand the relation between TCP throughput and network coding in different mesh topologies. We show that network coding not only reduces the number of transmissions by sending multiple packets via a single transmission but also results in a smaller loss probability due to reduced contention on the wireless medium. Unfortunately, due to asynchronous packet transmissions, there is often little opportunity to code resulting in small throughput gains. Coding opportunity can be increased by inducing small delays at intermediate nodes. However, this extra delay at intermediate nodes results in longer round-trip-times that adversely affect TCP throughput. Through experimentation, we find a delay in the range of 1 ms to 2 ms to maximize TCP throughput. For the topologies considered in this paper, network coding improves TCP throughput by 10% to 85%.

TCP is the dominant transport protocol over both wired and wireless links. It is however, well known that TCP is not suitable for wireless networks and several solutions have been proposed to rectify this shortcoming. In this work, we explore cross-layer optimization of the rate adaptation feature of cellular networks to optimize throughput of a single long-lived TCP session. Modern cellular networks rate RF technology that allows them to dynamically vary the wireless channel rate in response to user demand and channel conditions. However, the set of data rates as well as the scheduler's rate adaptation policy are typically chosen to optimize throughput for inelastic applications. In order to optimize such a system for TCP, we propose a two state TCP-aware scheduler that switches between two chanrates as a function of the TCP sending rate. We develop a fluid model of the steady-state behavior of a TCP session in such a system and derive analytical expressions for TCP throughput that explicitly account for rate variability as well as the dependency between the scheduler and TCP. Using the model we choose RF layer parameters that, in conjunction with the TCP-aware scheduler, improve term throughput of a single TCP flow by 15.25%. We also compare our analytical results against those obtained from ns-2 simulations and confirm that our model indeed closely approximates TCP behavior in such an environment.

This paper addresses bandwidth allocation for an integrated voice/data broadband mobile wireless network. Specifically, we propose a new admission control scheme called EFGC, which is an extension of the well-known fractional guard channel scheme proposed for cellular networks supporting voice traffic. The main idea is to use two acceptance ratios, one for voice calls and the other for data calls in order to maintain the proportional service quality for voice and data traffic while guaranteeing a target handoff failure probability for voice calls. We describe two variations of the proposed scheme: EFGC-REST, a conservative approach which aims at preserving the proportional service quality by sacrificing the bandwidth utilization, and EFGC-UTIL, a greedy approach which achieves higher bandwidth utilization at the expense of increasing the handoff failure probability for voice calls. Extensive simulation results show that our schemes satisfy the hard constraints on handoff failure probability and service differentiation while maintaining a high bandwidth utilization.

Abstract Call admission control (CAC) is a key element in the provision of guaranteed quality of service (QoS) in wireless networks. The design of CAC algorithms for mobile cellular networks is especially challenging given the limited and highly variable resources, and the mobility of users encountered in such networks. This article provides a survey of admission control schemes for cellular networks and the research in this area. Our goal is to provide a broad classification and thorough discussion of existing CAC schemes. We classify these schemes based on factors such as deterministic/stochastic guarantees, distributed/local control and adaptivity to traffic conditions. In addition to this, we present some modeling and analysis basics to help in better understanding the performance and efficiency of admission control schemes in cellular networks. We describe several admission control schemes and compare them in terms of performance and complexity. Handoff prioritization is the common characteristic of these schemes. We survey different approaches proposed for achieving handoff prioritization with a focus on reservation schemes. Moreover, optimal and near‐optimal reservation schemes are presented and discussed. Also, we overview other important schemes such as those designed for multi‐service networks and hierarchical systems as well as complete knowledge schemes and those using pricing for CAC. Finally, the paper concludes on the state of current research and points out some of the key issues that need to be addressed in the context of CAC for future cellular networks. Copyright © 2005 John Wiley & Sons, Ltd.

We describe an analytical approach for deriving the packet delay distribution in a cell of a wireless network operating on the general packet radio service (GPRS) standard. Based on that, the average packet delay and packet loss probability are also computed. Our approach is based on a decomposition of system behavior into short-term and long-term behaviors to simplify the analytical modeling. In addition to the effect of voice call handoffs, the impact of packet forwarding and dedicated data channels on data service performance is also taken into consideration. The performance estimates produced by the analytical approach are compared with those generated by simulation experiments. The comparison results confirm the relative accuracy of the analytical approach.

We propose an all-IP wireless network architecture that does not require any change inside the network and can interwork with the existing wired network. This architecture is based on the operation of intserv over diffserv network. The standard KSVP protocol is used for signaling and reservation. The approach is based on probabilistic behavior of mobile users and does not require precise knowledge of user mobility specification. The architecture allows mobile users to specify both packet-level and connection-level quality of service (QoS) parameters. Simulation results show that the proposed architecture allows flexible network resource management while achieving high resource utilization.