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

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

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.