Efficient Algorithms for Problems in the Next Generation of Computing

下一代计算问题的高效算法哥伦比亚大学悬崖边计算机、计算机系统和互联网提供的计算基础设施现在对现代生活的许多方面都是必不可少的。众所周知，即使计算能力和网络带宽快速增长，用户和应用程序对这些资源的需求也会以大致相同的速度增长。因此，无论我们在硬件和网络端取得了多大的进步，我们总是需要有效的算法来管理这些资源。这项研究集中在计算机系统和网络中的几个算法问题；这些问题既源于现有的技术，也源于正在发展或已经提出的技术。通过提高我们管理设备和基础设施的效率，将在时间和经济上节省大量资金。此外，调查者整合了理论和系统，并鼓励这些领域之间进行更多的合作，带来了明显的好处。这项工作对目前正在做出的关于下一代互联网、互联网和操作系统调度的决策产生了影响。特别是，研究人员研究了四个具体的问题领域：操作系统中的调度--找到开销低且公平使用资源的调度；下一代路由器中的调度--设计算法，允许高效地路由具有不同服务级别的分组；网络编码--设计算法来管理这一令人兴奋的新路由技术，以及电源管理--设计调度作业的算法，以提供良好的响应时间并高效地使用电源。虽然这些不同领域的细节不同，但总体目标是设计简单、低开销的算法，使用具有严格证明的界限和分析的算法，设计新理论，并将现有理论更接近系统。研究人员还设计了适合向更广泛的受众教授算法的教育材料。

Efficient Algorithms for Problems in the Next Generation of ComputingCliff SteinColumbia UniversityComputers, computer systems and the computational infrastructureprovided by the Internet are now essential for many aspects of modernlife. It is well-known and well-documented that, even as computingpower and network bandwidth increase at a rapid rate, the demands thatusers and applications place on these resource increase at roughly thesame pace. Thus, no matter how much progress we make on the hardwareand network ends, we will always need efficient algorithms to managethese resources. This research focuses on several algorithmicproblems in computer systems and networks; arising both from existingtechnologies and at technologies that are evolving, or have beenproposed. By improve the efficiency with which we manage our devicesand infrastructure, there will be tremendous savings, both in time andeconomically. In addition, the investigator integrates theory andsystems and encourages more collaboration between these areas, withobvious benefits. This work has an impact on the decisions that arebeing made presently about the next generation of the Internet, ofrouting, and of scheduling in operating systems. In particular, the investigator studies four concrete problem areas:scheduling in operating systems -- finding schedules that are low overhead and use resources fairly; scheduling in the next generation of routers -- designing algorithmsthat allow packets with different levels of service to be routedefficiently; network coding -- designing algorithms to manage thisexciting new routing technology, and power management -- designingalgorithms that schedule jobs to provide good response time and to usepower efficiently. While the details of these various areas differ,the overall goals are to design simple, low overhead algorithms, usealgorithms with rigorously proved bounds and analysis, design newtheory and transfer existing theory closer to the systems. Theinvestigator also designs educational materials suitable for teachingalgorithms to a wider audience.