Handling Both Routing and Caching Effectively

ECE Associate Professor Stratis Ioannidis and Professor Edmund Yeh were awarded a patent for “Joint routing and caching method for content delivery with optimality guarantees for arbitrary networks.”

Abstract Source: USPTO

Embodiments solve a problem of minimizing routing costs by jointly optimizing caching and routing decisions over an arbitrary network topology. Embodiments solve an equivalent caching gain maximization problem, and consider both source routing and hop-by-hop routing settings. The respective offline problems are non-deterministic polynomial time (NP)-hard. Nevertheless, embodiments show that there exist polynomial time approximation methods producing solutions within a constant approximation from the optimal. Embodiments herein include distributed, adaptive networks, computer methods, systems, and computer program products that provide guarantees of routing cost reduction. Simulation is performed over a broad array of different topologies. Embodiments reduce routing costs by several orders of magnitude compared to existing approaches, including existing approaches optimizing caching under fixed routing.

first page of patent

Related Faculty: Stratis Ioannidis, Edmund Yeh

Related Departments:Electrical & Computer Engineering