Yuanyuan Li PhD Dissertation Defense

Title: Sub-modularity in Cache Networks

Committee Members:
Prof. Stratis Ioannidis
Prof. Lili Su
Prof. Edmund Yeh

Abstract:
As information-based demand surges, distributed network services, e.g., cache networks, play an important role to mitigate network traffic. Cache networks are a natural abstraction for many applications, including information-centric networks, content delivery networks, cloud computing, and edge/wireless IoT. How to allocate resources (routing, placing items in caches, flow control, etc.) in cache networks is a crucial problem, as resources (storage space, and bandwidths) are usually limited. Resource allocation in networks has been traditionally approached through classic convex optimization. However, simple problems becomes combinotorial in cache networks, which leads to NP-hardness. Enlightened by several works studying cache networks, we identify a useful property, submodularity, which is the key to approximation algorithms solving those NP hard resource allocation problem in cache networks.

Leveraging submodularity, we study a cache network, in which intermediate nodes equipped with caches can serve content requests, from different angles.

First, we model this network as a universally stable queuing system, in which packets carrying identical responses are consolidated before being forwarded downstream. We refer to resulting queues as $\info$ or counting queues, as consolidated packets carry a counter indicating the packet’s multiplicity. Cache networks comprising such queues are hard to analyze; we propose two approximations: one via $\mminf$ queues, and one based on $\info$ queues under the assumption of Poisson arrivals. We show that, in both cases, the problem of jointly determining (a) content placements and (b) service rates admits a poly-time, $1-1/e$ approximation algorithm. We also show that our analysis, with respect to both algorithms and associated guarantees, extends to (a) counting queues over items, rather than responses, as well as to (b) queuing at nodes and edges, as opposed to just edges.

Second, we refer to the cost reduction enabled by caching as the caching gain, and the product of the caching gain of a content request and its request rate as \emph{caching gain rate}. We aim to study \emph{fair} content allocation strategies through a utility-driven framework, where each request achieves a utility of its caching gain rate, and consider a family of $\alpha$-fair utility functions to capture different degrees of fairness. The resulting problem is an NP-hard problem with a non-decreasing submodular objective function. Submodularity allows us to devise a deterministic allocation strategy with an optimality guarantee factor arbitrarily close to $1-1/e$.  When $0 < \alpha \leq 1$, we further propose a randomized strategy that attains an improved optimality guarantee,  $(1-1/e)^{1-\alpha}$, in expectation.

Third, we study a cache network, and model the problem of jointly optimizing caching and routing decisions with link capacity constraints over an arbitrary network topology. This problem can be formulated as a continuous diminishing-returns(DR) submodular maximization problem under multiple continuous DR-supermodular constraints, and is NP-hard. We propose a poly-time alternating primal-dual  heuristic algorithm, in which primal steps produce solutions within $1-\frac{1}{e}$ approximation factor from the optimal. Through extensive experiments, we demonstrate that our proposed algorithm significantly outperforms competitors.

Forth, we study a cache network under arbitrary adversarial request arrivals. We propose a distributed online policy based on the online tabular greedy algorithm. Our distributed policy achieves sublinear $(1-\frac{1}{e})$-regret, also in the case when update costs cannot be neglected.

Finally, we propose an {\em experimental design network} paradigm, wherein learner nodes train possibly different Bayesian linear regression models via consuming data streams generated by data source nodes over a network. We formulate this problem as a social welfare optimization problem in which the global objective is defined as the sum of experimental design objectives of individual learners, and the decision variables are the data transmission strategies subject to network constraints. We first show that, assuming Poisson data streams, the global objective is a continuous DR-submodular function. We then propose a Frank-Wolfe type algorithm that outputs a solution within a $1-1/e$ factor from the optimal. Our algorithm contains a novel gradient estimation component which is carefully designed based on Poisson tail bounds and sampling.