 |
Center for Nonlinear Studies |
Abstract. A central operational problem in a network is the scheduling of resources to resolve contention between various entities accessing them. Some popular examples are switch scheduling, MAC scheduling in wireless network and bandwidth allocation in a flow network. Ideally, an implementor would like to have access to a parametrized class of algorithms so that by `tuning' parameters a necessary trade-off between the ease of implementation and performance can be achieved. In this talk, I will present such a parametrized class of simple, distributed message-passing algorithms for two network problems: (1) Scheduling in an input-queued switches that are dominant architecture in commercially available routers (find a good matching), and (2) Scheduling of sub-carriers for transmission in OFDMA based communication (find a good f-matching). These algorithms utilize light-weight data structures; are distributed and iterative (hence pipeline-able). Our algorithms are based on a blend of techniques from optimization and belief propagation. We will discuss implications in the context of "theory of belief propagation". Bio. Devavrat Shah is currently an assistant professor with the department of EECS at MIT. His primary research interests are in the algorithms for networks, stochastic networks, statistical inference and network information theory. He received his Ph.D. from the Computer Science Department at Stanford University in October, 2004. He was co-awarded the IEEE INFOCOM best paper award in 2004 and ACM SIGMETRIC/Performance best paper award in 2006. He received 2005 George B. Dantzig best desseration award from INFORMS and NSF CAREER in 2006.