Large Language Model (LLM) agent systems have advanced rapidly, driven by their strong generalization in zero-shot settings. To further enhance reasoning and accuracy on complex tasks, Multi-Agent Debate (MAD) has emerged as a promising framework that engages multiple LLM agents in structured debates to encourage diverse reasoning. However, triggering MAD for every query is inefficient, as it incurs substantial computational (token) cost and may even degrade accuracy by overturning correct answers from single-agent. To address these limitations, we propose intelligent Multi-Agent Debate (iMAD), a token-efficient framework that selectively triggers MAD only when it is likely to be beneficial (i.e., correcting an initially wrong answer). To achieve this goal, iMAD learns generalizable model behaviors to make accurate debate decisions. Specifically, iMAD first prompts a single agent to produce a structured self-critique response, from which we extract 41 interpretable linguistic and semantic features capturing hesitation cues. Then, iMAD uses a lightweight debate decision classifier, trained using our proposed FocusCal loss without test-dataset-specific tuning, to make robust zero-shot debate decisions. Through extensive experiments using six (visual) question answering datasets against five competitive baselines, we show that iMAD significantly reduces token usage (by up to 92%) while also improving final answer accuracy (by up to 13.5%).

While eye tracking provides valuable capabilities for virtual reality, such as gaze interaction and dynamic foveated rendering (DFR), eye-tracking data can inadvertently reveal sensitive user information if not properly protected. Current protections, such as adding permission prompts or gatekeeping gaze data, are insufficient on DFR-enabled systems because gaze data is used internally to drive DFR. When DFR is implemented, objects in the fovea (i.e., immediate gaze area) incur a higher GPU workload than those in the periphery. This gaze-contingent workload creates a novel side channel, which can be leveraged to reconstruct gaze positions. Specifically, we design a novel attack that sweeps imperceptible high-cost objects (HCOs) across the user's field of view and logs rendering performance metrics (e.g., frame rate or frame time) commonly exposed through standard game engines. Then, we correlate variation in these metrics (caused by HCO-foveal overlap) with the known HCOs' positions to infer gaze coordinates directly without using eye-tracking APIs. Our experimental results show that mean gaze prediction errors (1.1-4.4 degrees) across the Meta Quest Pro, Varjo XR-4, and desktop platforms are comparable to typical eye-tracker accuracy. We demonstrate that the attack generalizes across various hardware platforms, standard game engines, and foveated rendering pipelines. Finally, we design defense mechanisms based on supervised and unsupervised detectors that can flag the attack reliably (F1 of 0.99) over short time windows.

Real-time multi-label video classification on embedded devices is constrained by limited compute and energy budgets. Yet, video streams exhibit structural properties such as label sparsity, temporal continuity, and label co-occurrence that can be leveraged for more efficient inference. We introduce Polymorph, a context-aware framework that activates a minimal set of lightweight Low Rank Adapters (LoRA) per frame. Each adapter specializes in a subset of classes derived from co-occurrence patterns and is implemented as a LoRA weight over a shared backbone. At runtime, Polymorph dynamically selects and composes only the adapters needed to cover the active labels, avoiding fullmodel switching and weight merging. This modular strategy improves scalability while reducing latency, and energy overhead. Polymorph achieves 40% lower energy consumption and improves mAP by 9 points over strong baselines executing the TAO dataset.

Augmented Reality (AR) headsets continuously sense their surroundings, capturing nearby bystanders and raising privacy risks. Visual bystander privacy-enhancing technologies (PETs) mitigate this risk by detecting bystanders in egocentric scene views and applying privacy transformations (e.g., obfuscation). However, traditional PET evaluation is human-dependent, high-overhead, and device-specific, making it difficult to reproduce across devices. We present EvaluatAR, a cross-device evaluation framework for rapid prototyping at the early stage of PET evaluation. Our framework enables controlled replication of experimental conditions by standardizing PET inputs (sensor data and visual stimuli) and outputs through a record-replay workflow. We validate EvaluatAR through three case studies on HoloLens 2, Magic Leap 2, and Meta Quest 3 across implicit (continuous, context-driven) and explicit (intent-driven) PETs: (1) cross-device replay of inputs to a PET to reveal device-specific privacy-performance trade-offs; (2) generalizability of the same framework workflow across implicit and explicit PET design categories; and (3) replay of privacy-relevant edge cases to diagnose failures and validate PET modifications, yielding an improvement over the state-of-the-art baseline. These results demonstrate EvaluatAR's support for rapid, iterative PET development to advance reproducible cross-device evaluation of bystander PETs at a critical moment in the emergence of ubiquitous AR.

High-resolution Vision-Language Models (VLMs) are widely used in multimodal tasks to enhance accuracy by preserving detailed image information. However, these models often generate an excessive number of visual tokens due to the need to encode multiple partitions of a high-resolution image input. Processing such a large number of visual tokens poses significant computational challenges, particularly for resource-constrained commodity GPUs. To address this challenge, we propose High-Resolution Early Dropping (HiRED), a plug-and-play token-dropping method designed to operate within a fixed token budget. HiRED leverages the attention of CLS token in the vision transformer (ViT) to assess the visual content of the image partitions and allocate an optimal token budget for each partition accordingly. The most informative visual tokens from each partition within the allocated budget are then selected and passed to the subsequent Large Language Model (LLM). We showed that HiRED achieves superior accuracy and performance, compared to existing token-dropping methods. Empirically, HiRED-20% (i.e., a 20% token budget) on LLaVA-Next-7B achieves a 4.7x increase in token generation throughput, reduces response latency by 78%, and saves 14% of GPU memory for single inference on an NVIDIA TESLA P40 (24 GB). For larger batch sizes (e.g., 4), HiRED-20% prevents out-of-memory errors by cutting memory usage by 30%, while preserving throughput and latency benefits.

Split Learning (SL) is an emerging privacy-preserving machine learning technique that enables resource constrained edge devices to participate in model training by partitioning a model into client-side and server-side sub-models. While SL reduces computational overhead on edge devices, it encounters significant challenges in heterogeneous environments where devices vary in computing resources, communication capabilities, environmental conditions, and privacy requirements. Although recent studies have explored heterogeneous SL frameworks that optimize split points for devices with varying resource constraints, they often neglect personalized privacy requirements and local model customization under varying environmental conditions. To address these limitations, we propose P3SL, a Personalized Privacy-Preserving Split Learning framework designed for heterogeneous, resource-constrained edge device systems. The key contributions of this work are twofold. First, we design a personalized sequential split learning pipeline that allows each client to achieve customized privacy protection and maintain personalized local models tailored to their computational resources, environmental conditions, and privacy needs. Second, we adopt a bi-level optimization technique that empowers clients to determine their own optimal personalized split points without sharing private sensitive information (i.e., computational resources, environmental conditions, privacy requirements) with the server. This approach balances energy consumption and privacy leakage risks while maintaining high model accuracy. We implement and evaluate P3SL on a testbed consisting of 7 devices including 4 Jetson Nano P3450 devices, 2 Raspberry Pis, and 1 laptop, using diverse model architectures and datasets under varying environmental conditions. Experimental results demonstrate that P3SL significantly mitigates privacy leakage risks, reduces system energy consumption by up to 59.12%, and consistently retains high accuracy compared to the state-of-the-art heterogeneous SL system.

With the advancement of Artificial Intelligence (AI) towards multiple modalities (language, vision, speech, etc.), multi-modal models have increasingly been used across various applications (e.g., visual question answering or image generation/captioning). Despite the success of AI as a service for multi-modal applications, it relies heavily on clouds, which are constrained by bandwidth, latency, privacy concerns, and unavailability under network or server failures. While on-device AI becomes popular, supporting multiple tasks on edge devices imposes significant resource challenges. To address this, we introduce S2M3, a split-and-share multi-modal architecture for multi-task inference on edge devices. Inspired by the general-purpose nature of multi-modal models, which are composed of multiple modules (encoder, decoder, classifier, etc.), we propose to split multi-modal models at functional-level modules; and then share common modules to reuse them across tasks, thereby reducing resource usage. To address cross-model dependency arising from module sharing, we propose a greedy module-level placement with per-request parallel routing by prioritizing compute-intensive modules. Through experiments on a testbed consisting of 14 multi-modal models across 5 tasks and 10 benchmarks, we demonstrate that S2M3 can reduce memory usage by up to 50% and 62% in single-task and multi-task settings, respectively, without sacrificing accuracy. Furthermore, S2M3 achieves optimal placement in 89 out of 95 instances (93.7%) while reducing inference latency by up to 56.9% on resource-constrained devices, compared to cloud AI.

The growing gap between the increasing complexity of large language models (LLMs) and the limited computational budgets of edge devices poses a key challenge for efficient on-device inference, despite gradual improvements in hardware capabilities. Existing strategies, such as aggressive quantization, pruning, or remote inference, trade accuracy for efficiency or lead to substantial cost burdens. This position paper introduces a new framework that leverages speculative decoding, previously viewed primarily as a decoding acceleration technique for autoregressive generation of LLMs, as a promising approach specifically adapted for edge computing by orchestrating computation across heterogeneous devices. We propose SLED, a framework that allows lightweight edge devices to draft multiple candidate tokens locally using diverse draft models, while a single, shared edge server verifies the tokens utilizing a more precise target model. To further increase the efficiency of verification, the edge server batches the diverse verification requests from devices. This approach supports heterogeneous devices and reduces server-side memory footprint by sharing a single upstream target model across devices. Our initial experiments with Jetson Orin Nano, Raspberry Pi 4B/5, and an edge server equipped with 4 Nvidia A100 GPUs indicate substantial benefits: ×2.2 higher system throughput, ×2.8 higher system capacity, and better cost efficiency, all without sacrificing model accuracy.

