Federated learning (FL) enables collaborative model training using decentralized private data from multiple clients. While FL has shown robustness against poisoning attacks with basic defenses, our research reveals new vulnerabilities stemming from non-independent and identically distributed (non-IID) data among clients. These vulnerabilities pose a substantial risk of model poisoning in real-world FL scenarios.To demonstrate such vulnerabilities, we develop a novel collaborative backdoor poisoning attack called CollaPois. In this attack, we distribute a single pre-trained model infected with a Trojan to a group of compromised clients. These clients then work together to produce malicious gradients, causing the FL model to consistently converge towards a low-loss region centered around the Trojan-infected model. Consequently, the impact of the Trojan is amplified, especially when the benign clients have diverse local data distributions and scattered local gradients. CollaPois stands out by achieving its goals while involving only a limited number of compromised clients, setting it apart from existing attacks. Also, CollaPois effectively avoids noticeable shifts or degradation in the FL model’s performance on legitimate data samples, allowing it to operate stealthily and evade detection by advanced robust FL algorithms.Thorough theoretical analysis and experiments conducted on various benchmark datasets demonstrate the superiority of CollaPois compared to state-of-the-art backdoor attacks. Notably, CollaPois bypasses existing backdoor defenses, especially in scenarios where clients possess diverse data distributions. Moreover, the results show that CollaPois remains effective even when involving a small number of compromised clients. Notably, clients whose local data is closely aligned with compromised clients experience higher risks of backdoor infections.

In the ever-evolving landscape of Deep Neural Networks (DNN) hardware acceleration, unlocking the true potential of systolic array accelerators has long been hindered by the daunting challenges of expertise and time investment. Large Language Models (LLMs) offer a promising solution for automating code generation, which is key to unlocking unprecedented efficiency and performance in various domains, including hardware descriptive code. The generative power of LLMs can enable the effective utilization of preexisting designs and dedicated hardware generators. However, the successful application of LLMs to hardware accelerator design is contingent upon the availability of specialized datasets tailored for this purpose. To bridge this gap, we introduce the Systolic Array-based Accelerator DataSet (SA-DS). SA-DS comprises a diverse collection of spatial array designs following the standardized Berkeley’s Gemmini accelerator generator template, enabling design reuse, adaptation, and customization. SA-DS is intended to spark LLM-centered research on DNN hardware accelerator architecture. We envision that SA-DS provides a framework that will shape the course of DNN hardware acceleration research for generations to come. SA-DS is open-sourced under the permissive MIT license at https://github.com/ACADLab/SA-DS.

The capability of generating high-quality source code using large language models (LLMs) reduces software development time and costs. However, they often introduce security vulnerabilities due to training on insecure open-source data. This highlights the need for ensuring secure and functional code generation. This paper introduces PromSec, an algorithm for prom optimization for secure and functioning code generation using LLMs. In PromSec, we combine 1) code vulnerability clearing using a generative adversarial graph neural network, dubbed as gGAN, to fix and reduce security vulnerabilities in generated codes and 2) code generation using an LLM into an interactive loop, such that the outcome of the gGAN drives the LLM with enhanced prompts to generate secure codes while preserving their functionality. Introducing a new contrastive learning approach in gGAN, we formulate code-clearing and generation as a dual-objective optimization problem, enabling PromSec to notably reduce the number of LLM inferences. PromSec offers a cost-effective and practical solution for generating secure, functional code. Extensive experiments conducted on Python and Java code datasets confirm that PromSec effectively enhances code security while upholding its intended functionality. Our experiments show that while a state-of-the-art approach fails to address all code vulnerabilities, PromSec effectively resolves them. Moreover, PromSec achieves more than an order-of-magnitude reduction in operation time, number of LLM queries, and security analysis costs. Furthermore, prompts optimized with PromSec for a certain LLM are transferable to other LLMs across programming languages and generalizable to unseen vulnerabilities in training. This study is a step in enhancing the trustworthiness of LLMs for secure and functional code generation, supporting their integration into real-world software development.

This paper introduces SGCode, a flexible prompt-optimizing system to generate secure code with large language models (LLMs). SGCode integrates recent prompt-optimization approaches with LLMs in a unified system accessible through front-end and back-end APIs, enabling users to 1) generate secure code, which is free of vulnerabilities, 2) review and share security analysis, and 3) easily switch from one prompt optimization approach to another, while providing insights on model and system performance. We populated SGCode on an AWS server with PromSec, an approach that optimizes prompts by combining an LLM and security tools with a lightweight generative adversarial graph neural network to detect and fix security vulnerabilities in the generated code. Extensive experiments show that SGCode is practical as a public tool to gain insights into the trade-offs between model utility, secure code generation, and system cost. SGCode has only a marginal cost compared with prompting LLMs. SGCode is available at: http://3.131.141.63:8501/.

Malicious domain detection (MDD) is an open security challenge that aims to detect if an Internet domain name is associated with cyber attacks. Many techniques have been applied to tackle this problem, among which graph neural networks (GNNs) are deemed one of the most effective approaches. GNN-based MDD employs domain name system (DNS) logs to represent Internet domains as nodes in a graph, dubbed domain maliciousness graph (DMG) and trains a GNN model to infer the maliciousness of Internet domains by leveraging the maliciousness of already identified ones. As this method heavily relies on the "publicly" accessible DNS logs to build DMGs, it creates a vulnerability for adversaries to manipulate the features and edges of their domain nodes within these graphs. The current body of literature primarily focuses on threat models that involve manipulating individual adversary (attacker) nodes. Nonetheless, adversaries usually create numerous domains to accomplish their attack objectives, aiming to reduce costs and evade detection. Hence, they aim to remain undetected across as many domains as possible. In this work, we call the attack that manipulates several nodes in the DMG concurrently a multi-instance evasion attack. To the best of our knowledge, this type of attack has not been explored in the prior art. We present both theoretical and empirical evidence to show that the existing single-instance evasion techniques for GNN-based MDDs are inadequate to launch multi-instance evasion attacks. Therefore, we propose an inference-time, multi-instance adversarial attack, dubbed MintA, against GNN-based MDD. MintA optimizes node perturbations to enhance the evasiveness of a node and its neighborhood. MintA only requires black-box access to the target model to launch the attack successfully. In other words, MintA does not require any knowledge of the MDD model’s parameters, architecture, or information on non-adversary nodes. We formulate an optimization problem that satisfies the attack objectives of MintA and devise an approximate solution for it. We evaluate MintA on a state-of-the-art GNN-based MDD technique using real-world data, and our experiments demonstrate an attack success rate of over 80%. The findings of this study serve as a cautionary note for security experts, highlighting the vulnerability of GNN-based MDD to practical attacks that can impede the effectiveness and advantages of this approach.

Trojan backdoor is a poisoning attack against neural network (NN) classifiers in which adversaries try to exploit the (highly desirable) model reuse property to implant Trojans into model parameters for backdoor breaches through a poisoned training process. To misclassify an input to a target class, the attacker activates the backdoor by augmenting the input with a predefined trigger that is only known to her/him. Most of the proposed defenses against Trojan attacks assume a white-box setup, in which the defender either has access to the inner state of NN or is able to run backpropagation through it. In this work, we propose a more practical black-box defense, dubbed TrojDef. In a black-box setup, the defender can only run forward-pass of the NN. TrojDef is motivated by the Trojan poisoned training, in which the model is trained on both benign and Trojan inputs. TrojDef tries to identify and filter out Trojan inputs (i.e., inputs augmented with the Trojan trigger) by monitoring the changes in the prediction confidence when the input is repeatedly perturbed by random noise. We derive a function based on the prediction outputs which is called the prediction confidence bound to decide whether the input example is Trojan or not. The intuition is that Trojan inputs are more stable as the misclassification only depends on the trigger, while benign inputs will suffer when augmented with noise due to the perturbation of the classification features. Through mathematical analysis, we show that if the attacker is perfect in injecting the backdoor, the Trojan infected model will be trained to learn the appropriate prediction confidence bound, which is used to distinguish Trojan and benign inputs under arbitrary perturbations. However, because the attacker might not be perfect in injecting the backdoor, we introduce a nonlinear transform to the prediction confidence bound to improve the detection accuracy in practical settings. Extensive empirical evaluations show that TrojDef significantly outperforms the-state-of-the-art defenses and is highly stable under different settings, even when the classifier architecture, the training process, or the hyperparameters change.

