AF:Small:Scheduling and Routing: Algorithms with novel cost measures

Columbia University, New York NY

Investigators

Abstract

Computers, computer systems and the computational infrastructure provided by the internet are now essential for many aspects of modern life.  It is well-known and well-documented that, even as computing power and network bandwidth increase at a rapid rate, users and applications increase their demand for computation and their use of networks at roughly the same pace.  Thus, no matter how much progress is made on the hardware and network ends, efficient algorithms to manage these resources are essential. These efficient algorithms will lead to tremendous savings in both time and money and will have a positive environmental impact. They will also contribute to the decisions that are being made presently about the next generation of the internet, in particular in the design of routing protocols and the management of data centers. It is now well-understood that time and space are not the only resources that need to be carefully managed.  For the past few decades, there has been a growing emphasis on other concerns such as accuracy of solution, availability of information, use of cache, management of disk, etc.  More recently, there has been a growing understanding that energy and power management are also resources that should be carefully managed.  In this project, the PI will study several algorithmic problems that arise in applications such as computer systems and networks.  For each of these, the PI will focus on algorithms for better managing the technologies, and that have objectives that go beyond time or solution quality.  In particular, the project will study energy consumption in both computers and networks, and we will also consider environments in which other resources must be managed, such as minimizing the number of changes to a solution over time. The problem areas studied include power management in routing, power management in scheduling, extending speed scaling to other domains, and online problems with a reassignment cost. The PI will design efficient solutions to important practical problems, and the research will have broader impact.