We investigate a binary classification problem in an edge intelligence system where false negatives are more costly than false positives. The system features a compact, locally deployed model, supplemented by a larger, remote model that is accessible via the network, albeit at an offloading cost. For each sample, our system first uses the locally deployed model for inference. Based on the output of the local model, the sample may be offloaded to the remote model. This work aims to understand the fundamental trade-off between classification accuracy and the offloading costs within such a hierarchical inference (HI) system. To optimise this system, we propose an online learning framework that continuously adapts a pair of thresholds on the local model's confidence scores. These thresholds determine the prediction of the local model and whether a sample is classified locally or offloaded to the remote model. We present a closed-form solution for the setting where the local model is calibrated. For the more general case of uncalibrated models, we introduce H2T2, an online two-threshold hierarchical inference policy, and prove it achieves sublinear regret. H2T2 is model-agnostic, requires no training, and learns during the inference phase using limited feedback. Simulations on real-world datasets show that H2T2 consistently outperforms naive and single-threshold HI policies, sometimes even surpassing single-threshold offline optima. The policy also demonstrates robustness to distribution shifts and adapts effectively to mismatched classifiers.

In a Hierarchical Inference (HI) system, an end device processes data samples using a local Deep Learning (DL) model. Only when the confidence of the local DL is less than a chosen threshold, it offloads the sample for remote DL inference on an edge server. By balancing the misclassifications and offloading costs, a HI system can improve accuracy and responsiveness and reduce bandwidth usage. To this end, prior work studied a HI learning problem for classification tasks, aiming to learn an optimal threshold on the confidence to minimize the cumulative costs. However, existing formulations considered (i) abstract offloading costs and (ii) assumed that the remote DL inference for an offloaded task is available by the end of each round. In contrast, considering that end devices are wirelessly connected to edge servers, we study a HI system with an offload queue where the offloading cost is implicitly modeled by the queue length. Also, we consider the practical setting, where the remote DL inference is obtained only after the task is served from the offload queue. For bounded but unknown arrival and service processes, we formulate the problem of average mismatch error minimization subject to queue stability. We propose a BOLD Hedge-Q policy based on Lyapunov optimization. The novelty of BOLD Hedge-Q lies in solving a delayed-feedback online learning problem — with sub-linear regret — that results from the Lyapunov drift-plus-penalty analysis. Given a penalty parameter V ≥ 1, we show that under BOLD Hedge-Q, the queue is upper bounded by V + λm, and the mismatch error is within an additive factor of O(1/V) from that of the optimal policy, where λm is the maximum number of arrivals in a round.

The freshness of sensor data is critical for all types of cyber-physical systems. An established measure for quantifying data freshness is the Age-of-Information (AoI), which has been the subject of extensive research. Recently, there has been increased interest in multi-sensor systems: redundant sensors producing samples of the same physical process, sensors such as cameras producing overlapping views, or distributed sensors producing correlated samples. When the information from a particular sensor is outdated, fresh samples from other correlated sensors can be helpful. To quantify the utility of distant but correlated samples, we put forth a two-dimensional (2D) model of AoI that takes into account the sensor distance in an age-equivalent representation. Since we define 2D-AoI as equivalent to AoI, it can be readily linked to existing AoI research, especially on parallel systems. We consider physical phenomena modeled as spatio-temporal processes and derive the 2D-AoI for different Gaussian covariance kernels. For a basic exponential product kernel, we find that spatial distance causes an additive offset of the AoI, while for other kernels the effects of spatial distance are more complex and vary with time. Using our methodology, we evaluate the 2D-AoI of different spatial topologies and sensor densities.

Epidemiologists and social scientists have used the Network Scale-Up Method (NSUM) for over thirty years to estimate the size of a hidden sub-population within a social network. This method involves querying a subset of network nodes about the number of their neighbors belonging to the hidden sub-population. In general, NSUM assumes that the social network topology and the hidden sub-population distribution are well-behaved; hence, the NSUM estimate is close to the actual value. However, bounds on NSUM estimation errors have not been analytically proven. This paper provides analytical bounds on the error incurred by the two most popular NSUM estimators. These bounds assume that the queried nodes accurately provide their degree and the number of neighbors belonging to the hidden sub-population. Our key findings are twofold. First, we show that when an adversary designs the network and places the hidden sub-population, then the estimate can be a factor of Ω(√n) off from the real value (in a network with n nodes). Second, we also prove error bounds when the underlying network is randomly generated, showing that a small constant factor can be achieved with high probability using samples of logarithmic size O(log n). We present improved analytical bounds for Erdős-Rényi and Scale-Free networks. Our theoretical analysis is supported by an extensive set of numerical experiments designed to determine the effect of the sample size on the accuracy of the estimates in both synthetic and real networks.

