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

网络算法的设计和分析，即运行在高速互联网路由器上的软件和硬件系统背后的技术和原理，已经成为一个丰富的研究领域。一般来说，网络运营商希望路由器在各种各样的、通常不可预见的操作条件下提供稳健的性能。 为了满足这一需求，该项目首先研究了可以保证一定性能水平的网络算法解决方案，不仅在先前研究中的典型或平均参数设置下，而且在所有允许的参数设置下。为了实现这一目标，PI建议开发一种新的数学方法，称为最坏情况下的大偏差理论，需要证明这种普遍的性能下限。该项目由三个紧密相连的研究线索组成。 首先，主要研究者（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.