We consider a remote inference system with multiple modalities, where a multimodal machine learning (ML) model performs real-time inference using features collected from remote sensors. When sensor observations evolve dynamically over time, fresh features are critical for inference tasks. However, timely delivery of features from all modalities is often infeasible because of limited network resources. Towards this end, in this paper, we study a two-modality scheduling problem that seeks to minimize the ML model’s inference error, expressed as a penalty function of the Age of Information (AoI) vector of the two modalities. We develop an index-based threshold policy and prove its optimality. Specifically, the scheduler switches to the other modality once the current modality’s index function exceeds a predetermined threshold. We show that both modalities share the same threshold and that the index functions and the threshold can be computed efficiently. Our optimality results hold for general AoI functions (which could be non-monotonic and non-separable) and heterogeneous transmission times across modalities. To demonstrate the importance of considering a task-oriented AoI function, we conduct numerical experiments based on robot state prediction and compare our policy with round-robin and uniform random policies (both are oblivious to the AoI and the inference error). The results show that our policy reduces inference error by up to 55% compared with these baselines.

Network slicing plays a crucial role in realizing 5G/6G advances, enabling diverse Service Level Agreement (SLA) requirements related to latency, throughput, and reliability. Since network slices are deployed end-to-end (E2E), across multiple domains including access, transport, and core networks, it is essential to efficiently decompose an E2E SLA into domain-level targets, so that each domain can provision adequate resources for the slice. However, decomposing SLAs is highly challenging due to the heterogeneity of domains, dynamic network conditions, and the fact that the SLA orchestrator is oblivious to the domain's resource optimization. In this work, we propose Odin, a Bayesian Optimization-based solution that leverages each domain's online feedback for provably-efficient SLA decomposition. Through theoretical analyses and rigorous evaluations, we demonstrate that Odin's E2E orchestrator can achieve up to 45% performance improvement in SLA satisfaction when compared with baseline solutions whilst reducing overall resource costs even in the presence of noisy feedback from the individual domains.

Mixed Reality (MR) devices are being increasingly adopted across a wide range of real-world applications, ranging from education and healthcare to remote work and entertainment. However, the unique immersive features of MR devices, such as 3D spatial interactions and the encapsulation of virtual objects by invisible elements, introduce new vulnerabilities leading to interaction obstruction and misdirection. We implemented latency, click redirection, object occlusion, and spatial occlusion attacks within a remote collaborative MR platform using the Microsoft HoloLens 2 and evaluated user behavior and mitigations through a user study. We compared responses to MR-specific attacks, which exploit the unique characteristics of remote collaborative immersive environments, and traditional security attacks implemented in MR. Our findings indicate that users generally exhibit lower recognition rates for immersive attacks (e.g., spatial occlusion) compared to attacks inspired by traditional ones (e.g., click redirection). Our results demonstrate a clear gap in user awareness and responses when collaborating remotely in MR environments. Our findings emphasize the importance of training users to recognize potential threats and enhanced security measures to maintain trust in remote collaborative MR systems.

Radar spoofing attacks mislead victim radars by injecting false information. Successful attacks require prior knowledge of the victim radar's mode and parameters, and existing works obtain this critical information with expensive equipment, e.g., software-defined radio or spectrum analyzer. In this paper, we proposeWaston, a low-cost system for radar mode detection and parameter estimation using commercial off-the-shelf (COTS) mmWave radars. To overcome the disadvantage of low sampling frequency of COTS mmWave radars, we design two special local signals to detect frequency points and spectral shapes for radar mode detection. We propose a novel parameter estimation algorithm to estimate frequency- and time-domain parameters for spoofing different radars. We have implemented a prototype on the TI AWR1843 platform and conducted extensive experiments to evaluate the performance ofWaston. Our experimental results demonstrate thatWastonachieves an accuracy of 100$\%$for mode detection and 99$\%$for parameter estimation. Furthermore, we demonstrate that the estimated parameters can be used to launch a successful spoofing attack against the victim radar.

In this paper, we study the two-level ski-rental problem, where a user needs to fulfill a sequence of demands for multiple items by choosing one of the three payment options: paying for the on-demand usage (i.e., rent), buying individual items (i.e., single purchase), and buying all the items (i.e., combo purchase). Without knowing future demands, the user aims to minimize the total cost (i.e., the sum of the rental, single purchase, and combo purchase costs) by balancing the trade-off between the expensive upfront costs (for purchase) and the potential future expenses (for rent). We first design a robust online algorithm (RDTSR) that offers a worst-case performance guarantee. While online algorithms are robust against the worst-case scenarios, they are often overly cautious and thus suffer a poor average performance in typical scenarios. On the other hand, Machine Learning (ML) algorithms typically show promising average performance in various applications but lack worst-case performance guarantees. To harness the benefits of both methods, we develop a learning-augmented algorithm (LADTSR) by integrating ML predictions into the robust online algorithm, which outperforms the robust online algorithm under accurate predictions while ensuring worst-case performance guarantees even when predictions are inaccurate. Finally, we conduct numerical experiments on both synthetic and real-world trace data to corroborate the effectiveness of our approach.

Federated Learning (FL) is an emerging distributed machine learning (ML) technique that enables in-situ model training and inference on decentralized edge devices. We propose Totoro, a novel scalable FL engine, that enables massive FL applications to run simultaneously on edge networks. The key insight is to explore a distributed hash table (DHT)-based peer-to-peer (P2P) model to re-architect the centralized FL system design into a fully decentralized one. In contrast to previous studies where many FL applications shared one centralized parameter server, Totoro assigns a dedicated parameter server to each individual application. Any edge node can act as any application's coordinator, aggregator, client selector, worker (participant device), or any combination of the above, thereby radically improving scalability and adaptivity. Totoro introduces three innovations to realize its design: a locality-aware P2P multi-ring structure, a publish/subscribe-based forest abstraction, and a bandit-based exploitation-exploration path planning model. Real-world experiments on 500 Amazon EC2 servers show that Totoro scales gracefully with the number of FL applications and N edge nodes, speeds up the total training time by 1.2 × -14.0×, achieves O (logN) hops for model dissemination and gradient aggregation with millions of nodes, and efficiently adapts to the practical edge networks and churns.

In this paper, we study the multi-armed bandit problem in the best-of-both-worlds (BOBW) setting with heavy-tailed losses, where the losses can be negative and unbounded but have $(1+v)$-th raw moments bounded by $u^{1+v}$ for some known $u>0$ and $v\in(0,1]$. Specifically, we consider the BOBW setting where the underlying environment could be either (oblivious) adversarial (i.e., the loss distribution can change arbitrarily over time) or stochastic (i.e., the loss distribution is fixed over time) and is unknown to the decision-maker a prior, and propose an algorithm that achieves a $T^{\frac{1}{1+v}}$-type worst-case (pseudo-)regret in the adversarial regime and a $\log T$-type gap-dependent regret in the stochastic regime, where $T$ is the time horizon. Compared to the state-of-the-art results, our algorithm offers stronger \emph{high-probability} regret guarantees rather than expected regret guarantees, and more importantly, relaxes a strong technical assumption on the loss distribution. This assumption is needed even for the weaker expected regret obtained in the literature and is generally hard to verify in practice. As a byproduct, relaxing this assumption leads to the first near-optimal regret result for heavy-tailed bandits with Huber contamination in the adversarial regime, in contrast to all previous works focused on the (easier) stochastic regime. Our result also implies a high-probability BOBW regret guarantee when the bounded true losses are protected with pure Local Differential Privacy (LDP), while the existing work ensures the (weaker) \emph{approximate} LDP with the regret bounds in expectation only.

Modern targeted attacks such as Advanced Persistent Threats use multiple hosts as stepping stones and move laterally across them to gain deeper access to the network. However, existing defenses lack end-to-end information flow visibility across hosts and cannot block cross-host attack traffic in real time. In this paper, we propose P4Control, a network defense system that precisely confines end-to-end information flows in a network and prevents cross-host attacks at line rate. P4Control introduces a novel in-network decentralized information flow control (DIFC) mechanism and is the first work that enforces DIFC at the network level at network line rate. This is achieved through: (1) an in-network primitive based on programmable switches for tracking inter-host information flows and enforcing line-rate DIFC policies; (2) a lightweight eBPF-based primitive deployed on hosts for tracking intra-host information flows. P4Control also provides an expressive policy framework for specifying DIFC policies against different attack scenarios. We conduct extensive evaluations to show that P4Control can effectively prevent cross-host attacks in real time, while maintaining line-rate network performance and imposing minimal overhead on the network and host machines. It is also noteworthy that P4Control can facilitate the realization of a zero trust architecture through its fine-grained least-privilege network access control.

As Augmented Reality (AR) devices become more prevalent and commercially viable, the need for quick, efficient, and secure schemes for pairing these devices has become more pressing. Current methods to securely exchange holograms require users to send this information through large data centers, creating security and privacy concerns. Existing techniques to pair these devices on a local network and share information fall short in terms of usability and scalability. These techniques either require hardware not available on AR devices, intricate physical gestures, removal of the device from the head, do not scale to multiple pairing partners, or rely on methods with low entropy to create encryption keys. To that end, we propose a novel pairing system, called GazePair, that improves on all existing local pairing techniques by creating an efficient, effective, and intuitive pairing protocol. GazePair uses eye gaze tracking and a spoken key sequence cue (KSC) to generate identical, independently generated symmetric encryption keys with 64 bits of entropy. GazePair also achieves improvements in pairing success rates and times over current methods. Additionally, we show that GazePair can extend to multiple users. Finally, we assert that GazePair can be used on any Mixed Reality (MR) device equipped with eye gaze tracking.