We study a variant of the experts problem in which new experts are revealed over time according to a stochastic process. The experts are represented by partitions of a hypercube $\mathbb{B}$ in $d$-dimensional Euclidean space. In each round, a point is drawn from $\mathbb{B}$ in an independent and identically distributed manner using an unknown distribution. For each chosen point, we draw $d$ orthogonal hyperplanes parallel to the $d$ faces of $\mathbb{B}$ passing through the point. The set of experts available in a round is the set of partitions of $\mathbb{B}$ created by all the hyperplanes drawn up to that point. Losses are adversarial, and the performance metrics of interest include expected regret and high probability bounds on the sample-path regret. We propose a suitably adapted version of the Hedge algorithm called Hedge-G, which uses a constant learning rate and has $O(\sqrt{2^d T \log T})$ expected regret, which is order-optimal. Further, we show that for Hedge-G, there exists a trade-off between choosing a learning rate that has optimal expected regret and a learning rate that leads to a high probability sample-path regret bound. We address this limitation by proposing AdaHedge-G, a variant of Hedge-G that uses an adaptive learning rate by tracking the loss of the experts revealed up to that round. AdaHedge-G simultaneously achieves $O(\log(\log T)\sqrt{ T \log T})$ expected regret and $O(\log T \sqrt{T \log T})$ sample-path regret, with probability at least $1-T^{-c}$, where $c > 0$ is a constant dependent on $d$.

On-device inference offers significant benefits in edge ML systems, such as improved energy efficiency, responsiveness, and privacy, compared to traditional centralized approaches. However, the resource constraints of embedded devices limit their use to simple inference tasks, creating a trade-off between efficiency and capability. In this context, the Hierarchical Inference (HI) system has emerged as a promising solution that augments the capabilities of the local ML by offloading selected samples to an edge server/cloud for remote ML inference. Existing works, primarily based on simulations, demonstrate that HI improves accuracy. However, they fail to account for the latency and energy consumption in real-world deployments, nor do they consider three key heterogeneous components that characterize ML-enabled IoT systems: hardware, network connectivity, and models. To bridge this gap, this paper systematically evaluates HI against standalone on-device inference by analyzing accuracy, latency, and energy trade-offs across five devices and three image classification datasets. Our findings show that, for a given accuracy requirement, the HI approach we designed achieved up to 73% lower latency and up to 77% lower device energy consumption than an on-device inference system. Despite these gains, HI introduces a fixed energy and latency overhead from on-device inference for all samples. To address this, we propose a hybrid system called Early Exit with HI (EE-HI) and demonstrate that, compared to HI, EE-HI reduces the latency up to 59.7% and lowers the device’s energy consumption up to 60.4%. These findings demonstrate the potential of HI and EE-HI to enable more efficient ML in IoT systems.

Low-power wireless Internet of Things (IoT) devices employ Time Slotted Channel Hopping (TSCH) Medium Access Control to achieve predictable timing behaviour. TSCH aims at collision-free scheduling by exploiting diversity over time (slots) and frequency (channels). However, existing works on performance and worst-case analysis are based on deterministic models, which lead to rather pessimistic non-realistic results, i.e. tools for probabilistic performance analysis of TSCH schedulers are still lacking. In this context, we devised a Stochastic Network Calculus model that enables to calculate end-to-end delays for specific traffic flows and (deadline) violation probability, building on Moment Generating Functions. We instantiate this SNC model and provide bounds for three widely used TSCH schedulers, namely Minimal Scheduling Function, Orchestra, and a custom collision-free scheduler, with different parameters such as radio duty-cycle, radio link quality, and traffic arrival rate. We demonstrate that our proposed model closely follows the simulation results, under different network scenarios.