In this paper, we propose IMA-GNN as an In-Memory Accelerator for centralized and decentralized Graph Neural Network inference, explore its potential in both settings and provide a guideline for the community targeting flexible and efficient edge computation. Leveraging IMA-GNN, we first model the computation and communication latencies of edge devices. We then present practical case studies on GNN-based taxi demand and supply prediction and also adopt four large graph datasets to quantitatively compare and analyze centralized and decentralized settings. Our cross-layer simulation results demonstrate that on average, IMA-GNN in the centralized setting can obtain ~790x communication speed-up compared to the decentralized GNN setting. However, the decentralized setting performs computation ~1400x faster while reducing the power consumption per device. This further underlines the need for a hybrid semi-decentralized GNN approach.

Machine learning models, especially neural network (NN) classifiers, have shown tremendous potential of being used in complex tasks such as image classification, object detection and video analytics. However, to be adopted in the real-world applications, there are still problems to be answered. One of these problems is that training machine learning models, especially NN models, requires a certain level of computation and data processing. Other problems are the limited bandwidth of the network and the possibility of exposing the privacy of the users to attacks if the training data (specially video) is going to be transferred through the network. To mitigate these problems, researchers recently proposed the concept of federated learning.In this paper, we build a video analytic application for traffic management and train it using federated learning. More specifically, each traffic surveillance camera combined with its co-located small PC are seen as the worker node in federated learning. In this way, the NN model in each node can be trained on data collected from all nodes without transmitting and sharing with a central server, which resolves all of the above mentioned problems. The performance of the trained NN model is evaluated via experiments under different open sourced datasets to demonstrate that the proposed work has the potential to enhance the detection accuracy (mAP) over 40%.

Recently, network coding has become a promising transmission approach to support high throughput and low latency in distributed multihop networks. In this article, we develop a delay-controlled distributed route establishment scheme that can provide maximal bidirectional transmission to enhance network coding gain while satisfying a time-critical route setup. The scheme is called network coding-aware delayed store and forwarding (NC-DSF). It delays the received route information packets before forwarding them according to the link status and network topology. We propose a tight delay function derived using a strict end-to-end delay bound for delay control. Subsequently, we suggest a relaxed delay function derived using realistic and practical conditions. Finally, we propose a load-weighted delay function considering the tradeoff between bidirectionality and network-load balancing. The simulations confirm that the proposed scheme offers increased throughput and decreased latency in mesh and random multihop networks. The proposed transmission scheme, NC-DSF, can be efficiently employed in the future industrial Internet of Things networks requiring a time-constrained route setup, high throughput, and low latency.

Retroreflective visible light communication and positioning (R-VLCP) is a novel ultralow-power Internet of Things (IoT) technology leveraging indoor light infrastructures. Compared to traditional VLCP, R-VLCP offers several additional favorable features, including self-alignment, low-size, weight, and power (SWaP), glaring-free, and sniff-proof. In analogy to RFID, R-VLCP employs a microwatt optical modulator (e.g., LCD shutter) to manipulate the intensity of the reflected light from a corner-cube retroreflector (CCR) to the photodiodes (PDs) mounted on a light source. In our previous works, we derived a closed-form expression for the retroreflection channel model, assuming that the PD is much smaller than the CCR in geometric analysis. In this article, we generalize the channel model to arbitrary size of PD and CCR. The received optical power is fully characterized relative to the sizes of PD and CCR, and the 3-D location of CCR. We also develop a custom and open-source ray tracing simulator—RetroRay, and use it to validate the channel model. Performance evaluation of area spectral efficiency and horizontal location error is carried out based on the channel model validated by RetroRay. The results reveal that increasing the size of PD and the density of CCRs improves communication and positioning performance with diminishing returns.

The growing use of media has led to the development of several machine learning (ML) and natural language processing (NLP) tools to process the unprecedented amount of social media content to make actionable decisions. However, these ML and NLP algorithms have been widely shown to be vulnerable to adversarial attacks. These vulnerabilities allow adversaries to launch a diversified set of adversarial attacks on these algorithms in different applications of social media text processing. In this article, we provide a comprehensive review of the main approaches for adversarial attacks and defenses in the context of social media applications with a particular focus on key challenges and future research directions. In detail, we cover literature on six key applications: 1) rumors detection; 2) satires detection; 3) clickbaits and spams identification; 4) hate speech detection; 5) misinformation detection; and 6) sentiment analysis. We then highlight the concurrent and anticipated future research questions and provide recommendations and directions for future work.

Graph neural networks (GNNs) are susceptible to privacy inference attacks (PIAS) given their ability to learn joint representation from features and edges among nodes in graph data. To prevent privacy leakages in GNNs, we propose a novel heterogeneous randomized response (HeteroRR) mechanism to protect nodes’ features and edges against PIAS under differential privacy (DP) guarantees, without an undue cost of data and model utility in training GNNs. Our idea is to balance the importance and sensitivity of nodes’ features and edges in redistributing the privacy budgets since some features and edges are more sensitive or important to the model utility than others. As a result, we derive significantly better randomization probabilities and tighter error bounds at both levels of nodes’ features and edges departing from existing approaches, thus enabling us to maintain high data utility for training GNNs. An extensive theoretical and empirical analysis using benchmark datasets shows that HeteroRR significantly outperforms various baselines in terms of model utility under rigorous privacy protection for both nodes’ features and edges. That enables us to defend PIAs in DP-preserving GNNs effectively.

Traffic management systems capture tremendous video data and leverage advances in video processing to detect and monitor traffic incidents. The collected data are traditionally forwarded to the traffic management center (TMC) for in-depth analysis and may thus exacerbate the network paths to the TMC. To alleviate such bottlenecks, we propose to utilize edge computing by equipping edge nodes that are close to cameras with computing resources (e.g., cloudlets). A cloudlet, with limited computing resources as compared to TMC, provides limited video processing capabilities. In this paper, we focus on two common traffic monitoring tasks, congestion detection, and speed detection, and propose a two-tier edge computing based model that takes into account of both the limited computing capability in cloudlets and the unstable network condition to the TMC. Our solution utilizes two algorithms for each task, one implemented at the edge and the other one at the TMC, which are designed with the consideration of different computing resources. While the TMC provides strong computation power, the video quality it receives depends on the underlying network conditions. On the other hand, the edge processes very high-quality video but with limited computing resources. Our model captures this trade-off. We evaluate the performance of the proposed two-tier model as well as the traffic monitoring algorithms via test-bed experiments under different weather as well as network conditions and show that our proposed hybrid edge-cloud solution outperforms both the cloud-only and edge-only solutions.

