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.

Abstract0635119 Northeastern Universityrajaraman，Rajmohanhow幸福是无知吗？忽略在网络激化中的作用下一代互联网将是规模更大的数量级，将节点连接在一起，这些节点在功能和要求上截然不同。 传统算法设计倾向于专注于均匀平台上完整信息的问题。 但是，尺度和异质性的急剧增加意味着节点既不能希望获得也不希望获取和处理完整信息。 因此，今天重要的是要专注于可以遗忘的算法和协议，即具有有限的知识。 这项研究开发了正式的框架，以量化遗忘网络优化中相关的权衡，并提供基础架构级算法，这些算法可以确保明天的互联网基础。 该项目还培训学生的高级网络基础架构设计，并将研究纳入算法和网络课程中。这项研究的重点是三倍。 第一个组件涉及通过普遍近似解决方案的网络设计算法，这些算法同时近似于最佳的总体可能输入。 研究人员研究了此框架内的TSP，Steiner树和其他基本优化问题，并将这些想法应用于Sensornetworks中数据获取的协议。 该项目的第二个组成部分是针对负载平衡和调度的符合故障算法的设计，这些算法可以为任意未知和无法预测的福特模式提供性能保证。 这项研究的第三个组成部分是汇合路由，这是一种源代码的路由方法，可提高效率，同时保持可伸缩性。