Hierarchical Inference (HI) has emerged as a promising approach for efficient distributed inference between end devices deployed with small pre-trained Deep Learning (DL) models and edge/cloud servers running large DL models. Under HI, a device uses the local DL model to perform inference on the data samples it collects, and only the data samples on which this inference is likely to be incorrect are offloaded to a remote DL model running on the server. Thus, gauging the likelihood of incorrect local inference is key to implementing HI. A natural approach is to compute a confidence metric for the local DL inference and then use a threshold on this confidence metric to determine whether to offload or not. Recently, the HI online learning problem was studied to learn an optimal threshold for the confidence metric over a sequence of data samples collected over time. However, existing algorithms have computation complexity that grows with the number of rounds and do not exhibit a sub-linear regret bound. In this work, we propose the Hedge-HI algorithm and prove that it has [EQUATION] regret, where T is the number of rounds, and NT is the number of distinct confidence metric values observed till round T. Further, under a mild assumption, we propose Hedge-HI-Restart, which has an [EQUATION] regret bound with high probability and has a much lower computation complexity that grows sub-linearly in the number of rounds. Using runtime measurements on Raspberry Pi, we demonstrate that Hedge-HI-Restart has a runtime lower by order of magnitude and achieves cumulative loss close to that of the alternatives.

An established policy for updating systems is zerowait: a source immediately sends a new sample as soon as the sink acknowledges the receipt of the previous one. The rationale of zero-wait is that with instantaneous feedback, the transmission of samples can fully utilize the forward link without ever causing a queue. However, this ideal behavior does not extend to multihop networks and two-way delay. One approach to generalize zero-wait for use in larger networks is message pipelining, where there is a fixed number of samples and acknowledgments $k \geq 1$ in the network at any time. We analyze the peak age-of-information of updating systems with pipelining in multi-hop networks with arbitrarily many queues in the forward and feedback paths. While pipelining improves network utilization, it also increases queuing delays, and the optimal degree k must strike a balance between the two. We show how this depends on the diameter and topology of the network, the presence of bottlenecks, and the statistical distribution of service times. In an a priori unknown and changing network, it is beneficial to adjust the pipelining adaptively. We demonstrate how basic delay-based congestion control can be effectively used to achieve this goal.

The Hierarchical Inference (HI) paradigm has recently emerged as an effective method for balancing inference accuracy, data processing, transmission throughput, and offloading cost. This approach proves particularly efficient in scenarios involving resource-constrained edge devices like micro controller units (MCUs), tasked with executing tinyML inference. Notably, it outperforms strategies such as local inference execution, inference offloading, and split inference (i.e., inference execution distributed between two endpoints). Building upon the HI paradigm, this work explores different techniques aimed at further optimizing inference task execution. We propose three distinct HI approaches and evaluate their utility for image classification.

We study the problem of finding efficient sampling policies in an edge-based feedback system, where sensor samples are offloaded to a back-end server that processes them and generates feedback to a user. Sampling the system at maximum frequency results in the detection of events of interest with minimum delay but incurs higher energy costs due to the communication and processing of redundant samples. On the other hand, lower sampling frequency results in higher delay in detecting the event, thus increasing the idle energy usage and degrading the quality of experience. We quantify this trade-off as a weighted function between the number of samples and the sampling interval. We solve the minimisation problem for exponential and Rayleigh distributions, for the random time to the event of interest. We prove the convexity of the objective functions by using novel techniques, which can be of independent interest elsewhere. We argue that adding an initial offset to the periodic sampling can further reduce the energy consumption and jointly compute the optimum offset and sampling interval. We apply our framework to two practically relevant applications and show energy savings of up to$36\%$when compared to an existing periodic scheme.