In this paper, we study the role of feedback in online learning with switching costs. It has been shown that the minimax regret is $\widetilde{\Theta}(T^{2/3})$ under bandit feedback and improves to $\widetilde{\Theta}(\sqrt{T})$ under full-information feedback, where $T$ is the length of the time horizon. However, it remains largely unknown how the amount and type of feedback generally impact regret. To this end, we first consider the setting of bandit learning with extra observations; that is, in addition to the typical bandit feedback, the learner can freely make a total of $B_{\mathrm{ex}}$ *extra observations*. We fully characterize the minimax regret in this setting, which exhibits an interesting *phase-transition phenomenon*: when $B_{\mathrm{ex}} = O(T^{2/3})$, the regret remains $\widetilde{\Theta}(T^{2/3})$, but when $B_{\mathrm{ex}} = \Omega(T^{2/3})$, it becomes $\widetilde{\Theta}(T/\sqrt{B_{\mathrm{ex}}})$, which improves as the budget $B_{\mathrm{ex}}$ increases. To design algorithms that can achieve the minimax regret, it is instructive to consider a more general setting where the learner has a budget of $B$ *total* observations. We fully characterize the minimax regret in this setting as well and show that it is $\widetilde{\Theta}(T/\sqrt{B})$, which scales smoothly with the total budget $B$. Furthermore, we propose a generic algorithmic framework, which enables us to design different learning algorithms that can achieve matching upper bounds for both settings based on the amount and type of feedback. One interesting finding is that while bandit feedback can still guarantee optimal regret when the budget is relatively limited, it no longer suffices to achieve optimal regret when the budget is relatively large.

Bandits with arm selection constraints and bandits with switching costs have both gained recent attention in wireless networking research. Pessimistic-optimistic algorithms, which combine bandit learning with virtual queues to track the constraints, are commonly employed in the former. Block-based algorithms, where switching is disallowed within a block, are commonly employed in the latter. While efficient algorithms have been developed for both problems, it remains challenging to guarantee low regret and constraint violation in a bandit problem that includes both arm selection constraints and switching costs due to the tight coupling between the two. Here, switching may be necessary to decrease the constraint violation but comes at the cost of increased switching regret. In this paper, we tackle the constrained bandits with switching costs problem, for which we design a block-based pessimistic-optimistic algorithm. We identify three timely wireless networking applications for this framework in edge computing, mobile crowdsensing, and wireless network selection. We also prove that our algorithm achieves sublinear regret and vanishing constraint violation and corroborate these results with synthetic simulations and extensive trace-based simulations in the wireless network selection setting.

Augmented Reality (AR) devices are set apart from other mobile devices by the immersive experience they offer. While the powerful suite of sensors on modern AR devices is necessary for enabling such an immersive experience, they can create unease in bystanders (i.e., those surrounding the device during its use) due to potential bystander data leaks, which is called the bystander privacy problem. In this paper, we propose BystandAR, the first practical system that can effectively protect bystander visual (camera and depth) data in real-time with only on-device processing. BystandAR builds on a key insight that the device user's eye gaze and voice are highly effective indicators for subject/bystander detection in interpersonal interaction, and leverages novel AR capabilities such as eye gaze tracking, wearer-focused microphone, and spatial awareness to achieve a usable frame rate without offloading sensitive information. Through a 16-participant user study,we show that BystandAR correctly identifies and protects 98.14% of bystanders while allowing access to 96.27% of subjects. We accomplish this with average frame rates of 52.6 frames per second without the need to offload unprotected bystander data to another device.

Augmented Reality (AR) devices are set apart from other mobile devices by the immersive experience they offer. While the powerful suite of sensors on modern AR devices is necessary for enabling such an immersive experience, they can create unease in bystanders (i.e., those surrounding the device during its use) due to potential bystander data leaks, which is called the bystander privacy problem. In this poster, we propose BystandAR, the first practical system that can effectively protect bystander visual (camera and depth) data in real-time with only on-device processing. BystandAR builds on a key insight that the device user's eye gaze and voice are highly effective indicators for subject/bystander detection in interpersonal interaction, and leverages novel AR capabilities such as eye gaze tracking, wearer-focused microphone, and spatial awareness to achieve a usable frame rate without offloading sensitive information. Through a 16-participant user study, we show that BystandAR correctly identifies and protects 98.14% of bystanders while allowing access to 96.27% of subjects. We accomplish this with average frame rates of 52.6 frames per second without the need to offload unprotected bystander data to another device.

We propose a practical and efficient radar interference mitigation system, Radar-CA. Radar-CA overcomes the limitations of requiring any additional equipment or resources. Radar-CA transfers the access time estimation problem to a frequency estimation problem, enabling interference mitigation through a central controller, and our preliminary result shows that Radar-CA is capable of mitigating interference efficiently in a dense radar network.

In this article, we consider a discrete-time information-update system, where a service provider can proactively retrieve information from the information source to update its data and users query the data at the service provider. One example is crowdsensing-based applications. In order to keep users satisfied, the application desires to provide users with fresh data, where the freshness is measured by the age-of-information (AoI). However, maintaining fresh data requires the application to update its database frequently, which incurs an update cost (e.g., incentive payment). Hence, there exists a natural tradeoff between the AoI and the update cost at the service provider who needs to make update decisions. To capture this tradeoff, we formulate an optimization problem with the objective of minimizing the total cost, which is the sum of the staleness cost (which is a function of the AoI) and the update cost. Then, we provide two useful guidelines for the design of efficient update policies. Following these guidelines and assuming that the aggregated request arrival process is Bernoulli, we prove that there exists a threshold-based policy that is optimal among all online policies and thus focus on the class of threshold-based policies. Furthermore, we derive the closed-form formula for computing the long-term average cost under any threshold-based policy and obtain the optimal threshold. Finally, we perform extensive simulations using both synthetic data and real traces to verify our theoretical results and demonstrate the superior performance of the optimal threshold-based policy compared with several baseline policies.

Millimeter-wave (mmWave) radars have found applications in a wide range of domains, including human tracking, health monitoring, and autonomous driving, for their unobtrusive nature and high range accuracy. These capabilities, however, if used for malicious purposes, could also result in serious security and privacy issues. For example, a user’s daily life could be secretly monitored by a spy radar. Hence, there is a strong urge to develop systems that can detect and locate such spy radars. In this paper, we proposeRadar2, a practical system for passive spy radar detection and localization using a single commercial off-the-shelf (COTS) mmWave radar. Specifically, we propose a novelFrequency Component Detectionmethod to detect the existence of mmWave signals, distinguish between mmWave radar and WiGig signals using a waveform classifier based on a convolutional neural network (CNN), and localize spy radars using triangulation based on the detector’s observations at multiple anchor points. Not only doesRadar2work for different types of mmWave radar, but it can also detect and localize multiple radars simultaneously. Finally, we performed extensive experiments to evaluate the effectiveness and robustness ofRadar2in various settings. Our evaluation results show that the radar detection rate is above 96% and the localization error is within 0.3m. The results also reveal thatRadar2is robust against various environmental factors (e.g., room layout and human activities).

Network function virtualization (NFV) is an emerging design paradigm that replaces physical middlebox devices with software modules running on general purpose commodity servers. While gradually transitioning to NFV, Internet service providers face the problem of where to introduce NFV in order to make the most benefit of that; here, we measure the benefit by the amount of traffic that can be served in an NFV-enabled network. This problem is non-trivial as it is composed of two challenging subproblems: 1) placement of nodes to support virtual network functions (referred to as VNF-nodes); 2) allocation of the VNF-nodes’ resources to network flows. These two subproblems must be jointly considered to satisfy the objective of serving the maximum amount of traffic. This problem has been studied for the one-dimensional setting, where all network flows require one network function, which requires a unit of resource to process a unit of flow. In this work, we consider the multi-dimensional setting, where flows must be processed by multiple network functions, which require a different amount of each resource to process a unit of flow. The multi-dimensional setting introduces new challenges in addition to those of the one-dimensional setting (e.g., NP-hardness and non-submodularity) and also makes the resource allocation subproblem a multi-dimensional generalization of the generalized assignment problem with assignment restrictions. To address these difficulties, we propose a novel two-level relaxation method that allows us to draw a connection to the sequence submodular theory and utilize the property of sequence submodularity along with the primal-dual technique to design two approximation algorithms. We further prove that the proposed algorithms have a non-trivial approximation ratio that depends on the number of VNF-nodes, resources, and a measure of the available resource compared to flow demand. Finally, we perform trace-driven simulations to show the effectiveness of the proposed algorithms.

In this paper, we consider a discrete-time information-update system, where a service provider can proactively retrieve information from the information source to update its data and users query the data at the service provider. One example is crowdsensing-based applications. In order to keep users satisfied, the application desires to provide users with fresh data, where the freshness is measured by the Age-of-Information (AoI). However, maintaining fresh data requires the application to update its database frequently, which incurs an update cost (e.g., incentive payment). Hence, there exists a natural tradeoff between the AoI and the update cost at the service provider who needs to make update decisions. To capture this tradeoff, we formulate an optimization problem with the objective of minimizing the total cost, which is the sum of the staleness cost (which is a function of the AoI) and the update cost. Then, we provide two useful guidelines for the design of efficient update policies. Following these guidelines and assuming that the aggregated request arrival process is Bernoulli, we prove that there exists a threshold-based policy that is optimal among all online policies and thus focus on the class of threshold-based policies. Furthermore, we derive the closed-form formula for computing the long-term average cost under any threshold-based policy and obtain the optimal threshold. Finally, we perform extensive simulations using both synthetic data and real traces to verify our theoretical results and demonstrate the superior performance of the optimal threshold-based policy compared with several baseline policies.

