NeTS: Small: Caching Networks with Optimality Guarantees

今天的互联网包括缓存网络-具有存储功能的网络-用于广泛的现实网络应用程序。它们在内容在线分发的商业系统中发挥着核心作用（例如流媒体电影和其他视频）。缓存显然有利于内容提供商，因为它减少了到达其服务器的流量。 它还有利于最终用户，因为它减少了他们所经历的延迟-例如下载电影的时间-以及网络服务提供商，因为它减少了穿越或退出其网络的整体互联网流量。尽管缓存部署的实际好处是众所周知的，但对缓存网络的性能如何的正式的数学理解在很大程度上仍然难以捉摸。 这个项目的目标是一个正式的了解如何互联网流量路由和缓存可以联合优化，以提供可证明的性能保证方面的一些设计目标，如吞吐量优化或成本最小化。 优化传统的网络操作，如路由、拥塞和流量控制、主动队列管理等，在高速缓存网络的上下文中变得非常具有挑战性。这项工作可以对现有和未来的网络架构和商业系统产生直接和长期的影响，包括信息中心网络（ICN）和内容交付网络（CDN）。该项目也是一个很好的平台，促进跨学科学习的网络和组合和凸优化领域，是非常适合本科生的研究，包括动手项目，涉及模拟实验和validation. Contrast缓存网络之前的工作，该项目提供了分布式，自适应，随机优化协议的最优性保证在任意网络拓扑结构。特别是，使用所提出的方法，组合性质的缓存以及缺乏凸性的自然目标，克服通过凸松弛。该项目利用这种放松来设计常数逼近、分布式、自适应、随机优化算法，做出距离最佳值在恒定因子内的联合路由和缓存决策。此外，该项目实现和评估这些算法在现实的网络拓扑结构，各种现实生活中的网络服务负载和用户需求。

The Internet today includes networks of caches--networks with storage capabilities--that are used in a broad array of real-life networking applications. They play a central role in commercial systems for the online distribution of content (for example streaming movies and other videos). Caching clearly benefits content providers, as it reduces traffic reaching their servers. It also benefits end-users, as it reduces the latency they experience--for example the time to download a movie--and network service providers, as it reduces the overall Internet traffic traversing or exiting their network. Despite the known practical benefits of cache deployments, a formal, mathematical understanding of how well caching networks perform remains largely elusive. The goal of this project is a formal understanding of how Internet traffic routing and caching can be jointly optimized so as to provide provable performance guarantees with respect to some set of design objectives, such as throughput optimization or cost minimization. Optimizing traditional network operations, such as routing, congestion and flow control, active queue management, etc., becomes significantly challenging in the context of caching networks. This work can have a direct and long-term impact on both existing and future network architectures and commercial systems, including information-centric networks (ICNs) and content-delivery networks (CDNs). The project is also an excellent platform for promoting interdisciplinary learning in the areas of networking and combinatorial and convex optimization, and is well-suited to undergraduate research, including hands-on projects involving simulation experiments and validation.Contrary to prior work on caching networks, this project provides distributed, adaptive, stochastic optimization protocols with optimality guarantees over arbitrary network topologies. In particular, using the proposed methodology, both the combinatorial nature of caching as well the lack of convexity of natural objectives are overcome through convex relaxations. The project leverages such relaxations to design constant-approximation, distributed, adaptive, stochastic optimization algorithms, making joint routing and caching decisions that are within a constant factor from the optimal. In addition, the project implements and evaluates these algorithms over realistic network topologies, under a variety of real-life network service loads and user demands.