With the emergence of edge computing, the problem of offloading jobs between an Edge Device (ED) and an Edge Server (ES) received significant attention in the past. Motivated by the fact that an increasing number of applications are using Machine Learning (ML) inference from the data samples collected at the EDs, we study the problem of offloadinginference jobsby considering the following novel aspects: 1) in contrast to a typical computational job, the processing time of an inference job depends on the size of the ML model, and 2) recently proposed Deep Neural Networks (DNNs) for resource-constrained devices provide the choice of scaling down the model size by trading off the inference accuracy. Considering that multiple ML models are available at the ED, and a powerful ML model is available at the ES, we formulate an Integer Linear Programming (ILP) problem with the objective of maximizing the total inference accuracy of$n$data samples at the ED subject to a time constraint$T$on the makespan. Noting that the problem is NP-hard, we propose an approximation algorithm Accuracy Maximization using LP-Relaxation and Rounding (AMR$^{2}$) and prove that it results in a makespan at most$\text{2}T$and achieves a total accuracy that is lower by a small constant from the optimal total accuracy implying that AMR$^{2}$is asymptotically optimal. Further, if the data samples are identical we propose Accuracy Maximization using Dynamic Programming (AMDP), an optimal pseudo-polynomial time algorithm. Furthermore, we extend AMR$^{2}$for the case of multiple ESs, where each ES is equipped with a powerful ML model. As proof of concept, we implemented AMR$^{2}$on a Raspberry Pi, equipped with MobileNets, that is connected to a server equipped with ResNet, and studied the total accuracy and makespan performance of AMR$^{2}$for image classification.

With the emergence of edge computing, the problem of offloading jobs between an Edge Device (ED) and an Edge Server (ES) received significant attention in the past. Motivated by the fact that an increasing number of applications are using Machine Learning (ML) inference from the data samples collected at the EDs, we study the problem of offloading inference jobs by considering the following novel aspects: in contrast to a typical computational job 1) both inference accuracy and processing time of an inference job increase with the size of the ML model and 2)recently proposed Deep Neural Networks (DNNs) for resource-constrained EDs provide the choice of scaling down the model size by trading off the inference accuracy. Therefore, we consider that multiple small-size ML models are available at the ED and a powerful large-size ML model is available at the ES, and study a general assignment problem with the objective of maximizing the total inference accuracy for the data samples at the ED subject to a time constraint T on the makespan. Noting that the problem is NP-hard, we propose an approximation algorithm: Accuracy Maximization using LP-Relaxation and Rounding (AMR2), and prove that it results in a makespan at most 2T, and achieves a total accuracy that is lower by a small constant from the optimal total accuracy. As proof of concept, we implemented AMR2 on a Raspberry Pi, equipped with MobileNets, that is connected via LAN to a server equipped with ResNet, and studied the total accuracy and makespan performance of AMR2 for image classification.

We study task scheduling and offloading in a cloud computing system with multiple users where tasks have different processing times, release times, communication times, and weights. Each user may schedule a task locally or offload it to a shared cloud with heterogeneous processors by paying a price for the resource usage. We consider four different models in this article: (i) zero task release and communication times; (ii) non-zero task release times and zero communication times; (iii) non-zero task release times and fixed communication times; and (iv) non-zero task release times and sequence-dependent communication times. Our article aims at identifying a task scheduling decision that minimizes the weighted sum completion time of all tasks, while satisfying the users’ budget constraints. We propose an efficient solution framework for this NP-hard problem. As a first step, we use a relaxation and a rounding technique to obtain an integer solution that is a constant factor approximation to the minimum weighted sum completion time. This solution violates the budget constraints, but the average budget violation decreases as the number of users increases. Thus, we develop a scalable algorithm termed Single-Task Unload for Budget Resolution (STUBR), which resolves budget violations and orders the tasks to obtain robust solutions. We prove performance bounds for the rounded solution as well as for the budget-resolved solution, for all four models considered. Via extensive trace-driven simulation for both chess and compute-intensive applications, we observe that STUBR exhibits robust performance under practical scenarios and outperforms existing alternatives. We also use simulation to study the scalability of STUBR algorithm as the number of tasks and the number of users in the system increases.

We consider a finite-state Discrete-Time Markov Chain (DTMC) source that can be sampled for detecting the events when the DTMC transits to a new state. Our goal is to study the trade-off between sampling frequency and staleness in detecting the events. We argue that, for the problem at hand, using Age of Information (AoI) for quantifying the staleness of a sample is conservative and therefore, study another freshness metricage penalty, which is defined as the time elapsed since the first transition out of the most recently observed state. We study two optimization problems: minimize average age penalty subject to an average sampling frequency constraint, and minimize average sampling frequency subject to an average age penalty constraint; both are Constrained Markov Decision Problems. We solve them using the Lagrangian MDP approach, where we also provide structural results that reduce the search space. Our numerical results demonstrate that the computed Markov policies not only outperform optimal periodic sampling policies, but also achieve sampling frequencies close to or lower than that of an optimal clairvoyant (non-causal) sampling policy, if a small age penalty is allowed.