Fueled by advances in distributed deep learning (DDL), recent years have witnessed a rapidly growing demand for resource-intensive distributed/parallel computing to process DDL computing jobs. To resolve network communication bottleneck and load balancing issues in distributed computing, the so-called "ring-all-reduce" decentralized architecture has been increasingly adopted to remove the need for dedicated parameter servers. To date, however, there remains a lack of theoretical understanding on how to design resource optimization algorithms for efficiently scheduling ring-all-reduce DDL jobs in computing clusters. This motivates us to fill this gap by proposing a series of new resource scheduling designs for ring-all-reduce DDL jobs. Our contributions in this paper are threefold: i) We propose a new resource scheduling analytical model for ring-all-reduce deep learning, which covers a wide range of objectives in DDL performance optimization (e.g., excessive training avoidance, energy efficiency, fairness); ii) Based on the proposed performance analytical model, we develop an efficient resource scheduling algorithm called GADGET (greedy ring-all-reduce distributed graph embedding technique), which enjoys a provable strong performance guarantee; iii) We conduct extensive trace-driven experiments to demonstrate the effectiveness of the GADGET approach and its superiority over the state of the art.

Powered by advances in deep learning (DL) techniques, machine learning and artificial intelligence have achieved astonishing successes. However, the rapidly growing needs for DL also led to communication- and resource-intensive distributed training jobs for large-scale DL training, which are typically deployed over GPU clusters. To sustain the ever-increasing demand for DL training, the so-called "ring-all-reduce" (RAR) technologies have recently emerged as a favorable computing architecture to efficiently process network communication and computation load in GPU clusters. The most salient feature of RAR is that it removes the need for dedicated parameter servers, thus alleviating the potential communication bottleneck. However, when multiple RAR-based DL training jobs are deployed over GPU clusters, communication bottlenecks could still occur due to contentions between DL training jobs. So far, there remains a lack of theoretical understanding on how to design contention-aware resource scheduling algorithms for RAR-based DL training jobs, which motivates us to fill this gap in this work. Our main contributions are three-fold: i) We develop a new analytical model that characterizes both communication overhead related to the worker distribution of the job and communication contention related to the co-location of different jobs; ii) Based on the proposed analytical model, we formulate the problem as a non-convex integer program to minimize the makespan of all RAR-based DL training jobs. To address the unique structure in this problem that is not amenable for optimization algorithm design, we reformulate the problem into an integer linear program that enables provable approximation algorithm design called SJF-BCO (Smallest Job First with Balanced Contention and Overhead); and iii) We conduct extensive experiments to show the superiority of SJF-BCO over existing schedulers. Collectively, our results contribute to the state-of-the-art of distributed GPU system optimization and algorithm design.

We study a stochastic bandit problem with a general unknown reward function and a general unknown constraint function. Both functions can be non-linear (even non-convex) and are assumed to lie in a reproducing kernel Hilbert space (RKHS) with a bounded norm. This kernelized bandit setup strictly generalizes standard multi-armed bandits and linear bandits. In contrast to safety-type hard constraints studied in prior works, we consider soft constraints that may be violated in any round as long as the cumulative violations are small, which is motivated by various practical applications. Our ultimate goal is to study how to utilize the nature of soft constraints to attain a finer complexity-regret-constraint trade-off in the kernelized bandit setting. To this end, leveraging primal-dual optimization, we propose a general framework for both algorithm design and performance analysis. This framework builds upon a novel sufficient condition, which not only is satisfied under general exploration strategies, including \emph{upper confidence bound} (UCB), \emph{Thompson sampling} (TS), and new ones based on \emph{random exploration}, but also enables a unified analysis for showing both sublinear regret and sublinear or even zero constraint violation. We demonstrate the superior performance of our proposed algorithms via numerical experiments based on both synthetic and real-world datasets. Along the way, we also make the first detailed comparison between two popular methods for analyzing constrained bandits and Markov decision processes (MDPs) by discussing the key difference and some subtleties in the analysis, which could be of independent interest to the communities.

In this paper, we study the problem of global reward maximization with only partial distributed feedback. This problem is motivated by several real-world applications (e.g., cellular network configuration, dynamic pricing, and policy selection) where an action taken by a central entity influences a large population that contributes to the global reward. However, collecting such reward feedback from the entire population not only incurs a prohibitively high cost, but often leads to privacy concerns. To tackle this problem, we consider differentially private distributed linear bandits, where only a subset of users from the population are selected (called clients) to participate in the learning process and the central server learns the global model from such partial feedback by iteratively aggregating these clients’ local feedback in a differentially private fashion. We then propose a unified algorithmic learning framework, called differentially private distributed phased elimination (DP-DPE), which can be naturally integrated with popular differential privacy (DP) models (including central DP, local DP, and shuffle DP). Furthermore, we prove that DP-DPE achieves both sublinear regret and sublinear communication cost. Interestingly, DP-DPE also achieves privacy protection “for free” in the sense that the additional cost due to privacy guarantees is a lower-order additive term. Finally, we conduct simulations to corroborate our theoretical results and demonstrate the effectiveness of DP-DPE.

Multi-user panoramic video streaming demands 4~6× bandwidth of a regular video with the same resolution, which poses a significant challenge on the wireless scheduling design to achieve desired performance. On the other hand, recent studies reveal that one can effectively predict the user's Field-of-View (FoV) and thus simply deliver the corresponding portion instead of the entire scenes. Motivated by this important fact, we aim to employ autoregressive process for motion prediction and analytically characterize the user's successful viewing probability as a function of the delivered portion. Then, we consider the problem of wireless scheduling design with the goal of maximizing application-level throughput (i.e., average rate for successfully viewing the desired content) and service regularity performance (i.e., how often each user gets successful views) subject to the minimum required service rate and wireless interference constraints. As such, we incorporate users' successful viewing probabilities into our scheduling design and develop a scheduling algorithm that not only asymptotically achieves the optimal application-level throughput but also provides service regularity guarantees. Finally, we perform simulations to demonstrate the efficiency of our proposed algorithm using a real dataset of users' head motion.

A new timeliness metric, called Age-of-Information (AoI), has recently attracted a lot of research interests for real-time applications with information updates. It has been extensively studied for various queueing models based on the probabilistic approaches, where the analyses heavily depend on the properties of specific distributions (e.g., the memoryless property of the exponential distribution or the i.i.d. assumption). In this work, we take an alternative new approach, the robust queueing approach, to analyze the Peak Age-of-Information (PAoI). Specifically, we first model the uncertainty in the stochastic arrival and service processes using uncertainty sets. This enables us to approximate the expected PAoI performance for very general arrival and service processes, including those exhibiting heavy-tailed behaviors or correlations, where traditional probabilistic approaches cannot be applied. We then derive a new bound on the PAoI in the single-source single-server setting. Furthermore, we generalize our analysis to two-source single-server systems with symmetric arrivals, which involves new challenges (e.g., the service times of the updates from two sources are coupled in one single uncertainty set). Finally, through numerical experiments, we show that our new bounds provide a good approximation for the expected PAoI. Compared to some well-known bounds in the literature (e.g., one based on Kingman's bound under the i.i.d. assumption) that tends to be inaccurate under light load, our new approximation is accurate under both light and high loads, both of which are critical scenarios for the AoI performance.

In recent years, to sustain the resource-intensive computational needs for training deep neural networks (DNNs), it is widely accepted that exploiting the parallelism in large-scale computing clusters is critical for the efficient deployments of DNN training jobs. However, existing resource schedulers for traditional computing clusters are not well suited for DNN training, which results in unsatisfactory job completion time performance. The limitations of these resource scheduling schemes motivate us to propose a new computing cluster resource scheduling framework that is able to leverage the special layered structure of DNN jobs and significantly improve their job completion times. Our contributions in this paper are three-fold: i) We develop a new resource scheduling analytical model by considering DNN's layered structure, which enables us to analytically formulate the resource scheduling optimization problem for DNN training in computing clusters; ii) Based on the proposed performance analytical model, we then develop an efficient resource scheduling algorithm based on the widely adopted parameter-server architecture using a sum-of-ratios multi-dimensional-knapsack decomposition (SMD) method to offer strong performance guarantee; iii) We conduct extensive numerical experiments to demonstrate the effectiveness of the proposed schedule algorithm and its superior performance over the state of the art.

In this paper, we study the problem of fair worker selection in Federated Learning systems, where fairness serves as an incentive mechanism that encourages more workers to participate in the federation. Considering the achieved training accuracy of the global model as the utility of the selected workers, which is typically a monotone submodular function, we formulate the worker selection problem as a new multi-round monotone submodular maximization problem with cardinality and fairness constraints. The objective is to maximize the time-average utility over multiple rounds subject to an additional fairness requirement that each worker must be selected for a certain fraction of time. While the traditional submodular maximization with a cardinality constraint is already a well-known NP-Hard problem, the fairness constraint in the multi-round setting adds an extra layer of difficulty. To address this novel challenge, we propose three algorithms: Fair Continuous Greedy (FairCGl and FairCG2) and Fair Discrete Greedy (FairDG), all of which satisfy the fairness requirement whenever feasible. Moreover, we prove nontrivial lower bounds on the achieved time-average utility under FairCGl and FairCG2. In addition, by giving a higher priority to fairness, FairDG ensures a stronger short-term fairness guarantee, which holds in every round. Finally, we perform extensive simulations to verify the effectiveness of the proposed algorithms in terms of the time-average utility and fairness satisfaction.

The deep penetration of electric vehicles (EVs) into the transportation section and the associated charging management has yielded a critical issue, namely, how to efficiently store the generated charging records. In this article, we investigate the cost-efficient charging-record storage scheme by exploiting blockchain (BC). Accounting for the operational cost due to the consensus process via the practical Byzantine fault tolerance (PBFT) protocol, we model the associated cost for storing the charging records via an ideal multiblockchain system and formulate a joint optimization of the storage selection (i.e., either storing the charging record locally or selecting one of the BCs for storing the charging record) and server-node allocation for each BC, with the objective of minimizing a systemwise cost. Despite the nature of the complicated mixed binary and integer programming problem, we exploit the decomposition structure and propose a layered algorithm (i.e., the bottom subproblem for determining the optimal storage selection and the top problem for finding the server-node allocation) to solve it. For the bottom subproblem, we exploit the nature of minimum weighted matching of the problem and propose a distributed auction-based algorithm for computing the optimal storage selection. With the optimal solution from the subproblem, we further propose an annealing-based algorithm to determine the server-node allocation for each BC. Numerical results are provided to validate the effectiveness of our proposed algorithms and the performance of our cost-efficient charging-record storage scheme via BC.

