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.