NeTS: Small: Collaborative Research: Research into Worst-Case Large Deviation Theory for Network Algorithmics

网络算法的设计和分析，即运行在高速互联网路由器上的软硬件系统背后的技术和原理，已经成为一个丰富的研究领域。一般而言，网络运营商希望路由器能够在各种通常不可预见的运行条件下提供强大的性能。为了解决这一需求，本项目首先研究了网络算法解决方案，这些解决方案不仅可以像以前的研究那样在典型或平均参数设置下，而且在所有可接受的参数设置下，都可以保证一定水平的性能。为了实现这一目标，PI建议开发一种新的数学方法，称为最坏情况大偏差理论，该理论需要证明性能的通用下限。该项目由三条紧密相连的研究线索组成。首先，主要调查人员(PI)将为分布式数据流问题开发解决方案，在所有可能的方式下，将给定的数据集划分为分布式子集，这些解决方案可以保证一定的性能水平。其次，他们将开发丰富的负载平衡交换解决方案系列，在所有可接受的流量工作负载下保证高吞吐量和合理的低延迟。第三，他们将在过去几年开发的最坏情况下的大偏差技术之间建立数学联系，以获得先前网络算法解决方案中的通用性能界限，他们预计这将揭示他们在前两个研究线索中将遇到的新数学问题。这个项目将通过综合课堂课程和研究培训，从基础数学、算法设计到硬件实现，吸引研究生和本科生。将根据每个机构的政策，通过出版物、特邀讲座、教程和为该项目开发的软件开源等方式广泛传播成果。私人投资促进机构将与领先的网络和系统解决方案提供商密切合作，促进技术转让。此外，两家私人投资机构都致力于在各自的校园开展外联工作，以扩大任职人数不足的群体在研究和高等教育方面的参与。

The design and analysis of network algorithmics, namely, techniques and principles behind the software and hardware systems running on high-speed Internet routers, has become a rich area of research. In general, network operators would like routers to deliver robust performance under a wide variety of, often unforeseen, operating conditions. To address this need, this project takes a first look into network algorithmics solutions that can guarantee a certain level of performance, not only under typical or average parameter settings as in prior studies, but also under all admissible parameter settings. Toward this goal, PIs propose to develop a novel mathematical approach, called worst-case large deviation theory that is needed to prove such universal lower bounds on performance. This project consists of three closely connected research threads. First, the principal investigators (PIs) will develop solutions for distributed data streaming problems that can guarantee a certain level of performance, under all possible ways a given data set is partitioned into distributed subsets. Second, they will develop a rich family of load-balanced switching solutions that can guarantee high throughput and reasonably low delay under all admissible traffic workloads. Third, they will build mathematical connections between worst-case large deviation techniques they developed in the past several years for deriving such universal performance bounds in prior network algorithmics solutions, which they expect will shed light on the new mathematical problems they will encounter in the first two research threads.This project will engage both graduate and undergraduate students through integrated classroom curriculum and research training that span multiple disciplines, from fundamental mathematics, algorithm design, to hardware implementation. The results will be broadly disseminated through publications, invited talks, tutorials, and open-sourcing of software developed for this project in accordance with the policies of each institution. The PIs will work closely with leading networking and systems solution providers to facilitate technology transfers. Further, both PIs are committed to outreach efforts at their corresponding campuses to broaden the participation of under-represented groups in research and higher education.