A National Science Foundation (NSF) grant (Award Number 1535887, September 2015 - August 2018) to Johns Hopkins University. A component of the NSF Algorithms in the Field (AitF) program.
Principal Investigator: Michael Dinitz. Co-Principal Investigator: Yair Amir.

Overview

This project aims to enable new Internet services with demanding timeliness and reliability requirements by developing new theory and a practical architecture for resilient routing. Emerging interactive applications, such as remote manipulation, have such strict timeliness requirements that reliability cannot be achieved solely through buffering and recovery protocols, as packets may arrive too late to be useful. While redundant sending along a single path and network coding can improve reliability, the combination of correlated loss on the Internet and the strict timeliness constraints of target applications dramatically reduces the effectiveness of such approaches.

This project seeks to provide timeliness and reliability by sending each packet over a subgraph of the network, rather than along a single best path, and to select subgraphs that are cost-effective, which is essential to enable these services to become widely available in practice. There is currently no way to optimally trade-off reliability and cost, so we are developing new algorithms to solve the problem at several levels of abstraction, and are implementing and testing the performance of these algorithms on a global wide-area network to evaluate the practicality of the abstractions and the effectiveness of the solutions.

Contributors

• Faculty
  • Yair Amir
  • Michael Dinitz
• Students
  • Amy Babay
  • Emily Wagner
  • Yasamin Nazari

Related Publications

• Characterizing Demand Graphs for (Fixed-Parameter) Shallow-Light Steiner Network
  Amy Babay, Michael Dinitz, and Zeyu Zhang.
  Submitted.
• Timely, Reliable, and Cost-effective Internet Transport Service using Dissemination Graphs
  Amy Babay, Emily Wagner, Michael Dinitz, and Yair Amir.
  The IEEE 37th International Conference on Distributed Computing Systems (ICDCS), Atlanta GA, June 2017. Best paper award.
• Structured Overlay Networks for a New Generation of Internet Services
  Amy Babay, Claudiu Danilov, John Lane, Michal Miskin-Amir, Daniel Obenshain, John Schultz, Jonathan Stanton, Thomas Tantillo, Yair Amir.
  The IEEE 37th International Conference on Distributed Computing Systems (ICDCS), Vision track, Atlanta GA, June 2017. Invited paper.
• Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion
  Eden Chlamtac, Michael Dinitz, Yury Makarychev.
  The 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2017.
• The Densest k-Subhypergraph Problem
  Eden Chlamtac, Michael Dinitz, Christian Konrad, Guy Kortsarz, George Rabanca.
  The 19th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2016). Paris, France.
• Timely, Reliable, and Cost-effective Transport Service using Dissemination Graphs
  Amy Babay.
  The 45th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), Student Forum. Rio de Janeiro, Brazil, June 2015.