Collaborative Research: Emerging Directions in Network Design and Optimization

协作研究：网络设计和优化的新兴方向

• 批准号: 0729022
• 负责人: Anupam Gupta
• 金额: $ 25.1万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-09-01 至 2011-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0729022&HistoricalAwards=false
• 关键词: Collaborative; Research; Emerging; Directions; Network

The main focus of the research is to develop good algorithms for designing networks. With the popularity and ubiquity of the Internet, it has become important to develop simple and scalable algorithms to design good networks which offer the most flexibility and functionality. Thenetwork designer has to build networks given only partial information and loose estimates of the traffic that will eventually be carried, to build networks knowing that faults will almost surely occur and to provision for handling these faults gracefully, and to do this in the most economic and efficient fashion. Along with this, the network designer today must take into account the heterogeneity of networks (which will include wireless and optical parts), and the fact that eachnetwork has to interact with potentially many other networks. In addition, these interacting networks may be controlled by different entities having different pricing schemes and different incentive structures.The investigators from Carnegie Mellon University and Bell Laboratories draw on their mix of backgrounds to mathematically model the problems faced in network design contexts, and to develop algorithmic tools and good algorithms with provable guarantees for these problems. To achieve these goals, the research adapts and augments a rich set of algorithmic techniques from linear and convex programming, stochastic optimization, metric embeddings, and randomization, as well as complexity-theoretic techniques that have developed in theoretical computer science over the past few years. The research reflects a collaboration between academia and research laboratories to transfer ideas, problems and algorithms between theory and practice: in particular, the research encourages students to learn problem modeling and solving, and to move between thetwo environments gaining a balanced view of issues in network design. Research progress is propagated into the curriculum via specialized courses presenting the theoretical advances in the context of their applications, as well as basic courses teaching the fundamental ideas and techniques behind these research advances.

研究的主要重点是开发用于设计网络的良好算法。随着互联网的普及和普及，开发简单且可扩展的算法来设计提供最大灵活性和功能的良好网络变得非常重要。网络设计者必须在仅给出部分信息和对最终将承载的流量的松散估计的情况下构建网络，构建知道几乎肯定会发生故障的网络，并准备好处理这些故障，并以最经济和最有效的方式做到这一点。高效时尚。除此之外，今天的网络设计者必须考虑网络的异构性（包括无线和光学部分），以及每个网络必须与潜在的许多其他网络交互的事实。此外，这些相互作用的网络可能由具有不同定价方案和不同激励结构的不同实体控制。卡内基梅隆大学和贝尔实验室的研究人员利用他们的混合背景对网络设计环境中面临的问题进行数学建模，并开发算法工具和好的算法可以为这些问题提供可证明的保证。为了实现这些目标，该研究采用并增强了一系列丰富的算法技术，包括线性和凸规划、随机优化、度量嵌入和随机化，以及过去几年在理论计算机科学中发展的复杂性理论技术。该研究反映了学术界和研究实验室之间的合作，以在理论和实践之间转移思想、问题和算法：特别是，该研究鼓励学生学习问题建模和解决，并在两种环境之间移动，获得对网络中问题的平衡看法设计。研究进展通过专业课程和基础课程传播到课程中，专业课程介绍其应用背景下的理论进展，基础课程教授这些研究进展背后的基本思想和技术。