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

无知有多幸福？

• 批准号: 0635119
• 负责人: Rajmohan Rajaraman
• 金额: $ 20万
• 依托单位: Northeastern University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-10-01 至 2009-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0635119&HistoricalAwards=false
• 关键词: How; Blissful; Ignorance; Role; Obliviousness

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.

摘要0635119东北大学 Rajaraman, Rajmohan 无知有多幸福？遗忘在网络优化中的作用下一代互联网的规模将扩大几个数量级，将能力和要求截然不同的节点连接在一起。 传统的算法设计倾向于关注同质平台上具有完整信息的问题。 然而，规模和异构性的急剧增加意味着节点既不能希望获取也不能存储和处理完整的信息。 因此，今天重要的是关注可以在不知不觉中（即用有限的知识）运行的算法和协议。 这项研究开发了正式的框架，用于量化不经意的网络优化中的相关权衡，并提供可以保护未来互联网基础的基础设施级算法。 该项目还对学生进行高级网络基础设施设计方面的培训，并将研究成果纳入算法和网络课程中。这项研究的重点有三个方面。 第一个组成部分涉及通过通用近似解决方案进行网络设计的不经意算法，该解决方案同时近似最佳的总体可能输入。 研究人员研究了该框架内的 TSP、斯坦纳树和其他基本优化问题，并将这些想法应用于传感器网络中的数据采集协议。 该项目的第二个组成部分是设计用于负载平衡和调度的故障忽略算法，该算法可以为任意未知和不可预测的故障模式提供性能保证。 这项研究的第三个组成部分是融合路由，这是一种忽略源的路由方法，可以在保持可扩展性的同时提高效率。