Jinkun Zhang PhD Dissertation Defense

Announcing:
PhD Dissertation Defense

Name:
Jinkun Zhang

Title:
Low-latency Forwarding, Caching and Computation Placement in Data-centric Networks

Date:
4/8/2024

Time:
3:30:00 PM

Location:
EXP-459,

Committee Members:
Prof. Edmund Yeh (Advisor)
Prof. Stratis Ioannidis
Prof. Kaushik Chowdhury

Abstract:
With the exponential growth of data- and computation-intensive network applications, such as real-time augmented reality/virtual reality rendering and large-scale language model training, traditional cloud computing frameworks exhibit inherent limitations. To address these challenges, dispersed computing has emerged as a promising next-generation networking paradigm. By enabling geographically distributed nodes with heterogeneous computation capabilities to collaborate, dispersed computing overcomes the bottlenecks of traditional cloud computing and facilitates in-network computation tasks, including the training of large models. In data-centric networks, communication and computation are resolved around data names instead of host addresses. The deployment of network caches, by enabling data reuse, offers substantial benefits for data-centric networks. For instance, consider a scenario where multiple machine learning applications seek to train different models simultaneously. This application could (partially) share data samples and/or computational results. Optimal caching of data and/or results can significantly reduce the overall training cost, compared to each application independently gathering and transmitting data.

This dissertation aims to minimize average user delay in a general cache-enabled computing network. We introduce a low-latency framework that jointly optimizes packet forwarding, storage deployment, and computation placement. The proposed framework effectively supports data-intensive and latency-sensitive computation applications in data-centric computing networks with heterogeneous communication, storage, and computation capabilities. To minimize user latency in congestible networks, we model delays caused by link transmissions and CPU computations using traffic-dependent nonlinear functions. We consider a series of related network resource allocation problems in a unified network model.

We first investigate the joint forwarding and computation placement problem, then the joint forwarding and elastic caching problem. Despite the non-convexity of the former subproblem, we provide a set of sufficient optimality conditions that lead to a distributed algorithm with polynomial-time convergence to the global optimum. For the latter subproblem, we demonstrate its NP-hardness and non-submodularity, even after continuous relaxation. We propose a set of conditions that provide a finite bound from the optimum. To the best of our knowledge, our method represents the first analytical progress in addressing the joint caching and forwarding problem with arbitrary topology and non-linear costs. Upon solving the above two subproblems, we formally propose the low-latency joint forwarding, caching, and computation placement framework. We formulate the mixed-integer NP-hard total cost minimization problem jointly over forwarding, caching, and computation offloading variables. Developing on the established result for both subproblems, we propose two methods, each with an analytical guarantee. The first method achieves a 1/2 approximation guarantee by exploiting the “submodular + concave” structure of the problem, leading to an offline distributed algorithm. In real scenarios, however, request patterns and network status are not known prior and can be time-varying. To this end, our second method leads to an online adaptive algorithm exploiting its “convex + geodesic-convex” nature, with a proven bounded gap from the optimum.

The proposed solutions are followed by a few extension problems. Specifically, we generalize the computation from “single-step” to “service chain” applications. We also generalize the solution to incorporate congestion control by considering an “extended graph”. Furthermore, several network resource allocation optimization problems related to data-centric networking are introduced, expanding the scope of this dissertation. For example, we investigate joint caching and transmission power allocation in wireless heterogeneous networks, where the total transmission energy is minimized subject to constraints for SINR lower bounds, cache capacities, and total power budget at each node. We also study the optimal multi-commodity pricing with finite menu length, where novel asymptotic bounds on quantization errors are devised.