To enable edge AI providers to recruit edge devices and use them to deploy AI models and provision inference services, we conduct a comprehensive mathematical and algorithmic study on a novel incentive and optimization mechanism based on repeated auctions. We first model and formulate a time-cumulative social cost optimization problem to capture the challenges of the trade-off between cost and accuracy, the dependency between adjacent auctions, and the need of achieving desired economic properties. Then, to solve this intractable non-linear integer program in an online manner, we design a set of polynomial-time algorithms that work together. Our approach dynamically chooses and switches winning bids under careful control, incorporates online learning to overcome posterior inference accuracy and workload queue dynamics, and leverages randomization to strategically convert fractional decisions of model placement and query dispatch into integers. We also allocate payments to meet the necessary and sufficient conditions for the desired economic properties. Further, we rigorously prove the constant competitive ratio, the sub-linear regret and fit, and the truthfulness and individual rationality for our proposed approach. Finally, through extensive experiments using real devices, AI models, and data traces, we have validated the substantial advantages of our proposed approach compared to the baselines and the state-of-the-art methods.

Continuously orchestrating in-network model aggregations for federated learning faces fundamental challenges such as the combinatorial nature of traffic reduction, the dynamic trade-offs between system overhead and model convergence, and the unpredictable inputs from uncertain system environments. In this work, we model a nonlinear mixed-integer program to optimize the long-term total cost of federated learning computation overhead, traffic reduction, network delay, and programmable switch reconfigurations over time. To attack the lexicographic minimax, submodular, and online nature of this problem, we propose a polynomial-time algorithmic framework to judiciously designate the timing of reconfigurations, while designing and invoking a linearized transformation for selecting routing paths, a greedy sub-algorithm for selecting aggregation locations, and an online learning sub-algorithm for controlling federated learning convergence. We demonstrate our rigorous mathematical insights behind our algorithms, and prove the competitive ratio as the performance guarantee. Using trace-driven evaluations, we have validated our approach's superiority over existing methods.

Network visualization is essential for network operators to diagnose ongoing network failures and understand the quality of the network. In-Band Network Telemetry (INT) supports network visualization by inserting P4 switch state information (e.g., queue length, hop latency, and link utilization) into the specific INT packets. In order to achieve network-wide coverage, paths of INT packets need to be delicately designed to ensure non-overlapping, high performance, and low overhead. However, existing INT path planning solutions ignore capturing the dynamic network status and fail to obtain the optimum. In this paper, we model the INT path planning based on the directed Edge Cover problem upon the dynamic network status, with the objective of minimizing the INT path latency. Although it is actually a non-linear integer program problem, by adopting delicate transformations, we design approximation algorithms with performance guarantees. We implement our system prototype INTView based on INTCollector upon real devices, i.e., Barefoot Wedge100BF and Inspur Rack. Extensive evaluation upon realistic settings shows that our proposed algorithm achieves 2x performance improvement regarding the completion time, compared with state-of-the-art schemas.

Delayed Gradient Averaging (DGA) has gained massive attention for improving the training efficiency of Federated Learning (FL) at edge networks, by allowing local computation in parallel to communication. However, it faces multiple challenges due to data distribution across heterogeneous edge devices and dynamic network environments. To address these challenges, we present A-DGA, a novel communication learning parallel federated learning algorithm designed for fluctuating, heterogeneous, and high-latency network conditions. Our proposed A-DGA dynamically sets extra local updates based on network status, avoiding inefficient training upon the outdated gradients. Theoretical analysis demonstrates that A-DGA outperforms DGA in terms of convergence rates given the fixed time slot length. We further conduct massive evaluations under various conditions, including different datasets, models, and data distribution. The experimental results show that A-DGA performs the best, compared to the state-of-the-art methods, achieving an acceleration factor of approximately x2 ∼ x4 and x1.2 ∼ x2, compared to FedAvg and DGA, respectively. Besides, our A-DGA also reduces energy consumption by about 40% ∼ 50% compared to DGA.

