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

东北大学拉吉拉曼，拉吉莫汉无知有多幸福？遗忘在网络优化中的作用下一代互联网的规模将更大，将功能和要求截然不同的节点连接在一起。传统的算法设计倾向于在同构平台上关注具有完全信息的问题。然而，规模和异构性的急剧增加意味着节点既不能希望获得全部信息，也不能存储和处理全部信息。因此，今天重要的是要专注于可以忽略操作的算法和协议，即，在知识有限的情况下。这项研究开发了正式的框架，用于量化不经意的网络优化中的相关权衡，并提供基础设施级算法，以确保未来互联网的基础。该项目还培训学生设计高级网络基础设施，并将研究纳入算法和网络课程。本研究的重点有三个方面。第一个组成部分涉及通过通用近似解同时逼近最优总体可能输入的网络设计的不经意算法。研究人员在这个框架内研究了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.