## 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. - Scheduling using Interactive Optimization Oracles for Constrained Queueing Networks
Tonghoon Suk and Jinwoo Shin
*Mathematics of Operations Research*, 2017 (accepted to appear, preliminary version appeared in*SIGMETRICS*2014)
- From Local to Global Stability in Stochastic Processing Networks through Quadratic Lyapunov Functions
Antonius B. Dieker and Jinwoo Shin
*Mathematics of Operations Research*, vol. 38, vol 4, pp. 638-664, 2013
- Randomized Scheduling Algorithm for Queueing Networks
Devavrat Shah and Jinwoo Shin
*The Annals of Applied Probability*, vol. 22, no. 1, pp. 128-171, 2012
- Medium Access using Queues
Devavrat Shah, Jinwoo Shin, and Prasad Tetali
*FOCS*2011
- Delay Optimal Queue-based CSMA
Devavrat Shah and Jinwoo Shin
*SIGMETRICS*2010
- Network Adiabatic Theorem: An Efficient Randomized Protocol for Contention Resolution
Shreevatsa Rajagopalan, Devavrat Shah and Jinwoo Shin
*SIGMETRICS*2009
(edited by Jinwoo Shin, Nov 2016) ## 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 scheduling algorithms to meet the demand. We developed such an algorithm inspired by the the network adiabatic theorem. - Delay Optimal CSMA with Linear Virtual Channels under a General Topology
Donggyu Yun, Dongmyung Lee, Se-Young Yun, Jinwoo Shin, and Yung Yi
*IEEE/ACM Transactions on Networking*, vol. 24, no. 5, pp. 2847-2857, 2016 (preliminary version appeared in*INFOCOM*2014)
- Distributed Medium Access over Time-varying Channels
Se-Young Yun, Jinwoo Shin, and Yung Yi
*IEEE/ACM Transactions on Networking*, vol. 24, no. 5, pp. 3000-3013, 2016 (preliminary version appeared in*MOBIHOC*2013)
- Distributed Random Access Algorithm: Scheduling and Congestion Control
Libin Jiang, Devavrat Shah, Jinwoo Shin, and Jean Walrand
*IEEE Transactions on Information Theory*, vol. 56, vol. 12, pp. 6182-6207, 2010
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. - CSMA Using the Bethe Approximation: Scheduling and Utility Maximization
Se-Young Yun, Jinwoo Shin, and Yung Yi
*IEEE Transactions on Information Theory*, vol. 61, no. 9, pp. 4776-4787, 2015 (preliminary version appeared in*ISIT*2013)
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) |