| 1. |
- Al-Atat, Ghina, et al.
(författare)
-
The Case for Hierarchical Deep Learning Inference at the Network Edge
- 2023
-
Ingår i: NetAISys 2023 - Proceedings of the 1st International Workshop on Networked AI Systems, Part of MobiSys 2023. - : Association for Computing Machinery (ACM). ; , s. 13-18
-
Konferensbidrag (refereegranskat)abstract
- Resource-constrained Edge Devices (EDs), e.g., IoT sensors and microcontroller units, are expected to make intelligent decisions using Deep Learning (DL) inference at the edge of the network. Toward this end, developing tinyML models is an area of active research - DL models with reduced computation and memory storage requirements - that can be embedded on these devices. However, tinyML models have lower inference accuracy. On a different front, DNN partitioning and inference offloading techniques were studied for distributed DL inference between EDs and Edge Servers (ESs). In this paper, we explore Hierarchical Inference (HI), a novel approach proposed in [19] for performing distributed DL inference at the edge. Under HI, for each data sample, an ED first uses a local algorithm (e.g., a tinyML model) for inference. Depending on the application, if the inference provided by the local algorithm is incorrect or further assistance is required from large DL models on edge or cloud, only then the ED offloads the data sample. At the outset, HI seems infeasible as the ED, in general, cannot know if the local inference is sufficient or not. Nevertheless, we present the feasibility of implementing HI for image classification applications. We demonstrate its benefits using quantitative analysis and show that HI provides a better trade-off between offloading cost, throughput, and inference accuracy compared to alternate approaches.
|
|
| 2. |
- Champati, Jaya Prakash, et al.
(författare)
-
Delay and Cost Optimization in Computational Offloading Systems with Unknown Task Processing Times
- 2021
-
Ingår i: IEEE Transactions on Cloud Computing. - : Institute of Electrical and Electronics Engineers (IEEE). - 2168-7161. ; 9:4, s. 1422-1438
-
Tidskriftsartikel (refereegranskat)abstract
- 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(root 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(root 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.
|
|
| 3. |
- Champati, Jaya Prakash, et al.
(författare)
-
Detecting State Transitions of a Markov Source : Sampling Frequency and Age Trade-off
- 2020
-
Ingår i: IEEE INFOCOM 2020 - IEEE CONFERENCE ON COMPUTER COMMUNICATIONS WORKSHOPS (INFOCOM WKSHPS). - : IEEE. ; , s. 7-12
-
Konferensbidrag (refereegranskat)abstract
- 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, introduce age penalty for this purpose. 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 linear programming approach and compute Markov policies that are optimal among all causal policies. 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.
|
|
| 4. |
- Champati, Jaya Prakash, et al.
(författare)
-
Detecting State Transitions of a Markov Source : Sampling Frequency and Age Trade-off
- 2022
-
Ingår i: IEEE Transactions on Communications. - New York : Institute of Electrical and Electronics Engineers (IEEE). - 0090-6778 .- 1558-0857. ; 70:5, s. 3081-3095
-
Tidskriftsartikel (refereegranskat)abstract
- 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 metric age 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.
|
|
| 5. |
- Champati, Jaya Prakash, et al.
(författare)
-
Minimum Achievable Peak Age of Information Under Service Preemptions and Request Delay
- 2021
-
Ingår i: IEEE Journal on Selected Areas in Communications. - : IEEE Communications Society. - 0733-8716 .- 1558-0008. ; 39:5, s. 1365-1379
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
| 6. |
- Champati, Jaya Prakash, et al.
(författare)
-
On the Distribution of AoI for the GI/GI/1/1 and GI/GI/1/2*Systems : Exact Expressions and Bounds
- 2019
-
Ingår i: IEEE CONFERENCE ON COMPUTER COMMUNICATIONS (IEEE INFOCOM 2019). - : IEEE. - 9781728105154 ; , s. 37-45
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 7. |
- Champati, Jaya Prakash, et al.
(författare)
-
On the Minimum Achievable Age of Information for General Service-Time Distributions
- 2020
-
Ingår i: Proceedings 39th IEEE Conference on Computer Communications, INFOCOM 2020.
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 8. |
- Champati, Jaya Prakash, et al.
(författare)
-
Performance Characterization Using AoI in a Single-loop Networked Control System
- 2019
-
Ingår i: IEEE INFOCOM 2019 - IEEE Conference on Computer Communications Workshops, INFOCOM Workshops 2019. - : IEEE. - 9781728118789 ; , s. 197-203
-
Konferensbidrag (refereegranskat)abstract
- The joint design of control and communication scheduling in a Networked Control System (NCS) is known to be a hard problem. Several research works have successfully designed optimal sampling and/or control strategies under simplified communication models, where transmission delays/times are negligible or fixed. However, considering sophisticated communication models, with random transmission times, result in highly coupled and difficult-to-solve optimal design problems due to the parameter inter-dependencies between estimation/control and communication layers. To tackle this problem, in this work, we investigate the applicability of Age-of-Information (AoI) for solving control/estimation problems in an NCS under i.i.d. transmission times. Our motivation for this investigation stems from the following facts: 1) recent results indicate that AoI can be tackled under relatively sophisticated communication models, and 2) a lower AoI in an NCS may result in a lower estimation/control cost. We study a joint optimization of sampling and scheduling for a single-loop stochastic LTI networked system with the objective of minimizing the time-average squared norm of the estimation error. We first show that, under mild assumptions on information structure the optimal control policy can be designed independently from the sampling and scheduling policies. We then derive a key result that minimizing the estimation error is equivalent to minimizing a non-negative and non-decreasing function of AoI. The parameters of this function include the LTI matrix and the covariance of exogenous noise in the LTI system. Noting that the formulated problem is a stochastic combinatorial optimization problem and is hard to solve, we resort to heuristic algorithms by extending existing algorithms in the AoI literature. We also identify a class of LTI system dynamics for which minimizing the estimation error is equivalent to minimizing the expected AoI.
|
|
| 9. |
- Champati, Jaya Prakash, et al.
(författare)
-
Single Restart with Time Stamps for Parallel Task Processing with Known and Unknown Processors
- 2020
-
Ingår i: IEEE Transactions on Parallel and Distributed Systems. - : Institute of Electrical and Electronics Engineers (IEEE). - 1045-9219 .- 1558-2183. ; 31:1, s. 187-200
-
Tidskriftsartikel (refereegranskat)abstract
- We study the problem of scheduling nn tasks on m+m^{\prime }m+m' parallel processors, where the processing times on mm processors are known while those on the remaining m^{\prime }m' processors are not known a priori. This semi-online model is an abstraction of certain heterogeneous computing systems, e.g., with the mm 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^{\prime }=1m'=1 and propose a semi-online algorithm termed Single Restart with Time Stamps (SRTS), which has time complexity O(n \log n)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 mm. 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^{\prime }>1m'>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.
|
|
| 10. |
- Champati, Jaya Prakash, et al.
(författare)
-
Statistical Guarantee Optimization for AoI in Single-Hop and Two-Hop FCFS Systems With Periodic Arrivals
- 2021
-
Ingår i: IEEE Transactions on Communications. - : Institute of Electrical and Electronics Engineers (IEEE). - 0090-6778 .- 1558-0857. ; 69:1, s. 365-381
-
Tidskriftsartikel (refereegranskat)abstract
- 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 alpha-relaxed Upper Bound Minimization Problem (alpha-UBMP), where alpha > 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.
|
|