Interactive applications with automated feedback will largely influence the design of future networked infrastructures. In such applications, status information about an environment of interest is captured and forwarded to a compute node, which analyzes the information and generates a feedback message. Timely processing and forwarding must ensure the feedback information to be still applicable; thus, the quality-of-service parameter for such applications is the end-to-end latency over the entire loop. By modelling the communication of a feedback loop as a two-hop network, we address the problem of allocating network resources in order to minimize the delay violation probability (DVP), i.e. the probability of the end-to-end latency exceeding a target value. We investigate the influence of the network queue states along the network path on the performance of semi-static and dynamic scheduling policies. The former determine the schedule prior to the transmission of the packet, while the latter benefit from feedback on the queue states as time evolves and reallocate time slots depending on the queue’s evolution. The performance of the proposed policies is evaluated for variations in several system parameters and comparison baselines. Results show that the proposed semi-static policy achieves close-to-optimal DVP and the dynamic policy outperforms the state-of-the-art algorithms.

There is a growing interest in analysing freshness of data in networked systems. Age of Information (AoI) has emerged as a relevant metric to quantify this freshness at a receiver, and minimizing this metric for different system models has received significant research attention. However, a fundamental question remains: what is the minimum achievable AoI in any single-server-single-source queuing system for a given service-time distribution? We address this question for the average peak AoI (PAoI) statistic by considering generate-at-will source model, service preemptions, and request delays. Our main result is on the characterization of the minimum achievable average PAoI, and we show that it is achieved by a fixed-threshold policy among the set of all causal policies. We use the characterization to provide necessary and sufficient condition for preemptions to be beneficial for a given service-time distribution. Our numerical results, obtained using well-known distributions, demonstrate that the heavier the tail of a distribution the higher the performance gains of using preemptions.

Computational offloading systems, where computational tasks can be processed locally or offloaded to a remote cloud, have become prevalent since the advent of cloud computing. The task scheduler in a computational offloading system decides both the selection of tasks to be offloaded to the remote cloud and the scheduling of tasks on the local processors. In this work, we consider the problem of minimizing a weighted sum of the makespan of the tasks and the offloading cost at the remote cloud. In contrast to prior works, we do not assume that the task processing times are known a priori. We show that the original problem can be solved by algorithms designed toward minimizing the maximum between the makespan and the weighted offloading cost, only with doubling of the competitive ratio. Furthermore, when the remote cloud is much faster than the local processors, the latter problem can be equivalently transformed into a makespan minimization problem with unrelated processors. For this case, we propose a Greedy-One-Restart (GOR) algorithm based on online estimation of the unknown processing times, and one-time cancellation and rescheduling of tasks that turn out to require long processing times. Given$m$local processors, we show that GOR has$O(\sqrt{m})$competitive ratio, which is a substantial improvement over the best known algorithms in the literature. For the general case of arbitrary speed at the remote cloud, we extend GOR to a Greedy-Two-Restart (GTR) algorithm and show that it is$O(\sqrt{m})$-competitive. Furthermore, where tasks arrive dynamically with unknown arrival times, we extend GOR and GTR to Dynamic-GOR (DGOR) and Dynamic-GTR (DGTR), respectively, and find their competitive ratios. Finally, we discuss how GOR can be extended to accommodate multiple remote processors. In addition to performance bounding by competitive ratios, our simulation results demonstrate that the proposed algorithms are favorable also in terms of average performance, in comparison with the well-known list scheduling algorithm and other alternatives.

