Combinatorial Resource AllocationAllocation or scheduling of resources among various entities contending for their access is one of the fundamental problems in engineering and operations research. The importance of high-performance scheduling algorithm design for such resource allocation problems in communication networks and manufacturing systems has resulted in exciting progress over the past few decades. The key insight here is that if contention resolution is framed as an appropriate global, network-wide combinatorial optimization problem, then this will lead to the desired efficiency of network operations. However, the optimization problem is computationally hard, and more importantly, its optimizing parameters (e.g. queue-size) keep changing over time. On the other hand, for the architecture of a large scalable networked system in practice, algorithms are required to use only local information or limited resources. Therefore, the challenge arises in designing simple, distributed algorithms for such hard dynamic network-wide optimization problems. A priori, it is not even clear whether such an algorithm exists. Queue-based ApproachWe developed a mathematical framework to identify the sufficient conditions for the existence of such algorithms which we call the the network adiabatic theorem. Roughly speaking, like a the classical adiabatic theorem from quantum mechanics, this theorem states that if the effective networked control system changes slowly in a certain sense, then the system is always operating in a desirable equilibrium state. This result represents an advance in our understanding of complex (Markovian) networked systems using transient properties of significantly simpler time-varying ones. As the next step, we used the network adiabatic framework to design and analyze an extremely simple distributed high-performance algorithm that solves general resource allocation problems. This algorithm utilizes transformed network parameters (precisely, slowly growing functions of local queue-sizes) along with the classical Metropolis-Hastings sampling mechanism and the Markov chain tree theorem so that it is guaranteed to satisfy the network adiabatic theorem. As a special instance, our algorithm provides an efficient MAC (Medium Access Control) protocol for arbitrary wireless networks. Methodically, the network adiabatic framework is applicable to design a variety of low-complexity and high-throughput algorithms for a wide class of combinatorial resource allocation problems.
Rate-based ApproachAnother approach for designing resource allocation algorithms is utilizing the knowledge of long-term external demands (or rates), which often relaxes the complexity of dynamic network-wide optimization problems and results in better delay performances. Here, the main challenge is how to design distributed or low complexity scheduling algorithms to meet the demand. We developed such an algorithm inspired by the the network adiabatic theorem.
In essence, the rate-based approach is closely related to the parameter estimation problem in graphical models of the machine learning community, which motivated us to apply the popular Belief Propagation algorithm.
People often do not distinguish the queue-based and rate-based approaches since resulting algorithms often similar. However, the former and the latter are essentially in the areas of the distributed control and the model parameter estimation, which are different in their performance guarantees. (edited by Jinwoo Shin, Nov 2016) |