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.

该研究的主要重点是开发用于设计网络的良好算法。随着互联网的流行和普遍性，开发简单可扩展的算法来设计良好的网络已经变得很重要，从而提供最灵活的网络。当时的网络设计师只需要在最终将携带的部分信息和宽松的估计中构建网络，以建立网络，因为他们知道故障几乎会肯定会发生，并为优雅地处理这些故障，并以最经济和高效的方式进行此操作。与此同时，今天的网络设计师必须考虑网络的异质性（其中包括无线和光学零件），并且每个网络必须与潜在的许多其他网络进行交互这一事实。此外，这些相互作用的网络可以由具有不同定价方案和不同激励结构的不同实体控制。卡内基·梅隆大学和贝尔实验室的研究人员借鉴了他们的背景，以模拟网络设计环境中所面临的问题，并与这些算法工具和良好的算法有关这些问题的保证。为了实现这些目标，研究适应并增强了一系列来自线性和凸编程，随机优化，指标嵌入和随机化以及复杂性理论技术的丰富算法技术。这项研究反映了学术界和研究实验室之间的合作，以转移理论和实践之间的思想，问题和算法：尤其是，研究鼓励学生学习问题建模和解决问题，并在对网络设计问题平衡的环境之间进行平衡的环境之间进行移动。研究进度通过专业课程传播到课程中，这些课程在其应用程序的背景下介绍了理论进步，以及教授这些研究进步背后的基本思想和技术的基本课程。