CAREER: Implementable Network Algorithms via Randomization, Belief Propagation and Heavy Traffic

职业：通过随机化、置信传播和大流量实现的网络算法

• 批准号: 0546590
• 负责人: Devavrat Shah
• 金额: $ 45万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-02-15 至 2012-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0546590&HistoricalAwards=false
• 关键词: CAREER; Implementable; Network; Algorithms; via

Communication networks are becoming irreplaceable components of any large engineering system. The performance of such networks is determined by the algorithms implemented within them. This proposal aims at developing novel design and analysis methods for implementable network algorithms. Designing high-performance implementable network algorithms is an extremely challenging task. For example, a typical network algorithm operating in the core of the Internet needs to make complicated decisions roughly every 50ns while utilizing limited resources. Similarly, in the context of wireless networks, algorithms have access to limited computation and energy resources for performing desired tasks. Consequently, only the simplest algorithms are implementable in such networks. But a simple algorithm may perform rather poorly if it is not well-designed. Addressing this tension between simplicity and high-performance is the focal point of this proposal. The algorithm designer experiences this tension in the context of scheduling and routing algorithms, which are critical for the operation of Internet and wireless mesh networks. The established theoretical solutions for these tasks require solving complicated optimization problems. The known algorithmic solutions to these optimization problems are un-implementable. Hence ad-hoc solutions are implemented in the current networks which are poor in performance. For example, in many cases current solutions utilize no more than 30% of the network capacity ! I intend to bridge the gap between theory and practice by designing implementable good approximations of appropriate optimization problems using two simple yet powerful ideas: (1) Belief propagation (BP) and (2) Randomization. In operational terms, BP is an iterative, distributed, simple message-passing style heuristic for optimization problems. BP is based on deep insights of Statistical Physics and Artificial Intelligence. Algorithms based on BP have been very successful in solving notoriously hard problems in areas such as Turbo Decoding, Image Reconstruction, and Constraint Satisfiability. The method of randomization has been extremely successful in simplifying implementation of complex algorithms. The idea behind randomization is very simple: base decision on a few randomly chosen samples instead of the whole state. The clever choice of random samples result in excellent performance wherein the state of system has a lot of redundant information. Such is the case in many networking application, which makes randomization well-suited. The design approach based on BP and randomization for scheduling and routing may lead to more than 90% utilization of network capacity. An important counterpart of algorithm design is the analysis method that is useful to quantify the performance of algorithm. The so-called "curse of dimensionality" of large networks makes performance analysis of algorithms mathematically intractable. The principal investigator (PI) plans to develop analysis method by reducing the "effective dimension of algorithm" and thus making it tractable for analysis using effective framework of heavy traffic theory from stochastic networks. Intellectual merit. This proposal will primarily advance the understanding of design and analysis of implementable network algorithms. Further, it will advance the understanding of BP, which is one of the central (and rather mysterious) topics of current research in AI and Statistical Physics community. The heavy traffic based analysis method will be helpful in advancing the application and development of theory in stochastic networks. Broad impact. The scheduling and routing algorithms that will be developed as a part of the proposed research may help in designing high-performance LAN switches and efficient wireless mesh network architecture. This may lead to a cost-effective architectural solution for broad-band access networks. The proposed research will be disseminated to the community via publications in journals, conferences and workshops. Further, the PI plans to interact and collaborate closely with networking industry. In particular, Cisco systems Inc. is supportive of this research.

通信网络正成为任何大型工程系统不可替代的组成部分。 这种网络的性能取决于其中实现的算法。该建议旨在开发新的设计和分析方法，可实现的网络算法。设计高性能可实现的网络算法是一项极具挑战性的任务。例如，在互联网核心中运行的典型网络算法需要在利用有限资源的同时大约每50 ns做出复杂的决策。类似地，在无线网络的上下文中，算法可以访问有限的计算和能量资源以执行期望的任务。 因此，只有最简单的算法在这样的网络中是可实现的。 但是，一个简单的算法，如果设计得不好，可能会表现得相当差。解决简单性和高性能之间的矛盾是本提案的重点。算法设计者在调度和路由算法的上下文中体验到这种紧张，这对互联网和无线网状网络的操作至关重要。为这些任务建立的理论解决方案需要解决复杂的优化问题。这些优化问题的已知算法解决方案是不可实现的。因此，ad-hoc解决方案在当前的网络中实现，这是在性能差。例如，在许多情况下，当前的解决方案利用不超过30%的网络容量！我打算弥合理论和实践之间的差距，通过使用两个简单而强大的思想设计适当的优化问题的可实现的良好近似：（1）置信传播（BP）和（2）随机化。在操作方面，BP是一种迭代的，分布式的，简单的消息传递风格的启发式优化问题。BP基于对统计物理和人工智能的深刻见解。基于BP的算法在解决诸如Turbo解码、图像重建和约束可满足性等领域的困难问题方面已经非常成功。随机化方法在简化复杂算法的实现方面非常成功。随机化背后的想法非常简单：基于一些随机选择的样本而不是整个状态。在系统状态具有大量冗余信息的情况下，随机样本的巧妙选择使系统具有良好的性能。 这是许多网络应用程序的情况，这使得随机化非常适合。基于BP和随机化的调度和路由设计方法可以使网络容量利用率达到90%以上。 算法设计的一个重要对应部分是算法性能的分析方法。大型网络的所谓“维数灾难”使得算法的性能分析在数学上变得棘手。主要研究者（PI）计划通过减少“算法的有效维度”来开发分析方法，从而使其易于使用随机网络的重流量理论的有效框架进行分析。智力上的优点。该建议将主要推进对可实现的网络算法的设计和分析的理解。此外，它将促进对BP的理解，这是人工智能和统计物理界当前研究的中心（也是相当神秘的）主题之一。基于重业务的分析方法将有助于推动随机网络理论的应用和发展。广泛的影响。调度和路由算法，将被开发作为拟议的研究的一部分，可能有助于设计高性能的局域网交换机和高效的无线网状网络架构。这可能导致宽带接入网络的成本效益的架构解决方案。拟议的研究将通过期刊、会议和讲习班的出版物向社区传播。此外，PI计划与网络行业密切互动和合作。具体而言，思科系统公司（Cisco Systems Inc.）支持这项研究。