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

ITR：大规模路由和网络设计的近似算法的高性能实现

• 批准号: 0213848
• 负责人: Daniel Bienstock
• 金额: $ 23.38万
• 依托单位: Columbia University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2002
• 资助国家: 美国
• 起止时间: 2002-09-01 至 2005-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0213848&HistoricalAwards=false
• 关键词: ITR; Performance; Implementation; Approximate; Algorithms

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.

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