IP networks for live TV production have unique requirements such as the ultra high bandwidth and the high sensitivity to packet loss that causes video impairments. Existing multicast protocols are not bandwidth-aware and could cause links to over-subscribe leading to packet loss and negative user quality of experience. Existing video quality error detection tools are reactive by design with no insights into the video domain. In this paper, we introduceMediaFlow, a system for bandwidth aware multicast routing, active in-network detection of video errors, and proactive recovery.MediaFlowutilizes a novel greedy online multicast routing algorithm for efficient routing and admission control. It also introduces novel per-flow video quality metric utilizing unique switch ASIC capabilities for scalable in-network video quality monitoring and rerouting. We implementMediaFlowusing data center switches and our testing results confirm thatMediaFlowalgorithm increases fabric capacity up to 60% compared to state of art multicast routing.MediaFlowcan detect errors in video flow integrity at a granularity of 100 mSec at line rate for thousands of flows. The system can proactively recover impacted flows within 1 sec.MediaFlowincreases video detection and recovery scale by a thousandfold compared to network edge solutions.

The pervasiveness of neural networks (NNs) in critical computer vision and image processing applications makes them very attractive for adversarial manipulation. A large body of existing research thoroughly investigates two broad categories of attacks targeting the integrity of NN models. The first category of attacks, commonly called Adversarial Examples, perturbs the model’s inference by carefully adding noise into input examples. In the second category of attacks, adversaries try to manipulate the model during the training process by implanting Trojan backdoors. Researchers show that such attacks pose severe threats to the growing applications of NNs and propose several defenses against each attack type individually. However, such one-sided defense approaches leave potentially unknown risks in real-world scenarios when an adversary can unify different attacks to create new and more lethal ones bypassing existing defenses.In this work, we show how to jointly exploit adversarial perturbation and model poisoning vulnerabilities to practically launch a new stealthy attack, dubbed AdvTrojan. AdvTrojan is stealthy because it can be activated only when: 1) a carefully crafted adversarial perturbation is injected into the input examples during inference, and 2) a Trojan backdoor is implanted during the training process of the model. We leverage adversarial noise in the input space to move Trojan-infected examples across the model decision boundary, making it difficult to detect. The stealthiness behavior of AdvTrojan fools the users into accidentally trusting the infected model as a robust classifier against adversarial examples. AdvTrojan can be implemented by only poisoning the training data similar to conventional Trojan backdoor attacks. Our thorough analysis and extensive experiments on several benchmark datasets show that AdvTrojan can bypass existing defenses with a success rate close to 100% in most of our experimental scenarios and can be extended to attack federated learning as well as high-resolution images.

Adversarial examples are among the biggest challenges for machine learning models, especially neural network classifiers. Adversarial examples are inputs manipulated with perturbations insignificant to humans while being able to fool machine learning models. Researchers achieve great progress in utilizing adversarial training as a defense. However, the overwhelming computational cost degrades its applicability, and little has been done to overcome this issue. Single-Step adversarial training methods have been proposed as computationally viable solutions; however, they still fail to defend against iterative adversarial examples. In this work, we first experimentally analyze several different state-of-the-art (SOTA) defenses against adversarial examples. Then, based on observations from experiments, we propose a novel single-step adversarial training method that can defend against both single-step and iterative adversarial examples. Through extensive evaluations, we demonstrate that our proposed method successfully combines the advantages of both single-step (low training overhead) and iterative (high robustness) adversarial training defenses. Compared with ATDA on the CIFAR-10 dataset, for example, our proposed method achieves a 35.67% enhancement in test accuracy and a 19.14% reduction in training time. When compared with methods that use BIM or Madry examples (iterative methods) on the CIFAR-10 dataset, our proposed method saves up to 76.03% in training time, with less than 3.78% degeneration in test accuracy. Finally, our experiments with the ImageNet dataset clearly show the scalability of our approach and its performance advantages over SOTA single-step approaches.

Visible light communication (VLC)-based indoor localization approaches enjoy many advantages, such as utilizing ubiquitous lighting infrastructure, high location accuracy, and no interruption to RF-based devices. However, existing VLC-based localization methods lack a real-time backward channel from the device to landmarks and necessitate computation at the device, which make them unsuitable for real-time tracking of small IoT devices. In this paper, we propose and prototype RETRO, that establishes an almost zero-delay backward channel by retroreflection. RETRO localizes passive IoT devices without requiring computation and heavy sensing (e.g., camera) at the devices. Multiple photodiodes (i.e., landmarks) are mounted on any single unmodified light source to sense the retroreflected optical signal (i.e., location signature). We derive a closed-form expression, which is validated by experiments and ray tracing simulations, for the reflected optical power relative to the location and the orientation of the retroreflector. The expression is applied to a received signal strength indicator and trilateration based localization algorithm. Extensive experiments demonstrate centimeter-level location accuracy and single-digit angular error. For practicality concern, to mitigate the thickness problem of a single retroreflector, the capabilities of different retroreflector arrays are studied. The range of the localization system is theoretically evaluated for different light emission patterns.

Neural Network classifiers have been used successfully in a wide range of applications. However, their underlying assumption of attack free environment has been defied by adversarial examples. Researchers tried to develop defenses; however, existing approaches are still far from providing effective solutions to this evolving problem. In this paper, we design a generative adversarial net (GAN) based zero knowledge adversarial training defense, dubbed ZK-GanDef, which does not consume adversarial examples during training. Therefore, ZK-GanDef is not only efficient in training but also adaptive to new adversarial examples. This advantage comes at the cost of small degradation in test accuracy compared to full knowledge approaches. Our experiments show that ZK-GanDef enhances test accuracy on adversarial examples by up-to 49.17% compared to zero knowledge approaches. More importantly, its test accuracy is close to that of the state-of-the-art full knowledge approaches (maximum degradation of 8.46%), while taking much less training time.

Identifying the accurate location of small objects is a key element of Internet of Things (IoT). This paper investigates the feasibility of tracking the real-time location of a completely passive retroreflector using visible light for IoT applications. Existing ultra-low power visible light retroreflector systems modulate light with a liquid crystal display (LCD) shutter, which is powered by a solar cell. However, the solar cell costs additional space exclusively for energy harvesting, and it may not be able to supply enough power to the advanced power-hungry LCD shutter and its driver circuit. To eliminate the power supply, we design, implement and evaluate PassiveRETRO, an enhanced retroreflector-based visible light localization system. The PassiveRETRO system completely eliminates the necessity of any electronic component on the IoT devices. Polarization-based modulation and bandpass optical filters are adopted to identify the retroreflected optical signal and create multiple channels. Each IoT device operates on a specific range of the visible light spectrum. Optical rotatory dispersion is further applied to mitigate the mutual interference among different channels. Experimental results from our prototyped system show that PassiveRETRO is robust to environmental reflection and can still achieve centimeter-level location accuracy when multiple IoT devices are deployed.

Orthogonal frequency division multiplexing (OFDM) is currently the most prominent modulation technique, mainly due to it's spectral efficiency. To improve the security performance of OFDM based systems, multiple security approaches are proposed in literature, including physical-layer (PHY) approaches. However, these techniques are technology specific, i.e. mostly designed for radio frequency (RF) transmission and cannot be directly deployed in other technologies such as optical wireless communications (OWC). In this paper, security aware OFDM (SA-OFDM) is presented as a technology independent PHY security approach designed to suppress eavesdropping. The novelty of SA-OFDM is not only its versatility in deployment, but also in its perception in combining PHY encryption and the receiver's architecture to improve security performance. SA-OFDM is tested under additive white Gaussian noise (AWGN) and Rayleigh channel models, indicating negligible impact on system performance for both RF and OWC links. Results show that the eavesdropper becomes oblivious to the transmitted information, i.e. has a bit-error-rate (BER) of 0.5, which is equivalent to random guessing. Even if the key is seized, the eavesdropper's BER does not exceed 10-2.

