- Home
- Research Areas
- Biological Sciences (BIO)
- Computer and Information Science and Engineering (CISE)
- Education and Human Resources (EHR)
- Engineering (ENG)
- Environmental Research and Education (ERE)
- Geosciences (GEO)
- Integrative Activities (OIA)
- International Science and Engineering (OISE)
- Mathematical and Physical Sciences (MPS)
- Social, Behavioral and Economic Sciences (SBE)
- Funding
- About Funding
- Archived Funding Search
- Due Dates
- Find Funding
- Merit Review
- Policies and Procedures
- Preparing Proposals
- Recent Opportunities
- Transformative Research
- Related Links
- Proposal and Award Policies and Procedures Guide (PAPPG)
- Research.gov
- FastLane
- Funding Opportunities For
- Graduate Students
- K-12 Educators
- Postdoctoral Fellows
- Undergraduate Students
- Small Business
- Awards
- Document Library
- News
- About NSF
Award Abstract # 1535887
AitF: EXPL: Wide-area Dissemination under Strict Timeliness, Reliability, and Cost Constraints
| NSF Org: |
CCF Division of Computing and Communication Foundations |
| Awardee: |
|
| Initial Amendment Date: | August 20, 2015 |
| Latest Amendment Date: | August 20, 2015 |
| Award Number: | 1535887 |
| Award Instrument: | Standard Grant |
| Program Manager: |
Tracy Kimbrel
tkimbrel@nsf.gov (703)292-7924 CCF Division of Computing and Communication Foundations CSE Direct For Computer & Info Scie & Enginr |
| Start Date: | September 1, 2015 |
| End Date: | August 31, 2019 (Estimated) |
| Total Intended Award Amount: | $400,000.00 |
| Total Awarded Amount to Date: | $400,000.00 |
| Funds Obligated to Date: |
|
| History of Investigator: |
|
| Awardee Sponsored Research Office: |
1101 E 33rd St Baltimore MD US 21218-2686 (443)997-1898 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
3400 N CHARLES ST Baltimore MD US 21218-2608 |
| Primary Place of Performance Congressional District: |
|
| DUNS ID: |
|
| Parent DUNS ID: |
|
| NSF Program(s): | Algorithms in the Field |
| Primary Program Source: |
|
| Program Reference Code(s): |
|
| Program Element Code(s): |
|
| Award Agency Code: | 4900 |
| Fund Agency Code: | 4900 |
| Assistance Listing Number(s): | 47.070 |
ABSTRACT
Many new Internet applications have extremely strict reliability and timeliness constraints. For example, when trying to remotely manipulate an object (such as in remote robotic surgery), in order to provide seamless feedback the connection needs to be essentially uninterrupted and have delay of at most 130 ms. One way of achieving this is to build an overlay network: a small number of computers, strategically positioned in datacenters around the world, which communicate with each other over the Internet in a way designed to improve reliability while maintaining timeliness.
This project seeks to provide timeliness and reliability by sending messages over a select subset of the network, rather than along the best path, and to select subsets that are cost-effective. Successfully designing such techniques will enable applications that require timely, reliable service, well beyond what the current state-of-the-art can provide over the Internet. In addition to the practical benefits, this research will also significantly improve our understanding of the theory of overlay networks and network design: existing algorithms and techniques do not give the strong guarantees that are required, so we will need to develop both new algorithms and new mathematical tools to analyze these algorithms. Hence this research will also have significant impact on the state of the art in the mathematics and theory of networking.
This project will develop new theory and a practical architecture for resilient routing. There has since been extensive work on designing approximation algorithms for related reliability-under-random-faults problems, as well as studying them for specific graph classes. However, there has been almost no work on the network design versions of these problems, which form the theoretical aspects of this proposal. Thus the results of this work will be a significant step forward in fault-tolerant network design. Moreover, the proposed research will advance the understanding of how to model practical networking problems and how to translate theoretical solutions into concrete systems, by evaluating solutions developed under different levels of abstraction in a fully realistic setting.
PUBLICATIONS PRODUCED AS A RESULT OF THIS RESEARCH
Note:
When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
Some links on this page may take you to non-federal websites. Their policies may differ from this site.
Amy Babay, Claudiu Danilov, John Lane, Michal Miskin-Amir, Daniel Obenshain, John L. Schultz, Jonathan Robert Stanton, Thomas Tantillo, Yair Amir:
"Structured Overlay Networks for a New Generation of Internet Services"
Proceedings of the 37th IEEE International Conference on Distributed Computing Systems (ICDCS 2017)
, 2017
10.1109/ICDCS.2017.119
Amy Babay, Emily Wagner, Michael Dinitz, and Yair Amir
"Timely, Reliable, and Cost-Effective Internet Transport Service using Dissemination Graphs"
Proceedings of the 37th IEEE International Conference on Distributed Computing Systems (ICDCS 2017)
, 2017
10.1109/ICDCS.2017.63
Eden Chlamtac, Michael Dinitz, and Yury Makarychev
"Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion"
Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017)
, 2017
10.1137/1.9781611974782.56
Eden Chlamtac, Michael Dinitz, Christian Konrad, Guy Kortsarz, George Rabanca
"The Densest k-Subhypergraph Problem"
The 19th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)
, 2016
Michael Dinitz and Yasamin Nazari
"Distributed Distance-Bounded Network Design Through Distributed Convex Programming"
Proceedings of the 21st International Conference on Principles of Distributed Systems (OPODIS 2017)
, 2017
10.4230/LIPIcs.OPODIS.2017.5
Eden Chlamtá?, Michael Dinitz, Christian Konrad, Guy Kortsarz, and George Rabanca
"The Densest k-Subhypergraph Problem"
SIAM Journal on Discrete Mathematics
, v.32
, 2018
, p.1458
0895-4801
Michael Dinitz and Michael Schapira and Gal Shahaf
"Large Low-Diameter Graphs are Good Expanders"
Proceedings of the 26th Annual European Symposium on Algorithms (ESA 2018)
, 2018
10.4230/LIPIcs.ESA.2018.71
PROJECT OUTCOMES REPORT
Disclaimer
This Project Outcomes Report for the General Public is displayed verbatim as submitted by the Principal Investigator (PI) for this award. Any opinions, findings, and conclusions or recommendations expressed in this Report are those of the PI and do not necessarily reflect the views of the National Science Foundation; NSF has not approved or endorsed its content.
This project resulted in a prototype system for wide-area communication that is reliable, timely, and efficient. This system is described in our ICDCS 2017 paper "Timely, Reliable, and Cost-Effective Internet Transport Service using Dissemination Graphs". The goal of this system was to be able to route data across long-distances (e.g., cross-country or trans-Atlantic) in a way that is both reliable and fast. Traditional approaches are either reliable but slow or fast but unreliable. We wanted to get the best of both worlds (fast and reliable) without incurring too much extra cost. We were particularly motivated by applications requiring haptic feedback (such as remote surgery), but our system is more broadly applicable to any setting where speed, reliability, and cost are all important factors.
Our main idea was to route data not just along paths, as in traditional approaches, but rather to use more complicated routes we call "dissemination graphs". By choosing the dissemination graph appropriately, we can provide extra reliability relatively cheaply by only reinforcing parts of the routes that are prone to experiencing failure, rather than equally reinforcing across the routes. This enables a high degree of reliability without costing too much.
Our prototype system is remarkably successful at achieving our goals. For example, on a real country-scale overlay network on which we test for a month, our system was able to close the "reliability gap" (the gap between the most reliable possible system and the least reliable system) by 99.81% at a cost of only 2.098 times the least reliable system, while achieving maximum reliability would have cost 15.75 times as much. In other words: by paying twice as much as a totally unreliable system, we got over 99% of the maximum reliability possible, which would have cost 15 times as much to achieve.
In addition to our system itself, the study of dissemination graphs led us to a set of important theoretical problems in algorithm design. Namely: how can we compute the best dissemination graphs? We designed extremely efficient algorithms for many cases (so-called "fixed-parameter tractable algorithms"), but also showed that there are some cases when such algorithms do not exist. For these cases we are forced to use suboptimal dissemination graphs. We also generalized these results, giving a complete characterization of what settings allow for efficient algorithms that find optimal dissemination graphs and which settings do not. Hence in the future we will be able to look at a particular setting and immediately know whether it is possible to design an efficient algorithm for finding dissemination graphs, or whether we will be forced to find suboptimal graphs.
Last Modified: 11/20/2019
Modified by: Michael Dinitz
Please report errors in award information by writing to: awardsearch@nsf.gov.
