Combinatorial Resource Allocation

Allocation 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 Approach

We 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 Approach

Another 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)