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

Massachusetts Institute Of Technology, Cambridge MA

Investigators

Abstract

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.