In vehicular ad-hoc networks, due to high mobility, vehicles usually communicate for short periods of time with several neighboring vehicles and are required to process data fast; sometimes in the order of few milliseconds. This urgency of data processing is further heightened in safety-critical scenarios that involve many vehicles. Such scenarios require data to be prioritized and processed with minimum delay. While packet scheduling has been extensively studied, these studies focus on channel scheduling, our work focuses on processing received packets by a vehicle in dense scenarios. In this paper, we formulate the prioritized data processing problem as an integer linear program given a prior knowledge of the request sequence and prove that it is NP-complete. Due to the difficulty of predicting the traffic patterns and obtaining the request sequence in advance, we propose an online algorithm that does not require the prior knowledge of the request sequence and achieves an O(1) competitive ratio. The proposed online algorithm strives to accept higher severity packets for processing in order to maximize the cumulative severity given vehicular communications/computation capacity constraints. Using real traffic traces, we evaluate the performance of the online algorithm against three online algorithms, in which two of them use an exponentially weighted moving average-based threshold while the other one accepts requests as capacity permits. Our evaluation shows that our algorithm achieves up to 492% more cumulative severity compared to the three other baseline algorithms.

Multicast is widely deployed in data centers for point-to-multi-point communications. Multicast is increasingly being used to carry uncompressed video in media data centers with very large bandwidth requirements per flow. Multicast control protocols such as IGMP and PIM build multicast trees without trying to maximize the overall fabric capacity, leading to decreased fabric utilization and inability to service flows. In addition, existing multicast protocols are not bandwidth-aware and could cause links to over-subscribe leading to packet loss and negative user quality of experience. In this paper, we formulate offline optimization for multicast trees in clos fabric. We then design and implement two novel algorithms, iRP and LiRP, to optimize multicast tree formation and increase overall fabric multicast capacity. iRP algorithm optimizes online formation of multicast trees while addressing bandwidth requirements using SDN controller. We share analysis of TV studio repetitive traffic patterns the benefits of time series forecasting to predict multicast group membership and bring online optimization efficiency closer to offline optimization results. We then implement and test LiRP algorithm to increases iRP's fabric efficiency by implementing k-fold cross validation method to predict future multicast group memberships leading to optimized multicast tree placement. We implement iRP and LiRP algorithms using controller-based system and test both algorithms using Cisco Nexus commercially available switches. Testing results confirm that iRP Algorithm increases fabric capacity by 60% compared to PIM performance. LiRP system increases the efficiency of iRP by up to 40% through prediction of multicast group memberships with online arrival.

The concept of fog computing is centered around providing computation resources at the edge of the network, thereby reducing the latency and improving the quality of service. However, it is still desirable to investigate how and where at the edge of the network the computation capacity should be provisioned. To this end, we propose a hierarchical capacity provisioning scheme. In particular, we consider a two-tier network architecture consisting of shallow and deep cloudlets and explore the benefits of hierarchical capacity provisioning based on queuing analysis. Moreover, we explore two different network scenarios in which the network delay between the two tiers is negligible and the case that the deep cloudlet is located somewhere deeper in the network and thus the delay is significant. More importantly, we model the first network delay scenario with bufferless shallow cloudlets and the second scenario with finite-size buffer shallow cloudlets, and formulate an optimization problem for each model. We also use stochastic ordering to solve the optimization problem formulated for the first model and an upper bound-based technique is proposed for the second model. The performance of the proposed scheme is evaluated via simulations in which we show the accuracy of the proposed upper bound technique and the queue length estimation approach for both randomly generated input and real trace data.

Indoor localization is very important to enable Internet-of-things (IoT) applications. Visible light communication (VLC)-based indoor localization approaches enjoy many advantages, such as utilization of existing ubiquitous lighting infrastructure, high location and orientation accuracy, and no interruption to RF -based devices. However, existing VLC-based localization methods lack a real-time backward channel from the device to landmarks and necessitate computation at the device, which make them unsuitable for real-time tracking of small IoT devices. In this paper, we propose and prototype a retroreflector-based visible light localization system (RETRO), that establishes an almost zero-delay backward channel using a retroreflector to reflect light back to its source. RETRO localizes passive IoT devices without requiring computation and heavy sensing (e.g., camera) at the devices. Multiple photodiodes (i.e., landmarks) are mounted on any single unmodified light source to sense the retroreflected optical signal (i.e., location signature). We theoretically derive a closed-form expression for the reflected optical power related to the location and orientation of the retroreflector, and validate the theory by experiments. The characterization of received optical power is applied to a received signal strength indicator and trilateration based localization algorithm. Extensive experiments demonstrate centimeter-level location accuracy and single-digit angular error.

Visible light communication (VLC) has the potential to add significant capacity to short range wireless access technology by piggybacking data on light from overhead luminaires. However, an uplink is required to complete such a network, which introduces new issues. In this paper, we propose and implement a practical hybrid WiFi-VLC system that does not require a separate VLC uplink but rather aggregates WiFi and VLC downlinks and shares the WiFi uplink. Aggregated downlink bandwidth of the hybrid system is achieved by using a Linux bonding driver and media access control (MAC) address redirection. The throughput of the system is tested and compared with WiFi-only (one WiFi downlink) and asymmetric (one VLC downlink) systems under a congested WiFi environment. The evaluation results show that our system achieves aggregated downlink bandwidth that is approximately the summation of the downlink capacities of the WiFi-only and asymmetric systems. The study of the round-trip time (RTT) demonstrates the tradeoff between bandwidth utilization and latency that can be used in the design of load-balancing algorithms. Finally, the deployed system demonstrates feasibility in typical indoor space room dimensions.

Unmanned aerial vehicles (UAVs) can be used as aerial wireless base stations when cellular networks go down. Prior studies on UAV-based wireless coverage typically consider downlink scenarios from an aerial base station to ground users. In this paper, we consider an uplink scenario under disaster situations (such as earthquakes or floods), when cellular networks are down. We formulate the problem of optimal UAV placement, where the objective is to determine the placement of a single UAV such that the sum of time durations of uplink transmissions is maximized. We prove that the constraint sets of problem can be represented by the intersection of half spheres and the region formed by this intersection is a convex set in terms of two variables. This proof enables us to transform our problem to an optimization problem with two variables. We also prove that the objective function of the transformed problem is a concave function under a restriction on the minimum altitude of the UAV and propose a gradient projection-based algorithm to find the optimal location of the UAV. We validate the analysis by simulations and demonstrate the effectiveness of the proposed algorithm under different cases.

Unmanned aerial vehicles (UAVs) can be used as aerial wireless base stations when cellular networks go down. Prior studies on UAV-based wireless coverage typically consider an Air-to-Ground path loss model, which assumes that the users are outdoor and they are located on a 2D plane. In this paper, we propose using a single UAV to provide wireless coverage for indoor users inside a high-rise building under disaster situations (such as earthquakes or floods), when cellular networks are down. First, we present a realistic Outdoor-Indoor path loss model and describe the tradeoff introduced by this model. Then, we study the problem of efficient UAV placement, where the objective is to minimize the total transmit power required to cover the entire high-rise building. The formulated problem is non-convex and is generally difficult to solve. To that end, we consider two cases of practical interest and provide the efficient solutions to the formulated problem under these cases. In the first case, we aim to find the minimum transmit power such that an indoor user with the maximum path loss can be covered. In the second case, we assume that the locations of indoor users are symmetric across the dimensions of each floor.

