ITR: High Performance Implementation of Approximate Algorithms for Large-Scale Routing and Network Design

该项目将解决网络设计和路由中的大规模近似优化问题的理论和计算方法，包括静态和在线问题。这项工作的一个中心组成部分将是在诸如IBM即将推出的BG/L等体系结构上实现PI的算法。工作将针对网络和电信中出现的问题实例，这些实例远远超过数学编程社区目前所研究的问题。虽然城域网络在适当的聚合水平上只涉及几百个节点，但计算机网络可能要大得多。展望下一代网络，特别是无线和临时网络，对能够处理更大网络的优化工具的需求变得迫切。PI之前的工作建立在过去十年主要由理论计算机科学界开发的线性规划潜在函数方法的方法论基础上。他的工作进一步发展了这一方法，并产生了有效的实施。这种实现速度很快(比竞争的专用算法更有效，也比商业软件快得多)，对于工程目的来说，它相当准确，而且它是通用的：它处理网络设计问题、静态吞吐量路由问题、多商品流问题，实际上，它是一类更一般的线性规划问题，所有这些问题都具有公共接口，没有用户选择的参数。它成功地处理了涉及具有数百个甚至几千个节点的网络的问题。由此产生的线性规划具有数千万个变量和约束，是最先进的线性规划软件可以考虑的极限。然而，当考虑更大的网络时，优化问题的维度增加了几个数量级，远远超出了当前方法和实现的能力-这些问题足够大，以至于优化的想法变得相当令人望而生畏。与此同时，网络应用的复杂性、经济性和快速变化的性质对具有成本效益、可生存的设计和高吞吐量的路由方案提出了严格的需求。这项工作将寻求建立在新的、具体的方法论思想上，以开发具有更强收敛特性的算法；此外，它还将开发能够处理大规模问题的高性能实现。并行努力将涉及在线路由问题。许多在线布线方法(例如，寻求最小化拥塞或实现公平布线的动态布线方案)可以被视为对应静态问题的势函数方法的单一迭代。该项目将使用这一想法，以及PI在静态问题上的工作，目的是开发有效的路由算法；同样，这项工作的很大一部分将是计算。在这两种情况下，该项目都将使用先前建立的行业研究伙伴关系来验证方法并获得真实的数据。

This project will address theoretical and computational methodology for massively large, approximate optimization problems in network design and routing, encompassing both static and online problems. A central component of the work will be the implementation of the PI's algorithms on architectures such as IBM's forthcoming BG/L.The work will be directed at problem instances arising in networking and telecommunications, that are far larger than those currently studied by the mathematical programming community. While metropolitan area networks, at an appropriate level of aggregation, involve a few hundred nodes, computer networks can be far larger. Looking toward next-generation networking, especially wireless and adhoc networking, the need for optimization tools that can handle much larger networks becomes pressing.The PI's previous work built upon methodologies on potential function methods for linear programming, developed during the last decade primarily by the theoretical computer science community. His work further developed the methodology and produced an effective implementation. This implementation is fast (more efficient than competing special-purpose algorithms and much faster than commercial software), it is quite accurate for engineering purposes, and it is general: it handles network design problems, static throughput routing problems, multicommodity flow problems, and in fact, a much more general class of linear programming problems, all with a common interface and no user-selected parameters. It successfully handles problems involving networks with hundreds and up to a few thousand nodes. The resulting linear programs, with tens of millions of variables and constraints, are at the limit of what can be considered approachable with state-of-the-art linear programming software.When considering larger networks, however, the dimensions of the optimization problems increase by several orders of magnitude, placing them well beyond the capabilities of current methods and implementations - these problems are large enough that the idea of optimization becomes rather daunting. At the same time, the complexity, economics, and fast-changing nature of networking applications provides a stringent need for cost-effective, survivable designs and high throughput routing schemes. This work will seek to build on new, concrete methodological ideas so as to develop algorithms with provably stronger convergence properties; further, it will also develop high-performance implementations that can tackle massively large problems.A parallel effort will concern online routing problems. Many online routing methods (for example, dynamic routing schemes that seek to minimize congestion, or to achieve fair routings) can be viewed as single iterations of potential function methods for corresponding static problems. This project will use this idea, together with the PI's work on static problems, with the aim of developing effective routing algorithms; again, a significant part of this work will be computational.In both cases, this project will use previously established industrial research partnerships to validate methodologies and to obtain realistic data.