Performing machine learning inference at the network edge, named Edge Inference, showing benefits like low latency, reduced data traffic, and improved user privacy, has attracted massive attention. Computing Power Network (CPN) creates opportunities for edge inference, but also poses multiple challenges for service providers, including computing power selections from different enterprises, the time-coupled decision for resource provisioning and the unpredictable CPN network status. To overcome these challenges, this study formulates a time-varying integer program problem whose goal is to minimize long-term costs, involving switching costs, operational costs, communication costs, and queuing costs. Then we design a group of polynomial-time online algorithms to make online decisions, by taking into account stochastic inputs. Our algorithms adaptively make control decisions by solving delicately constructed subproblems based on the inputs predicted via online learning. Specifically, we first obtain fractional solutions which are transformed into integers for deployment with expectations preserving. Furthermore, we conduct a rigorous proof and establish the competitive ratio which highlights the difference between the performance of our proposed algorithms and the offline optimum. Our comprehensive evaluations, using datasets from real systems, demonstrate that our algorithms outperform multiple alternatives, up to an average of 35% cost reduction, confirming the effectiveness of our algorithms.

Many crowdsourcing platforms are emerging, leveraging the resources of recruited workers to execute various outsourcing tasks, mainly for those computing-intensive video analytics with high quality requirements. Although the profit of each platform is strongly related to the quality of analytics feedback, due to the uncertainty on diverse performance of workers and the conflicts of interest over platforms, it is non-trivial to determine the dispatch of tasks with maximum benefits. In this paper, we design a decentralized mechanism for a Crowd of Crowdsourcing platforms, denoted as Crowd2, optimizing the worker selection to maximize the social welfare of these platforms in a long-term scope, under the consideration of both proportional fairness and dynamic flexibility. Concretely, we propose a video analytics dispatch algorithm based on multi-agent bandit, for which the more accurate profit estimates are attained via the decoupling of multi-knapsack based mapping problem. Via rigorous proofs, a sub-linear regret bound for social welfare of crowdsourcing profits is achieved while both fairness and flexibility are ensured. Extensive trace-driven experiments demonstrate that Crowd2improves the social welfare by 36.8%, compared with other alternatives.

In-band Network Telemetry (INT) is proposed to detect networks via injecting specific probes to collect the hop-by-hop metadata within programmable switches. But there exist multiple challenges to conducting INT at Computing Power Network, such as control decisions of different INT frequencies, and the unforeseeable INT query workloads. In this study, we formulate an online non-linear time-varying integer programming problem that aims to maximize the overall quality of service through both frequency selection and INT query workload distribution. To achieve this, we propose an online learning, INTService, which utilizes a primal-dual mechanism to make fractional decisions. At last, extensive evaluations show that our proposed INTService exhibits up-lift performance 40% on average over other state-of-the-art algorithms.

Provisioning machine learning inference near the users at the network’s edge is emerging as a promising area for Edge AI. Due to the excessive energy consumption of edge devices, their owners often lack the motivation to actively contribute to their edge resources. To tackle this issue, we propose an incentive mechanism based on auctions, which enables edge device owners to submit their bids and compensates such bids via reward payments, ensuring the minimization of inference accuracy loss. We formulate a nonlinear mixed-integer program problem with the objective of minimizing the social cost, including accuracy loss cost, edge device cost, and service provider cost in the edge inference system. Then an Online Learning algorithm is devised to find the solutions, based on the primal-dual. To calculate the remuneration, we design a payment allocation algorithm based on the bid-winning probabilities. Our rigorous theoretical analysis shows that our algorithm designed achieves sub-linear growth on dynamic regret and dynamic fit over time while preserving the economic properties of truthfulness and individual rationality. Finally, multiple experiments validate the efficacy of the proposed auction mechanism algorithm from various perspectives compared with three other existing algorithms.

Conducting federated learning across distributed sites with In-Band Network Telemetry (INT) based data collection faces critical challenges, including control decisions of different frequencies, convergence of the models being trained, and resource provisioning coupled over time. To study this problem, we formulate a non-linear mixed-integer program to optimize the long-term INT overhead, resource cost, and federated learning cost. We then design polynomial-time online algorithms to solve this problem with only observable inputs on the fly, featuring laziness-aware resource adaption, online-learning-based INT flow selection and model aggregation control, as well as expectation-preserving randomized dependent rounding. We rigorously prove the parameterized-constant competitive ratio of our approach against the offline optimum, and the time-averaged constraint violation that vanishes in the long run. With extensive trace-driven evaluations, we confirm the superiority of our approach over other alternative approaches for reducing total cost and the efficacy of our trained models for solving real machine learning problems, reducing the real-time cost by 34% on average.