How Blissful is Ignorance? The Role of Obliviousness in Network Optimization

东北大学拉贾拉曼，拉贾莫汉无知有多幸福？下一代互联网的规模将大上几个数量级，将功能和需求截然不同的节点连接在一起。传统的算法设计倾向于关注同构平台上具有完整信息的问题。然而，规模和异构性的急剧增加意味着节点既不能指望获得也不能存储和处理完整的信息。因此，今天重要的是关注那些可以在有限的知识下隐性操作的算法和协议。本研究开发了形式化框架，用于量化遗忘网络优化中的相关权衡，并提供了可以确保未来互联网基础的基础设施类算法。该项目还训练学生设计先进的网络基础设施，并将研究纳入算法和网络课程。这项研究的重点有三个方面。第一部分涉及网络设计的遗忘算法，通过同时逼近最佳整体可能输入的普遍近似解。研究人员在此框架内研究TSP，斯坦纳树和其他基本优化问题，并将这些思想应用于传感器网络中的数据采集协议。该项目的第二个组成部分是设计用于负载平衡和调度的无故障算法，该算法可以为任意未知和不可预测的故障模式提供性能保证。本研究的第三个组成部分是融合路由，这是一种源无关的路由方法，可以在保持可伸缩性的同时提高效率。

ABSTRACT0635119Northeastern UniversityRajaraman, RajmohanHow blissful is ignorance? The role of obliviousness in networkoptimization The next-generation Internet will be orders of magnitude bigger in scale, connecting together nodes that are very different in their capabilities and requirements. Traditional algorithm design has tended to focus on problems with complete information over a homogeneous platform. However, the dramatic increase in scale and heterogeneity means that nodes can neither hope to obtain nor store and process full information. Therefore, it is important today to focus on algorithms and protocols that can operate obliviously, i.e.,with limited knowledge. This research develops formal frameworks for quantifying the associated tradeoffs in oblivious network optimization and delivers infrastructure-class algorithms that can secure thefoundations of the Internet of tomorrow. This project also trains students in the design of advanced network infrastructure and incorporates the research into the curriculum for algorithms and networking.The focus of this research is three-fold. The first component concerns oblivious algorithms for network design through universally approximate solutions that simultaneously approximate the optimal overall possible inputs. The investigators study the TSP, Steiner tree, and other fundamental optimization problems within this framework, and also apply these ideas to protocols for data acquisition in sensornetworks. The second component of this project is the design of fault-oblivious algorithms for load balancing and scheduling that can offer performance guarantees for arbitrary unknown and unpredictablefault patterns. The third component of this research is confluent routing, which is a source-oblivious approach to routing that increases efficiency while maintaining scalability.