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.