With the rapid growth of Internet-of-Things (IoT) applications in recent years, there is a strong need for wireless uplink scheduling algorithms that determine when and which subset of a large number of users should transmit to the central controller. Different from the downlink case, the central controller in the uplink scenario typically has very limited information about the users. On the other hand, periodically collecting all such information from a large number of users typically incurs a prohibitively high communication overhead. This motivates us to investigate the development of an efficient and low-overhead uplink scheduling algorithm that is suitable for large-scale IoT applications. Specifically, we first characterize a capacity outer bound subject to the sampling constraint where only a small subset of users are allowed to use control channels for system state reporting at each time. Next, we relax the sampling constraint and propose a joint sampling and transmission algorithm, which utilizes full knowledge of channel state distributions and instantaneous queue lengths to achieve the capacity outer bound. The insights obtained from this capacity-achieving algorithm allow us to develop a low-overhead scheduling algorithm that can strictly satisfy the sampling constraint with asymptotically diminishing throughput loss.

Powering cellular networks with hybrid energy supplies is not only environment-friendly but can also reduce the on-grid energy consumption, thus being emerging as a promising solution for green networking. Intelligent management of spectrum and power can increase the network utility in cellular networks with hybrid energy supplies, usually at the cost of higher energy consumption. Unlike prior studies on either the network utility maximization or on-grid energy cost minimization, this paper studies the joint spectrum and power allocation problem that maximizes the system revenue in a heterogeneous small-cell network with hybrid energy supplies. Specifically, the system revenue is considered as the difference between the network utility and on-grid energy cost. By developing the convexity of the optimization problem through transformation and reparameterization, we propose a joint spectrum and power allocation algorithm based on the primal-dual arguments to obtain the optimal solution by iteratively solving the primal and dual sub-problems of the convex optimization problem. To solve the primal sub-problem, we further propose the Lagrangian maximization based on the alternating direction method of multipliers (ADMM), and derive the optimal solution in the closed-form expression at each iteration. It is shown that the proposed joint spectrum and power allocation algorithm approaches the global optimality at the rate of 1=n with n being the number of iterations. Also, the proposed ADMM-based Lagrangian maximization algorithm approaches the primal optimal solution with the time complexity of O(1=εr) iterations with εrbeing the termination parameter. Simulation results show that in comparison with the power control with equal frequency allocation algorithm and frequency allocation with equal power allocation algorithms the proposed algorithm increases the system revenue by over 20 and 60 percent without consuming more on-grid energy when the proportional fairness utility and the weighted sum rate utility are considered with the approximate system parameter settings, respectively. Meanwhile, in comparison with the full frequency reuse case, the proposed algorithm increases the system revenue by 20 percent at least in terms of the weighted sum rate utility, although it achieves the similar system revenue when considering the proportional fairness utility. Simulation results also show that our proposed algorithm can perform well under the realistic fast fading channel conditions.

The Age-of-Information is an important metric for investigating the timeliness performance in information-update systems. In this paper, we study the AoI minimization problem under a new Pull model with replication schemes, where a user proactively sends a replicated request to multiple servers to “pull” the information of interest. Interestingly, we find that under this new Pull model, replication schemes capture a novel tradeoff between different values of the AoI across the servers (due to the random updating processes) and different response times across the servers, which can be exploited to minimize the expected AoI at the user's side. Specifically, assuming Poisson updating process for the servers and exponentially distributed response time, we derive a closed-form formula for computing the expected AoI and obtain the optimal number of responses to wait for to minimize the expected AoI. Then, we extend our analysis to the setting where the user aims to maximize the AoI-based utility, which represents the user's satisfaction level with respect to freshness of the received information. Furthermore, we consider a more realistic scenario where the user has no prior knowledge of the system. In this case, we reformulate the utility maximization problem as a stochastic Multi-Armed Bandit problem with side observations and leverage a special linear structure of side observations to design learning algorithms with improved performance guarantees. Finally, we conduct extensive simulations to elucidate our theoretical results and compare the performance of different algorithms. Our findings reveal that under the Pull model, waiting does not necessarily lead to aging; waiting for more than one response can often significantly reduce the AoI and improve the AoI-based utility in most scenarios.

With the advent of Network Function Virtualization (NFV), network services that traditionally run on proprietary dedicated hardware can now be realized using Virtual Network Functions (VNFs) that are hosted on general-purpose commodity hardware. This new network paradigm offers a great flexibility to Internet service providers (ISPs) for efficiently operating their networks (collecting network statistics, enforcing management policies, etc.). However, introducing NFV requires an investment to deploy VNFs at certain network nodes (called VNF-nodes), which has to account for practical constraints such as the deployment budget and the VNF-node capacity. To that end, it is important to design a joint VNF-nodes placement and capacity allocation algorithm that can maximize the total amount of network flows that are fully processed by the VNF-nodes while respecting such practical constraints. In contrast to most prior work that often neglects either the budget constraint or the capacity constraint, we explicitly consider both of them. We prove that accounting for these constraints introduces several new challenges. Specifically, we prove that the studied problem is not only NP-hard but also non-submodular. To address these challenges, we introduce a novel relaxation method such that the objective function of the relaxed placement subproblem becomes submodular. Leveraging this useful submodular property, we propose two algorithms that achieve an approximation ratio of \frac 12(1-1/e) and \frac 13(1-1/e) for the original non-relaxed problem, respectively. Finally, we corroborate the effectiveness of the proposed algorithms through extensive evaluations using trace-driven simulations.

The implementation of network services is changed from dedicated hardware to software middleboxes with the evolution of Network Function Virtualization (NFV). The placement of such middleboxes are complicated not only by the selection of multiple available hosting servers, but also by the traffic-changing effect of middleboxes. In this paper, we address the placement problem of a single type of traffic-diminishing middlebox (e.g., spam filters), where the objective is to minimize the total bandwidth consumption when the total number of placed middleboxes is limited. We prove the NP-hardness of checking the feasibility of our problem in general topologies. Then we propose a greedy solution and prove that it is performance-guaranteed when it generates a feasible deployment. Next we narrow down to tree-structured networks and propose an optimal dynamic programming based strategy. In order to improve the time efficiency, we also introduce an efficient greedy solution with an intuitive insight. Extensive simulations are conducted on a real-world dataset to evaluate the performance of our algorithms.

Submodularity is an important property of set functions and has been extensively studied in the literature. It models set functions that exhibit a diminishing returns property, where the marginal value of adding an element to a set decreases as the set expands. This notion has been generalized to considering sequence functions, where the order of adding elements plays a crucial role and determines the function value; the generalized notion is called sequence (or string) submodularity. In this paper, we study a new problem of robust sequence submodular maximization with cardinality constraints. The robustness is against the removal of a subset of elements in the selected sequence (e.g., due to malfunctions or adversarial attacks). Compared to robust submodular maximization for set function, new challenges arise when sequence functions are concerned. Specifically, there are multiple definitions of submodularity for sequence functions, which exhibit subtle yet critical differences. Another challenge comes from two directions of monotonicity: forward monotonicity and backward monotonicity, both of which are important to proving performance guarantees. To address these unique challenges, we design two robust greedy algorithms: while one algorithm achieves a constant approximation ratio but is robust only against the removal of a subset of contiguous elements, the other is robust against the removal of an arbitrary subset of the selected elements but requires a stronger assumption and achieves an approximation ratio that depends on the number of the removed elements. Finally, we generalize the analyses to considering sequence functions under weaker assumptions based on approximate versions of sequence submodularity and backward monotonicity.

Network Function Virtualization (NFV) has promoted the implementation of network functions from expensive hardwares to software middleboxes. These software middleboxes, also called Virtual Network Functions (VNFs), are executed on switch-connected servers. Efficiently deploying such VNFs on servers is challenging because the traffic rate of flows must be fully processed by their requested VNFs when they reach destinations, and the deployed positions of VNFs are restricted by the server capacity. In addition, each network function offers non-uniform VNF models (types) with different configurations of processing volumes and costs. This paper focuses on minimizing the total cost of deploying VNFs for providing a specific network function to all flows in tree-structured networks. First, we prove the NP-hardness of non-uniform VNF deployment in a tree topology and propose a dynamic programming based solution with a pseudo-polynomial time complexity. Then we narrow it down to three simplified cases by focusing on either uniform VNFs or the linear line topology. Specifically, three algorithms are introduced: an improved dynamic programming based algorithm for deploying uniform VNFs in a tree topology, a performance-guaranteed algorithm for deploying non-uniform VNFs in a linear line topology, and an optimal greedy algorithm for deploying uniform VNFs in a linear line topology. Additionally, we generalize our approach to a case of deploying a service chain, which consists of multiple network functions applied to flows in a specific order. We propose two solutions: one is optimal but time-consuming while another is heuristic but efficient. Extensive simulations are conducted to evaluate our algorithms.

The last decade has witnessed an unprecedented growth in the demand for data-driven real-time services. These services are fueled by emerging applications that require rapidly injecting data streams and computing updated analytics results in real-time (or near-real-time). In many of such applications, the computing resources are often shared for processing both updates from information sources and queries from end users. This requires joint scheduling of updates and queries because the service provider needs to make a critical decision upon receiving a user query: either it responds immediately with currently available but possibly stale information, or it first processes new updates and then responds with fresher information. Hence, the tradeoff between service performance (e.g., response time) and information freshness naturally arises in this context. To that end, we propose a simple single-server two-queue model that captures the coupled scheduling of updates and queries and aim to design scheduling policies that can properly address the important tradeoff between performance and freshness. Specifically, we consider the response time as a performance metric and the Age of Information (AoI) as a freshness metric. After demonstrating the limitations of the simplest First-Come-First-Served (FCFS) policy, we propose two threshold-based policies: the Query-k policy that prioritizes queries and the Update-k policy that prioritizes updates. Then, we rigorously analyze both the response time and the Peak AoI (PAoI) of the threshold-based policies. Further, we propose the Joint-(M, N) policy, which allows flexibly prioritizing updates or queries through choosing different values of two thresholds M and N. Finally, we conduct simulations to evaluate the response time and the PAoI of the proposed policies. The results show that our proposed threshold-based policies can effectively control the balance between performance and freshness.

