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.
