Collaborative Research: Emerging Directions in Network Design and Optimization

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

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.