Events - Colloquia & Seminars

CCIS Colloquium Fall 2006

Message-Passing Algorithms for Network Scheduling

Speaker: Devavrat Shah

Affiliation: Department of EECS, MIT

Date: Friday, November 17, 2006

Talk: 12:00 pm, 366 WVH

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 ease of implementation and performance be achieved.

In this talk, I will present such a parametrized class of simple, distributed message-passing algorithm for scheduling in switches and wireless network based on belief propagation. I will talk about the correctness and convergence properties of the algorithm in this context. I will discuss its relation to the dual (aka auction) algorithm as well as some extensions. The talk will be self-contained and an attempt will be made to provide sufficient background on the topic of belief propagation.

The talk is based on joint work with Mohsen Bayati (Stanford) and Mayank Sharma (IBM).

Biography

Devavrat Shah is currently an assistant professor with department of EECS at MIT. His primary research interests are in the algorithms for networks, stochastic networks, statistical inference and network information theory.

Devavrat received his BTech degree in Computer Science from IIT-Bombay in 1999 with the honor of the President of India Gold Medal. He received his Ph.D. from the Computer Science at Stanford University in 2004. He was a post-doc in the Statistics department at Stanford and MSRI, Berkeley in 2004-05. 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.