Collaborative Research: Emerging Directions in Network Design and Optimization

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

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.