Age of Information (AoI) has proven to be a useful metric in networked systems where timely information updates are of importance. In the literature, minimizing “average age” has received considerable attention. However, various applications pose stricter age requirements on the updates which demand knowledge of the AoI distribution. Furthermore, the analysis of AoI distribution in a multi-hop setting, which is important for the study of Wireless Networked Control Systems (WNCS), has not been addressed before. Toward this end, we study the distribution of AoI in a WNCS with two hops and devise a problem of minimizing the tail of the AoI distribution with respect to the frequency of generating information updates, i.e., the sampling rate of monitoring a process, under first-come-first-serve (FCFS) queuing discipline. We argue that computing an exact expression for the AoI distribution may not always be feasible; therefore, we opt for computing upper bounds on the tail of the AoI distribution. Using these upper bounds, we formulate Upper Bound Minimization Problems (UBMP), namely, Chernoff-UBMP and α-relaxed Upper Bound Minimization Problem (α-UBMP), where α > 1 is an approximation factor, and solve them to obtain “good” heuristic rate solutions for minimizing the tail. We demonstrate the efficacy of our approach by solving the proposed UBMPs for three service distributions: geometric, exponential, and Erlang. Simulation results show that the rate solutions obtained are near optimal for minimizing the tail of the AoI distribution for the considered distributions.

In future industrial scenarios, Wireless Sensor Networks (WSN) are envisioned to support the traffic of Networked Control Systems (NCS). WirelessHART is a prevalent WSN protocol that uses the Time Slotted Channel Hopping (TSCH) medium access to cope with the delay and reliability requirements of NCS in the harsh industrial environment. In TSCH, time slots and frequencies can be scheduled by a network coordinator to provide Quality of Service (QoS). In contrast to previous works that consider the end-to-end delay requirement of a flow of packets, we focus on a finite sequence of time-critical packets. These packets may belong to a time-critical message whose latency could significantly impact the NCS. Given an end-to-end delay deadline, our objective is to minimize the Delay Violation Probability (DVP) for a finite sequence of packets by dynamically scheduling the time slots in each frame. This is a challenging task as DVP depends on the instantaneous state of the network and requires its transient analysis. In this work, we model the wireless NCS as a two-queue lossy wireless network and propose the first transient analysis of DVP for a finite sequence of time-critical packets. Noting that DVP cannot be directly used for dynamic resource allocation, we propose a heuristic algorithm by relating DVP with the network's throughput. The proposed heuristic maximizes the expected throughput, is computed by solving a finite-horizon Markov Decision Process (MDP), and can be implemented at the network coordinator. Using simulation we demonstrate that the MDP-based heuristic achieves lower DVP compared to the classical MaxWeight and Weighted-Fair Queuing.

There is a growing interest in analysing the freshness of data in networked systems. Age of Information (AoI) has emerged as a popular metric to quantify this freshness at a given destination. There has been a significant research effort in optimizing this metric in communication and networking systems under different settings. In contrast to previous works, we are interested in a fundamental question, what is the minimum achievable AoI in any single-server-single-source queuing system for a given service-time distribution? To address this question, we study a problem of optimizing AoI under service preemptions. Our main result is on the characterization of the minimum achievable average peak AoI (PAoI). We obtain this result by showing that a fixed-threshold policy is optimal in the set of all randomized-threshold causal policies. We use the characterization to provide necessary and sufficient conditions for the service-time distributions under which preemptions are beneficial.

In this article, we investigate the transient behavior of a sequence of packets/bits traversing a multi-hop wireless network under static routing. Our work is motivated by novel applications from the domain of process automation, Machine-Type Communication (MTC) and cyber-physical systems, where short messages are communicated and statistical guarantees need to be provided on a per-message level. In order to optimize such a network, apart from understanding the stationary system dynamics, an understanding of the short-term dynamics (i.e. transient behavior) is also required. To this end, we derive novel Wireless Transient Bounds (WTB) for end-to-end delay and backlog in a multi-hop wireless network using stochastic network calculus approach. We start by analyzing a single end-to-end path, i.e. a line topology, and then we show how the obtained results can be applied to a mesh network with static routing using a concept called 'leftover service'. WTB depends on the initial backlog at each node as well as the instantaneous channel states. We numerically compare WTB with Kernel-Based-Transient Bound (KBTB), which can be obtained by adapting existing stationary bound, as well as simulated end-to-end delay of the investigated network. While KBTB and stationary bounds are not able to capture the short-term system dynamics well, WTB provides relatively tight upper bound and has a decay rate that closely matches the simulation. This is achieved by WTB only with a slight increase in the computational complexity, by a factor of O(T + N), where T is the duration of the arriving sequence and N is the number of hops in the network. We believe that the presented analysis and the bounds are necessary tools for future work on transient network optimization for many important emerging applications, e.g., massive MTC, critical MTC, edge computing and autonomous vehicle.