Network function virtualization (NFV) is an emerging design paradigm that replaces physical middlebox devices with software modules running on general purpose commodity servers. While gradually transitioning to NFV, Internet service providers face the problem of where to introduce NFV in order to make the most benefit of that; here, we measure the benefit by the amount of traffic that can be serviced through the NFV. This problem is non-trivial as it is composed of two challenging subproblems: 1) placement of nodes to support virtual network functions (referred to as VNF-nodes); and 2) allocation of the VNF-nodes resources to network flows; the two subproblems need to be considered jointly to satisfy the objective of serving the maximum amount of traffic. This problem has been studied recently but for the one-dimensional setting, where all network flows require one network function, which requires a unit of resource to process a unit of flow. In this work, we extend to the multi-dimensional setting, where flows can require multiple network functions, which can also require a different amount of each resource to process a unit of flow. The multi-dimensional setting introduces new challenges in addition to those of the onedimensional setting (e.g., NP-hardness and non-submodularity) and also makes the resource allocation a multi-dimensional generalization of the generalized assignment problem with assignment restrictions. To address these difficulties, we propose a novel two-level relaxation method and utilize the primal-dual technique to design two approximation algorithms that achieve an approximation ratio of ((Z-1)(e-1))/(2e2Z(kR)1/(Z-1)) and ((e-1)(Z-1))/(2e(Z-1+eZR1/(Z-1)), where k (resp. R) is the number of VNF-nodes (resp. resources), and Z is a measure of the available resource compared to flow demand. Finally, we perform extensive trace-driven simulations to show the effectiveness of the proposed algorithms.

The multi-armed bandit (MAB) model has been widely adopted for studying many practical optimization problems (network resource allocation, ad placement, crowdsourcing, etc.) with unknown parameters. The goal of the player (i.e., the decision maker) here is to maximize the cumulative reward in the face of uncertainty. However, the basic MAB model neglects several important factors of the system in many realworld applications, where multiple arms (i.e., actions) can be simultaneously played and an arm could sometimes be “sleeping” (i.e., unavailable). Besides reward maximization, ensuring fairness is also a key design concern in practice. To that end, we propose a new Combinatorial Sleeping MAB model with Fairness constraints, called CSMAB-F, aiming to address the aforementioned crucial modeling issues. The objective is now to maximize the reward while satisfying the fairness requirement of a minimum selection fraction for each individual arm. To tackle this new problem, we extend an online learning algorithm, called Upper Confidence Bound (UCB), to deal with a critical tradeoff between exploitation and exploration and employ the virtual queue technique to properly handle the fairness constraints. By carefully integrating these two techniques, we develop a new algorithm, called Learning with Fairness Guarantee (LFG), for the CSMAB-F problem. Further, we rigorously prove that not only LFG is feasibility-optimal, but it also has a time-average regret upper bounded by N/2η + β1√mNT log T +β2N/T, where N is the total T number of arms, m is the maximum number of arms that can be simultaneously played, T is the time horizon, β1and β2are constants, and η is a design parameter that we can tune. Finally, we perform extensive simulations to corroborate the effectiveness of the proposed algorithm. Interestingly, the simulation results reveal an important tradeoff between the regret and the speed of convergence to a point satisfying the fairness constraints.

With the advent of Network Function Virtualization (NFV), network services that traditionally run on proprietary dedicated hardware can now be realized using Virtual Network Functions (VNFs) that are hosted on general-purpose commodity hardware. This new network paradigm offers a great flexibility to Internet service providers (ISPs) for efficiently operating their networks (collecting network statistics, enforcing management policies, etc.). However, introducing NFV requires an investment to deploy VNFs at certain network nodes (called VNF-nodes), which has to account for practical constraints such as the deployment budget and the VNF-node capacity. To that end, it is important to design a joint VNF-nodes placement and capacity allocation algorithm that can maximize the total amount of network flows that are fully processed by the VNF-nodes while respecting such practical constraints. In contrast to most prior work that often neglects either the budget constraint or the capacity constraint, we explicitly consider both of them. We prove that accounting for these constraints introduces several new challenges. Specifically, we prove that the studied problem is not only NP-hard but also non-submodular. To address these challenges, we introduce a novel relaxation method such that the objective function of the relaxed placement subproblem becomes submodular. Leveraging this useful submodular property, we propose two algorithms that achieve an approximation ratio of 1/2(1 - 1/e) and 1/3(1 - 1/e) for the original non-relaxed problem, respectively. Finally, we corroborate the effectiveness of the proposed algorithms through extensive evaluations using both trace-driven simulations and simulations based on synthesized network settings.

Nonorthogonal multiple access (NOMA) and mobile edge computing (MEC) have been emerging as promising techniques in narrowband Internet of Things (NB-IoT) systems to provide ubiquitously connected IoT devices with efficient transmission and computation. However, the successive interference cancellation (SIC) ordering of NOMA has become the bottleneck limiting the performance improvement for the uplink transmission, which is the dominant traffic flow of NB-IoT communications. Also, in order to guarantee the fairness of task execution latency across NB-IoT devices, the computation resource of MEC units has to be fairly allocated to tasks from IoT devices according to the task size. For these reasons, we investigate the joint optimization of SIC ordering and computation resource allocation in this paper. Specifically, we formulate a combinatorial optimization problem with the objective to minimize the maximum task execution latency required per task bit across NB-IoT devices under the limitation of computation resource. We prove the NP-hardness of this joint optimization problem. To tackle this challenging problem, we first propose an optimal algorithm to obtain the optimal SIC ordering and computation resource allocation in two stages: the convex computation resource allocation optimization followed by the combinatorial SIC ordering optimization. To reduce the computational complexity, we design an efficient heuristic algorithm for the SIC ordering optimization. As a good feature, the proposed low-complexity algorithm suffers a negligible performance degradation in comparison with the optimal algorithm. Simulation results demonstrate the benefits of NOMA in reducing the task execution latency.

This paper focuses on testing the current viability of using quantum computers for the processing of data-driven tasks fueled by emerging data science applications. We test the publicly available IBM quantum computers using Grover's algorithm, a well-known quantum search algorithm, to obtain a baseline for the general evaluations of these quantum devices and to investigate the impacts of various factors such as number of quantum bits (or qubits), qubit choice, and device choice. The main contributions of this paper include a new 4-qubit implementation of Grover's algorithm and test results showing the current capabilities of quantum computers. Our study indicates that quantum computers can currently only be used accurately for solving simple problems with very small amounts of data. There are also notable differences between different selections of the qubits in the implementation design and between different quantum devices that execute the algorithm.

Due to the fast increase of mobile traffic, most mobile network operators face the congestion issue in licensed spectrum bands. Several telecommunication vendors and operators propose to expand LTE service to the unlicensed spectrum bands to relieve the traffic congestion. However, LTE in unlicensed spectrum may interfere with Wi-Fi communications in the same bands and cause significant decrease in the quality of service of Wi-Fi. In this paper, we propose a novel mechanism that enables negotiations between two different wireless technologies (Wi-Fi and LTE), which ensures fair spectrum sharing between Wi-Fi and LTE-Unlicensed (LTE-U) in the same bands. We formulate the co-existence of Wi-Fi and LTE-U as a constrained optimization problem, and we solve the problem. We evaluate the performance of the proposed scheme via NS-3 simulations. The simulation results show that our approach can effectively improve the overall channel utilization and reduce the interference between Wi-Fi and LTE-U.

Network Function Virtualization (NFV) evolves the implementation of network functions from expensive hardwares to software middleboxes. These software middleboxes, also called Virtual Network Functions (VNFs), are executed on switch-connected servers. Efficiently deploying such VNFs is challenging, because VNFs must fully process all flows with their traffic rates before they reach their destinations while VNF locations are restricted by the constraint of vertex capacity. In addition, each network function offers heterogeneous VNF types with different configurations of processing volumes and costs. This paper focuses on minimizing the total cost of deploying VNF instances for providing a specific network function to all flows in tree-structured networks. First we prove the NP-hardness of heterogeneous VNF deployment in a tree topology and propose a dynamic programming based solution with a pseudo-polynomial time complexity. Then we narrow down to three simplified cases by focusing on homogeneous VNFs or the linear line topology. Specifically, three algorithms are introduced: an improved dynamic programming based algorithm for deploying homogeneous VNFs in a tree topology, a performance-guaranteed algorithm for deploying heterogeneous VNFs in a linear line topology, and an optimal greedy algorithm for deploying homogeneous VNFs in a linear line topology. Extensive simulations are conducted to evaluate the performance of our algorithms.

With the advent of Network Function Virtualization (NFV), Physical Network Functions (PNFs) are gradually being replaced by Virtual Network Functions (VNFs) that are hosted on general purpose servers. Depending on the call flows for specific services, the packets need to pass through an ordered set of network functions (physical or virtual) called Service Function Chains (SFC) before reaching the destination. Conceivably for the next few years during this transition, these networks would have a mix of PNFs and VNFs, which brings an interesting mix of network problems that are studied in this paper: (1) How to find an SFC-constrained shortest path between any pair of nodes? (2) What is the achievable SFC-constrained maximum flow? (3) How to place the VNFs such that the cost (the number of nodes to be virtualized) is minimized, while the maximum flow of the original network can still be achieved even under the SFC constraint? In this work, we will try to address such emerging questions. First, for the SFC-constrained shortest path problem, we propose a transformation of the network graph to minimize the computational complexity of subsequent applications of any shortest path algorithm. Second, we formulate the SFC-constrained maximum flow problem as a fractional multicommodity flow problem, and develop a combinatorial algorithm for a special case of practical interest. Third, we prove that the VNFs placement problem is NP-hard and present an alternative Integer Linear Programming (ILP) formulation. Finally, we conduct simulations to elucidate our theoretical results.

We consider the problem of scheduling real-time traffic with hard deadlines in a wireless ad hoc network. In contrast to existing real-time scheduling policies that merely ensure a minimal timely throughput, our design goal is to provide guarantees on both the timely throughput and data freshness in terms of age-of-information (AoI), which is a newly proposed metric that captures the "age" of the most recently received information at the destination of a link. The main idea is to introduce the AoI as one of the driving factors in making scheduling decisions. We first prove that the proposed scheduling policy is feasibility-optimal, i.e., satisfying the per-traffic timely throughput requirement. Then, we derive an upper bound on a considered data freshness metric in terms of AoI, demonstrating that the network-wide data freshness is guaranteed and can be tuned under the proposed scheduling policy. Interestingly, we reveal that the improvement of network data freshness is at the cost of slowing down the convergence of the timely throughput. Extensive simulations are performed to validate our analytical results. Both analytical and simulation results confirm the capability of the proposed scheduling policy to improve the data freshness without sacrificing the feasibility optimality.

With the rapid growth of Internet of Things (IoT) applications in recent years, there is a strong need for wireless uplink scheduling algorithms that determine when and which subset of a large number of users should transmit to the central controller. Different from the downlink case, the central controller in the uplink scenario typically has very limited information about the users. On the other hand, collecting all such information from a large number of users typically incurs a prohibitively high communication overhead. This motivates us to investigate the development of an efficient and low-overhead uplink scheduling algorithm that is suitable for large-scale IoT applications with limited amount of coordination from the central controller. Specifically, we first characterize a capacity outer bound subject to the sampling constraint where only a small subset of users are allowed to use control channels for system state reporting and wireless channel probing. Next, we relax the sampling constraint and propose a joint sampling and transmission algorithm, which utilizes full knowledge of channel state distributions and instantaneous queue lengths to achieve the capacity outer bound. The insights obtained from this capacity-achieving algorithm allow us to develop an efficient and low-overhead scheduling algorithm that can strictly satisfy the sampling constraint with asymptotically diminishing throughput loss. Moreover, the throughput performance of our proposed algorithm is independent of the number of users, a highly desirable property in large-scale IoT systems. Finally, we perform extensive simulations to validate our theoretical results.

This paper focuses on the design of provably efficient online link scheduling algorithms for multi-hop wireless networks. We consider single-hop traffic and the one-hop interference model. The objective is twofold: 1) maximizing the throughput when the flow sources continuously inject packets into the network, and 2) minimizing the evacuation time when there are no future packet arrivals. The prior work mostly employs the link-based approach, which leads to throughput-efficient algorithms but often does not guarantee satisfactory evacuation time performance. In this paper, we propose a novel Node-based Service-Balanced (NSB) online scheduling algorithm. NSB aims to give scheduling opportunities to heavily congested nodes in a balanced manner, by maximizing the total weight of the scheduled nodes in each scheduling cycle, where the weight of a node is determined by its workload and whether the node was scheduled in the previous scheduling cycle(s). We rigorously prove that NSB guarantees to achieve an efficiency ratio no worse (or no smaller) than 2/3 for the throughput and an approximation ratio no worse (or no greater) than 3/2 for the evacuation time. It is remarkable that NSB is both throughput-optimal and evacuation-time-optimal if the underlying network graph is bipartite. Further, we develop a lower-complexity NSB algorithm, called LC-NSB, which provides the same performance guarantees as NSB. Finally, we conduct numerical experiments to elucidate our theoretical results.

