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

NeTS：小型：协作研究：网络算法最坏情况大偏差理论的研究

• 批准号: 1423182
• 负责人: Jun Xu
• 金额: $ 25万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-10-01 至 2018-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1423182&HistoricalAwards=false
• 关键词: NeTS; Small; Collaborative; Research; into

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.

网络算法的设计和分析，即在高速互联网路由器上运行的软件和硬件系统背后的技术和原理，已成为丰富的研究领域。通常，网络运营商希望路由器在各种各样的，通常无法预料的操作条件下提供出色的性能。 为了满足这一需求，该项目首次查看网络算法解决方案，这些解决方案可以保证一定水平的性能，不仅在典型或平均参数设置下，如先前的研究，而且在所有可接受的参数设置下。为了实现这一目标，PIS建议开发一种新型的数学方法，称为最坏的大偏差理论，该理论证明了性能的普遍下限。该项目由三个紧密连接的研究线程组成。 首先，主要研究人员（PIS）将根据分布式数据流问题开发解决方案，以确保一定水平的性能，并在给定数据集分配给分布式子集中。 其次，他们将开发丰富的负载平衡的切换解决方案，可以保证在所有可接受的交通工作负载下，可以保证高通量和相当低的延迟。 第三，他们将在过去几年开发的最严重的大偏差技术之间建立数学联系，以在先前的网络算法解决方案中得出这种普遍的性能界限，他们期望这将揭示他们在前两个研究线程中将遇到的新数学问题，这些项目将通过研究生和研究培训，从而通过整体培训培训，这些培训与整体培训，这些培训跨越了培训，这些培训跨越了培训，这些培训跨越了培训，这些培训跨越了培训，这些培训跨越了多元化的培训，这些培训跨越了培训，这些培训跨越了培训，这些培训跨越了培训，这些培训跨越了培训，这些培训跨越了培训，这些培训跨越了培训。算法设计，用于硬件实现。 根据每个机构的政策，将通过出版物，邀请的会谈，教程以及为该项目开发的软件开源的结果大致传播结果。 PI将与领先的网络和系统解决方案提供商紧密合作，以促进技术转移。 此外，这两个PI都致力于在相应的校园内开展工作，以扩大代表性不足的群体在研究和高等教育中的参与。