We study the problem of scheduling n tasks on m + m' parallel processors, where the processing times on m processors are known while those on the remaining m' processors are not known a priori. This semi-online model is an abstraction of certain heterogeneous computing systems, e.g., with them known processors representing local CPU cores and the unknown processors representing remote servers with uncertain availability of computing cycles. Our objective is to minimize the makespan of all tasks. We initially focus on the case m' = 1 and propose a semi-online algorithm termed Single Restart with Time Stamps (SRTS), which has time complexity O(nlogn). We derive its competitive ratio in comparison with the optimal offline solution. If the unknown processing times are deterministic, the competitive ratio of SRTS is shown to be either always constant or asymptotically constant in practice, respectively in cases where the processing times are independent and dependent on m. A similar result is obtained when the unknown processing times are random. Furthermore, extending the ideas of SRTS, we propose a heuristic algorithm termed SRTS-Multiple (SRTS-M) for the case m' > 1. Finally, where tasks arrive dynamically with unknown arrival times, we extend SRTS to Dynamic SRTS (DSRTS) and find its competitive ratio. Besides the proven competitive ratios, simulation results further suggest that SRTS and SRTS-M give superior performance on average over randomly generated task processing times, substantially reducing the makespan over the best known alternatives. Interestingly, the performance gain is more significant for task processing times sampled from heavy-tailed distributions.

Since Age of Information (AoI) has been proposed as a metric that quantifies the freshness of information updates in a communication system, there has been a constant effort in understanding and optimizing different statistics of the AoI process for classical queueing systems. In addition to classical queuing systems, more recently, systems with no queue or a unit capacity queue storing the latest packet have been gaining importance as storing and transmitting older packets do not reduce AoI at the receiver. Following this line of research, we study the distribution of AoI for the GI/GI/1/1 and GI/GI/1/2* systems, under non-preemptive scheduling. For any single-source-single-server queueing system, we derive, using sample path analysis, a fundamental result that characterizes the AoI violation probability, and use it to obtain closed-form expressions for D/GI/1/1, M/GI/1/1 as well as systems that use zero-wait policy. Further, when exact results are not tractable, we present a simple methodology for obtaining upper bounds for the violation probability for both GI/GI/1/1 and GI/GI/1/2* systems. An interesting feature of the proposed upper bounds is that, if the departure rate is given, they overestimate the violation probability by at most a value that decreases with the arrival rate. Thus, given the departure rate and for a fixed average service, the bounds are tighter at higher utilization.

We study task scheduling and offloading in a cloud computing system with multiple users, where tasks have different processing times, release times, communication times, and weights. Each user may schedule a task locally or offload it to a finite-capacity shared cloud with heterogeneous processors by paying a price for the resource usage. Our work aims at identifying a task scheduling decision that minimizes the weighted sum completion time of all tasks, while satisfying the users' budget constraints. We propose an efficient solution framework for this NP-hard problem. As a first step, we solve an integer-relaxed problem and use a rounding technique to obtain an integer solution that is a constant factor approximation to the minimum weighted sum completion time. This solution violates the budget constraints, but the average budget violation decreases as the number of users increases. Thus, we develop a scalable Single-Task Unload for Budget Resolution (STUBR) algorithm, which resolves budget violations and orders the tasks to reduce the weighted sum completion time. Our trace-driven simulation shows that STUBR exhibits robust performance under practical scenarios and outperforms several alternatives.

