Caching has been widely leveraged to significantly improve network performance and mitigate congestion. However, characterizing the optimal tradeoff between routing cost and cache deployment cost remains an open problem. In this paper, for a network with arbitrary topology and congestion-dependent nonlinear cost functions, we aim to jointly determine the cache deployment, content placement, and hop-by-hop routing strategies, so that the sum of routing cost and cache deployment cost is minimized. We tackle this mixed-integer nonlinear problem starting with a fixed-routing setting, and then generalize to a dynamic-routing setting. For the fixed-routing setting, a Gradient-combining Frank-Wolfe algorithm with (1/2, 1)-approximation is presented. For the general dynamic-routing setting, we obtain a set of KKT conditions, and devise a distributed and adaptive online algorithm based on these conditions. We demonstrate via extensive simulation that our algorithms significantly outperform a number of baselines.

Deploying data- and computation-intensive applications such as large-scale AI into heterogeneous dispersed computing networks can significantly enhance application performance by mitigating network resource bottlenecks, including bandwidth, storage, and computing power. However, current resource allocation methods do not provide a comprehensive solution that jointly considers arbitrary topology, elastic resource amount, reuse of computation results, and congestion-dependent optimization objectives. These aspects are vital when modeling state-of-the-art heterogeneous dispersed computing networks with high demand volume. In this paper, we propose LOAM, a low-latency joint communication, caching, and computation placement framework. LOAM incorporates the above aspects with a rigorous analytical foundation. It tackles the formulated NP-hard cost minimization problem with two methods: an offline method with a constant factor approximation of 1/2, and an online adaptive method with a bounded gap from the optimum. Through extensive packetlevel simulation, LOAM outperforms multiple baselines in both synthesis and real-world network scenarios.

Collaborative edge computing (CEC) is an emerging paradigm for heterogeneous devices to collaborate on edge computation jobs. For congestible links and computing units, delay-optimal forwarding and offloading for service chain tasks (e.g., DNN with vertical split) in CEC remains an open problem. In this paper, we formulate the service chain forwarding and offloading problem in CEC with arbitrary topology and heterogeneous transmission/computation capability, and aim to minimize the aggregated network cost. We consider congestion-aware nonlinear cost functions that cover various performance metrics and constraints, such as average queueing delay with limited processor capacity. We solve the non-convex optimization problem globally by analyzing the KKT condition and proposing a sufficient condition for optimality. We then propose a distributed algorithm that converges to the global optimum. The algorithm adapts to changes in input rates and network topology, and can be implemented as an online algorithm. Numerical evaluation shows that our method significantly outperforms baselines in multiple network instances, especially in congested scenarios.

Caching can be leveraged to significantly improve network performance and mitigate congestion. However, characterizing the optimal tradeoff between routing cost and cache deployment cost remains an open problem. In this paper, for a network with arbitrary topology and congestion-dependent nonlinear cost functions, we aim to jointly determine the cache deployment, content placement, and hop-by-hop routing strategies, so that the sum of routing cost and cache deployment cost is minimized. We tackle this mixed-integer nonlinear problem starting with a fixed-routing setting, and then generalize to a dynamic-routing setting. For the fixed-routing setting, a Gradient-combining Frank-Wolfe algorithm with $\left( {\frac{1}{2},1} \right)$-approximation is presented. For the general dynamic-routing setting, we obtain a set of KKT conditions, and devise a distributed and adaptive online algorithm based on these conditions. We demonstrate via extensive simulation that our algorithms significantly outperform a number of baselines.

We study the problem of minimizing energy costs for content delivery in wireless heterogeneous networks by jointly optimizing caching and power control strategies. This can be equivalently cast as a problem of maximizing the joint caching and power gain subject to meeting minimum signal-to-interference-plus-noise ratio constraints. The offline version of this problem is NP-hard, but we show that there exist polynomial-time approximation algorithms producing solutions within a constant factor 1 - 1/$e$from the optimal. We further provide an adaptive algorithm based on projected subgradient ascent over a concave relaxation of the expected joint caching and power gain, which yields the same approximation guarantee. We show that our proposed algorithm outperforms the alternating optimization method and other baseline algorithms in a number of network scenarios, in total power consumption and run time.

A fundamental challenge in wireless heterogeneous networks (HetNets) is to effectively utilize the limited transmission and storage resources in the presence of increasing deployment density and backhaul capacity constraints. To alleviate bottlenecks and reduce resource consumption, we design optimal caching and power control algorithms for multi-hop wireless HetNets. We formulate a joint optimization framework to minimize the average transmission delay as a function of the caching variables and the signal-to-interference-plus-noise ratios (SINR) which are determined by the transmission powers, while explicitly accounting for backhaul connection costs and the power constraints. Using convex relaxation and rounding, we obtain a reduced-complexity formulation (RCF) of the joint optimization problem, which can provide a constant factor approximation to the globally optimal solution. We then solve RCF in two ways: 1) alternating optimization of the power and caching variables by leveraging biconvexity, and 2) joint optimization of power control and caching. We characterize the necessary (KKT) conditions for an optimal solution to RCF, and use quasi-convexity to show that the KKT points are Pareto optimal for RCF. We then devise a subgradient projection algorithm to jointly update the caching and power variables under general SINR conditions. Finally, our analytical findings are supported by results from extensive numerical experiments.

Collaborative edge computing (CEC) is an emerging paradigm where heterogeneous edge devices collaborate to fulfill computation tasks, such as model training or video processing, by sharing communication and computation resources. Nevertheless, when considering network congestion, the optimal data/result routing and computation offloading strategy of CEC still remains an open problem. In this paper, we formulate a flow model of partial-offloading and multi-hop routing in CEC network with arbitrarily topology and heterogeneous communication/computation capability. In contrast to most existing works, our model applies to tasks with non-negligible result size, and allows data sources to be distinct from the result destination. We propose a network-wide cost minimization problem with congestion-aware convex cost functions. Such convex cost covers various performance metrics and constraints, such as average queueing delay with limited processor capacity. Although the problem is non-convex, we provide necessary conditions and sufficient conditions for the global-optimal solution, and devise a fully distributed algorithm that converges to the optimum in polynomial time. Our proposed method allows asynchronous individual updating, and is adaptive to changes of network parameters. Numerical evaluation shows that our method significantly outperforms other baseline algorithms in multiple network instances, especially in congested scenarios.

A fundamental challenge in wireless heterogeneous networks (HetNets) is to effectively use the limited transmission and storage resources in the presence of increasing deployment density and backhaul capacity constraints. To alleviate bottlenecks and reduce resource consumption, we design optimal caching and power control algorithms for multi-hop wireless HetNets. We devise a joint optimization framework to minimize the average transmission delay as a function of the caching variables and the signal-to-interference-plus-noise ratios (SINR) as determined by the transmission powers, while explicitly accounting for backhaul connection costs and the power constraints.Using convex relaxation and rounding, we obtain a reduced-complexity formulation (RCF) of the joint optimization problem, which can provide a constant factor approximation to the globally optimal solution. We characterize the necessary (KKT) conditions for an optimal solution to RCF, and use strict quasi-convexity to show that the KKT points are Pareto optimal for RCF. We then devise a subgradient projection algorithm to jointly update the caching and power variables, and show that under appropriate conditions, the algorithm converges at a linear rate to the local minima of RCF, under general SINR. We support our analytical findings with results from numerical experiments.