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

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

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.