The Age-of-Information (AoI) has recently been proposed as an important metric for investigating the timeliness performance in information-update systems. Prior studies on AoI optimization often consider a Push model, which is concerned about when and how to "push" (i.e., generate and transmit) the updated information to the user. In stark contrast, in this paper we introduce a new Pull model, which is more relevant for certain applications (such as the real-time stock quotes service), where a user sends requests to the servers to proactively "pull" the information of interest. Moreover, we propose to employ request replication to reduce the AoI. Interestingly, we find that under this new Pull model, replication schemes capture a novel tradeoff between different levels of information freshness and different response times across the servers, which can be exploited to minimize the expected AoI at the user's side. Specifically, assuming Poisson updating process at the servers and exponentially distributed response time, we derive a closed-form formula for computing the expected AoI and obtain the optimal number of responses to wait for to minimize the expected AoI. Finally, we conduct numerical simulations to elucidate our theoretical results. Our findings show that waiting for more than one response can significantly reduce the AoI in most scenarios.

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.

Network Function Virtualization (NFV) has the potential to significantly reduce the capital and operating expenses, shorten product release cycle, and improve service agility. In this paper, we focus on minimizing the total number of Virtual Network Function (VNF) instances to provide a specific service (possibly at different locations) to all the flows in a network. Certain network security and analytics applications may allow fractional processing of a flow at different nodes (corresponding to datacenters), giving an opportunity for greater optimization of resources. Through a reduction from the set cover problem, we show that this problem is NP-hard and cannot even be approximated within a factor of (1 - o(1))lnm (where m is the number of flows) unless P=NP. Then, we design two simple greedy algorithms and prove that they achieve an approximation ratio of (1 - o(1))ln m + 2, which is asymptotically optimal. For special cases where each node hosts multiple VNF instances (which is typically true in practice), we also show that our greedy algorithms have a constant approximation ratio. Further, for tree topologies we develop an optimal greedy algorithm by exploiting the inherent topological structure. Finally, we conduct extensive numerical experiments to evaluate the performance of our proposed algorithms in various scenarios.

This paper focuses on the design of provably efficient online link scheduling algorithms for multi-hop wireless networks. We consider single-hop flows and the one-hop interference model. The objective is twofold: 1) maximize the throughput when the flow sources continuously inject packets into the network, and 2) minimize the evacuation time when there are no future packet arrivals. The prior work mostly employs the link-based approach, which leads to throughput-efficient algorithms but often does not guarantee satisfactory evacuation time performance. In this paper, we adopt a novel node-based approach and propose a service-balanced online scheduling algorithm, called NSB, which gives balanced scheduling opportunities to the nodes with heavy workload. We rigorously prove that NSB guarantees to achieve an efficiency ratio no worse (or no smaller) than 2/3 for the throughput and an approximation ratio no worse (or no greater) than 3/2 for the evacuation time. It is remarkable that NSB is both throughput-optimal and evacuation-time-optimal if the underlying network graph is bipartite. Further, we develop a lower-complexity NSB algorithm, called LC-NSB, which provides the same performance guarantees as NSB. Finally, we conduct numerical experiments to elucidate our theoretical results.

There have been recent attempts to develop scheduling schemes for downlink transmission in a single cell of a multi-channel (e.g., OFDM-based) cellular network. These works have been quite promising in that they have developed low-complexity index scheduling policies that are delay-optimal (in a large deviation rate-function sense). However, these policies require that the channel is ON or OFF in each time-slot with a fixed probability (i.e., there is no memory in the system), while the reality is that due to channel fading and doppler shift, channels are often time-correlated in these cellular systems. Thus, an important open question is whether one can find simple index scheduling policies that are delay-optimal even when the channels are time-correlated. In this paper, we attempt to answer this question for time-correlated ON/OFF channels. In particular, we show that the class of oldest packets first (OPF) policies that give a higher priority to packets with a large delay is delay rate-function optimal under two conditions: 1) The channel is non-negatively correlated, and 2) The distribution of the OFF period is geometric. We use simulations to further elucidate the theoretical results.

Maximum Vertex-weighted Matching (MVM) is an important link scheduling algorithm for multihop wireless networks. Under certain assumptions, it has been shown that if the underlying network graph is bipartite, MVM not only maximizes the throughput in settings with continuous packet arrivals, but also minimizes the evacuation time (i.e., time to drain all the initial packets) in settings without future packet arrivals. Further, even if the network graph is arbitrary, MVM achieves the best known performance guarantee for the evacuation time among existing online link scheduling algorithms. Also, it empirically exhibits close-to-optimal throughput performance and good delay performance. However, in an arbitrary network graph the throughput performance of MVM has not been well understood. To that end, in this paper we aim to carry out a systematic study of the throughput performance of MVM, assuming single-hop flows and the node-exclusive interference model. Inspired by the celebrated Gallai-Edmonds structure theorem, we introduce a novel topological notion, called the Gallai-Edmonds decomposition factor, and rigorously prove that the efficiency ratio of MVM is no smaller than the Gallai-Edmonds decomposition factor of the network graph. Further, we show that if the smallest size of an odd cycle in a graph is 2m + 1 for a positive integer m, then the Gallai-Edmonds decomposition factor is equal to 2m/(2m + 1). This implies that the Gallai-Edmonds decomposition factor is at least 2/3 for an arbitrary graph and is equal to 1 for bipartite graphs. Having these results, the throughput performance of MVM can be well characterized.

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.