We revisit the problem of assigning n jobs to m machines/servers. We study this problem under more general settings, which capture important aspects of applications that arise in networking and information systems. In particular, we consider jobs that have placement constraints and machines that are heterogeneous. The cost incurred at a machine is given by any general convex function on the number of jobs assigned to it. We aim to minimize the sum cost and the maximum differential cost. Through a network-flow equivalence transformation, we observe how these two objectives are fundamentally related, showing that sum-cost minimization implies maximum-differential-cost minimization. We propose an efficient algorithm termed Maximum Edge-Cost Cycle Cancelling (MEC3) to solve the sum-cost minimization problem with O(n2m2) time complexity. Furthermore, for applications where only the maximum differential cost is of concern, we further improve the efficiency of MEC3by proposing an early stop condition. We implement MEC3and two other algorithms from the literature. Using benchmark input instances, we show that MEC3has substantially lower run time than the other algorithms.

We study the problem of scheduling n tasks on m + m' parallel processors, where the processing times on m processors are known while those on the remaining m' processors are not known a priori. This semi-online model is an abstraction of certain heterogeneous computing systems, e.g., with the m known processors representing local CPU cores and the unknown processors representing remote servers with uncertain availability of computing cycles. Our objective is to minimize the makespan of all tasks. We initially focus on the case m' = 1 and propose a semi-online algorithm termed Single Restart with Time Stamps (SRTS), which has time complexity O(n log n). We derive its competitive ratio in comparison with the optimal offline solution. If the unknown processing times are deterministic, the competitive ratio of SRTS is shown to be either always constant or asymptotically constant in practice, respectively in cases where the processing times are independent and dependent on m. A similar result is obtained when the unknown processing times are random. Furthermore, extending the ideas of SRTS, we propose a heuristic algorithm termed SRTS-Multiple (SRTS-M) for the case m' > 1. Besides the proven competitive ratios, simulation results further suggest that SRTS and SRTS-M give superior performance on average over randomly generated task processing times, substantially reducing the makespan over the best known alternatives. Interestingly, the performance gain is more significant for task processing times sampled from heavy-tailed distributions.

We study the scheduling of computational tasks on one local processor and one remote processor with communication delay. This problem has important application in cloud computing. Although the communication time to transmit a task can be inferred from the known data size of the task and the transmission bandwidth, the processing time of the task is generally unknown until it is processed to completion. Given a set of independent tasks with unknown processing times, our objective is to minimize makespan. We study the problem under two scenarios: (1) the communication times of the tasks to the remote processor are smaller than their corresponding processing times on the remote processor, and (2) the communication times of the tasks to the remote processor are larger than their corresponding processing times on the remote processor. For the first scenario we propose the Semi-online Partitioning and Communication (SPaC) algorithm, and for the second scenario we propose the SPaC-Restart (SPaC-R) algorithm. Even though the offline version of this problem, with a priori known processing times, is NP-hard, we show that the proposed semionline algorithms achieve O(1) competitive ratios for their intended scenarios. We also provide competitive ratios for both algorithms for more general communication times. We use simulation to demonstrate that SPaC and SPaC-R outperform online list scheduling and performs comparably well with the best known offline heuristics.

The hybrid cloud architecture utilizes both privately owned cloud servers and rented instances from public cloud providers, to offer flexible services that are particularly suited to enterprise computing. The task scheduler at a hybrid cloud decides both the selection of tasks to be offloaded to the public cloud and the scheduling of the remaining tasks on the processors at the private cloud. In this work, we consider the problem of minimizing a weighted sum of the makespan at the private cloud and the offloading cost to the public cloud. In contrast to prior works, we do not assume that the task processing times are known a priori. We show that the original problem can be solved by the same algorithms designed toward minimizing the maximum between the makespan and the weighted offloading cost, only with doubling of the competitive ratio. Furthermore, the latter problem can be equivalently transformed into a makespan minimization problem with unrelated processors. In the case where all tasks arrive at time zero, we propose a Greedy-One-Restart (GOR) algorithm based on online estimation of the unknown processing times, and one-time cancellation and rescheduling of tasks that turn out to require long processing times. We derive its competitive ratio and show that it is upper bounded on the order of the square root of the number of private processors, which is a substantial improvement over the best known algorithms in the literature. We present also a tight constant competitive ratio for the special two-processor case. In the case where tasks arrive dynamically with unknown arrival times, we extend GOR to Dynamic-GOR (DGOR) and find its competitive ratio. Further simulation results demonstrate that GOR and DGOR are favorable also in terms of average performance, in comparison with the well-known list scheduling algorithm and idealized offline algorithms.