| NSF Org: |
CCF Division of Computing and Communication Foundations |
| Recipient: |
|
| Initial Amendment Date: | August 29, 2013 |
| Latest Amendment Date: | August 29, 2013 |
| Award Number: | 1349602 |
| 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, 2015 (Estimated) |
| Total Intended Award Amount: | $99,993.00 |
| Total Awarded Amount to Date: | $99,993.00 |
| Funds Obligated to Date: |
|
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
615 W 131ST ST NEW YORK NY US 10027-7922 (212)854-6851 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
2960 Broadway New York NY US 10027-6902 |
| 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
Even as the availability of computing power, network bandwidth and other resources increases at a rapid rate, users and applications increase their demand for computation and their use of resources at roughly the same pace. Thus, no matter how much progress is made on hardware efficiency, we will always need efficient algorithms to manage these resources. The philosophy of managing additional resources in an intelligent manner goes beyond computer systems, and is relevant to many other scientific and industrial areas. In various real-life systems, processing times may be controllable by allocating resources, such as additional money, overtime, energy, fuel, catalysts, subcontracting, or additional manpower, to the job operations. In such systems, job scheduling and resource allocation decisions should be coordinated carefully to achieve the most efficient system performance. Applications arise in many industrial areas.
The PI plans to study several algorithmic problems that arise in scheduling with additional resource constraints. While this field has received much attention over the past ten years and beyond, the PI will focus on two areas that have received very little attention in the computer science community -- scheduling when the benefit of the schedule and the cost of energy or other resources are monetized, and scheduling in models that go beyond the typically studied computer systems setting. Because these have received very little attention, this work is somewhat speculative. If successful, this work could have a high impact, with applications into many new areas. The PI will design simple, low overhead algorithms.
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 involved the study of algorithms for scheduling and related problems in which there are additional resource constraints. Examples of such constraints include energy (electricity) or quality or number of changes in a solution. We had two major findings regarding the use of algorithms to manage energy consumption in networks, both general networks such as the internet, and energy harvesting networks.
First, we considered eneregy usage in a network, observing that components that have higher loads use more energy. In fact, the usage of energy is typically superlinear, that is, as components receive large loads they use energy less efficeintly. Of course, it is occassionally necessary to highly load a component in order to achieve the desired network utilization. We gave the first algorithms that show how to achieve a desired routing while managing the use of energy.
We also considered problems that arise in energy harvesting network. Recent advances in the development of ultra-low-power transceivers and energy harvesting devices (e.g., solar cells) will enable self-sustainable and perpetual wireless networks In contrast to legacy wireless sensor networks, where the available energy only decreases as the nodes sense and forward data, in energy harvesting networks the available energy can also increase through a replenishment process. This results in significantly more complex variations of the available energy, which pose challenges in the design of resource allocation and routing algorithms. We gave algorithms that show how to route in a way that is fair to all the agents and is balanced over time.
We also showed how to manage networks that change over times. Networks naturally grow and shrink, as new nodes and connections appear. As networks evolve, it is important to be able to quickly recompute various important parameters, and to be able to continue to use the network efficiently. We gave algorithms that address how to manage routes in networks as they evolve. These algorithms addressed two different components of change. In one work, we showed how, as the network changes, we can continue to route while makiing as few changes as possible to our routing. In another work we showed how make a small number of changes, but do so in a very efficient manner.
All of this work advanced the state of the art in algorithms research and has potential use in important applications in networks and routing.
Last Modified: 01/02/2016
Modified by: Clifford S Stein
Please report errors in award information by writing to: awardsearch@nsf.gov.