Many interactive applications running in data centers such as web search, social networks, online gaming, and financial services are delay-sensitive, and often have a deadline. These deadlines vary across users and applications, which makes the job scheduling problem very challenging when the overall system performance needs to be optimized. In this paper, the performance of interest is the total utility gain of multiple interactive jobs, and our objective is to maximize the total utility gain. The interactive jobs arrive to the system over time, and are allowed to be partially executed before their deadlines. We focus on the preemptive scenario, where a job in service can be interrupted by other jobs, and its service can be resumed later. We propose a deadline agnostic scheduler, called ISPEED (Interactive Services with Partial Execution and Deadlines). Being deadline agnostic is an attractive property of ISPEED because data center schedulers are often not privy to individual job deadlines, and thus schedulers that are deadline dependent may not be amenable to implementation. We first prove that ISPEED achieves the maximum total utility when jobs have homogeneous deadlines and their utility functions are non-decreasing and concave. Then, in the case of heterogeneous job deadlines we prove that ISPEED achieves a competitive ratio of 2 + α, where α is a shape parameter for a large class of non-decreasing utility functions. In the special case of α = 0, i.e., The utility functions are concave, ISPEED has a competitive ratio of 2, while no causal scheduler can achieve a competitive ratio smaller than ½5+1/2. Finally, we show through trace-driven simulations that ISPEED outperforms the state-of-the-art schedulers in a wide range of scenarios.

In this paper, we focus on the scheduling problem in multichannel wireless networks, e.g., the downlink of a single cell in fourth-generation (4G) OFDM-based cellular networks. Our goal is to design practical scheduling policies that can achieve provably good performance in terms of both throughput and delay, at a low complexity. While a class of O(n2.5log n)-complexity hybrid scheduling policies is recently developed to guarantee both rate-function delay optimality (in the many-channel many-user asymptotic regime) and throughput optimality (in the general non-asymptotic setting), their practical complexity is typically high. To address this issue, we develop a simple greedy policy called Delay-based Server-Side-Greedy (D-SSG) with a lower complexity 2n2+2n, and rigorously prove that D-SSG not only achieves throughput optimality, but also guarantees near-optimal asymptotic delay performance. Specifically, the rate-function of the delay-violation probability attained by D-SSG for any fixed integer delay threshold b > 0 is no smaller than the maximum achievable rate-function by any scheduling policy for threshold b-1. Thus, we are able to achieve a reduction in complexity (from O(n2.5logn) of the hybrid policies to 2n2+ 2n) with a minimal drop in the delay performance. More importantly, in practice, D-SSG generally has a substantially lower complexity than the hybrid policies that typically have a large constant factor hidden in the O(·) notation. Finally, we conduct simulations to validate our theoretical results in various scenarios. The simulation results show that in all scenarios we consider, D-SSG not only guarantees a near-optimal rate-function, but also empirically has a similar delay performance to the rate-function delay-optimal policies.

In this paper, we study the scheduling problem for downlink transmission in a multichannel (e.g., OFDM-based) wireless network. We focus on a single cell, with the aim of developing a unifying framework for designing low-complexity scheduling policies that can provide optimal performance in terms of both throughput and delay. We develop new easy-to-verify sufficient conditions for rate-function delay optimality (in the many-channel many-user asymptotic regime) and throughput optimality (in general nonasymptotic setting), respectively. The sufficient conditions allow us to prove rate-function delay optimality for a class of Oldest Packets First (OPF) policies and throughput optimality for a large class of Maximum Weight in the Fluid limit (MWF) policies, respectively. By exploiting the special features of our carefully chosen sufficient conditions and intelligently combining policies from the classes of OPF and MWF policies, we design hybrid policies that are both rate-function delay-optimal and throughput-optimal with a complexity of O(n2.5log n), where n is the number of channels or users. Our sufficient condition is also used to show that a previously proposed policy called Delay Weighted Matching (DWM) is rate-function delay-optimal. However, DWM incurs a high complexity of O(n5). Thus, our approach yields significantly lower complexity than the only previously designed delay and throughput-optimal scheduling policy. We also conduct numerical experiments to validate our theoretical results.

In this paper, we focus on the scheduling problem in multi-channel wireless networks, e.g., the downlink of a single cell in fourth generation (4G) OFDM-based cellular networks. Our goal is to design efficient scheduling policies that can achieve provably good performance in terms of both throughput and delay, at a low complexity. While a recently developed scheduling policy, called Delay Weighted Matching (DWM), has been shown to be both rate-function delay-optimal (in the many-channel many-user asymptotic regime) and throughput-optimal (in general non-asymptotic setting), it has a high complexity O(n5), which makes it impractical for modern OFDM systems. To address this issue, we first develop a simple greedy policy called Delay-based Queue-Side-Greedy (D-QSG) with a lower complexity O(n3), and rigorously prove that D-QSG not only achieves throughput optimality, but also guarantees near-optimal rate-function-based delay performance. Specifically, the rate-function attained by D-QSG for any fixed integer threshold b>0, is no smaller than the maximum achievable rate-function by any scheduling policy for threshold b-1. Further, we develop another simple greedy policy called Delay-based Server-Side-Greedy (D-SSG) with an even lower complexity O(n2), and show that D-SSG achieves the same performance as D-QSG. Thus, we are able to achieve a dramatic reduction in complexity (from O(n5) of DWM to O(n2)) with a minimal drop in the delay performance. Finally, we conduct numerical simulations to validate our theoretical results in various scenarios. The simulation results show that our proposed greedy policies not only guarantee a near-optimal rate-function, but also empirically are virtually indistinguishable from the delay-optimal policy DWM.

In this paper, we focus on the issue of stability in multihop wireless networks under flow-level dynamics, and explore the inefficiency and instability of the celebrated Back-Pressure algorithms. It has been well-known that the Back-Pressure (or Max-Weight) algorithms achieve queue stability and throughput optimality in a wide variety of scenarios. Yet, these results all rely on the assumptions that the set of flows is fixed, and that all the flows are long-lived and keep injecting packets into the network. Recently, in the presence of flow-level dynamics, where flows arrive and request to transmit a finite amount of packets, it has been shown that the Max-Weight algorithms may not guarantee stability due to channel fading or inefficient spatial reuse. However, these observations are made only for single-hop traffic, and thus have resulted in partial solutions that are limited to the single-hop scenarios. An interesting question is whether straightforward extensions of the previous solutions to the known instability problems would achieve throughput optimality in multihop traffic setting. To answer the question, we explore potential inefficiency and instability of the Back-Pressure algorithms, and provide interesting examples that are useful to obtain insights into developing an optimal solution. We also conduct simulations to further illustrate the instability issue of the Back-Pressure algorithms in various scenarios. Our study reveals that new types of inefficiencies may arise in the settings with multihop traffic due to underutilization of the link capacity or inefficient routing, and the stability problem becomes more challenging than in the single-hop traffic counterpart.

In this paper, we consider the problem of link scheduling in multihop wireless networks under general interference constraints. Our goal is to design scheduling schemes that do not use per-flow or per-destination information, maintain a single data queue for each link, and exploit only local information, while guaranteeing throughput optimality. Although the celebrated back-pressure algorithm maximizes throughput, it requires per-flow or per-destination information. It is usually difficult to obtain and maintain this type of information, especially in large networks, where there are numerous flows. Also, the back-pressure algorithm maintains a complex data structure at each node, keeps exchanging queue-length information among neighboring nodes, and commonly results in poor delay performance. In this paper, we propose scheduling schemes that can circumvent these drawbacks and guarantee throughput optimality. These schemes use either the readily available hop-count information or only the local information for each link. We rigorously analyze the performance of the proposed schemes using fluid limit techniques via an inductive argument and show that they are throughput-optimal. We also conduct simulations to validate our theoretical results in various settings and show that the proposed schemes can substantially improve the delay performance in most scenarios.

Scheduling is a critical and challenging resource allocation mechanism for multihop wireless networks. It is well known that scheduling schemes that favor links with larger queue length can achieve high throughput performance. However, these queue-length-based schemes could potentially suffer from large (even infinite) packet delays due to the well-known last packet problem, whereby packets belonging to some flows may be excessively delayed due to lack of subsequent packet arrivals. Delay-based schemes have the potential to resolve this last packet problem by scheduling the link based on the delay the packet has encountered. However, characterizing throughput optimality of these delay-based schemes has largely been an open problem in multihop wireless networks (except in limited cases where the traffic is single-hop.) In this paper, we investigate delay-based scheduling schemes for multihop traffic scenarios with fixed routes. We develop a scheduling scheme based on a new delay metric and show that the proposed scheme achieves optimal throughput performance. Furthermore, we conduct simulations to support our analytical results and show that the delay-based scheduler successfully removes excessive packet delays, while it achieves the same throughput region as the queue-length-based scheme.

Scheduling is a critical and challenging resource allocation mechanism for multi-hop wireless networks. It is well known that scheduling schemes that give a higher priority to the link with larger queue length can achieve high throughput performance. However, this queue-length-based approach could potentially suffer from large (even infinite) packet delays due to the well-known last packet problem, whereby packets may get excessively delayed due to lack of subsequent packet arrivals. Delay-based schemes have the potential to resolve this last packet problem by scheduling the link based on the delay for the packet has encountered. However, the throughput performance of delay-based schemes has largely been an open problem except in limited cases of single-hop networks. In this paper, we investigate delay-based scheduling schemes for multi-hop traffic scenarios. We view packet delays from a different perspective, and develop a scheduling scheme based on a new delay metric. Through rigorous analysis, we show that the proposed scheme achieves the optimal throughput performance. Finally, we conduct extensive simulations to support our analytical results, and show that the delay-based scheduler successfully removes excessive packet delays, while it achieves the same throughput region as the queue-length-based scheme.

This paper focuses on designing and analyzing throughput-optimal scheduling policies that avoid using per-flow or per-destination information, maintain a single data queue for each link, exploit only local information, and potentially improve the delay performance, for multi-hop wireless networks under general interference constraints. Although the celebrated backpressure algorithm maximizes throughput, it requires per-flow or per-destination information (which may be difficult to obtain and maintain), maintains per-flow or per-destination queues at each node, relies on constant exchange of queue length information among neighboring nodes to calculate link weights, and may result in poor delay performance. In contrast, the proposed schemes can circumvent these drawbacks while guaranteeing throughput optimality. We rigorously analyze the throughput performance of the proposed schemes and show that they are throughput-optimal using fluid limit techniques via an inductive argument. We also conduct simulations to show that the proposed schemes can substantially improve the delay performance.