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 纳秒做出一次复杂的决策，同时利用有限的资源。类似地，在无线网络的背景下，算法可以使用有限的计算和能源来执行所需的任务。 因此，在此类网络中只能实现最简单的算法。 但是，如果设计不当，简单的算法可能会表现得很差。解决简单性和高性能之间的紧张关系是该提案的重点。算法设计者在调度和路由算法的背景下经历了这种紧张，这对于互联网和无线网状网络的运行至关重要。这些任务的既定理论解决方案需要解决复杂的优化问题。这些优化问题的已知算法解决方案是无法实现的。因此，在性能较差的当前网络中实施了临时解决方案。例如，在许多情况下，当前解决方案仅利用不超过 30% 的网络容量！我打算通过使用两个简单但强大的想法设计适当优化问题的可实现的良好近似来弥合理论与实践之间的差距：（1）置信传播（BP）和（2）随机化。从操作角度来说，BP 是一种迭代的、分布式的、简单的消息传递风格的启发式优化问题。 BP 基于统计物理和人工智能的深刻见解。基于 BP 的算法在解决 Turbo 解码、图像重建和约束可满足性等领域中众所周知的难题方面非常成功。随机化方法在简化复杂算法的实现方面非常成功。随机化背后的想法非常简单：基于一些随机选择的样本而不是整个状态来做出决策。随机样本的巧妙选择会带来优异的性能，其中系统状态具有大量冗余信息。 许多网络应用都是这种情况，这使得随机化非常适合。基于BP和随机化的调度和路由设计方法可以使网络容量利用率达到90%以上。 算法设计的一个重要对应部分是有助于量化算法性能的分析方法。大型网络所谓的“维数灾难”使得算法的性能分析在数学上变得棘手。首席研究员（PI）计划通过减少“算法的有效维度”来开发分析方法，从而使其易于使用随机网络中的大流量理论的有效框架进行分析。智力上的优点。该提案将主要增进对可实现网络算法的设计和分析的理解。此外，它将增进对 BP 的理解，这是人工智能和统计物理社区当前研究的中心（而且相当神秘）的主题之一。基于大流量的分析方法将有助于推动随机网络理论的应用和发展。影响广泛。作为拟议研究的一部分将开发的调度和路由算法可能有助于设计高性能 LAN 交换机和高效的无线网状网络架构。这可能会为宽带接入网络带来具有成本效益的架构解决方案。拟议的研究将通过期刊、会议和研讨会上的出版物向社区传播。此外，PI 计划与网络行业密切互动和合作。思科系统公司特别支持这项研究。