Millimeter wave channels suffer from large path losses, penetration losses and atmospheric attenuation. Although beamforming techniques can significantly enhance link margins here, they also introduce initial beam access problems at the base and mobile stations prior to data transmission. Hence this paper presents an effective access scheme inspired by the Hooke Jeeves direct pattern search for analog beamforming cascaded codebooks. Simulation results show that the proposed algorithm delivers substantial performance improvements versus existing solutions in terms of computational complexity, access times and power and energy consumption.

Internet of Things (IoT) applications can benefit greatly from cloud-hosted message broker services that utilize publish-subscribe communications. The operators of IoT cloud-hosted services are often interested in delivering services that maximize their revenue given quality of service guarantees. In this paper, we formulate the problem of maximizing the profit of the service provider given the prior knowledge of the request sequence as an integer linear program and prove that it is strongly NP-complete, and thus there is no fully polynomialtime approximation scheme for the problem, unless P = NP. Due to the above-mentioned problem and the difficulty of obtaining the request sequence in advance in real-world scenarios, we propose an auction-based online algorithm that does not require the prior knowledge of the request sequence. We prove that the competitive ratio of the online algorithm is (9(log(N)), where N is the number of cloud zones that host the publish- subscribe services. Moreover, we show that no online algorithm can achieve a competitive ratio better than Ω(log(N)). Therefore, our online algorithm achieves the optimal competitive ratio in the asymptotic sense. Our simulations, based on real data traces, show that our algorithm achieves up to 83% more profit compared to a heuristic approach, while consuming 60% less resources.

We design and implement a novel communications latency based authentication scheme, dubbed CLAS, that strengthens the security of state-of-the-art web authentication approaches by leveraging the round trip network communications latency (RTL) between clients and authenticators. In addition to the traditional credentials, CLAS profiles RTL values of clients and uses them to defend against password compromise. The key challenges are (i) to prevent RTL manipulation, (ii) to alleviate network instabilities, and (iii) to address mobile clients. CLAS addresses the first challenge by introducing a novel network architecture, which makes it extremely difficult for attackers to simulate legitimate RTL values. The second challenge is addressed by outlier removal and multiple temporal profiling, while the last challenge is addressed by augmenting CLAS with out-of-band-channels or other authentication schemes. CLAS restricts login to profiled locations while demanding additional information for nonprofiled ones, which highly reduces the attack surface even when the legitimate credentials are compromised. Additionally, unlike many state-of-the-art authentication mechanisms, CLAS is resilient to phishing, pharming, man-in-the-middle, and social engineering attacks. Furthermore, CLAS is transparent to users and incurs negligible overhead. The experimental results show that CLAS can achieve very low false positive and false negative rates.

In this paper, we leverage the characteristics of round-trip communications latency (RTL) to design and implement a novel highly secure and usable web authentication scheme, dubbed CLAS. CLAS uses, in addition to the traditional credentials, round trip network communications latency to uniquely identify users. CLAS introduces a novel network architecture which turns RTL into a robust authentication feature that is extremely difficult to forge. CLAS offers robust defense against password compromise because, unlike many traditional authentication mechanisms, it is resilient to phishing/pharming, man-in-the-middle, and social engineering attacks. Most importantly, CLAS is transparent to users and incurs negligible overhead. Our experimental results show that CLAS can achieve 0.0017 false positive rate while maintaining false negative rate below 0.007.

Since the emergence of Content Centric Networking (CCN) as a new paradigm for content delivery in the Internet, copious of research targeted the evaluation or the enhancement of CCN caching schemes. Motivated by providing the Internet Service Providers with incentives to perform caching, the increasing deployment of in-network cloudlets, and the low cost of storage devices, we study caching in CCN from an economical point of view, where the content providers pay the Internet Service Providers in exchange for caching their content items. We propose an online caching algorithm for CCN that does not require the exact knowledge of content items' popularities to minimize the total cost paid by the content providers. The total cost here is the sum of the caching costs and the retrieval costs. Our analysis shows that the proposed algorithm achieves an O(1) competitive ratio when compared to the optimal offline caching scheme that possesses the exact knowledge of content items' popularities. We also show through simulations that the proposed algorithm can cut the cost incurred by widely used caching schemes such as Leave Copy Down (LCD) and Leave Copy Everywhere (LCE) by up to 65%.

These days we are witnessing a tremendous increase in the popularity of wireless devices, e.g. smartphones and tablets. These devices are typically connected to the Internet through cellular connections, such as LTE/4G. Because of the popularity of the wireless devices, a large portion of the traffic on the Internet goes through the cellular base stations. Caching the contents at the base stations brings the contents closer to the users, reduces the traffic on the Internet, and reduces the cost of providing the contents. In this paper, we study the problem of collaborative caching in cellular networks among a set of base stations. Motivated by the emergence of cloudlets, we consider unlimited cache space in our model, and our objective is to minimize the aggregated caching and download cost. We show that in the case of knowing the popularity of the contents, this optimization has a submodular property, and a greedy algorithm can achieve an approximation ratio of 2 for this optimization. We also provide an online algorithm that does not require any knowledge about the future requests and the content popularity. In order to evaluate our online algorithm, we compare its performance against the optimal solution through simulations.

We consider joint caching, routing, and channel assignment for video delivery over coordinated small-cell cellular systems of the future Internet. We formulate the problem of maximizing the throughput of the system as a linear program, in which the number of variables is very large. To address channel interference, our formulation incorporates the conflict graph that arises when wireless links interfere with each other due to simultaneous transmission. We utilize the column generation method to solve the problem by breaking it into a restricted master subproblem that involves a select subset of variables and a collection of pricing subproblems that select the new variable to be introduced into the restricted master problem, if that leads to a better objective function value. To control the complexity of the column generation optimization further, due to the exponential number of independent sets that arise from the conflict graph, we introduce an approximation algorithm that computes a solution that is within ϵ to optimality, at much lower complexity. Our framework demonstrates considerable gains in average transmission rate at which the video data can be delivered to the users, over the state-of-the-art Femtocaching system, of up to 46%. These operational gains in system performance map to analogous gains in video application quality, thereby enhancing the user experience considerably.

Caching at the base stations brings the contents closer to the users, reduces the traffic through the backhaul links, and reduces the delay experienced by the cellular users. The cellular network operator may charge the content providers for caching their contents. Moreover, content providers may lose their users if the users are not getting their desired quality of service, such as maximum tolerable delay in Video on Demand services. In this paper, we study the collaborative caching problem for a multicell-coordinated system from the point of view of minimizing the total cost paid by the content providers. We formulate the problem as an Integer Linear Program and prove its NP-completeness. We also provide an online caching algorithm that does not require any knowledge about the contents popularities. We prove that the online algorithm achieves a competitive ratio of O(log (n)), and we show that the best competitive ratio that any online algorithm can achieve is Ω (log (n) / log log (n)). Therefore, our proposed caching algorithm is provably efficient. Through simulations, we show that our online algorithm performs very close to the optimal offline collaborative scheme, and can outperform it when contents popularities are not properly estimated.

Video streaming generates a substantial fraction of the traffic on the Internet. The demands of video streaming also increase the workload on the video server, which in turn leads to substantial slowdowns. In order to resolve the slowdown problem, and to provide a scalable and robust infrastructure to support on-demand streaming, helper-assisted video-on-demand (VoD) systems have been introduced. In this architecture, helper nodes, which are micro-servers with limited storage and bandwidth resources, download and store the user-requested videos from a central server to decrease the load on the central server. Multi-layer videos, in which a video is divided into different layers, can also be used to improve the scalability of the system. In this paper, we study the problem of utilizing the helper nodes to minimize the pressure on the central servers. We formulate the problem as a linear programming using joint inter- and intra-layer network coding. Our solution can also be implemented in a distributed manner. We show how our method can be extended to the case of wireless live streaming, in which a set of videos is broadcasted. Moreover, we extend the proposed method to the case of unreliable connections. We carefully study the convergence and the gain of our distributed approach.

Content caching at intermediate nodes is an effective way to optimize the operations of Computer networks, so that future requests can be served without going back to the origin of the content. Several caching techniques have been proposed in literature, including techniques that require major changes to the Internet architecture. In this work, we present a low complexity, distributed, and online caching algorithm based on content popularity. Our algorithm performs en-route caching using a simple cost-reward comparison. Therefore, it can be integrated with the current TCP/IP model. We use the concept of competitive ratio to measure the performance of any online caching algorithm, in terms of traffic savings, with respect to the performance of the optimal offline algorithm that has a complete knowledge of the future. We show that under our settings, no online algorithm can achieve a better competitive ratio than Ω(logn), where n is the number of nodes in the network. Furthermore, we show that under realistic scenarios, our algorithm has an asymptotically optimal competitive ratio in terms of the number of nodes in the network. We also study several extensions to the basic algorithm and show their effectiveness through extensive simulations.

The coexistence of omnidirectional small cells (OSCs), such as RF small cells, and directional small cells (DSCs), such as visible-light communication cells, is investigated. The delay of two cases of such heterogeneous networks is evaluated. In the first case, resource allocated OSCs, such as RF femtocells, are considered. In the second case, contention-based OSCs, such as WiFi access point, are studied. For each case, two configurations are evaluated. In the first configuration, the non-aggregated scenario, any request is either allocated to OSC or DSC. While in the second configuration, the aggregated scenario, each request is split into two pieces, one is forwarded to OSC and the other is forwarded to DSC. For the first case, under Poisson request arrival process and exponential distribution of request size, the optimal traffic allocation ratio is derived for the non-aggregated scenario and it is mathematically proved that the aggregated scenario provides lower minimum average system delay than that of the non-aggregated scenario. For the second case, the average system delay is derived for both non-aggregated and aggregated scenarios, and extensive simulation results imply that, under certain conditions, the non-aggregated scenario outperforms the aggregated scenario due to the overhead caused by contention.

Network coding-based opportunistic routing has emerged as an elegant way to optimize the capacity of lossy wireless multihop networks by reducing the amount of required feedback messages. Most of the works on network coding-based opportunistic routing in the literature assume that the links are independent. This assumption has been invalidated by the recent empirical studies that showed that the correlation among the links can be arbitrary. In this work, we show that the performance of network coding-based opportunistic routing is greatly impacted by the correlation among the links. We formulate the problem of maximizing the throughput while achieving fairness under arbitrary channel conditions, and we identify the structure of its optimal solution. As is typical in the literature, the optimal solution requires a large amount of immediate feedback messages, which is unrealistic. We propose the idea of performing network coding on the feedback messages and show that if the intermediate node waits until receiving only one feedback message from each next-hop node, the optimal level of network coding redundancy can be computed in a distributed manner. The coded feedback messages require a small amount of overhead, as they can be integrated with the packets. Our approach is also oblivious to losses and correlations among the links, as it optimizes the performance without the explicit knowledge of these two factors.

Many web computing systems are running real time database services where their information change continuously and expand incrementally. In this context, web data services have a major role and draw significant improvements in monitoring and controlling the information truthfulness and data propagation. Currently, web telemedicine database services are of central importance to distributed systems. However, the increasing complexity and the rapid growth of the real world healthcare challenging applications make it hard to induce the database administrative staff. In this paper, we build an integrated web data services that satisfy fast response time for large scale Tele-health database management systems. Our focus will be on database management with application scenarios in dynamic telemedicine systems to increase care admissions and decrease care difficulties such as distance, travel, and time limitations. We propose three-fold approach based on data fragmentation, database websites clustering and intelligent data distribution. This approach reduces the amount of data migrated between websites during applications' execution; achieves cost-effective communications during applications' processing and improves applications' response time and throughput. The proposed approach is validated internally by measuring the impact of using our computing services' techniques on various performance features like communications cost, response time, and throughput. The external validation is achieved by comparing the performance of our approach to that of other techniques in the literature. The results show that our integrated approach significantly improves the performance of web database systems and outperforms its counterparts.

Abstract Broadcasting with network coding mixes packets to minimize the number of transmissions, which improves the energy efficiency of wireless networks. On the other hand, delaying the transmissions increases coding opportunities at intermediate nodes, but increases the delay of packets. In this paper, we consider these two contradicting factors and study the problem of minimizing the number of transmissions in wireless networks while meeting the deadline constraints. We show that this problem is NP‐complete; therefore, we provide a heuristic to solve it. First, we construct broadcasting trees, each of them rooted at one source. We then specify overlapping conditions based on the constructed trees, to determine the number of transmissions each node has to perform without the deadline constraints. Then, we partition the set of packets such that coding is performed among the packets of the same partition, which does not result in deadline misses. Linear coding may not be applicable in some wireless networks because of its computational complexity. For these networks, we propose three XOR coding approaches, which rely only on local neighborhood information. Simulation results show that our techniques not only reduce the number of transmissions but also allow the majority of nodes to receive the packets on time. Copyright © 2013 John Wiley & Sons, Ltd.

Software defined networking (SDN) provides a novel network resource management framework that overcomes several challenges related to network resources management. On the other hand, Cognitive Radio (CR) technology is a promising paradigm for addressing the spectrum scarcity problem through efficient dynamic spectrum access (DSA). CR provides unlicensed secondary users with the ability to coexist with licensed users in non-interfering mode. In this paper, we introduce a virtualization based SDN resource management framework for cognitive radio networks (CRNs). The framework uses the concept of multilayer hypervisors for efficient resources allocation. It also introduces a semi-decentralized control scheme that allows the CRN base station (BS) to delegate some of the management responsibilities to the network users. CRN resource virtualization allows dynamic, infrastructure free and efficient resources allocation to the CR users. The main objectives of the proposed framework is to reduce the CR users' reliance on the CRN BS and physical network resources while improving the network performance by reducing control overhead.

Content caching at intermediate nodes is a very effective way to optimize the operations of Computer networks, so that future requests can be served without going back to the origin of the content. Several caching techniques have been proposed since the emergence of the concept, including techniques that require major changes to the Internet architecture such as Content Centric Networking. Few of these techniques consider providing caching incentives for the nodes or quality of service guarantees for content owners. In this work, we present a low complexity, distributed, and online algorithm for making caching decisions based on content popularity, while taking into account the aforementioned issues. Our algorithm performs en-route caching. Therefore, it can be integrated with the current TCP/IP model. In order to measure the performance of any online caching algorithm, we define the competitive ratio as the ratio of the performance of the online algorithm in terms of traffic savings to the performance of the optimal offline algorithm that has a complete knowledge of the future. We show that under our settings, no online algorithm can achieve a better competitive ratio than O(log n), where n is the number of nodes in the network. Furthermore, we show that under realistic scenarios, our algorithm has an asymptotically optimal competitive ratio in terms of the number of nodes in the network.

Visible light communications (VLC) is emerging as a new alternative to the use of the existing and increasingly crowded radio frequency (RF) spectrum. VLC is unlicensed, has wide bandwidth, supports new levels of security due to the opacity of walls, and can be combined to provide both lighting and data communications for little net increase in energy cost. As part of a lighting system, VLC is ideal as a downlink technology in which data are delivered from overhead luminaries to receivers in the lighting field. However, realizing a symmetric optical channel is problematic because most receivers, such as mobile devices, are ill-suited for an optical uplink due to glare, device orientation, energy constraints. In this paper we propose and implement a hybrid solution in which the uplink challenge is resolved by the use of an asymmetric RF-VLC combination. VLC is used as a downlink, RF is used as an uplink, and the hybrid solution realizes full duplex communication without performance glare or throughput degradation expected in an all-VLC-based approach. Our proposed approach utilizes a software defined VLC platform (SDVLC) to implement the unidirectional optical wireless channel and a WiFi link as the back-channel. Experiments with the implemented prototype reveal that the integrated system outperforms conventional WiFi for crowded (congested) multiuser environments in term of throughput, and demonstrate functional access to full-duplex interactive applications such as web browsing with HTTP.

IEEE 802.22 Wireless Regional Area Network (WRAN) is the first wireless standard based on cognitive radio (CR) technology. WRAN is designed to allow secondary users (SUs) to opportunistically utilize idle TV channels on a non-interfering manner. A major challenge in enabling efficient WRAN communications is the interference-and-coexistence problem. There are two types of co-existence; incumbent co-existence and self-coexistence. In this paper, we investigate the self-coexistence problem among multiple overlapped WRANs. Specifically, we propose an adaptive cooperative exclusive traffic-aware channel allocation scheme (TAECA) that attempts to minimize the unnecessary blocking of SU transmissions in the overlapped cells, which consequently maximizes spectrum utilization. TAECA employs a novel max-min weighted fair mechanism for adaptively allocating idle channels to the different WRANs cells depending on their prevailing traffic conditions. Simulation results indicate that compared to reference allocation mechanisms, TAECA increases the number of served SU transmissions by up to 40%, which significantly improves spectrum utilization.

Network virtualization is a promising technology that enables the deployment of multiple virtual networks over a single physical network. These virtual networks are allowed to share the set of available resources in order to provide different services to their intended users. Although many projects are studying different aspects of network virtualization, the field of wireless network virtualization is not well investigated. In this work, we propose a dynamic cognitive radio virtualization framework in which several virtual networks are built over a set of physical nodes managed and controlled by a Base Station (BS). This framework is proposed to virtualize Cognitive Radio Networks (CRNs) in order to reduce the control overhead on the BS side by delegating some of its responsibilities to the node side. The proposed framework is applied to a network with multiple overlapping cells. To cope with the self-coexistence problem, we use a resource allocation algorithm to distribute the available channels over the overlapping cells based on their traffic loads with the goal of avoiding harmful interference, enhancing blocking rates and increasing throughput.

Video streaming is one of the dominant forms of traffic on the Internet. This increases workload on the video servers, which leads to substantial slowdowns. In order to resolve the slowdown problem, and to provide a scalable and robust infrastructure to support on-demand streaming, helper-assisted video-on-demand (VoD) systems have been introduced. In this architecture, helper nodes, which are micro-servers with limited storage and bandwidth resources, download and store the user requested videos from a central server to decrease the load on the central server. Multi-layer videos, in which a video is divided into different layers, can also be used to improve scalability. In this paper, we study the problem of utilizing the helper nodes to minimize the pressure on the central servers. We formulate the problem as a linear programming (LP) optimization using joint inter- and intra-layer network coding (NC). We show that a lightweight triangular inter-layer NC can be used, instead of the general form of inter-layer NC, to achieve the optimal solution. Our solution can also be implemented in a distributed manner. We show how our method can be extended to the case of wireless live streaming, in which a set of videos is broadcast. We carefully study the convergence and the gain of our distributed approach.

Client diversity is one of the main characteristics of wireless networks. Due to channel diversity, multicasting a video stream in a wireless LAN to multiple clients with different channel conditions is a challenging task. A promising approach for such a problem is to use multiresolution video coding (i.e. scalable video coding) with network coding. In this paper, we study a triangular approach for network coding in a one-hop wireless LAN network. Previous work searches for all possible coding opportunities, which is computationally expensive. In this work, we use regression to derive efficient transmission protocols that take into account the delivery rate, as well as the variance of the channels. We show that the regression approach is more practical than the previous method. Also, the achievable rate using the regression approach can produce competitive results.

Video is one of the main causes of the dramatic increase in data traffic over cellular networks. Caching is an effective mechanism that decreases the download rate from base stations and, as a result, the load on the base station, by storing the most popular files or videos on the caches and providing them to the users. The problem of efficient content placement on the caches is known as an NP-complete problem. In this paper, we study the role of network coding by increasing the amount of available data to the users through the cache nodes. We propose a network coding-based content placement method, and we compare it to the best uncoded content placement and the best triangular network coding strategies. Our method not only increases the amount of available data to the users, but also results in a fair distribution of data.

Providing reliable transmission over error-prone networks has received a lot of attention from the research community. In this paper, instead of using simple retransmissions to provide reliability, we consider a novel retransmission approach based on the importance of the bits (symbols). We study the problem of maximizing the total gain in the case of partial data delivery in error-prone wireless networks, in which each set of bits (symbols) has a different weight. We first address the case of one-hop single packet transmission, and prove that the optimal solution has a round-robin transmission pattern. Then, we extend our solution to the case of multiple packets. We also enhance the expected gain using random linear network coding. Our simulation results show that our proposed multiple packets transmission mechanism can increase the gain up to 60% compared to that of a simple retransmission. Moreover, our network coding scheme enhances the expected total gain up to 15% compared to our non-coding mechanism.

The performance of wireless networks can be enhanced by performing network coding on the intermediate relay nodes. To enhance the throughput of large wireless networks, we can decompose them into a superposition of simple relay networks called two-hop relay networks. Previously, the capacity region of two-hop relay networks with multiple unicast sessions and limited feedback was characterized where packet erasure channels are used. A near-optimal coding scheme that exploits the broadcast nature and the diversity of the wireless links was proposed. However, the complexity of the scheme is exponential in terms of the number of sessions, as it requires the knowledge of the packets that are received by any subset of the receivers. In this paper, we provide a polynomial time coding scheme and characterize its performance using linear equations. The coding scheme uses random network coding to carefully mix intra and intersession network coding and makes a linear, not exponential, number of decisions. For two-hop relay networks with two sessions, we provide an optimal coding scheme that does not require the knowledge of the channel conditions. We also provide a linear programming formulation that uses our two-hop relay network results as a building block in large lossy multihop networks.

Broadcasting with network coding mixes different packets to minimize the number of transmissions, which improves the energy efficiency of wireless networks. On the other hand, delaying the transmissions increases coding opportunities at the intermediate nodes, but increases the delay of the packets. In this paper, we consider these two contradicting factors and study the problem of minimizing the number of transmissions in wireless networks while meeting the deadlines of different packets. We show that this problem is NP-complete; therefore, we provide a heuristic to solve the problem. First, we construct broadcasting trees, each of them rooted at one source. We then specify overlapping conditions based on the constructed trees to determine the number of transmissions each node has to perform without the deadline constraints. Then, we partition the set of packets such that coding is performed among the packets of the same partition, which does not result in deadline misses. Our simulation results show that our technique not only reduces the number of transmissions, but also allows the majority of the nodes to receive their packets on time.

In this paper, we tackle the network coding-based opportunistic routing problem for multicast. We present the factors that affect the performance of the multicast protocols. Then, we formulate the problem as an optimization problem. Using the duality approach, we show that a distributed solution can be used to achieve the optimal solution. The distributed solution consists of two phases. In the first phase, the most reliable broadcasting tree is formed based on the ETX metric. In the second phase, a credit assignment algorithm is run at each node to determine the number of coded packets that the node has to send. The distributed algorithm adapts to the changes in the channel conditions and does not require explicit knowledge of the properties of the network. To reduce the number of feedback messages, and to resolve the problem of delayed feedback, we also perform network coding on the feedback messages. We evaluate our algorithm using simulations which show that in some realistic cases the throughput achieved by our algorithm can be double or triple that of the state-of-the-art.

Recent research has shown that the performance of opportunistic routing and network coding in wireless networks is greatly impacted by the correlation among the links. However, it is difficult to measure the correlation among the links, especially because of the time-varying behavior of the wireless links. Therefore, it is crucial to design a distributed algorithm that does not require the explicit knowledge of the channels' states and can adapt to the varying channel conditions. In this paper, we formulate the problem of maximizing the throughput while achieving fairness under arbitrary channel conditions, and we identify the structure of its optimal solution. As is typical in the literature, the optimal solution requires a large amount of immediate feedback messages, which is unrealistic. We propose the idea of performing network coding on the feedback messages and show that if the intermediate node waits until receiving only one feedback message from each next-hop node, the optimal level of network coding redundancy can be computed in a distributed manner. The coded feedback messages require a small amount of overhead as they can be integrated with the packets. Our approach is also oblivious to losses and correlations among the links as it optimizes the performance without the explicit knowledge of these two factors.

A practical way for maximizing the throughput of a wireless network is to decompose the network into a superposition of small two-hop networks such that network coding can be performed inside these small networks to resolve bottlenecks. We call these networks 2-hop relay networks. Therefore, studying the capacity of 2-hop relay networks is very important. Most practical network coding protocols that perform the superposition ignore the diversity among the links by turning off coding when the channels are lossy. Other protocols deal with the packets separately - not as members of flows - which makes the network coding problem with lossy links intractable. In this paper, we use a different approach by looking at flows or batches instead of individual packets. We characterize the capacity region of the 2-hop relay network with packet erasure channels when the coding operations are limited to XOR. We derive our results by constructing an upper bound on the capacity region and then providing a coding scheme that can achieve the upper bound. The capacity characterization is in terms of linear equations. We also extend our 2-hop relay networks results to multihop wireless networks by providing a linear program that can perform the superposition optimally. We perform extensive simulations for both the 2-hop relay and large wireless networks and show the superiority of our protocols over the network coding protocols that deal with the packets separately.

The broadcast nature of wireless links makes wireless networks an attractive environment for intersession network coding. Most intersession network coding protocols exploit this property, but ignore the diversity among the links by turning off coding when the channels are lossy. Other protocols deal with the packets separately - not as members of flows - which makes the intersession network coding problem with lossy links untractable. In this paper, we use a different approach by looking at flows or batches instead of individual packets. We characterize the capacity region of the 2-hop relay network when the coding operations are limited to XOR. The 2-hop relay network represents all of the local intersession network coding opportunities in large multihop networks. The characterization is in terms of linear equations. We also provide a coding scheme that can achieve the capacity with almost zero feedback overhead. Simulation results show that our scheme enhances the throughput by 82% while maintaining fairness among the flows compared to the intersession network coding protocols that deal with the packets separately.

Before the emergence of commercial cloud computing, interests in parallel algorithm analysis have been mostly academic. When computing and communication resources are charged by hours, cost effective parallel processing would become a required skill. This paper reports a resource planning study using a method derived from classical program time complexity analysis, we call Timing Models. Unlike existing qualitative performance analysis methods, a Timing Model uses application instrumented capacity measures to capture the quantitative dependencies between a computer program (sequential or parallel) and its processing environments. For applications planning to use commercial clouds, this tool is ideally suited for choosing the most cost-effective configuration. The contribution of the proposed tool is its ability to explore multiple dimensions of a program quantitatively to gain non-trivial insights. This paper uses a simple matrix multiplication application to illustrate the modeling, program instrumentation and performance prediction processes. Since cloud vender do offer HPC hardware resources, we use Amazon EC2 as the target processing environments. The computing and communication models are not only useful in choosing the processing platform but also for understanding the resource usage bills. Comparisons between predicted and actual resource usages show that poor processing granularity wastes resources. Prediction errors are minimized near the optimal number of processors.

The network coding problem across multiple unicasts is an open problem. Previously, the capacity region of 2-hop relay networks with multiple unicast sessions and limited feedback was characterized where the coding and decoding nodes are neighbors and packet erasure channels are used. A near-optimal coding scheme that exploits the broadcast nature and the diversity of the wireless links was proposed. However, the complexity of the scheme is hyper exponential as it requires the knowledge of the packets that are received by any subset of the receivers. In this paper, we provide a polynomial time coding scheme and characterize its performance using linear equations. The coding scheme uses random network coding to carefully mix intra and intersession network coding and makes a linear, not exponential, number of decisions. We also provide a linear programming formulation that uses our 2-hop relay network results as a building block in large lossy multihop networks. Through simulations, we verify the superiority of our proposed schemes over state-of-the art.

In this paper, we develop a distributed rate-control algorithm for networks with multiple unicast sessions when network coding is allowed across different sessions. Building on recent flow-based characterization ofpairwise intersession network coding, the corresponding optimal rate-control problem is formulated as a convex optimization problem. The formulation exploits pairwise coding possibilities between any pair of sessions, where any coded symbol is formed by coding over at most two original symbols. The objective function is the sum of the utilities based on the rates supported by each unicast session. Working on the Lagrangian of the formulated problem, a distributed algorithm is developed with little coordination among intermediate nodes. Each unicast session has the freedom to choose its own utility function. The only information exchange required by the source is the weighted sum of the queue length of each link, which can be piggybacked to the acknowledgment messages. In addition to the optimal rate-control algorithm, we propose a decentralizedpairwise random codingscheme that decouples the decision of coding from that of rate control, which further enhances the distributiveness of the proposed scheme. The convergence of the rate-control algorithm is proven analytically and verified by extensive simulations. Simulation results also demonstrate the advantage of the proposed algorithm over the state-of-the-art in terms of both throughput and fairness.

For wireless multi-hop networks with unicast sessions, most coding opportunities involve only two or three sessions as coding across many sessions requires greater transmission power to broadcast the coded symbol to many receivers, which enhances interference. This work shows that with a new flow-based characterization of pairwise intersession network coding (coding across two unicast sessions), an optimal joint coding, scheduling, and rate-control scheme can be devised and implemented using only the binary XOR operation. The new scheduling/rate-control scheme demonstrates provably graceful throughput degradation with imperfect scheduling, which facilitates the design tradeoff between the throughput optimality and computational complexity of different scheduling schemes. Our results show that pairwise intersession network coding improves the throughput of non-coding solutions regardless of whether perfect/imperfect scheduling is used. Both the deterministic and stochastic packet arrivals and departures are considered. This work shows a striking resemblance between pairwise intersession network coding and non-coded solutions, and thus advocates extensions of non-coding wisdoms to their network coding counterpart.

In this paper we develop a distributed rate control algorithm for multiple-unicast-sessions when network coding is allowed. Building on our recent flow-based characterization of network coding, we formulate the problem as a convex optimization problem. The formulation exploits pairwise coding possibilities between any pair of sessions, where the objective function is the sum of the utilities based on the rates supported by each session. With some manipulation on the Lagrangian of the formulated problem, a distributed algorithm is developed with no interaction between intermediate nodes, and each source having the freedom to choose its own utility function. The only information required by the source is the weighted sum of the queue length updates of each link, which can be piggy-backed on the acknowledgment messages. In addition to the optimal rate control algorithm, we propose a decentralized pairwise random coding scheme (PRC) that is optimal when a sufficiently large finite field is used for network coding. The convergence of the rate control algorithm is proved analytically and verified by extensive simulations. Simulations also demonstrate the advantage of our algorithm over the state-of-the-art in terms of throughput and fairness.