| NSF Org: |
CCF Division of Computing and Communication Foundations |
| Recipient: |
|
| Initial Amendment Date: | June 25, 2013 |
| Latest Amendment Date: | June 25, 2013 |
| Award Number: | 1320854 |
| Award Instrument: | Standard Grant |
| Program Manager: |
Rahul Shah
CCF Division of Computing and Communication Foundations CSE Directorate for Computer and Information Science and Engineering |
| Start Date: | September 1, 2013 |
| End Date: | August 31, 2017 (Estimated) |
| Total Intended Award Amount: | $354,172.00 |
| Total Awarded Amount to Date: | $354,172.00 |
| Funds Obligated to Date: |
|
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
21 N PARK ST STE 6301 MADISON WI US 53715-1218 (608)262-3822 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
WI US 53706-1685 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): | ALGORITHMS |
| 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
This project seeks to develop new algorithmic techniques for the
design of and routing in data networks. Classical network optimization
problems address transportation networks that carry physical
commodities. Data networks are fundamentally different --- data can be
modified, compressed, and replicated at little cost. Incorporating
this flexibility in altering traffic into network optimization
problems can bring about a considerable improvement in the capacities
of communication networks.
This project aims to revisit classical network optimization problems
within a new model where the cost of carrying data is non-linear and
depends on its compressibility. It aims to provide theoretical
underpinnings for new WAN optimization approaches proposed in the
networking literature, including, for example, traffic redundancy
elimination.
The PI considers a model where links in the network can compress data and
remove duplicate packets. For example, if two traffic streams contain
identical data and use overlapping routes, edges carrying both streams
need only transmit the common packets once; these can then be
replicated at routers where the streams diverge. Accordingly, the load
on an edge is a submodular function of the traffic streams that use
the edge. Unlike previous work on network optimization with non-linear
costs, in this model, the cost of routing depends on the identities of
the traffic streams involved, and not just on the total traffic
volume. Most of the problems considered are computationally
intractable and the PI aims to develop approximation algorithms.
Several graduate and undergraduate courses will benefit from this project.
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.
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 developed new algorithmic techniques for the design and optimization of communication networks. We studied network optimization problems where the cost of communication is non-linear owing to the compressibility of data, as well as those where the communication network must be able to support many different traffic patterns. We developed techniques for solving network design problems in an "online" context where traffic and requirements are revealed piecemeal rather than all at once. For each of these settings we developed novel algorithmic tools for obtaining approximately-optimal solutions. These settings are intractable to solve optimally and our algorithms provide nearly the best possible guarantees on the quality of the solution in each case. We also studied settings where many self-interested or competing parties aim to construct a single communication network and share in its cost; the network emerges as the outcome of a process where at each point of time a participant arrives, leaves, or changes its current routing. We showed that in the absence of any centralized control, the outcome of this "network design game" can be very far from optimal. On the other hand, it is possible to achieve an exponentially better outcome through a very limited amount of algorithmic control -- at every step of the aforementioned process, our algorithm chooses a participant, and recommends an action to this participant that is both beneficial for the participant to follow and leads to a cheap network overall.
During the course of this project, the PI trained two graduate students and developed a new graduate course on algorithms.
Last Modified: 01/07/2019
Modified by: Shuchi Chawla
Please report errors in award information by writing to: awardsearch@nsf.gov.
